bolt/lib/Passes/StackAllocationAnalysis.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-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->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