1 //===- bolt/Passes/StackAllocationAnalysis.cpp ----------------------------===//
2 //
3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4 // See https://llvm.org/LICENSE.txt for license information.
5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6 //
7 //===----------------------------------------------------------------------===//
8 //
9 // This file implements the StackAllocationAnalysis class.
10 //
11 //===----------------------------------------------------------------------===//
12 
13 #include "bolt/Passes/StackAllocationAnalysis.h"
14 #include "bolt/Passes/StackPointerTracking.h"
15 #include "llvm/Support/Debug.h"
16 
17 #define DEBUG_TYPE "saa"
18 
19 namespace llvm {
20 namespace bolt {
21 
22 void StackAllocationAnalysis::preflight() {
23   LLVM_DEBUG(dbgs() << "Starting StackAllocationAnalysis on \""
24                     << Func.getPrintName() << "\"\n");
25 
26   for (BinaryBasicBlock &BB : this->Func) {
27     for (MCInst &Inst : BB) {
28       MCPhysReg From, To;
29       if (!BC.MIB->isPush(Inst) &&
30           (!BC.MIB->isRegToRegMove(Inst, From, To) ||
31            To != BC.MIB->getStackPointer() ||
32            From != BC.MIB->getFramePointer()) &&
33           !BC.MII->get(Inst.getOpcode())
34                .hasDefOfPhysReg(Inst, BC.MIB->getStackPointer(), *BC.MRI))
35         continue;
36       this->Expressions.push_back(&Inst);
37       this->ExprToIdx[&Inst] = this->NumInstrs++;
38     }
39   }
40 }
41 
42 BitVector
43 StackAllocationAnalysis::getStartingStateAtBB(const BinaryBasicBlock &BB) {
44   return BitVector(this->NumInstrs, false);
45 }
46 
47 BitVector
48 StackAllocationAnalysis::getStartingStateAtPoint(const MCInst &Point) {
49   return BitVector(this->NumInstrs, false);
50 }
51 
52 void StackAllocationAnalysis::doConfluence(BitVector &StateOut,
53                                            const BitVector &StateIn) {
54   StateOut |= StateIn;
55 }
56 
57 BitVector StackAllocationAnalysis::doKill(const MCInst &Point,
58                                           const BitVector &StateIn,
59                                           int DeallocSize) {
60   int64_t SPOffset = SPT.getStateAt(Point)->first;
61   BitVector Next = StateIn;
62   if (SPOffset == SPT.SUPERPOSITION || SPOffset == SPT.EMPTY)
63     return Next;
64   for (auto I = this->expr_begin(Next), E = this->expr_end(); I != E; ++I) {
65     const MCInst *Instr = *I;
66     int64_t InstrOffset = SPT.getStateAt(*Instr)->first;
67     if (InstrOffset == SPT.SUPERPOSITION || InstrOffset == SPT.EMPTY)
68       continue;
69     if (InstrOffset < SPOffset) {
70       Next.reset(I.getBitVectorIndex());
71       LLVM_DEBUG({
72         dbgs() << "SAA FYI: Killed: ";
73         Instr->dump();
74         dbgs() << "by: ";
75         Point.dump();
76         dbgs() << "  (more info: Killed instr offset = " << InstrOffset
77                << ". SPOffset = " << SPOffset
78                << "; DeallocSize= " << DeallocSize << "\n";
79       });
80     }
81   }
82   return Next;
83 }
84 
85 void StackAllocationAnalysis::doConfluenceWithLP(BitVector &StateOut,
86                                                  const BitVector &StateIn,
87                                                  const MCInst &Invoke) {
88   BitVector NewIn = StateIn;
89   const int64_t GnuArgsSize = BC.MIB->getGnuArgsSize(Invoke);
90   if (GnuArgsSize >= 0)
91     NewIn = doKill(Invoke, NewIn, GnuArgsSize);
92   StateOut |= NewIn;
93 }
94 
95 BitVector StackAllocationAnalysis::computeNext(const MCInst &Point,
96                                                const BitVector &Cur) {
97   const auto &MIB = BC.MIB;
98   BitVector Next = Cur;
99   if (int Sz = MIB->getPopSize(Point)) {
100     Next = doKill(Point, Next, Sz);
101     return Next;
102   }
103   if (MIB->isPush(Point)) {
104     Next.set(this->ExprToIdx[&Point]);
105     return Next;
106   }
107 
108   MCPhysReg From, To;
109   int64_t SPOffset, FPOffset;
110   std::tie(SPOffset, FPOffset) = *SPT.getStateBefore(Point);
111   if (MIB->isRegToRegMove(Point, From, To) && To == MIB->getStackPointer() &&
112       From == MIB->getFramePointer()) {
113     if (MIB->isLeave(Point))
114       FPOffset += 8;
115     if (SPOffset < FPOffset) {
116       Next = doKill(Point, Next, FPOffset - SPOffset);
117       return Next;
118     }
119     if (SPOffset > FPOffset) {
120       Next.set(this->ExprToIdx[&Point]);
121       return Next;
122     }
123   }
124   if (BC.MII->get(Point.getOpcode())
125           .hasDefOfPhysReg(Point, MIB->getStackPointer(), *BC.MRI)) {
126     std::pair<MCPhysReg, int64_t> SP;
127     if (SPOffset != SPT.EMPTY && SPOffset != SPT.SUPERPOSITION)
128       SP = std::make_pair(MIB->getStackPointer(), SPOffset);
129     else
130       SP = std::make_pair(0, 0);
131     std::pair<MCPhysReg, int64_t> FP;
132     if (FPOffset != SPT.EMPTY && FPOffset != SPT.SUPERPOSITION)
133       FP = std::make_pair(MIB->getFramePointer(), FPOffset);
134     else
135       FP = std::make_pair(0, 0);
136     int64_t Output;
137     if (!MIB->evaluateSimple(Point, Output, SP, FP))
138       return Next;
139 
140     if (SPOffset < Output) {
141       Next = doKill(Point, Next, Output - SPOffset);
142       return Next;
143     }
144     if (SPOffset > Output) {
145       Next.set(this->ExprToIdx[&Point]);
146       return Next;
147     }
148   }
149   return Next;
150 }
151 
152 } // end namespace bolt
153 } // end namespace llvm
154