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
preflight()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
getStartingStateAtBB(const BinaryBasicBlock & BB)43 StackAllocationAnalysis::getStartingStateAtBB(const BinaryBasicBlock &BB) {
44 return BitVector(this->NumInstrs, false);
45 }
46
47 BitVector
getStartingStateAtPoint(const MCInst & Point)48 StackAllocationAnalysis::getStartingStateAtPoint(const MCInst &Point) {
49 return BitVector(this->NumInstrs, false);
50 }
51
doConfluence(BitVector & StateOut,const BitVector & StateIn)52 void StackAllocationAnalysis::doConfluence(BitVector &StateOut,
53 const BitVector &StateIn) {
54 StateOut |= StateIn;
55 }
56
doKill(const MCInst & Point,const BitVector & StateIn,int DeallocSize)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
doConfluenceWithLP(BitVector & StateOut,const BitVector & StateIn,const MCInst & Invoke)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
computeNext(const MCInst & Point,const BitVector & Cur)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->evaluateStackOffsetExpr(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