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