154 lines · cpp
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-exception6//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 19namespace llvm {20namespace bolt {21 22void 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 42BitVector43StackAllocationAnalysis::getStartingStateAtBB(const BinaryBasicBlock &BB) {44 return BitVector(this->NumInstrs, false);45}46 47BitVector48StackAllocationAnalysis::getStartingStateAtPoint(const MCInst &Point) {49 return BitVector(this->NumInstrs, false);50}51 52void StackAllocationAnalysis::doConfluence(BitVector &StateOut,53 const BitVector &StateIn) {54 StateOut |= StateIn;55}56 57BitVector 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 = " << InstrOffset77 << ". SPOffset = " << SPOffset78 << "; DeallocSize= " << DeallocSize << "\n";79 });80 }81 }82 return Next;83}84 85void 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 95BitVector 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 else130 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 else135 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 bolt153} // end namespace llvm154