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