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