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
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(Opcode: Inst.getOpcode())
34 .hasDefOfPhysReg(MI: Inst, Reg: BC.MIB->getStackPointer(), RI: *BC.MRI))
35 continue;
36 this->Expressions.push_back(x: &Inst);
37 this->ExprToIdx[&Inst] = this->NumInstrs++;
38 }
39 }
40}
41
42BitVector
43StackAllocationAnalysis::getStartingStateAtBB(const BinaryBasicBlock &BB) {
44 return BitVector(this->NumInstrs, false);
45}
46
47BitVector
48StackAllocationAnalysis::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(BV: Next), E = this->expr_end(); I != E; ++I) {
65 const MCInst *Instr = *I;
66 int64_t InstrOffset = SPT.getStateAt(Point: *Instr)->first;
67 if (InstrOffset == SPT.SUPERPOSITION || InstrOffset == SPT.EMPTY)
68 continue;
69 if (InstrOffset < SPOffset) {
70 Next.reset(Idx: 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
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(Inst: Invoke);
90 if (GnuArgsSize >= 0)
91 NewIn = doKill(Point: Invoke, StateIn: NewIn, DeallocSize: 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(Inst: Point)) {
100 Next = doKill(Point, StateIn: Next, DeallocSize: Sz);
101 return Next;
102 }
103 if (MIB->isPush(Inst: Point)) {
104 Next.set(this->ExprToIdx[&Point]);
105 return Next;
106 }
107
108 MCPhysReg From, To;
109 int64_t SPOffset, FPOffset;
110 std::tie(args&: SPOffset, args&: FPOffset) = *SPT.getStateBefore(Point);
111 if (MIB->isRegToRegMove(Inst: Point, From, To) && To == MIB->getStackPointer() &&
112 From == MIB->getFramePointer()) {
113 if (MIB->isLeave(Inst: Point))
114 FPOffset += 8;
115 if (SPOffset < FPOffset) {
116 Next = doKill(Point, StateIn: Next, DeallocSize: 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(Opcode: Point.getOpcode())
125 .hasDefOfPhysReg(MI: Point, Reg: MIB->getStackPointer(), RI: *BC.MRI)) {
126 std::pair<MCPhysReg, int64_t> SP;
127 if (SPOffset != SPT.EMPTY && SPOffset != SPT.SUPERPOSITION)
128 SP = std::make_pair(x: MIB->getStackPointer(), y&: SPOffset);
129 else
130 SP = std::make_pair(x: 0, y: 0);
131 std::pair<MCPhysReg, int64_t> FP;
132 if (FPOffset != SPT.EMPTY && FPOffset != SPT.SUPERPOSITION)
133 FP = std::make_pair(x: MIB->getFramePointer(), y&: FPOffset);
134 else
135 FP = std::make_pair(x: 0, y: 0);
136 int64_t Output;
137 if (!MIB->evaluateStackOffsetExpr(Inst: Point, Output, Input1: SP, Input2: FP))
138 return Next;
139
140 if (SPOffset < Output) {
141 Next = doKill(Point, StateIn: Next, DeallocSize: 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

source code of bolt/lib/Passes/StackAllocationAnalysis.cpp