1 //===- bolt/Passes/AllocCombiner.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 AllocCombinerPass class.
10 //
11 //===----------------------------------------------------------------------===//
12 
13 #include "bolt/Passes/AllocCombiner.h"
14 
15 #define DEBUG_TYPE "alloccombiner"
16 
17 using namespace llvm;
18 
19 namespace opts {
20 
21 extern cl::opt<bolt::FrameOptimizationType> FrameOptimization;
22 
23 } // end namespace opts
24 
25 namespace llvm {
26 namespace bolt {
27 
28 namespace {
29 
30 bool getStackAdjustmentSize(const BinaryContext &BC, const MCInst &Inst,
31                             int64_t &Adjustment) {
32   return BC.MIB->evaluateSimple(Inst, Adjustment,
33                                 std::make_pair(BC.MIB->getStackPointer(), 0LL),
34                                 std::make_pair(0, 0LL));
35 }
36 
37 bool isIndifferentToSP(const MCInst &Inst, const BinaryContext &BC) {
38   if (BC.MIB->isCFI(Inst))
39     return true;
40 
41   const MCInstrDesc II = BC.MII->get(Inst.getOpcode());
42   if (BC.MIB->isTerminator(Inst) ||
43       II.hasImplicitDefOfPhysReg(BC.MIB->getStackPointer(), BC.MRI.get()) ||
44       II.hasImplicitUseOfPhysReg(BC.MIB->getStackPointer()))
45     return false;
46 
47   for (int I = 0, E = MCPlus::getNumPrimeOperands(Inst); I != E; ++I) {
48     const MCOperand &Operand = Inst.getOperand(I);
49     if (Operand.isReg() && Operand.getReg() == BC.MIB->getStackPointer())
50       return false;
51   }
52   return true;
53 }
54 
55 bool shouldProcess(const BinaryFunction &Function) {
56   return Function.isSimple() && Function.hasCFG() && !Function.isIgnored();
57 }
58 
59 void runForAllWeCare(std::map<uint64_t, BinaryFunction> &BFs,
60                      std::function<void(BinaryFunction &)> Task) {
61   for (auto &It : BFs) {
62     BinaryFunction &Function = It.second;
63     if (shouldProcess(Function))
64       Task(Function);
65   }
66 }
67 
68 } // end anonymous namespace
69 
70 void AllocCombinerPass::combineAdjustments(BinaryFunction &BF) {
71   BinaryContext &BC = BF.getBinaryContext();
72   for (BinaryBasicBlock &BB : BF) {
73     MCInst *Prev = nullptr;
74     for (auto I = BB.rbegin(), E = BB.rend(); I != E; ++I) {
75       MCInst &Inst = *I;
76       if (isIndifferentToSP(Inst, BC))
77         continue; // Skip updating Prev
78 
79       int64_t Adjustment = 0LL;
80       if (!Prev || !BC.MIB->isStackAdjustment(Inst) ||
81           !BC.MIB->isStackAdjustment(*Prev) ||
82           !getStackAdjustmentSize(BC, *Prev, Adjustment)) {
83         Prev = &Inst;
84         continue;
85       }
86 
87       LLVM_DEBUG({
88         dbgs() << "At \"" << BF.getPrintName() << "\", combining: \n";
89         Inst.dump();
90         Prev->dump();
91         dbgs() << "Adjustment: " << Adjustment << "\n";
92       });
93 
94       if (BC.MIB->isSUB(Inst))
95         Adjustment = -Adjustment;
96 
97       BC.MIB->addToImm(Inst, Adjustment, BC.Ctx.get());
98 
99       LLVM_DEBUG({
100         dbgs() << "After adjustment:\n";
101         Inst.dump();
102       });
103 
104       BB.eraseInstruction(BB.findInstruction(Prev));
105       ++NumCombined;
106       FuncsChanged.insert(&BF);
107       Prev = &Inst;
108     }
109   }
110 }
111 
112 void AllocCombinerPass::runOnFunctions(BinaryContext &BC) {
113   if (opts::FrameOptimization == FOP_NONE)
114     return;
115 
116   runForAllWeCare(BC.getBinaryFunctions(), [&](BinaryFunction &Function) {
117     combineAdjustments(Function);
118   });
119 
120   outs() << "BOLT-INFO: Allocation combiner: " << NumCombined
121          << " empty spaces coalesced.\n";
122 }
123 
124 } // end namespace bolt
125 } // end namespace llvm
126