1//===- bolt/Passes/LivenessAnalysis.h ---------------------------*- C++ -*-===//
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#ifndef BOLT_PASSES_LIVENESSANALYSIS_H
10#define BOLT_PASSES_LIVENESSANALYSIS_H
11
12#include "bolt/Passes/DataflowAnalysis.h"
13#include "bolt/Passes/RegAnalysis.h"
14#include "llvm/MC/MCRegisterInfo.h"
15#include "llvm/Support/CommandLine.h"
16
17namespace opts {
18extern llvm::cl::opt<bool> AssumeABI;
19extern llvm::cl::opt<bool> TimeOpts;
20} // namespace opts
21
22namespace llvm {
23namespace bolt {
24
25class LivenessAnalysis : public DataflowAnalysis<LivenessAnalysis, BitVector,
26 true, RegStatePrinter> {
27 using Parent =
28 DataflowAnalysis<LivenessAnalysis, BitVector, true, RegStatePrinter>;
29 friend class DataflowAnalysis<LivenessAnalysis, BitVector, true,
30 RegStatePrinter>;
31
32public:
33 LivenessAnalysis(const RegAnalysis &RA, BinaryFunction &BF,
34 MCPlusBuilder::AllocatorIdTy AllocId)
35 : Parent(BF, AllocId), RA(RA),
36 NumRegs(BF.getBinaryContext().MRI->getNumRegs()) {}
37 virtual ~LivenessAnalysis();
38
39 bool isAlive(ProgramPoint PP, MCPhysReg Reg) const {
40 BitVector BV = (*this->getStateAt(Point: PP));
41 const BitVector &RegAliases = BC.MIB->getAliases(Reg);
42 BV &= RegAliases;
43 return BV.any();
44 }
45
46 void run() { Parent::run(); }
47
48 // Return a usable general-purpose reg after point P. Return 0 if no reg is
49 // available.
50 MCPhysReg scavengeRegAfter(ProgramPoint P) {
51 BitVector BV = *this->getStateAt(Point: P);
52 BV.flip();
53 BitVector GPRegs(NumRegs, false);
54 this->BC.MIB->getGPRegs(Regs&: GPRegs, /*IncludeAlias=*/IncludeAlias: false);
55 // Ignore the register used for frame pointer even if it is not alive (it
56 // may be used by CFI which is not represented in our dataflow).
57 BitVector FP = BC.MIB->getAliases(Reg: BC.MIB->getFramePointer());
58 FP.flip();
59 BV &= GPRegs;
60 BV &= FP;
61 int Reg = BV.find_first();
62 return Reg != -1 ? Reg : 0;
63 }
64
65protected:
66 /// Reference to the result of reg analysis
67 const RegAnalysis &RA;
68 const uint16_t NumRegs;
69
70 void preflight() {}
71
72 BitVector getStartingStateAtBB(const BinaryBasicBlock &BB) {
73 // Entry points start with default live out (registers used as return
74 // values).
75 if (BB.succ_size() == 0) {
76 BitVector State(NumRegs, false);
77 if (opts::AssumeABI) {
78 BC.MIB->getDefaultLiveOut(Regs&: State);
79 BC.MIB->getCalleeSavedRegs(Regs&: State);
80 } else {
81 State.set();
82 State.reset(Idx: BC.MIB->getFlagsReg());
83 }
84 return State;
85 }
86 return BitVector(NumRegs, false);
87 }
88
89 BitVector getStartingStateAtPoint(const MCInst &Point) {
90 return BitVector(NumRegs, false);
91 }
92
93 void doConfluence(BitVector &StateOut, const BitVector &StateIn) {
94 StateOut |= StateIn;
95 }
96
97 BitVector computeNext(const MCInst &Point, const BitVector &Cur) {
98 BitVector Next = Cur;
99 bool IsCall = this->BC.MIB->isCall(Inst: Point);
100 // Kill
101 BitVector Written = BitVector(NumRegs, false);
102 if (!IsCall) {
103 this->BC.MIB->getWrittenRegs(Inst: Point, Regs&: Written);
104 } else {
105 RA.getInstClobberList(Inst: Point, KillSet&: Written);
106 // When clobber list is conservative, it is clobbering all/most registers,
107 // a conservative estimate because it knows nothing about this call.
108 // For our purposes, assume it kills no registers/callee-saved regs
109 // because we don't really know what's going on.
110 if (RA.isConservative(Vec&: Written)) {
111 Written.reset();
112 BC.MIB->getDefaultLiveOut(Regs&: Written);
113 // If ABI is respected, everything except CSRs should be dead after a
114 // call
115 if (opts::AssumeABI) {
116 BitVector CSR = BitVector(NumRegs, false);
117 BC.MIB->getCalleeSavedRegs(Regs&: CSR);
118 CSR.flip();
119 Written |= CSR;
120 }
121 }
122 }
123 Written.flip();
124 Next &= Written;
125 // Gen
126 if (!this->BC.MIB->isCFI(Inst: Point)) {
127 if (BC.MIB->isCleanRegXOR(Inst: Point))
128 return Next;
129
130 BitVector Used = BitVector(NumRegs, false);
131 if (IsCall) {
132 RA.getInstUsedRegsList(Inst: Point, RegSet&: Used, /*GetClobbers*/ GetClobbers: true);
133 if (RA.isConservative(Vec&: Used)) {
134 Used = BC.MIB->getRegsUsedAsParams();
135 BC.MIB->getDefaultLiveOut(Regs&: Used);
136 }
137 }
138 const MCInstrDesc &InstInfo = BC.MII->get(Opcode: Point.getOpcode());
139 for (const MCOperand &Op : BC.MIB->useOperands(Inst: Point))
140 if (Op.isReg())
141 Used |= BC.MIB->getAliases(Reg: Op.getReg(), /*OnlySmaller=*/OnlySmaller: false);
142 for (MCPhysReg ImplicitUse : InstInfo.implicit_uses())
143 Used |= BC.MIB->getAliases(Reg: ImplicitUse, OnlySmaller: false);
144 if (IsCall &&
145 (!BC.MIB->isTailCall(Inst: Point) || !BC.MIB->isConditionalBranch(Inst: Point))) {
146 // Never gen FLAGS from a non-conditional call... this is overly
147 // conservative
148 Used.reset(Idx: BC.MIB->getFlagsReg());
149 }
150 Next |= Used;
151 }
152 return Next;
153 }
154
155 StringRef getAnnotationName() const { return StringRef("LivenessAnalysis"); }
156};
157
158} // end namespace bolt
159} // end namespace llvm
160
161#endif
162

source code of bolt/include/bolt/Passes/LivenessAnalysis.h