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