1 //===--- HexagonBranchRelaxation.cpp - Identify and relax long jumps ------===//
2 //
3 // The LLVM Compiler Infrastructure
4 //
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
7 //
8 //===----------------------------------------------------------------------===//
9
10 #define DEBUG_TYPE "hexagon-brelax"
11
12 #include "Hexagon.h"
13 #include "HexagonInstrInfo.h"
14 #include "HexagonSubtarget.h"
15 #include "HexagonTargetMachine.h"
16 #include "llvm/ADT/DenseMap.h"
17 #include "llvm/CodeGen/MachineFunction.h"
18 #include "llvm/CodeGen/MachineFunctionPass.h"
19 #include "llvm/CodeGen/Passes.h"
20 #include "llvm/PassSupport.h"
21 #include "llvm/Support/CommandLine.h"
22 #include "llvm/Support/Debug.h"
23 #include "llvm/Support/raw_ostream.h"
24
25 using namespace llvm;
26
27 // Since we have no exact knowledge of code layout, allow some safety buffer
28 // for jump target. This is measured in bytes.
29 static cl::opt<uint32_t> BranchRelaxSafetyBuffer("branch-relax-safety-buffer",
30 cl::init(200), cl::Hidden, cl::ZeroOrMore, cl::desc("safety buffer size"));
31
32 namespace llvm {
33 FunctionPass *createHexagonBranchRelaxation();
34 void initializeHexagonBranchRelaxationPass(PassRegistry&);
35 }
36
37 namespace {
38 struct HexagonBranchRelaxation : public MachineFunctionPass {
39 public:
40 static char ID;
HexagonBranchRelaxation__anon9598290f0111::HexagonBranchRelaxation41 HexagonBranchRelaxation() : MachineFunctionPass(ID) {
42 initializeHexagonBranchRelaxationPass(*PassRegistry::getPassRegistry());
43 }
44
45 bool runOnMachineFunction(MachineFunction &MF) override;
46
getPassName__anon9598290f0111::HexagonBranchRelaxation47 const char *getPassName() const override {
48 return "Hexagon Branch Relaxation";
49 }
50
getAnalysisUsage__anon9598290f0111::HexagonBranchRelaxation51 void getAnalysisUsage(AnalysisUsage &AU) const override {
52 AU.setPreservesCFG();
53 MachineFunctionPass::getAnalysisUsage(AU);
54 }
55
56 private:
57 const HexagonInstrInfo *HII;
58 const HexagonRegisterInfo *HRI;
59
60 bool relaxBranches(MachineFunction &MF);
61 void computeOffset(MachineFunction &MF,
62 DenseMap<MachineBasicBlock*, unsigned> &BlockToInstOffset);
63 bool reGenerateBranch(MachineFunction &MF,
64 DenseMap<MachineBasicBlock*, unsigned> &BlockToInstOffset);
65 bool isJumpOutOfRange(MachineInstr &MI,
66 DenseMap<MachineBasicBlock*, unsigned> &BlockToInstOffset);
67 };
68
69 char HexagonBranchRelaxation::ID = 0;
70 } // end anonymous namespace
71
72 INITIALIZE_PASS(HexagonBranchRelaxation, "hexagon-brelax",
73 "Hexagon Branch Relaxation", false, false)
74
createHexagonBranchRelaxation()75 FunctionPass *llvm::createHexagonBranchRelaxation() {
76 return new HexagonBranchRelaxation();
77 }
78
79
runOnMachineFunction(MachineFunction & MF)80 bool HexagonBranchRelaxation::runOnMachineFunction(MachineFunction &MF) {
81 DEBUG(dbgs() << "****** Hexagon Branch Relaxation ******\n");
82
83 auto &HST = MF.getSubtarget<HexagonSubtarget>();
84 HII = HST.getInstrInfo();
85 HRI = HST.getRegisterInfo();
86
87 bool Changed = false;
88 Changed = relaxBranches(MF);
89 return Changed;
90 }
91
92
computeOffset(MachineFunction & MF,DenseMap<MachineBasicBlock *,unsigned> & OffsetMap)93 void HexagonBranchRelaxation::computeOffset(MachineFunction &MF,
94 DenseMap<MachineBasicBlock*, unsigned> &OffsetMap) {
95 // offset of the current instruction from the start.
96 unsigned InstOffset = 0;
97 for (auto &B : MF) {
98 if (B.getAlignment()) {
99 // Although we don't know the exact layout of the final code, we need
100 // to account for alignment padding somehow. This heuristic pads each
101 // aligned basic block according to the alignment value.
102 int ByteAlign = (1u << B.getAlignment()) - 1;
103 InstOffset = (InstOffset + ByteAlign) & ~(ByteAlign);
104 }
105 OffsetMap[&B] = InstOffset;
106 for (auto &MI : B.instrs())
107 InstOffset += HII->getSize(&MI);
108 }
109 }
110
111
112 /// relaxBranches - For Hexagon, if the jump target/loop label is too far from
113 /// the jump/loop instruction then, we need to make sure that we have constant
114 /// extenders set for jumps and loops.
115
116 /// There are six iterations in this phase. It's self explanatory below.
relaxBranches(MachineFunction & MF)117 bool HexagonBranchRelaxation::relaxBranches(MachineFunction &MF) {
118 // Compute the offset of each basic block
119 // offset of the current instruction from the start.
120 // map for each instruction to the beginning of the function
121 DenseMap<MachineBasicBlock*, unsigned> BlockToInstOffset;
122 computeOffset(MF, BlockToInstOffset);
123
124 return reGenerateBranch(MF, BlockToInstOffset);
125 }
126
127
128 /// Check if a given instruction is:
129 /// - a jump to a distant target
130 /// - that exceeds its immediate range
131 /// If both conditions are true, it requires constant extension.
isJumpOutOfRange(MachineInstr & MI,DenseMap<MachineBasicBlock *,unsigned> & BlockToInstOffset)132 bool HexagonBranchRelaxation::isJumpOutOfRange(MachineInstr &MI,
133 DenseMap<MachineBasicBlock*, unsigned> &BlockToInstOffset) {
134 MachineBasicBlock &B = *MI.getParent();
135 auto FirstTerm = B.getFirstInstrTerminator();
136 if (FirstTerm == B.instr_end())
137 return false;
138
139 unsigned InstOffset = BlockToInstOffset[&B];
140 unsigned Distance = 0;
141
142 // To save time, estimate exact position of a branch instruction
143 // as one at the end of the MBB.
144 // Number of instructions times typical instruction size.
145 InstOffset += HII->nonDbgBBSize(&B) * HEXAGON_INSTR_SIZE;
146
147 MachineBasicBlock *TBB = NULL, *FBB = NULL;
148 SmallVector<MachineOperand, 4> Cond;
149
150 // Try to analyze this branch.
151 if (HII->analyzeBranch(B, TBB, FBB, Cond, false)) {
152 // Could not analyze it. See if this is something we can recognize.
153 // If it is a NVJ, it should always have its target in
154 // a fixed location.
155 if (HII->isNewValueJump(&*FirstTerm))
156 TBB = FirstTerm->getOperand(HII->getCExtOpNum(&*FirstTerm)).getMBB();
157 }
158 if (TBB && &MI == &*FirstTerm) {
159 Distance = std::abs((long long)InstOffset - BlockToInstOffset[TBB])
160 + BranchRelaxSafetyBuffer;
161 return !HII->isJumpWithinBranchRange(&*FirstTerm, Distance);
162 }
163 if (FBB) {
164 // Look for second terminator.
165 auto SecondTerm = std::next(FirstTerm);
166 assert(SecondTerm != B.instr_end() &&
167 (SecondTerm->isBranch() || SecondTerm->isCall()) &&
168 "Bad second terminator");
169 if (&MI != &*SecondTerm)
170 return false;
171 // Analyze the second branch in the BB.
172 Distance = std::abs((long long)InstOffset - BlockToInstOffset[FBB])
173 + BranchRelaxSafetyBuffer;
174 return !HII->isJumpWithinBranchRange(&*SecondTerm, Distance);
175 }
176 return false;
177 }
178
179
reGenerateBranch(MachineFunction & MF,DenseMap<MachineBasicBlock *,unsigned> & BlockToInstOffset)180 bool HexagonBranchRelaxation::reGenerateBranch(MachineFunction &MF,
181 DenseMap<MachineBasicBlock*, unsigned> &BlockToInstOffset) {
182 bool Changed = false;
183
184 for (auto &B : MF) {
185 for (auto &MI : B) {
186 if (!MI.isBranch() || !isJumpOutOfRange(MI, BlockToInstOffset))
187 continue;
188 DEBUG(dbgs() << "Long distance jump. isExtendable("
189 << HII->isExtendable(&MI) << ") isConstExtended("
190 << HII->isConstExtended(&MI) << ") " << MI);
191
192 // Since we have not merged HW loops relaxation into
193 // this code (yet), soften our approach for the moment.
194 if (!HII->isExtendable(&MI) && !HII->isExtended(&MI)) {
195 DEBUG(dbgs() << "\tUnderimplemented relax branch instruction.\n");
196 } else {
197 // Find which operand is expandable.
198 int ExtOpNum = HII->getCExtOpNum(&MI);
199 MachineOperand &MO = MI.getOperand(ExtOpNum);
200 // This need to be something we understand. So far we assume all
201 // branches have only MBB address as expandable field.
202 // If it changes, this will need to be expanded.
203 assert(MO.isMBB() && "Branch with unknown expandable field type");
204 // Mark given operand as extended.
205 MO.addTargetFlag(HexagonII::HMOTF_ConstExtended);
206 Changed = true;
207 }
208 }
209 }
210 return Changed;
211 }
212