File: | lib/Target/Hexagon/HexagonHardwareLoops.cpp |
Location: | line 655, column 24 |
Description: | Division by zero |
1 | //===-- HexagonHardwareLoops.cpp - Identify and generate hardware loops ---===// | |||
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 | // This pass identifies loops where we can generate the Hexagon hardware | |||
11 | // loop instruction. The hardware loop can perform loop branches with a | |||
12 | // zero-cycle overhead. | |||
13 | // | |||
14 | // The pattern that defines the induction variable can changed depending on | |||
15 | // prior optimizations. For example, the IndVarSimplify phase run by 'opt' | |||
16 | // normalizes induction variables, and the Loop Strength Reduction pass | |||
17 | // run by 'llc' may also make changes to the induction variable. | |||
18 | // The pattern detected by this phase is due to running Strength Reduction. | |||
19 | // | |||
20 | // Criteria for hardware loops: | |||
21 | // - Countable loops (w/ ind. var for a trip count) | |||
22 | // - Assumes loops are normalized by IndVarSimplify | |||
23 | // - Try inner-most loops first | |||
24 | // - No nested hardware loops. | |||
25 | // - No function calls in loops. | |||
26 | // | |||
27 | //===----------------------------------------------------------------------===// | |||
28 | ||||
29 | #include "llvm/ADT/SmallSet.h" | |||
30 | #include "Hexagon.h" | |||
31 | #include "HexagonSubtarget.h" | |||
32 | #include "llvm/ADT/Statistic.h" | |||
33 | #include "llvm/CodeGen/MachineDominators.h" | |||
34 | #include "llvm/CodeGen/MachineFunction.h" | |||
35 | #include "llvm/CodeGen/MachineFunctionPass.h" | |||
36 | #include "llvm/CodeGen/MachineInstrBuilder.h" | |||
37 | #include "llvm/CodeGen/MachineLoopInfo.h" | |||
38 | #include "llvm/CodeGen/MachineRegisterInfo.h" | |||
39 | #include "llvm/PassSupport.h" | |||
40 | #include "llvm/Support/CommandLine.h" | |||
41 | #include "llvm/Support/Debug.h" | |||
42 | #include "llvm/Support/raw_ostream.h" | |||
43 | #include "llvm/Target/TargetInstrInfo.h" | |||
44 | #include <algorithm> | |||
45 | #include <vector> | |||
46 | ||||
47 | using namespace llvm; | |||
48 | ||||
49 | #define DEBUG_TYPE"hwloops" "hwloops" | |||
50 | ||||
51 | #ifndef NDEBUG | |||
52 | static cl::opt<int> HWLoopLimit("max-hwloop", cl::Hidden, cl::init(-1)); | |||
53 | #endif | |||
54 | ||||
55 | STATISTIC(NumHWLoops, "Number of loops converted to hardware loops")static llvm::Statistic NumHWLoops = { "hwloops", "Number of loops converted to hardware loops" , 0, 0 }; | |||
56 | ||||
57 | namespace llvm { | |||
58 | void initializeHexagonHardwareLoopsPass(PassRegistry&); | |||
59 | } | |||
60 | ||||
61 | namespace { | |||
62 | class CountValue; | |||
63 | struct HexagonHardwareLoops : public MachineFunctionPass { | |||
64 | MachineLoopInfo *MLI; | |||
65 | MachineRegisterInfo *MRI; | |||
66 | MachineDominatorTree *MDT; | |||
67 | const HexagonInstrInfo *TII; | |||
68 | #ifndef NDEBUG | |||
69 | static int Counter; | |||
70 | #endif | |||
71 | ||||
72 | public: | |||
73 | static char ID; | |||
74 | ||||
75 | HexagonHardwareLoops() : MachineFunctionPass(ID) { | |||
76 | initializeHexagonHardwareLoopsPass(*PassRegistry::getPassRegistry()); | |||
77 | } | |||
78 | ||||
79 | bool runOnMachineFunction(MachineFunction &MF) override; | |||
80 | ||||
81 | const char *getPassName() const override { return "Hexagon Hardware Loops"; } | |||
82 | ||||
83 | void getAnalysisUsage(AnalysisUsage &AU) const override { | |||
84 | AU.addRequired<MachineDominatorTree>(); | |||
85 | AU.addRequired<MachineLoopInfo>(); | |||
86 | MachineFunctionPass::getAnalysisUsage(AU); | |||
87 | } | |||
88 | ||||
89 | private: | |||
90 | /// Kinds of comparisons in the compare instructions. | |||
91 | struct Comparison { | |||
92 | enum Kind { | |||
93 | EQ = 0x01, | |||
94 | NE = 0x02, | |||
95 | L = 0x04, // Less-than property. | |||
96 | G = 0x08, // Greater-than property. | |||
97 | U = 0x40, // Unsigned property. | |||
98 | LTs = L, | |||
99 | LEs = L | EQ, | |||
100 | GTs = G, | |||
101 | GEs = G | EQ, | |||
102 | LTu = L | U, | |||
103 | LEu = L | EQ | U, | |||
104 | GTu = G | U, | |||
105 | GEu = G | EQ | U | |||
106 | }; | |||
107 | ||||
108 | static Kind getSwappedComparison(Kind Cmp) { | |||
109 | assert ((!((Cmp & L) && (Cmp & G))) && "Malformed comparison operator")(((!((Cmp & L) && (Cmp & G))) && "Malformed comparison operator" ) ? static_cast<void> (0) : __assert_fail ("(!((Cmp & L) && (Cmp & G))) && \"Malformed comparison operator\"" , "/tmp/buildd/llvm-toolchain-snapshot-3.7~svn236768/lib/Target/Hexagon/HexagonHardwareLoops.cpp" , 109, __PRETTY_FUNCTION__)); | |||
110 | if ((Cmp & L) || (Cmp & G)) | |||
111 | return (Kind)(Cmp ^ (L|G)); | |||
112 | return Cmp; | |||
113 | } | |||
114 | }; | |||
115 | ||||
116 | /// \brief Find the register that contains the loop controlling | |||
117 | /// induction variable. | |||
118 | /// If successful, it will return true and set the \p Reg, \p IVBump | |||
119 | /// and \p IVOp arguments. Otherwise it will return false. | |||
120 | /// The returned induction register is the register R that follows the | |||
121 | /// following induction pattern: | |||
122 | /// loop: | |||
123 | /// R = phi ..., [ R.next, LatchBlock ] | |||
124 | /// R.next = R + #bump | |||
125 | /// if (R.next < #N) goto loop | |||
126 | /// IVBump is the immediate value added to R, and IVOp is the instruction | |||
127 | /// "R.next = R + #bump". | |||
128 | bool findInductionRegister(MachineLoop *L, unsigned &Reg, | |||
129 | int64_t &IVBump, MachineInstr *&IVOp) const; | |||
130 | ||||
131 | /// \brief Analyze the statements in a loop to determine if the loop | |||
132 | /// has a computable trip count and, if so, return a value that represents | |||
133 | /// the trip count expression. | |||
134 | CountValue *getLoopTripCount(MachineLoop *L, | |||
135 | SmallVectorImpl<MachineInstr *> &OldInsts); | |||
136 | ||||
137 | /// \brief Return the expression that represents the number of times | |||
138 | /// a loop iterates. The function takes the operands that represent the | |||
139 | /// loop start value, loop end value, and induction value. Based upon | |||
140 | /// these operands, the function attempts to compute the trip count. | |||
141 | /// If the trip count is not directly available (as an immediate value, | |||
142 | /// or a register), the function will attempt to insert computation of it | |||
143 | /// to the loop's preheader. | |||
144 | CountValue *computeCount(MachineLoop *Loop, | |||
145 | const MachineOperand *Start, | |||
146 | const MachineOperand *End, | |||
147 | unsigned IVReg, | |||
148 | int64_t IVBump, | |||
149 | Comparison::Kind Cmp) const; | |||
150 | ||||
151 | /// \brief Return true if the instruction is not valid within a hardware | |||
152 | /// loop. | |||
153 | bool isInvalidLoopOperation(const MachineInstr *MI) const; | |||
154 | ||||
155 | /// \brief Return true if the loop contains an instruction that inhibits | |||
156 | /// using the hardware loop. | |||
157 | bool containsInvalidInstruction(MachineLoop *L) const; | |||
158 | ||||
159 | /// \brief Given a loop, check if we can convert it to a hardware loop. | |||
160 | /// If so, then perform the conversion and return true. | |||
161 | bool convertToHardwareLoop(MachineLoop *L); | |||
162 | ||||
163 | /// \brief Return true if the instruction is now dead. | |||
164 | bool isDead(const MachineInstr *MI, | |||
165 | SmallVectorImpl<MachineInstr *> &DeadPhis) const; | |||
166 | ||||
167 | /// \brief Remove the instruction if it is now dead. | |||
168 | void removeIfDead(MachineInstr *MI); | |||
169 | ||||
170 | /// \brief Make sure that the "bump" instruction executes before the | |||
171 | /// compare. We need that for the IV fixup, so that the compare | |||
172 | /// instruction would not use a bumped value that has not yet been | |||
173 | /// defined. If the instructions are out of order, try to reorder them. | |||
174 | bool orderBumpCompare(MachineInstr *BumpI, MachineInstr *CmpI); | |||
175 | ||||
176 | /// \brief Get the instruction that loads an immediate value into \p R, | |||
177 | /// or 0 if such an instruction does not exist. | |||
178 | MachineInstr *defWithImmediate(unsigned R); | |||
179 | ||||
180 | /// \brief Get the immediate value referenced to by \p MO, either for | |||
181 | /// immediate operands, or for register operands, where the register | |||
182 | /// was defined with an immediate value. | |||
183 | int64_t getImmediate(MachineOperand &MO); | |||
184 | ||||
185 | /// \brief Reset the given machine operand to now refer to a new immediate | |||
186 | /// value. Assumes that the operand was already referencing an immediate | |||
187 | /// value, either directly, or via a register. | |||
188 | void setImmediate(MachineOperand &MO, int64_t Val); | |||
189 | ||||
190 | /// \brief Fix the data flow of the induction varible. | |||
191 | /// The desired flow is: phi ---> bump -+-> comparison-in-latch. | |||
192 | /// | | |||
193 | /// +-> back to phi | |||
194 | /// where "bump" is the increment of the induction variable: | |||
195 | /// iv = iv + #const. | |||
196 | /// Due to some prior code transformations, the actual flow may look | |||
197 | /// like this: | |||
198 | /// phi -+-> bump ---> back to phi | |||
199 | /// | | |||
200 | /// +-> comparison-in-latch (against upper_bound-bump), | |||
201 | /// i.e. the comparison that controls the loop execution may be using | |||
202 | /// the value of the induction variable from before the increment. | |||
203 | /// | |||
204 | /// Return true if the loop's flow is the desired one (i.e. it's | |||
205 | /// either been fixed, or no fixing was necessary). | |||
206 | /// Otherwise, return false. This can happen if the induction variable | |||
207 | /// couldn't be identified, or if the value in the latch's comparison | |||
208 | /// cannot be adjusted to reflect the post-bump value. | |||
209 | bool fixupInductionVariable(MachineLoop *L); | |||
210 | ||||
211 | /// \brief Given a loop, if it does not have a preheader, create one. | |||
212 | /// Return the block that is the preheader. | |||
213 | MachineBasicBlock *createPreheaderForLoop(MachineLoop *L); | |||
214 | }; | |||
215 | ||||
216 | char HexagonHardwareLoops::ID = 0; | |||
217 | #ifndef NDEBUG | |||
218 | int HexagonHardwareLoops::Counter = 0; | |||
219 | #endif | |||
220 | ||||
221 | /// \brief Abstraction for a trip count of a loop. A smaller version | |||
222 | /// of the MachineOperand class without the concerns of changing the | |||
223 | /// operand representation. | |||
224 | class CountValue { | |||
225 | public: | |||
226 | enum CountValueType { | |||
227 | CV_Register, | |||
228 | CV_Immediate | |||
229 | }; | |||
230 | private: | |||
231 | CountValueType Kind; | |||
232 | union Values { | |||
233 | struct { | |||
234 | unsigned Reg; | |||
235 | unsigned Sub; | |||
236 | } R; | |||
237 | unsigned ImmVal; | |||
238 | } Contents; | |||
239 | ||||
240 | public: | |||
241 | explicit CountValue(CountValueType t, unsigned v, unsigned u = 0) { | |||
242 | Kind = t; | |||
243 | if (Kind == CV_Register) { | |||
244 | Contents.R.Reg = v; | |||
245 | Contents.R.Sub = u; | |||
246 | } else { | |||
247 | Contents.ImmVal = v; | |||
248 | } | |||
249 | } | |||
250 | bool isReg() const { return Kind == CV_Register; } | |||
251 | bool isImm() const { return Kind == CV_Immediate; } | |||
252 | ||||
253 | unsigned getReg() const { | |||
254 | assert(isReg() && "Wrong CountValue accessor")((isReg() && "Wrong CountValue accessor") ? static_cast <void> (0) : __assert_fail ("isReg() && \"Wrong CountValue accessor\"" , "/tmp/buildd/llvm-toolchain-snapshot-3.7~svn236768/lib/Target/Hexagon/HexagonHardwareLoops.cpp" , 254, __PRETTY_FUNCTION__)); | |||
255 | return Contents.R.Reg; | |||
256 | } | |||
257 | unsigned getSubReg() const { | |||
258 | assert(isReg() && "Wrong CountValue accessor")((isReg() && "Wrong CountValue accessor") ? static_cast <void> (0) : __assert_fail ("isReg() && \"Wrong CountValue accessor\"" , "/tmp/buildd/llvm-toolchain-snapshot-3.7~svn236768/lib/Target/Hexagon/HexagonHardwareLoops.cpp" , 258, __PRETTY_FUNCTION__)); | |||
259 | return Contents.R.Sub; | |||
260 | } | |||
261 | unsigned getImm() const { | |||
262 | assert(isImm() && "Wrong CountValue accessor")((isImm() && "Wrong CountValue accessor") ? static_cast <void> (0) : __assert_fail ("isImm() && \"Wrong CountValue accessor\"" , "/tmp/buildd/llvm-toolchain-snapshot-3.7~svn236768/lib/Target/Hexagon/HexagonHardwareLoops.cpp" , 262, __PRETTY_FUNCTION__)); | |||
263 | return Contents.ImmVal; | |||
264 | } | |||
265 | ||||
266 | void print(raw_ostream &OS, const TargetRegisterInfo *TRI = nullptr) const { | |||
267 | if (isReg()) { OS << PrintReg(Contents.R.Reg, TRI, Contents.R.Sub); } | |||
268 | if (isImm()) { OS << Contents.ImmVal; } | |||
269 | } | |||
270 | }; | |||
271 | } // end anonymous namespace | |||
272 | ||||
273 | ||||
274 | INITIALIZE_PASS_BEGIN(HexagonHardwareLoops, "hwloops",static void* initializeHexagonHardwareLoopsPassOnce(PassRegistry &Registry) { | |||
275 | "Hexagon Hardware Loops", false, false)static void* initializeHexagonHardwareLoopsPassOnce(PassRegistry &Registry) { | |||
276 | INITIALIZE_PASS_DEPENDENCY(MachineDominatorTree)initializeMachineDominatorTreePass(Registry); | |||
277 | INITIALIZE_PASS_DEPENDENCY(MachineLoopInfo)initializeMachineLoopInfoPass(Registry); | |||
278 | INITIALIZE_PASS_END(HexagonHardwareLoops, "hwloops",PassInfo *PI = new PassInfo("Hexagon Hardware Loops", "hwloops" , & HexagonHardwareLoops ::ID, PassInfo::NormalCtor_t(callDefaultCtor < HexagonHardwareLoops >), false, false); Registry.registerPass (*PI, true); return PI; } void llvm::initializeHexagonHardwareLoopsPass (PassRegistry &Registry) { static volatile sys::cas_flag initialized = 0; sys::cas_flag old_val = sys::CompareAndSwap(&initialized , 1, 0); if (old_val == 0) { initializeHexagonHardwareLoopsPassOnce (Registry); sys::MemoryFence(); AnnotateIgnoreWritesBegin("/tmp/buildd/llvm-toolchain-snapshot-3.7~svn236768/lib/Target/Hexagon/HexagonHardwareLoops.cpp" , 279); AnnotateHappensBefore("/tmp/buildd/llvm-toolchain-snapshot-3.7~svn236768/lib/Target/Hexagon/HexagonHardwareLoops.cpp" , 279, &initialized); initialized = 2; AnnotateIgnoreWritesEnd ("/tmp/buildd/llvm-toolchain-snapshot-3.7~svn236768/lib/Target/Hexagon/HexagonHardwareLoops.cpp" , 279); } else { sys::cas_flag tmp = initialized; sys::MemoryFence (); while (tmp != 2) { tmp = initialized; sys::MemoryFence(); } } AnnotateHappensAfter("/tmp/buildd/llvm-toolchain-snapshot-3.7~svn236768/lib/Target/Hexagon/HexagonHardwareLoops.cpp" , 279, &initialized); } | |||
279 | "Hexagon Hardware Loops", false, false)PassInfo *PI = new PassInfo("Hexagon Hardware Loops", "hwloops" , & HexagonHardwareLoops ::ID, PassInfo::NormalCtor_t(callDefaultCtor < HexagonHardwareLoops >), false, false); Registry.registerPass (*PI, true); return PI; } void llvm::initializeHexagonHardwareLoopsPass (PassRegistry &Registry) { static volatile sys::cas_flag initialized = 0; sys::cas_flag old_val = sys::CompareAndSwap(&initialized , 1, 0); if (old_val == 0) { initializeHexagonHardwareLoopsPassOnce (Registry); sys::MemoryFence(); AnnotateIgnoreWritesBegin("/tmp/buildd/llvm-toolchain-snapshot-3.7~svn236768/lib/Target/Hexagon/HexagonHardwareLoops.cpp" , 279); AnnotateHappensBefore("/tmp/buildd/llvm-toolchain-snapshot-3.7~svn236768/lib/Target/Hexagon/HexagonHardwareLoops.cpp" , 279, &initialized); initialized = 2; AnnotateIgnoreWritesEnd ("/tmp/buildd/llvm-toolchain-snapshot-3.7~svn236768/lib/Target/Hexagon/HexagonHardwareLoops.cpp" , 279); } else { sys::cas_flag tmp = initialized; sys::MemoryFence (); while (tmp != 2) { tmp = initialized; sys::MemoryFence(); } } AnnotateHappensAfter("/tmp/buildd/llvm-toolchain-snapshot-3.7~svn236768/lib/Target/Hexagon/HexagonHardwareLoops.cpp" , 279, &initialized); } | |||
280 | ||||
281 | ||||
282 | /// \brief Returns true if the instruction is a hardware loop instruction. | |||
283 | static bool isHardwareLoop(const MachineInstr *MI) { | |||
284 | return MI->getOpcode() == Hexagon::J2_loop0r || | |||
285 | MI->getOpcode() == Hexagon::J2_loop0i; | |||
286 | } | |||
287 | ||||
288 | FunctionPass *llvm::createHexagonHardwareLoops() { | |||
289 | return new HexagonHardwareLoops(); | |||
290 | } | |||
291 | ||||
292 | ||||
293 | bool HexagonHardwareLoops::runOnMachineFunction(MachineFunction &MF) { | |||
294 | DEBUG(dbgs() << "********* Hexagon Hardware Loops *********\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("hwloops")) { dbgs() << "********* Hexagon Hardware Loops *********\n" ; } } while (0); | |||
295 | ||||
296 | bool Changed = false; | |||
297 | ||||
298 | MLI = &getAnalysis<MachineLoopInfo>(); | |||
299 | MRI = &MF.getRegInfo(); | |||
300 | MDT = &getAnalysis<MachineDominatorTree>(); | |||
301 | TII = MF.getSubtarget<HexagonSubtarget>().getInstrInfo(); | |||
302 | ||||
303 | for (MachineLoopInfo::iterator I = MLI->begin(), E = MLI->end(); | |||
304 | I != E; ++I) { | |||
305 | MachineLoop *L = *I; | |||
306 | if (!L->getParentLoop()) | |||
307 | Changed |= convertToHardwareLoop(L); | |||
308 | } | |||
309 | ||||
310 | return Changed; | |||
311 | } | |||
312 | ||||
313 | ||||
314 | bool HexagonHardwareLoops::findInductionRegister(MachineLoop *L, | |||
315 | unsigned &Reg, | |||
316 | int64_t &IVBump, | |||
317 | MachineInstr *&IVOp | |||
318 | ) const { | |||
319 | MachineBasicBlock *Header = L->getHeader(); | |||
320 | MachineBasicBlock *Preheader = L->getLoopPreheader(); | |||
321 | MachineBasicBlock *Latch = L->getLoopLatch(); | |||
322 | if (!Header || !Preheader || !Latch) | |||
323 | return false; | |||
324 | ||||
325 | // This pair represents an induction register together with an immediate | |||
326 | // value that will be added to it in each loop iteration. | |||
327 | typedef std::pair<unsigned,int64_t> RegisterBump; | |||
328 | ||||
329 | // Mapping: R.next -> (R, bump), where R, R.next and bump are derived | |||
330 | // from an induction operation | |||
331 | // R.next = R + bump | |||
332 | // where bump is an immediate value. | |||
333 | typedef std::map<unsigned,RegisterBump> InductionMap; | |||
334 | ||||
335 | InductionMap IndMap; | |||
336 | ||||
337 | typedef MachineBasicBlock::instr_iterator instr_iterator; | |||
338 | for (instr_iterator I = Header->instr_begin(), E = Header->instr_end(); | |||
339 | I != E && I->isPHI(); ++I) { | |||
340 | MachineInstr *Phi = &*I; | |||
341 | ||||
342 | // Have a PHI instruction. Get the operand that corresponds to the | |||
343 | // latch block, and see if is a result of an addition of form "reg+imm", | |||
344 | // where the "reg" is defined by the PHI node we are looking at. | |||
345 | for (unsigned i = 1, n = Phi->getNumOperands(); i < n; i += 2) { | |||
346 | if (Phi->getOperand(i+1).getMBB() != Latch) | |||
347 | continue; | |||
348 | ||||
349 | unsigned PhiOpReg = Phi->getOperand(i).getReg(); | |||
350 | MachineInstr *DI = MRI->getVRegDef(PhiOpReg); | |||
351 | unsigned UpdOpc = DI->getOpcode(); | |||
352 | bool isAdd = (UpdOpc == Hexagon::A2_addi); | |||
353 | ||||
354 | if (isAdd) { | |||
355 | // If the register operand to the add is the PHI we're | |||
356 | // looking at, this meets the induction pattern. | |||
357 | unsigned IndReg = DI->getOperand(1).getReg(); | |||
358 | if (MRI->getVRegDef(IndReg) == Phi) { | |||
359 | unsigned UpdReg = DI->getOperand(0).getReg(); | |||
360 | int64_t V = DI->getOperand(2).getImm(); | |||
361 | IndMap.insert(std::make_pair(UpdReg, std::make_pair(IndReg, V))); | |||
362 | } | |||
363 | } | |||
364 | } // for (i) | |||
365 | } // for (instr) | |||
366 | ||||
367 | SmallVector<MachineOperand,2> Cond; | |||
368 | MachineBasicBlock *TB = nullptr, *FB = nullptr; | |||
369 | bool NotAnalyzed = TII->AnalyzeBranch(*Latch, TB, FB, Cond, false); | |||
370 | if (NotAnalyzed) | |||
371 | return false; | |||
372 | ||||
373 | unsigned CSz = Cond.size(); | |||
374 | assert (CSz == 1 || CSz == 2)((CSz == 1 || CSz == 2) ? static_cast<void> (0) : __assert_fail ("CSz == 1 || CSz == 2", "/tmp/buildd/llvm-toolchain-snapshot-3.7~svn236768/lib/Target/Hexagon/HexagonHardwareLoops.cpp" , 374, __PRETTY_FUNCTION__)); | |||
375 | unsigned PredR = Cond[CSz-1].getReg(); | |||
376 | ||||
377 | MachineInstr *PredI = MRI->getVRegDef(PredR); | |||
378 | if (!PredI->isCompare()) | |||
379 | return false; | |||
380 | ||||
381 | unsigned CmpReg1 = 0, CmpReg2 = 0; | |||
382 | int CmpImm = 0, CmpMask = 0; | |||
383 | bool CmpAnalyzed = TII->analyzeCompare(PredI, CmpReg1, CmpReg2, | |||
384 | CmpMask, CmpImm); | |||
385 | // Fail if the compare was not analyzed, or it's not comparing a register | |||
386 | // with an immediate value. Not checking the mask here, since we handle | |||
387 | // the individual compare opcodes (including CMPb) later on. | |||
388 | if (!CmpAnalyzed) | |||
389 | return false; | |||
390 | ||||
391 | // Exactly one of the input registers to the comparison should be among | |||
392 | // the induction registers. | |||
393 | InductionMap::iterator IndMapEnd = IndMap.end(); | |||
394 | InductionMap::iterator F = IndMapEnd; | |||
395 | if (CmpReg1 != 0) { | |||
396 | InductionMap::iterator F1 = IndMap.find(CmpReg1); | |||
397 | if (F1 != IndMapEnd) | |||
398 | F = F1; | |||
399 | } | |||
400 | if (CmpReg2 != 0) { | |||
401 | InductionMap::iterator F2 = IndMap.find(CmpReg2); | |||
402 | if (F2 != IndMapEnd) { | |||
403 | if (F != IndMapEnd) | |||
404 | return false; | |||
405 | F = F2; | |||
406 | } | |||
407 | } | |||
408 | if (F == IndMapEnd) | |||
409 | return false; | |||
410 | ||||
411 | Reg = F->second.first; | |||
412 | IVBump = F->second.second; | |||
413 | IVOp = MRI->getVRegDef(F->first); | |||
414 | return true; | |||
415 | } | |||
416 | ||||
417 | ||||
418 | /// \brief Analyze the statements in a loop to determine if the loop has | |||
419 | /// a computable trip count and, if so, return a value that represents | |||
420 | /// the trip count expression. | |||
421 | /// | |||
422 | /// This function iterates over the phi nodes in the loop to check for | |||
423 | /// induction variable patterns that are used in the calculation for | |||
424 | /// the number of time the loop is executed. | |||
425 | CountValue *HexagonHardwareLoops::getLoopTripCount(MachineLoop *L, | |||
426 | SmallVectorImpl<MachineInstr *> &OldInsts) { | |||
427 | MachineBasicBlock *TopMBB = L->getTopBlock(); | |||
428 | MachineBasicBlock::pred_iterator PI = TopMBB->pred_begin(); | |||
429 | assert(PI != TopMBB->pred_end() &&((PI != TopMBB->pred_end() && "Loop must have more than one incoming edge!" ) ? static_cast<void> (0) : __assert_fail ("PI != TopMBB->pred_end() && \"Loop must have more than one incoming edge!\"" , "/tmp/buildd/llvm-toolchain-snapshot-3.7~svn236768/lib/Target/Hexagon/HexagonHardwareLoops.cpp" , 430, __PRETTY_FUNCTION__)) | |||
430 | "Loop must have more than one incoming edge!")((PI != TopMBB->pred_end() && "Loop must have more than one incoming edge!" ) ? static_cast<void> (0) : __assert_fail ("PI != TopMBB->pred_end() && \"Loop must have more than one incoming edge!\"" , "/tmp/buildd/llvm-toolchain-snapshot-3.7~svn236768/lib/Target/Hexagon/HexagonHardwareLoops.cpp" , 430, __PRETTY_FUNCTION__)); | |||
431 | MachineBasicBlock *Backedge = *PI++; | |||
432 | if (PI == TopMBB->pred_end()) // dead loop? | |||
433 | return nullptr; | |||
434 | MachineBasicBlock *Incoming = *PI++; | |||
435 | if (PI != TopMBB->pred_end()) // multiple backedges? | |||
436 | return nullptr; | |||
437 | ||||
438 | // Make sure there is one incoming and one backedge and determine which | |||
439 | // is which. | |||
440 | if (L->contains(Incoming)) { | |||
441 | if (L->contains(Backedge)) | |||
442 | return nullptr; | |||
443 | std::swap(Incoming, Backedge); | |||
444 | } else if (!L->contains(Backedge)) | |||
445 | return nullptr; | |||
446 | ||||
447 | // Look for the cmp instruction to determine if we can get a useful trip | |||
448 | // count. The trip count can be either a register or an immediate. The | |||
449 | // location of the value depends upon the type (reg or imm). | |||
450 | MachineBasicBlock *Latch = L->getLoopLatch(); | |||
451 | if (!Latch) | |||
452 | return nullptr; | |||
453 | ||||
454 | unsigned IVReg = 0; | |||
455 | int64_t IVBump = 0; | |||
456 | MachineInstr *IVOp; | |||
457 | bool FoundIV = findInductionRegister(L, IVReg, IVBump, IVOp); | |||
458 | if (!FoundIV) | |||
459 | return nullptr; | |||
460 | ||||
461 | MachineBasicBlock *Preheader = L->getLoopPreheader(); | |||
462 | ||||
463 | MachineOperand *InitialValue = nullptr; | |||
464 | MachineInstr *IV_Phi = MRI->getVRegDef(IVReg); | |||
465 | for (unsigned i = 1, n = IV_Phi->getNumOperands(); i < n; i += 2) { | |||
466 | MachineBasicBlock *MBB = IV_Phi->getOperand(i+1).getMBB(); | |||
467 | if (MBB == Preheader) | |||
468 | InitialValue = &IV_Phi->getOperand(i); | |||
469 | else if (MBB == Latch) | |||
470 | IVReg = IV_Phi->getOperand(i).getReg(); // Want IV reg after bump. | |||
471 | } | |||
472 | if (!InitialValue) | |||
473 | return nullptr; | |||
474 | ||||
475 | SmallVector<MachineOperand,2> Cond; | |||
476 | MachineBasicBlock *TB = nullptr, *FB = nullptr; | |||
477 | bool NotAnalyzed = TII->AnalyzeBranch(*Latch, TB, FB, Cond, false); | |||
478 | if (NotAnalyzed) | |||
479 | return nullptr; | |||
480 | ||||
481 | MachineBasicBlock *Header = L->getHeader(); | |||
482 | // TB must be non-null. If FB is also non-null, one of them must be | |||
483 | // the header. Otherwise, branch to TB could be exiting the loop, and | |||
484 | // the fall through can go to the header. | |||
485 | assert (TB && "Latch block without a branch?")((TB && "Latch block without a branch?") ? static_cast <void> (0) : __assert_fail ("TB && \"Latch block without a branch?\"" , "/tmp/buildd/llvm-toolchain-snapshot-3.7~svn236768/lib/Target/Hexagon/HexagonHardwareLoops.cpp" , 485, __PRETTY_FUNCTION__)); | |||
486 | assert ((!FB || TB == Header || FB == Header) && "Branches not to header?")(((!FB || TB == Header || FB == Header) && "Branches not to header?" ) ? static_cast<void> (0) : __assert_fail ("(!FB || TB == Header || FB == Header) && \"Branches not to header?\"" , "/tmp/buildd/llvm-toolchain-snapshot-3.7~svn236768/lib/Target/Hexagon/HexagonHardwareLoops.cpp" , 486, __PRETTY_FUNCTION__)); | |||
487 | if (!TB || (FB && TB != Header && FB != Header)) | |||
488 | return nullptr; | |||
489 | ||||
490 | // Branches of form "if (!P) ..." cause HexagonInstrInfo::AnalyzeBranch | |||
491 | // to put imm(0), followed by P in the vector Cond. | |||
492 | // If TB is not the header, it means that the "not-taken" path must lead | |||
493 | // to the header. | |||
494 | bool Negated = (Cond.size() > 1) ^ (TB != Header); | |||
495 | unsigned PredReg = Cond[Cond.size()-1].getReg(); | |||
496 | MachineInstr *CondI = MRI->getVRegDef(PredReg); | |||
497 | unsigned CondOpc = CondI->getOpcode(); | |||
498 | ||||
499 | unsigned CmpReg1 = 0, CmpReg2 = 0; | |||
500 | int Mask = 0, ImmValue = 0; | |||
501 | bool AnalyzedCmp = TII->analyzeCompare(CondI, CmpReg1, CmpReg2, | |||
502 | Mask, ImmValue); | |||
503 | if (!AnalyzedCmp) | |||
504 | return nullptr; | |||
505 | ||||
506 | // The comparison operator type determines how we compute the loop | |||
507 | // trip count. | |||
508 | OldInsts.push_back(CondI); | |||
509 | OldInsts.push_back(IVOp); | |||
510 | ||||
511 | // Sadly, the following code gets information based on the position | |||
512 | // of the operands in the compare instruction. This has to be done | |||
513 | // this way, because the comparisons check for a specific relationship | |||
514 | // between the operands (e.g. is-less-than), rather than to find out | |||
515 | // what relationship the operands are in (as on PPC). | |||
516 | Comparison::Kind Cmp; | |||
517 | bool isSwapped = false; | |||
518 | const MachineOperand &Op1 = CondI->getOperand(1); | |||
519 | const MachineOperand &Op2 = CondI->getOperand(2); | |||
520 | const MachineOperand *EndValue = nullptr; | |||
521 | ||||
522 | if (Op1.isReg()) { | |||
523 | if (Op2.isImm() || Op1.getReg() == IVReg) | |||
524 | EndValue = &Op2; | |||
525 | else { | |||
526 | EndValue = &Op1; | |||
527 | isSwapped = true; | |||
528 | } | |||
529 | } | |||
530 | ||||
531 | if (!EndValue) | |||
532 | return nullptr; | |||
533 | ||||
534 | switch (CondOpc) { | |||
535 | case Hexagon::C2_cmpeqi: | |||
536 | case Hexagon::C2_cmpeq: | |||
537 | Cmp = !Negated ? Comparison::EQ : Comparison::NE; | |||
538 | break; | |||
539 | case Hexagon::C2_cmpgtui: | |||
540 | case Hexagon::C2_cmpgtu: | |||
541 | Cmp = !Negated ? Comparison::GTu : Comparison::LEu; | |||
542 | break; | |||
543 | case Hexagon::C2_cmpgti: | |||
544 | case Hexagon::C2_cmpgt: | |||
545 | Cmp = !Negated ? Comparison::GTs : Comparison::LEs; | |||
546 | break; | |||
547 | // Very limited support for byte/halfword compares. | |||
548 | case Hexagon::A4_cmpbeqi: | |||
549 | case Hexagon::A4_cmpheqi: { | |||
550 | if (IVBump != 1) | |||
551 | return nullptr; | |||
552 | ||||
553 | int64_t InitV, EndV; | |||
554 | // Since the comparisons are "ri", the EndValue should be an | |||
555 | // immediate. Check it just in case. | |||
556 | assert(EndValue->isImm() && "Unrecognized latch comparison")((EndValue->isImm() && "Unrecognized latch comparison" ) ? static_cast<void> (0) : __assert_fail ("EndValue->isImm() && \"Unrecognized latch comparison\"" , "/tmp/buildd/llvm-toolchain-snapshot-3.7~svn236768/lib/Target/Hexagon/HexagonHardwareLoops.cpp" , 556, __PRETTY_FUNCTION__)); | |||
557 | EndV = EndValue->getImm(); | |||
558 | // Allow InitialValue to be a register defined with an immediate. | |||
559 | if (InitialValue->isReg()) { | |||
560 | if (!defWithImmediate(InitialValue->getReg())) | |||
561 | return nullptr; | |||
562 | InitV = getImmediate(*InitialValue); | |||
563 | } else { | |||
564 | assert(InitialValue->isImm())((InitialValue->isImm()) ? static_cast<void> (0) : __assert_fail ("InitialValue->isImm()", "/tmp/buildd/llvm-toolchain-snapshot-3.7~svn236768/lib/Target/Hexagon/HexagonHardwareLoops.cpp" , 564, __PRETTY_FUNCTION__)); | |||
565 | InitV = InitialValue->getImm(); | |||
566 | } | |||
567 | if (InitV >= EndV) | |||
568 | return nullptr; | |||
569 | if (CondOpc == Hexagon::A4_cmpbeqi) { | |||
570 | if (!isInt<8>(InitV) || !isInt<8>(EndV)) | |||
571 | return nullptr; | |||
572 | } else { // Hexagon::CMPhEQri_V4 | |||
573 | if (!isInt<16>(InitV) || !isInt<16>(EndV)) | |||
574 | return nullptr; | |||
575 | } | |||
576 | Cmp = !Negated ? Comparison::EQ : Comparison::NE; | |||
577 | break; | |||
578 | } | |||
579 | default: | |||
580 | return nullptr; | |||
581 | } | |||
582 | ||||
583 | if (isSwapped) | |||
584 | Cmp = Comparison::getSwappedComparison(Cmp); | |||
585 | ||||
586 | if (InitialValue->isReg()) { | |||
587 | unsigned R = InitialValue->getReg(); | |||
588 | MachineBasicBlock *DefBB = MRI->getVRegDef(R)->getParent(); | |||
589 | if (!MDT->properlyDominates(DefBB, Header)) | |||
590 | return nullptr; | |||
591 | OldInsts.push_back(MRI->getVRegDef(R)); | |||
592 | } | |||
593 | if (EndValue->isReg()) { | |||
594 | unsigned R = EndValue->getReg(); | |||
595 | MachineBasicBlock *DefBB = MRI->getVRegDef(R)->getParent(); | |||
596 | if (!MDT->properlyDominates(DefBB, Header)) | |||
597 | return nullptr; | |||
598 | } | |||
599 | ||||
600 | return computeCount(L, InitialValue, EndValue, IVReg, IVBump, Cmp); | |||
601 | } | |||
602 | ||||
603 | /// \brief Helper function that returns the expression that represents the | |||
604 | /// number of times a loop iterates. The function takes the operands that | |||
605 | /// represent the loop start value, loop end value, and induction value. | |||
606 | /// Based upon these operands, the function attempts to compute the trip count. | |||
607 | CountValue *HexagonHardwareLoops::computeCount(MachineLoop *Loop, | |||
608 | const MachineOperand *Start, | |||
609 | const MachineOperand *End, | |||
610 | unsigned IVReg, | |||
611 | int64_t IVBump, | |||
612 | Comparison::Kind Cmp) const { | |||
613 | // Cannot handle comparison EQ, i.e. while (A == B). | |||
614 | if (Cmp == Comparison::EQ) | |||
| ||||
615 | return nullptr; | |||
616 | ||||
617 | // Check if either the start or end values are an assignment of an immediate. | |||
618 | // If so, use the immediate value rather than the register. | |||
619 | if (Start->isReg()) { | |||
620 | const MachineInstr *StartValInstr = MRI->getVRegDef(Start->getReg()); | |||
621 | if (StartValInstr && StartValInstr->getOpcode() == Hexagon::A2_tfrsi) | |||
622 | Start = &StartValInstr->getOperand(1); | |||
623 | } | |||
624 | if (End->isReg()) { | |||
625 | const MachineInstr *EndValInstr = MRI->getVRegDef(End->getReg()); | |||
626 | if (EndValInstr && EndValInstr->getOpcode() == Hexagon::A2_tfrsi) | |||
627 | End = &EndValInstr->getOperand(1); | |||
628 | } | |||
629 | ||||
630 | assert (Start->isReg() || Start->isImm())((Start->isReg() || Start->isImm()) ? static_cast<void > (0) : __assert_fail ("Start->isReg() || Start->isImm()" , "/tmp/buildd/llvm-toolchain-snapshot-3.7~svn236768/lib/Target/Hexagon/HexagonHardwareLoops.cpp" , 630, __PRETTY_FUNCTION__)); | |||
631 | assert (End->isReg() || End->isImm())((End->isReg() || End->isImm()) ? static_cast<void> (0) : __assert_fail ("End->isReg() || End->isImm()", "/tmp/buildd/llvm-toolchain-snapshot-3.7~svn236768/lib/Target/Hexagon/HexagonHardwareLoops.cpp" , 631, __PRETTY_FUNCTION__)); | |||
632 | ||||
633 | bool CmpLess = Cmp & Comparison::L; | |||
634 | bool CmpGreater = Cmp & Comparison::G; | |||
635 | bool CmpHasEqual = Cmp & Comparison::EQ; | |||
636 | ||||
637 | // Avoid certain wrap-arounds. This doesn't detect all wrap-arounds. | |||
638 | // If loop executes while iv is "less" with the iv value going down, then | |||
639 | // the iv must wrap. | |||
640 | if (CmpLess && IVBump < 0) | |||
641 | return nullptr; | |||
642 | // If loop executes while iv is "greater" with the iv value going up, then | |||
643 | // the iv must wrap. | |||
644 | if (CmpGreater && IVBump > 0) | |||
645 | return nullptr; | |||
646 | ||||
647 | if (Start->isImm() && End->isImm()) { | |||
648 | // Both, start and end are immediates. | |||
649 | int64_t StartV = Start->getImm(); | |||
650 | int64_t EndV = End->getImm(); | |||
651 | int64_t Dist = EndV - StartV; | |||
652 | if (Dist == 0) | |||
653 | return nullptr; | |||
654 | ||||
655 | bool Exact = (Dist % IVBump) == 0; | |||
| ||||
656 | ||||
657 | if (Cmp == Comparison::NE) { | |||
658 | if (!Exact) | |||
659 | return nullptr; | |||
660 | if ((Dist < 0) ^ (IVBump < 0)) | |||
661 | return nullptr; | |||
662 | } | |||
663 | ||||
664 | // For comparisons that include the final value (i.e. include equality | |||
665 | // with the final value), we need to increase the distance by 1. | |||
666 | if (CmpHasEqual) | |||
667 | Dist = Dist > 0 ? Dist+1 : Dist-1; | |||
668 | ||||
669 | // assert (CmpLess => Dist > 0); | |||
670 | assert ((!CmpLess || Dist > 0) && "Loop should never iterate!")(((!CmpLess || Dist > 0) && "Loop should never iterate!" ) ? static_cast<void> (0) : __assert_fail ("(!CmpLess || Dist > 0) && \"Loop should never iterate!\"" , "/tmp/buildd/llvm-toolchain-snapshot-3.7~svn236768/lib/Target/Hexagon/HexagonHardwareLoops.cpp" , 670, __PRETTY_FUNCTION__)); | |||
671 | // assert (CmpGreater => Dist < 0); | |||
672 | assert ((!CmpGreater || Dist < 0) && "Loop should never iterate!")(((!CmpGreater || Dist < 0) && "Loop should never iterate!" ) ? static_cast<void> (0) : __assert_fail ("(!CmpGreater || Dist < 0) && \"Loop should never iterate!\"" , "/tmp/buildd/llvm-toolchain-snapshot-3.7~svn236768/lib/Target/Hexagon/HexagonHardwareLoops.cpp" , 672, __PRETTY_FUNCTION__)); | |||
673 | ||||
674 | // "Normalized" distance, i.e. with the bump set to +-1. | |||
675 | int64_t Dist1 = (IVBump > 0) ? (Dist + (IVBump-1)) / IVBump | |||
676 | : (-Dist + (-IVBump-1)) / (-IVBump); | |||
677 | assert (Dist1 > 0 && "Fishy thing. Both operands have the same sign.")((Dist1 > 0 && "Fishy thing. Both operands have the same sign." ) ? static_cast<void> (0) : __assert_fail ("Dist1 > 0 && \"Fishy thing. Both operands have the same sign.\"" , "/tmp/buildd/llvm-toolchain-snapshot-3.7~svn236768/lib/Target/Hexagon/HexagonHardwareLoops.cpp" , 677, __PRETTY_FUNCTION__)); | |||
678 | ||||
679 | uint64_t Count = Dist1; | |||
680 | ||||
681 | if (Count > 0xFFFFFFFFULL) | |||
682 | return nullptr; | |||
683 | ||||
684 | return new CountValue(CountValue::CV_Immediate, Count); | |||
685 | } | |||
686 | ||||
687 | // A general case: Start and End are some values, but the actual | |||
688 | // iteration count may not be available. If it is not, insert | |||
689 | // a computation of it into the preheader. | |||
690 | ||||
691 | // If the induction variable bump is not a power of 2, quit. | |||
692 | // Othwerise we'd need a general integer division. | |||
693 | if (!isPowerOf2_64(std::abs(IVBump))) | |||
694 | return nullptr; | |||
695 | ||||
696 | MachineBasicBlock *PH = Loop->getLoopPreheader(); | |||
697 | assert (PH && "Should have a preheader by now")((PH && "Should have a preheader by now") ? static_cast <void> (0) : __assert_fail ("PH && \"Should have a preheader by now\"" , "/tmp/buildd/llvm-toolchain-snapshot-3.7~svn236768/lib/Target/Hexagon/HexagonHardwareLoops.cpp" , 697, __PRETTY_FUNCTION__)); | |||
698 | MachineBasicBlock::iterator InsertPos = PH->getFirstTerminator(); | |||
699 | DebugLoc DL = (InsertPos != PH->end()) ? InsertPos->getDebugLoc() | |||
700 | : DebugLoc(); | |||
701 | ||||
702 | // If Start is an immediate and End is a register, the trip count | |||
703 | // will be "reg - imm". Hexagon's "subtract immediate" instruction | |||
704 | // is actually "reg + -imm". | |||
705 | ||||
706 | // If the loop IV is going downwards, i.e. if the bump is negative, | |||
707 | // then the iteration count (computed as End-Start) will need to be | |||
708 | // negated. To avoid the negation, just swap Start and End. | |||
709 | if (IVBump < 0) { | |||
710 | std::swap(Start, End); | |||
711 | IVBump = -IVBump; | |||
712 | } | |||
713 | // Cmp may now have a wrong direction, e.g. LEs may now be GEs. | |||
714 | // Signedness, and "including equality" are preserved. | |||
715 | ||||
716 | bool RegToImm = Start->isReg() && End->isImm(); // for (reg..imm) | |||
717 | bool RegToReg = Start->isReg() && End->isReg(); // for (reg..reg) | |||
718 | ||||
719 | int64_t StartV = 0, EndV = 0; | |||
720 | if (Start->isImm()) | |||
721 | StartV = Start->getImm(); | |||
722 | if (End->isImm()) | |||
723 | EndV = End->getImm(); | |||
724 | ||||
725 | int64_t AdjV = 0; | |||
726 | // To compute the iteration count, we would need this computation: | |||
727 | // Count = (End - Start + (IVBump-1)) / IVBump | |||
728 | // or, when CmpHasEqual: | |||
729 | // Count = (End - Start + (IVBump-1)+1) / IVBump | |||
730 | // The "IVBump-1" part is the adjustment (AdjV). We can avoid | |||
731 | // generating an instruction specifically to add it if we can adjust | |||
732 | // the immediate values for Start or End. | |||
733 | ||||
734 | if (CmpHasEqual) { | |||
735 | // Need to add 1 to the total iteration count. | |||
736 | if (Start->isImm()) | |||
737 | StartV--; | |||
738 | else if (End->isImm()) | |||
739 | EndV++; | |||
740 | else | |||
741 | AdjV += 1; | |||
742 | } | |||
743 | ||||
744 | if (Cmp != Comparison::NE) { | |||
745 | if (Start->isImm()) | |||
746 | StartV -= (IVBump-1); | |||
747 | else if (End->isImm()) | |||
748 | EndV += (IVBump-1); | |||
749 | else | |||
750 | AdjV += (IVBump-1); | |||
751 | } | |||
752 | ||||
753 | unsigned R = 0, SR = 0; | |||
754 | if (Start->isReg()) { | |||
755 | R = Start->getReg(); | |||
756 | SR = Start->getSubReg(); | |||
757 | } else { | |||
758 | R = End->getReg(); | |||
759 | SR = End->getSubReg(); | |||
760 | } | |||
761 | const TargetRegisterClass *RC = MRI->getRegClass(R); | |||
762 | // Hardware loops cannot handle 64-bit registers. If it's a double | |||
763 | // register, it has to have a subregister. | |||
764 | if (!SR && RC == &Hexagon::DoubleRegsRegClass) | |||
765 | return nullptr; | |||
766 | const TargetRegisterClass *IntRC = &Hexagon::IntRegsRegClass; | |||
767 | ||||
768 | // Compute DistR (register with the distance between Start and End). | |||
769 | unsigned DistR, DistSR; | |||
770 | ||||
771 | // Avoid special case, where the start value is an imm(0). | |||
772 | if (Start->isImm() && StartV == 0) { | |||
773 | DistR = End->getReg(); | |||
774 | DistSR = End->getSubReg(); | |||
775 | } else { | |||
776 | const MCInstrDesc &SubD = RegToReg ? TII->get(Hexagon::A2_sub) : | |||
777 | (RegToImm ? TII->get(Hexagon::A2_subri) : | |||
778 | TII->get(Hexagon::A2_addi)); | |||
779 | unsigned SubR = MRI->createVirtualRegister(IntRC); | |||
780 | MachineInstrBuilder SubIB = | |||
781 | BuildMI(*PH, InsertPos, DL, SubD, SubR); | |||
782 | ||||
783 | if (RegToReg) { | |||
784 | SubIB.addReg(End->getReg(), 0, End->getSubReg()) | |||
785 | .addReg(Start->getReg(), 0, Start->getSubReg()); | |||
786 | } else if (RegToImm) { | |||
787 | SubIB.addImm(EndV) | |||
788 | .addReg(Start->getReg(), 0, Start->getSubReg()); | |||
789 | } else { // ImmToReg | |||
790 | SubIB.addReg(End->getReg(), 0, End->getSubReg()) | |||
791 | .addImm(-StartV); | |||
792 | } | |||
793 | DistR = SubR; | |||
794 | DistSR = 0; | |||
795 | } | |||
796 | ||||
797 | // From DistR, compute AdjR (register with the adjusted distance). | |||
798 | unsigned AdjR, AdjSR; | |||
799 | ||||
800 | if (AdjV == 0) { | |||
801 | AdjR = DistR; | |||
802 | AdjSR = DistSR; | |||
803 | } else { | |||
804 | // Generate CountR = ADD DistR, AdjVal | |||
805 | unsigned AddR = MRI->createVirtualRegister(IntRC); | |||
806 | MCInstrDesc const &AddD = TII->get(Hexagon::A2_addi); | |||
807 | BuildMI(*PH, InsertPos, DL, AddD, AddR) | |||
808 | .addReg(DistR, 0, DistSR) | |||
809 | .addImm(AdjV); | |||
810 | ||||
811 | AdjR = AddR; | |||
812 | AdjSR = 0; | |||
813 | } | |||
814 | ||||
815 | // From AdjR, compute CountR (register with the final count). | |||
816 | unsigned CountR, CountSR; | |||
817 | ||||
818 | if (IVBump == 1) { | |||
819 | CountR = AdjR; | |||
820 | CountSR = AdjSR; | |||
821 | } else { | |||
822 | // The IV bump is a power of two. Log_2(IV bump) is the shift amount. | |||
823 | unsigned Shift = Log2_32(IVBump); | |||
824 | ||||
825 | // Generate NormR = LSR DistR, Shift. | |||
826 | unsigned LsrR = MRI->createVirtualRegister(IntRC); | |||
827 | const MCInstrDesc &LsrD = TII->get(Hexagon::S2_lsr_i_r); | |||
828 | BuildMI(*PH, InsertPos, DL, LsrD, LsrR) | |||
829 | .addReg(AdjR, 0, AdjSR) | |||
830 | .addImm(Shift); | |||
831 | ||||
832 | CountR = LsrR; | |||
833 | CountSR = 0; | |||
834 | } | |||
835 | ||||
836 | return new CountValue(CountValue::CV_Register, CountR, CountSR); | |||
837 | } | |||
838 | ||||
839 | ||||
840 | /// \brief Return true if the operation is invalid within hardware loop. | |||
841 | bool HexagonHardwareLoops::isInvalidLoopOperation( | |||
842 | const MachineInstr *MI) const { | |||
843 | ||||
844 | // call is not allowed because the callee may use a hardware loop | |||
845 | if (MI->getDesc().isCall()) | |||
846 | return true; | |||
847 | ||||
848 | // do not allow nested hardware loops | |||
849 | if (isHardwareLoop(MI)) | |||
850 | return true; | |||
851 | ||||
852 | // check if the instruction defines a hardware loop register | |||
853 | for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) { | |||
854 | const MachineOperand &MO = MI->getOperand(i); | |||
855 | if (!MO.isReg() || !MO.isDef()) | |||
856 | continue; | |||
857 | unsigned R = MO.getReg(); | |||
858 | if (R == Hexagon::LC0 || R == Hexagon::LC1 || | |||
859 | R == Hexagon::SA0 || R == Hexagon::SA1) | |||
860 | return true; | |||
861 | } | |||
862 | return false; | |||
863 | } | |||
864 | ||||
865 | ||||
866 | /// \brief - Return true if the loop contains an instruction that inhibits | |||
867 | /// the use of the hardware loop function. | |||
868 | bool HexagonHardwareLoops::containsInvalidInstruction(MachineLoop *L) const { | |||
869 | const std::vector<MachineBasicBlock *> &Blocks = L->getBlocks(); | |||
870 | for (unsigned i = 0, e = Blocks.size(); i != e; ++i) { | |||
871 | MachineBasicBlock *MBB = Blocks[i]; | |||
872 | for (MachineBasicBlock::iterator | |||
873 | MII = MBB->begin(), E = MBB->end(); MII != E; ++MII) { | |||
874 | const MachineInstr *MI = &*MII; | |||
875 | if (isInvalidLoopOperation(MI)) | |||
876 | return true; | |||
877 | } | |||
878 | } | |||
879 | return false; | |||
880 | } | |||
881 | ||||
882 | ||||
883 | /// \brief Returns true if the instruction is dead. This was essentially | |||
884 | /// copied from DeadMachineInstructionElim::isDead, but with special cases | |||
885 | /// for inline asm, physical registers and instructions with side effects | |||
886 | /// removed. | |||
887 | bool HexagonHardwareLoops::isDead(const MachineInstr *MI, | |||
888 | SmallVectorImpl<MachineInstr *> &DeadPhis) const { | |||
889 | // Examine each operand. | |||
890 | for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) { | |||
891 | const MachineOperand &MO = MI->getOperand(i); | |||
892 | if (!MO.isReg() || !MO.isDef()) | |||
893 | continue; | |||
894 | ||||
895 | unsigned Reg = MO.getReg(); | |||
896 | if (MRI->use_nodbg_empty(Reg)) | |||
897 | continue; | |||
898 | ||||
899 | typedef MachineRegisterInfo::use_nodbg_iterator use_nodbg_iterator; | |||
900 | ||||
901 | // This instruction has users, but if the only user is the phi node for the | |||
902 | // parent block, and the only use of that phi node is this instruction, then | |||
903 | // this instruction is dead: both it (and the phi node) can be removed. | |||
904 | use_nodbg_iterator I = MRI->use_nodbg_begin(Reg); | |||
905 | use_nodbg_iterator End = MRI->use_nodbg_end(); | |||
906 | if (std::next(I) != End || !I->getParent()->isPHI()) | |||
907 | return false; | |||
908 | ||||
909 | MachineInstr *OnePhi = I->getParent(); | |||
910 | for (unsigned j = 0, f = OnePhi->getNumOperands(); j != f; ++j) { | |||
911 | const MachineOperand &OPO = OnePhi->getOperand(j); | |||
912 | if (!OPO.isReg() || !OPO.isDef()) | |||
913 | continue; | |||
914 | ||||
915 | unsigned OPReg = OPO.getReg(); | |||
916 | use_nodbg_iterator nextJ; | |||
917 | for (use_nodbg_iterator J = MRI->use_nodbg_begin(OPReg); | |||
918 | J != End; J = nextJ) { | |||
919 | nextJ = std::next(J); | |||
920 | MachineOperand &Use = *J; | |||
921 | MachineInstr *UseMI = Use.getParent(); | |||
922 | ||||
923 | // If the phi node has a user that is not MI, bail... | |||
924 | if (MI != UseMI) | |||
925 | return false; | |||
926 | } | |||
927 | } | |||
928 | DeadPhis.push_back(OnePhi); | |||
929 | } | |||
930 | ||||
931 | // If there are no defs with uses, the instruction is dead. | |||
932 | return true; | |||
933 | } | |||
934 | ||||
935 | void HexagonHardwareLoops::removeIfDead(MachineInstr *MI) { | |||
936 | // This procedure was essentially copied from DeadMachineInstructionElim. | |||
937 | ||||
938 | SmallVector<MachineInstr*, 1> DeadPhis; | |||
939 | if (isDead(MI, DeadPhis)) { | |||
940 | DEBUG(dbgs() << "HW looping will remove: " << *MI)do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("hwloops")) { dbgs() << "HW looping will remove: " << *MI; } } while (0); | |||
941 | ||||
942 | // It is possible that some DBG_VALUE instructions refer to this | |||
943 | // instruction. Examine each def operand for such references; | |||
944 | // if found, mark the DBG_VALUE as undef (but don't delete it). | |||
945 | for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) { | |||
946 | const MachineOperand &MO = MI->getOperand(i); | |||
947 | if (!MO.isReg() || !MO.isDef()) | |||
948 | continue; | |||
949 | unsigned Reg = MO.getReg(); | |||
950 | MachineRegisterInfo::use_iterator nextI; | |||
951 | for (MachineRegisterInfo::use_iterator I = MRI->use_begin(Reg), | |||
952 | E = MRI->use_end(); I != E; I = nextI) { | |||
953 | nextI = std::next(I); // I is invalidated by the setReg | |||
954 | MachineOperand &Use = *I; | |||
955 | MachineInstr *UseMI = I->getParent(); | |||
956 | if (UseMI == MI) | |||
957 | continue; | |||
958 | if (Use.isDebug()) | |||
959 | UseMI->getOperand(0).setReg(0U); | |||
960 | // This may also be a "instr -> phi -> instr" case which can | |||
961 | // be removed too. | |||
962 | } | |||
963 | } | |||
964 | ||||
965 | MI->eraseFromParent(); | |||
966 | for (unsigned i = 0; i < DeadPhis.size(); ++i) | |||
967 | DeadPhis[i]->eraseFromParent(); | |||
968 | } | |||
969 | } | |||
970 | ||||
971 | /// \brief Check if the loop is a candidate for converting to a hardware | |||
972 | /// loop. If so, then perform the transformation. | |||
973 | /// | |||
974 | /// This function works on innermost loops first. A loop can be converted | |||
975 | /// if it is a counting loop; either a register value or an immediate. | |||
976 | /// | |||
977 | /// The code makes several assumptions about the representation of the loop | |||
978 | /// in llvm. | |||
979 | bool HexagonHardwareLoops::convertToHardwareLoop(MachineLoop *L) { | |||
980 | // This is just for sanity. | |||
981 | assert(L->getHeader() && "Loop without a header?")((L->getHeader() && "Loop without a header?") ? static_cast <void> (0) : __assert_fail ("L->getHeader() && \"Loop without a header?\"" , "/tmp/buildd/llvm-toolchain-snapshot-3.7~svn236768/lib/Target/Hexagon/HexagonHardwareLoops.cpp" , 981, __PRETTY_FUNCTION__)); | |||
982 | ||||
983 | bool Changed = false; | |||
984 | // Process nested loops first. | |||
985 | for (MachineLoop::iterator I = L->begin(), E = L->end(); I != E; ++I) | |||
986 | Changed |= convertToHardwareLoop(*I); | |||
987 | ||||
988 | // If a nested loop has been converted, then we can't convert this loop. | |||
989 | if (Changed) | |||
990 | return Changed; | |||
991 | ||||
992 | #ifndef NDEBUG | |||
993 | // Stop trying after reaching the limit (if any). | |||
994 | int Limit = HWLoopLimit; | |||
995 | if (Limit >= 0) { | |||
996 | if (Counter >= HWLoopLimit) | |||
997 | return false; | |||
998 | Counter++; | |||
999 | } | |||
1000 | #endif | |||
1001 | ||||
1002 | // Does the loop contain any invalid instructions? | |||
1003 | if (containsInvalidInstruction(L)) | |||
1004 | return false; | |||
1005 | ||||
1006 | // Is the induction variable bump feeding the latch condition? | |||
1007 | if (!fixupInductionVariable(L)) | |||
1008 | return false; | |||
1009 | ||||
1010 | MachineBasicBlock *LastMBB = L->getExitingBlock(); | |||
1011 | // Don't generate hw loop if the loop has more than one exit. | |||
1012 | if (!LastMBB) | |||
1013 | return false; | |||
1014 | ||||
1015 | MachineBasicBlock::iterator LastI = LastMBB->getFirstTerminator(); | |||
1016 | if (LastI == LastMBB->end()) | |||
1017 | return false; | |||
1018 | ||||
1019 | // Ensure the loop has a preheader: the loop instruction will be | |||
1020 | // placed there. | |||
1021 | bool NewPreheader = false; | |||
1022 | MachineBasicBlock *Preheader = L->getLoopPreheader(); | |||
1023 | if (!Preheader) { | |||
1024 | Preheader = createPreheaderForLoop(L); | |||
1025 | if (!Preheader) | |||
1026 | return false; | |||
1027 | NewPreheader = true; | |||
1028 | } | |||
1029 | MachineBasicBlock::iterator InsertPos = Preheader->getFirstTerminator(); | |||
1030 | ||||
1031 | SmallVector<MachineInstr*, 2> OldInsts; | |||
1032 | // Are we able to determine the trip count for the loop? | |||
1033 | CountValue *TripCount = getLoopTripCount(L, OldInsts); | |||
1034 | if (!TripCount) | |||
1035 | return false; | |||
1036 | ||||
1037 | // Is the trip count available in the preheader? | |||
1038 | if (TripCount->isReg()) { | |||
1039 | // There will be a use of the register inserted into the preheader, | |||
1040 | // so make sure that the register is actually defined at that point. | |||
1041 | MachineInstr *TCDef = MRI->getVRegDef(TripCount->getReg()); | |||
1042 | MachineBasicBlock *BBDef = TCDef->getParent(); | |||
1043 | if (!NewPreheader) { | |||
1044 | if (!MDT->dominates(BBDef, Preheader)) | |||
1045 | return false; | |||
1046 | } else { | |||
1047 | // If we have just created a preheader, the dominator tree won't be | |||
1048 | // aware of it. Check if the definition of the register dominates | |||
1049 | // the header, but is not the header itself. | |||
1050 | if (!MDT->properlyDominates(BBDef, L->getHeader())) | |||
1051 | return false; | |||
1052 | } | |||
1053 | } | |||
1054 | ||||
1055 | // Determine the loop start. | |||
1056 | MachineBasicBlock *LoopStart = L->getTopBlock(); | |||
1057 | if (L->getLoopLatch() != LastMBB) { | |||
1058 | // When the exit and latch are not the same, use the latch block as the | |||
1059 | // start. | |||
1060 | // The loop start address is used only after the 1st iteration, and the | |||
1061 | // loop latch may contains instrs. that need to be executed after the | |||
1062 | // first iteration. | |||
1063 | LoopStart = L->getLoopLatch(); | |||
1064 | // Make sure the latch is a successor of the exit, otherwise it won't work. | |||
1065 | if (!LastMBB->isSuccessor(LoopStart)) | |||
1066 | return false; | |||
1067 | } | |||
1068 | ||||
1069 | // Convert the loop to a hardware loop. | |||
1070 | DEBUG(dbgs() << "Change to hardware loop at "; L->dump())do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("hwloops")) { dbgs() << "Change to hardware loop at "; L->dump(); } } while (0); | |||
1071 | DebugLoc DL; | |||
1072 | if (InsertPos != Preheader->end()) | |||
1073 | DL = InsertPos->getDebugLoc(); | |||
1074 | ||||
1075 | if (TripCount->isReg()) { | |||
1076 | // Create a copy of the loop count register. | |||
1077 | unsigned CountReg = MRI->createVirtualRegister(&Hexagon::IntRegsRegClass); | |||
1078 | BuildMI(*Preheader, InsertPos, DL, TII->get(TargetOpcode::COPY), CountReg) | |||
1079 | .addReg(TripCount->getReg(), 0, TripCount->getSubReg()); | |||
1080 | // Add the Loop instruction to the beginning of the loop. | |||
1081 | BuildMI(*Preheader, InsertPos, DL, TII->get(Hexagon::J2_loop0r)) | |||
1082 | .addMBB(LoopStart) | |||
1083 | .addReg(CountReg); | |||
1084 | } else { | |||
1085 | assert(TripCount->isImm() && "Expecting immediate value for trip count")((TripCount->isImm() && "Expecting immediate value for trip count" ) ? static_cast<void> (0) : __assert_fail ("TripCount->isImm() && \"Expecting immediate value for trip count\"" , "/tmp/buildd/llvm-toolchain-snapshot-3.7~svn236768/lib/Target/Hexagon/HexagonHardwareLoops.cpp" , 1085, __PRETTY_FUNCTION__)); | |||
1086 | // Add the Loop immediate instruction to the beginning of the loop, | |||
1087 | // if the immediate fits in the instructions. Otherwise, we need to | |||
1088 | // create a new virtual register. | |||
1089 | int64_t CountImm = TripCount->getImm(); | |||
1090 | if (!TII->isValidOffset(Hexagon::J2_loop0i, CountImm)) { | |||
1091 | unsigned CountReg = MRI->createVirtualRegister(&Hexagon::IntRegsRegClass); | |||
1092 | BuildMI(*Preheader, InsertPos, DL, TII->get(Hexagon::A2_tfrsi), CountReg) | |||
1093 | .addImm(CountImm); | |||
1094 | BuildMI(*Preheader, InsertPos, DL, TII->get(Hexagon::J2_loop0r)) | |||
1095 | .addMBB(LoopStart).addReg(CountReg); | |||
1096 | } else | |||
1097 | BuildMI(*Preheader, InsertPos, DL, TII->get(Hexagon::J2_loop0i)) | |||
1098 | .addMBB(LoopStart).addImm(CountImm); | |||
1099 | } | |||
1100 | ||||
1101 | // Make sure the loop start always has a reference in the CFG. We need | |||
1102 | // to create a BlockAddress operand to get this mechanism to work both the | |||
1103 | // MachineBasicBlock and BasicBlock objects need the flag set. | |||
1104 | LoopStart->setHasAddressTaken(); | |||
1105 | // This line is needed to set the hasAddressTaken flag on the BasicBlock | |||
1106 | // object. | |||
1107 | BlockAddress::get(const_cast<BasicBlock *>(LoopStart->getBasicBlock())); | |||
1108 | ||||
1109 | // Replace the loop branch with an endloop instruction. | |||
1110 | DebugLoc LastIDL = LastI->getDebugLoc(); | |||
1111 | BuildMI(*LastMBB, LastI, LastIDL, | |||
1112 | TII->get(Hexagon::ENDLOOP0)).addMBB(LoopStart); | |||
1113 | ||||
1114 | // The loop ends with either: | |||
1115 | // - a conditional branch followed by an unconditional branch, or | |||
1116 | // - a conditional branch to the loop start. | |||
1117 | if (LastI->getOpcode() == Hexagon::J2_jumpt || | |||
1118 | LastI->getOpcode() == Hexagon::J2_jumpf) { | |||
1119 | // Delete one and change/add an uncond. branch to out of the loop. | |||
1120 | MachineBasicBlock *BranchTarget = LastI->getOperand(1).getMBB(); | |||
1121 | LastI = LastMBB->erase(LastI); | |||
1122 | if (!L->contains(BranchTarget)) { | |||
1123 | if (LastI != LastMBB->end()) | |||
1124 | LastI = LastMBB->erase(LastI); | |||
1125 | SmallVector<MachineOperand, 0> Cond; | |||
1126 | TII->InsertBranch(*LastMBB, BranchTarget, nullptr, Cond, LastIDL); | |||
1127 | } | |||
1128 | } else { | |||
1129 | // Conditional branch to loop start; just delete it. | |||
1130 | LastMBB->erase(LastI); | |||
1131 | } | |||
1132 | delete TripCount; | |||
1133 | ||||
1134 | // The induction operation and the comparison may now be | |||
1135 | // unneeded. If these are unneeded, then remove them. | |||
1136 | for (unsigned i = 0; i < OldInsts.size(); ++i) | |||
1137 | removeIfDead(OldInsts[i]); | |||
1138 | ||||
1139 | ++NumHWLoops; | |||
1140 | return true; | |||
1141 | } | |||
1142 | ||||
1143 | ||||
1144 | bool HexagonHardwareLoops::orderBumpCompare(MachineInstr *BumpI, | |||
1145 | MachineInstr *CmpI) { | |||
1146 | assert (BumpI != CmpI && "Bump and compare in the same instruction?")((BumpI != CmpI && "Bump and compare in the same instruction?" ) ? static_cast<void> (0) : __assert_fail ("BumpI != CmpI && \"Bump and compare in the same instruction?\"" , "/tmp/buildd/llvm-toolchain-snapshot-3.7~svn236768/lib/Target/Hexagon/HexagonHardwareLoops.cpp" , 1146, __PRETTY_FUNCTION__)); | |||
1147 | ||||
1148 | MachineBasicBlock *BB = BumpI->getParent(); | |||
1149 | if (CmpI->getParent() != BB) | |||
1150 | return false; | |||
1151 | ||||
1152 | typedef MachineBasicBlock::instr_iterator instr_iterator; | |||
1153 | // Check if things are in order to begin with. | |||
1154 | for (instr_iterator I = BumpI, E = BB->instr_end(); I != E; ++I) | |||
1155 | if (&*I == CmpI) | |||
1156 | return true; | |||
1157 | ||||
1158 | // Out of order. | |||
1159 | unsigned PredR = CmpI->getOperand(0).getReg(); | |||
1160 | bool FoundBump = false; | |||
1161 | instr_iterator CmpIt = CmpI, NextIt = std::next(CmpIt); | |||
1162 | for (instr_iterator I = NextIt, E = BB->instr_end(); I != E; ++I) { | |||
1163 | MachineInstr *In = &*I; | |||
1164 | for (unsigned i = 0, n = In->getNumOperands(); i < n; ++i) { | |||
1165 | MachineOperand &MO = In->getOperand(i); | |||
1166 | if (MO.isReg() && MO.isUse()) { | |||
1167 | if (MO.getReg() == PredR) // Found an intervening use of PredR. | |||
1168 | return false; | |||
1169 | } | |||
1170 | } | |||
1171 | ||||
1172 | if (In == BumpI) { | |||
1173 | instr_iterator After = BumpI; | |||
1174 | instr_iterator From = CmpI; | |||
1175 | BB->splice(std::next(After), BB, From); | |||
1176 | FoundBump = true; | |||
1177 | break; | |||
1178 | } | |||
1179 | } | |||
1180 | assert (FoundBump && "Cannot determine instruction order")((FoundBump && "Cannot determine instruction order") ? static_cast<void> (0) : __assert_fail ("FoundBump && \"Cannot determine instruction order\"" , "/tmp/buildd/llvm-toolchain-snapshot-3.7~svn236768/lib/Target/Hexagon/HexagonHardwareLoops.cpp" , 1180, __PRETTY_FUNCTION__)); | |||
1181 | return FoundBump; | |||
1182 | } | |||
1183 | ||||
1184 | ||||
1185 | MachineInstr *HexagonHardwareLoops::defWithImmediate(unsigned R) { | |||
1186 | MachineInstr *DI = MRI->getVRegDef(R); | |||
1187 | unsigned DOpc = DI->getOpcode(); | |||
1188 | switch (DOpc) { | |||
1189 | case Hexagon::A2_tfrsi: | |||
1190 | case Hexagon::A2_tfrpi: | |||
1191 | case Hexagon::CONST32_Int_Real: | |||
1192 | case Hexagon::CONST64_Int_Real: | |||
1193 | return DI; | |||
1194 | } | |||
1195 | return nullptr; | |||
1196 | } | |||
1197 | ||||
1198 | ||||
1199 | int64_t HexagonHardwareLoops::getImmediate(MachineOperand &MO) { | |||
1200 | if (MO.isImm()) | |||
1201 | return MO.getImm(); | |||
1202 | assert(MO.isReg())((MO.isReg()) ? static_cast<void> (0) : __assert_fail ( "MO.isReg()", "/tmp/buildd/llvm-toolchain-snapshot-3.7~svn236768/lib/Target/Hexagon/HexagonHardwareLoops.cpp" , 1202, __PRETTY_FUNCTION__)); | |||
1203 | unsigned R = MO.getReg(); | |||
1204 | MachineInstr *DI = defWithImmediate(R); | |||
1205 | assert(DI && "Need an immediate operand")((DI && "Need an immediate operand") ? static_cast< void> (0) : __assert_fail ("DI && \"Need an immediate operand\"" , "/tmp/buildd/llvm-toolchain-snapshot-3.7~svn236768/lib/Target/Hexagon/HexagonHardwareLoops.cpp" , 1205, __PRETTY_FUNCTION__)); | |||
1206 | // All currently supported "define-with-immediate" instructions have the | |||
1207 | // actual immediate value in the operand(1). | |||
1208 | int64_t v = DI->getOperand(1).getImm(); | |||
1209 | return v; | |||
1210 | } | |||
1211 | ||||
1212 | ||||
1213 | void HexagonHardwareLoops::setImmediate(MachineOperand &MO, int64_t Val) { | |||
1214 | if (MO.isImm()) { | |||
1215 | MO.setImm(Val); | |||
1216 | return; | |||
1217 | } | |||
1218 | ||||
1219 | assert(MO.isReg())((MO.isReg()) ? static_cast<void> (0) : __assert_fail ( "MO.isReg()", "/tmp/buildd/llvm-toolchain-snapshot-3.7~svn236768/lib/Target/Hexagon/HexagonHardwareLoops.cpp" , 1219, __PRETTY_FUNCTION__)); | |||
1220 | unsigned R = MO.getReg(); | |||
1221 | MachineInstr *DI = defWithImmediate(R); | |||
1222 | if (MRI->hasOneNonDBGUse(R)) { | |||
1223 | // If R has only one use, then just change its defining instruction to | |||
1224 | // the new immediate value. | |||
1225 | DI->getOperand(1).setImm(Val); | |||
1226 | return; | |||
1227 | } | |||
1228 | ||||
1229 | const TargetRegisterClass *RC = MRI->getRegClass(R); | |||
1230 | unsigned NewR = MRI->createVirtualRegister(RC); | |||
1231 | MachineBasicBlock &B = *DI->getParent(); | |||
1232 | DebugLoc DL = DI->getDebugLoc(); | |||
1233 | BuildMI(B, DI, DL, TII->get(DI->getOpcode()), NewR) | |||
1234 | .addImm(Val); | |||
1235 | MO.setReg(NewR); | |||
1236 | } | |||
1237 | ||||
1238 | ||||
1239 | bool HexagonHardwareLoops::fixupInductionVariable(MachineLoop *L) { | |||
1240 | MachineBasicBlock *Header = L->getHeader(); | |||
1241 | MachineBasicBlock *Preheader = L->getLoopPreheader(); | |||
1242 | MachineBasicBlock *Latch = L->getLoopLatch(); | |||
1243 | ||||
1244 | if (!Header || !Preheader || !Latch) | |||
1245 | return false; | |||
1246 | ||||
1247 | // These data structures follow the same concept as the corresponding | |||
1248 | // ones in findInductionRegister (where some comments are). | |||
1249 | typedef std::pair<unsigned,int64_t> RegisterBump; | |||
1250 | typedef std::pair<unsigned,RegisterBump> RegisterInduction; | |||
1251 | typedef std::set<RegisterInduction> RegisterInductionSet; | |||
1252 | ||||
1253 | // Register candidates for induction variables, with their associated bumps. | |||
1254 | RegisterInductionSet IndRegs; | |||
1255 | ||||
1256 | // Look for induction patterns: | |||
1257 | // vreg1 = PHI ..., [ latch, vreg2 ] | |||
1258 | // vreg2 = ADD vreg1, imm | |||
1259 | typedef MachineBasicBlock::instr_iterator instr_iterator; | |||
1260 | for (instr_iterator I = Header->instr_begin(), E = Header->instr_end(); | |||
1261 | I != E && I->isPHI(); ++I) { | |||
1262 | MachineInstr *Phi = &*I; | |||
1263 | ||||
1264 | // Have a PHI instruction. | |||
1265 | for (unsigned i = 1, n = Phi->getNumOperands(); i < n; i += 2) { | |||
1266 | if (Phi->getOperand(i+1).getMBB() != Latch) | |||
1267 | continue; | |||
1268 | ||||
1269 | unsigned PhiReg = Phi->getOperand(i).getReg(); | |||
1270 | MachineInstr *DI = MRI->getVRegDef(PhiReg); | |||
1271 | unsigned UpdOpc = DI->getOpcode(); | |||
1272 | bool isAdd = (UpdOpc == Hexagon::A2_addi); | |||
1273 | ||||
1274 | if (isAdd) { | |||
1275 | // If the register operand to the add/sub is the PHI we are looking | |||
1276 | // at, this meets the induction pattern. | |||
1277 | unsigned IndReg = DI->getOperand(1).getReg(); | |||
1278 | if (MRI->getVRegDef(IndReg) == Phi) { | |||
1279 | unsigned UpdReg = DI->getOperand(0).getReg(); | |||
1280 | int64_t V = DI->getOperand(2).getImm(); | |||
1281 | IndRegs.insert(std::make_pair(UpdReg, std::make_pair(IndReg, V))); | |||
1282 | } | |||
1283 | } | |||
1284 | } // for (i) | |||
1285 | } // for (instr) | |||
1286 | ||||
1287 | if (IndRegs.empty()) | |||
1288 | return false; | |||
1289 | ||||
1290 | MachineBasicBlock *TB = nullptr, *FB = nullptr; | |||
1291 | SmallVector<MachineOperand,2> Cond; | |||
1292 | // AnalyzeBranch returns true if it fails to analyze branch. | |||
1293 | bool NotAnalyzed = TII->AnalyzeBranch(*Latch, TB, FB, Cond, false); | |||
1294 | if (NotAnalyzed) | |||
1295 | return false; | |||
1296 | ||||
1297 | // Check if the latch branch is unconditional. | |||
1298 | if (Cond.empty()) | |||
1299 | return false; | |||
1300 | ||||
1301 | if (TB != Header && FB != Header) | |||
1302 | // The latch does not go back to the header. Not a latch we know and love. | |||
1303 | return false; | |||
1304 | ||||
1305 | // Expecting a predicate register as a condition. It won't be a hardware | |||
1306 | // predicate register at this point yet, just a vreg. | |||
1307 | // HexagonInstrInfo::AnalyzeBranch for negated branches inserts imm(0) | |||
1308 | // into Cond, followed by the predicate register. For non-negated branches | |||
1309 | // it's just the register. | |||
1310 | unsigned CSz = Cond.size(); | |||
1311 | if (CSz != 1 && CSz != 2) | |||
1312 | return false; | |||
1313 | ||||
1314 | unsigned P = Cond[CSz-1].getReg(); | |||
1315 | MachineInstr *PredDef = MRI->getVRegDef(P); | |||
1316 | ||||
1317 | if (!PredDef->isCompare()) | |||
1318 | return false; | |||
1319 | ||||
1320 | SmallSet<unsigned,2> CmpRegs; | |||
1321 | MachineOperand *CmpImmOp = nullptr; | |||
1322 | ||||
1323 | // Go over all operands to the compare and look for immediate and register | |||
1324 | // operands. Assume that if the compare has a single register use and a | |||
1325 | // single immediate operand, then the register is being compared with the | |||
1326 | // immediate value. | |||
1327 | for (unsigned i = 0, n = PredDef->getNumOperands(); i < n; ++i) { | |||
1328 | MachineOperand &MO = PredDef->getOperand(i); | |||
1329 | if (MO.isReg()) { | |||
1330 | // Skip all implicit references. In one case there was: | |||
1331 | // %vreg140<def> = FCMPUGT32_rr %vreg138, %vreg139, %USR<imp-use> | |||
1332 | if (MO.isImplicit()) | |||
1333 | continue; | |||
1334 | if (MO.isUse()) { | |||
1335 | unsigned R = MO.getReg(); | |||
1336 | if (!defWithImmediate(R)) { | |||
1337 | CmpRegs.insert(MO.getReg()); | |||
1338 | continue; | |||
1339 | } | |||
1340 | // Consider the register to be the "immediate" operand. | |||
1341 | if (CmpImmOp) | |||
1342 | return false; | |||
1343 | CmpImmOp = &MO; | |||
1344 | } | |||
1345 | } else if (MO.isImm()) { | |||
1346 | if (CmpImmOp) // A second immediate argument? Confusing. Bail out. | |||
1347 | return false; | |||
1348 | CmpImmOp = &MO; | |||
1349 | } | |||
1350 | } | |||
1351 | ||||
1352 | if (CmpRegs.empty()) | |||
1353 | return false; | |||
1354 | ||||
1355 | // Check if the compared register follows the order we want. Fix if needed. | |||
1356 | for (RegisterInductionSet::iterator I = IndRegs.begin(), E = IndRegs.end(); | |||
1357 | I != E; ++I) { | |||
1358 | // This is a success. If the register used in the comparison is one that | |||
1359 | // we have identified as a bumped (updated) induction register, there is | |||
1360 | // nothing to do. | |||
1361 | if (CmpRegs.count(I->first)) | |||
1362 | return true; | |||
1363 | ||||
1364 | // Otherwise, if the register being compared comes out of a PHI node, | |||
1365 | // and has been recognized as following the induction pattern, and is | |||
1366 | // compared against an immediate, we can fix it. | |||
1367 | const RegisterBump &RB = I->second; | |||
1368 | if (CmpRegs.count(RB.first)) { | |||
1369 | if (!CmpImmOp) | |||
1370 | return false; | |||
1371 | ||||
1372 | int64_t CmpImm = getImmediate(*CmpImmOp); | |||
1373 | int64_t V = RB.second; | |||
1374 | if (V > 0 && CmpImm+V < CmpImm) // Overflow (64-bit). | |||
1375 | return false; | |||
1376 | if (V < 0 && CmpImm+V > CmpImm) // Overflow (64-bit). | |||
1377 | return false; | |||
1378 | CmpImm += V; | |||
1379 | // Some forms of cmp-immediate allow u9 and s10. Assume the worst case | |||
1380 | // scenario, i.e. an 8-bit value. | |||
1381 | if (CmpImmOp->isImm() && !isInt<8>(CmpImm)) | |||
1382 | return false; | |||
1383 | ||||
1384 | // Make sure that the compare happens after the bump. Otherwise, | |||
1385 | // after the fixup, the compare would use a yet-undefined register. | |||
1386 | MachineInstr *BumpI = MRI->getVRegDef(I->first); | |||
1387 | bool Order = orderBumpCompare(BumpI, PredDef); | |||
1388 | if (!Order) | |||
1389 | return false; | |||
1390 | ||||
1391 | // Finally, fix the compare instruction. | |||
1392 | setImmediate(*CmpImmOp, CmpImm); | |||
1393 | for (unsigned i = 0, n = PredDef->getNumOperands(); i < n; ++i) { | |||
1394 | MachineOperand &MO = PredDef->getOperand(i); | |||
1395 | if (MO.isReg() && MO.getReg() == RB.first) { | |||
1396 | MO.setReg(I->first); | |||
1397 | return true; | |||
1398 | } | |||
1399 | } | |||
1400 | } | |||
1401 | } | |||
1402 | ||||
1403 | return false; | |||
1404 | } | |||
1405 | ||||
1406 | ||||
1407 | /// \brief Create a preheader for a given loop. | |||
1408 | MachineBasicBlock *HexagonHardwareLoops::createPreheaderForLoop( | |||
1409 | MachineLoop *L) { | |||
1410 | if (MachineBasicBlock *TmpPH = L->getLoopPreheader()) | |||
1411 | return TmpPH; | |||
1412 | ||||
1413 | MachineBasicBlock *Header = L->getHeader(); | |||
1414 | MachineBasicBlock *Latch = L->getLoopLatch(); | |||
1415 | MachineFunction *MF = Header->getParent(); | |||
1416 | DebugLoc DL; | |||
1417 | ||||
1418 | if (!Latch || Header->hasAddressTaken()) | |||
1419 | return nullptr; | |||
1420 | ||||
1421 | typedef MachineBasicBlock::instr_iterator instr_iterator; | |||
1422 | ||||
1423 | // Verify that all existing predecessors have analyzable branches | |||
1424 | // (or no branches at all). | |||
1425 | typedef std::vector<MachineBasicBlock*> MBBVector; | |||
1426 | MBBVector Preds(Header->pred_begin(), Header->pred_end()); | |||
1427 | SmallVector<MachineOperand,2> Tmp1; | |||
1428 | MachineBasicBlock *TB = nullptr, *FB = nullptr; | |||
1429 | ||||
1430 | if (TII->AnalyzeBranch(*Latch, TB, FB, Tmp1, false)) | |||
1431 | return nullptr; | |||
1432 | ||||
1433 | for (MBBVector::iterator I = Preds.begin(), E = Preds.end(); I != E; ++I) { | |||
1434 | MachineBasicBlock *PB = *I; | |||
1435 | if (PB != Latch) { | |||
1436 | bool NotAnalyzed = TII->AnalyzeBranch(*PB, TB, FB, Tmp1, false); | |||
1437 | if (NotAnalyzed) | |||
1438 | return nullptr; | |||
1439 | } | |||
1440 | } | |||
1441 | ||||
1442 | MachineBasicBlock *NewPH = MF->CreateMachineBasicBlock(); | |||
1443 | MF->insert(Header, NewPH); | |||
1444 | ||||
1445 | if (Header->pred_size() > 2) { | |||
1446 | // Ensure that the header has only two predecessors: the preheader and | |||
1447 | // the loop latch. Any additional predecessors of the header should | |||
1448 | // join at the newly created preheader. Inspect all PHI nodes from the | |||
1449 | // header and create appropriate corresponding PHI nodes in the preheader. | |||
1450 | ||||
1451 | for (instr_iterator I = Header->instr_begin(), E = Header->instr_end(); | |||
1452 | I != E && I->isPHI(); ++I) { | |||
1453 | MachineInstr *PN = &*I; | |||
1454 | ||||
1455 | const MCInstrDesc &PD = TII->get(TargetOpcode::PHI); | |||
1456 | MachineInstr *NewPN = MF->CreateMachineInstr(PD, DL); | |||
1457 | NewPH->insert(NewPH->end(), NewPN); | |||
1458 | ||||
1459 | unsigned PR = PN->getOperand(0).getReg(); | |||
1460 | const TargetRegisterClass *RC = MRI->getRegClass(PR); | |||
1461 | unsigned NewPR = MRI->createVirtualRegister(RC); | |||
1462 | NewPN->addOperand(MachineOperand::CreateReg(NewPR, true)); | |||
1463 | ||||
1464 | // Copy all non-latch operands of a header's PHI node to the newly | |||
1465 | // created PHI node in the preheader. | |||
1466 | for (unsigned i = 1, n = PN->getNumOperands(); i < n; i += 2) { | |||
1467 | unsigned PredR = PN->getOperand(i).getReg(); | |||
1468 | MachineBasicBlock *PredB = PN->getOperand(i+1).getMBB(); | |||
1469 | if (PredB == Latch) | |||
1470 | continue; | |||
1471 | ||||
1472 | NewPN->addOperand(MachineOperand::CreateReg(PredR, false)); | |||
1473 | NewPN->addOperand(MachineOperand::CreateMBB(PredB)); | |||
1474 | } | |||
1475 | ||||
1476 | // Remove copied operands from the old PHI node and add the value | |||
1477 | // coming from the preheader's PHI. | |||
1478 | for (int i = PN->getNumOperands()-2; i > 0; i -= 2) { | |||
1479 | MachineBasicBlock *PredB = PN->getOperand(i+1).getMBB(); | |||
1480 | if (PredB != Latch) { | |||
1481 | PN->RemoveOperand(i+1); | |||
1482 | PN->RemoveOperand(i); | |||
1483 | } | |||
1484 | } | |||
1485 | PN->addOperand(MachineOperand::CreateReg(NewPR, false)); | |||
1486 | PN->addOperand(MachineOperand::CreateMBB(NewPH)); | |||
1487 | } | |||
1488 | ||||
1489 | } else { | |||
1490 | assert(Header->pred_size() == 2)((Header->pred_size() == 2) ? static_cast<void> (0) : __assert_fail ("Header->pred_size() == 2", "/tmp/buildd/llvm-toolchain-snapshot-3.7~svn236768/lib/Target/Hexagon/HexagonHardwareLoops.cpp" , 1490, __PRETTY_FUNCTION__)); | |||
1491 | ||||
1492 | // The header has only two predecessors, but the non-latch predecessor | |||
1493 | // is not a preheader (e.g. it has other successors, etc.) | |||
1494 | // In such a case we don't need any extra PHI nodes in the new preheader, | |||
1495 | // all we need is to adjust existing PHIs in the header to now refer to | |||
1496 | // the new preheader. | |||
1497 | for (instr_iterator I = Header->instr_begin(), E = Header->instr_end(); | |||
1498 | I != E && I->isPHI(); ++I) { | |||
1499 | MachineInstr *PN = &*I; | |||
1500 | for (unsigned i = 1, n = PN->getNumOperands(); i < n; i += 2) { | |||
1501 | MachineOperand &MO = PN->getOperand(i+1); | |||
1502 | if (MO.getMBB() != Latch) | |||
1503 | MO.setMBB(NewPH); | |||
1504 | } | |||
1505 | } | |||
1506 | } | |||
1507 | ||||
1508 | // "Reroute" the CFG edges to link in the new preheader. | |||
1509 | // If any of the predecessors falls through to the header, insert a branch | |||
1510 | // to the new preheader in that place. | |||
1511 | SmallVector<MachineOperand,1> Tmp2; | |||
1512 | SmallVector<MachineOperand,1> EmptyCond; | |||
1513 | ||||
1514 | TB = FB = nullptr; | |||
1515 | ||||
1516 | for (MBBVector::iterator I = Preds.begin(), E = Preds.end(); I != E; ++I) { | |||
1517 | MachineBasicBlock *PB = *I; | |||
1518 | if (PB != Latch) { | |||
1519 | Tmp2.clear(); | |||
1520 | bool NotAnalyzed = TII->AnalyzeBranch(*PB, TB, FB, Tmp2, false); | |||
1521 | (void)NotAnalyzed; // suppress compiler warning | |||
1522 | assert (!NotAnalyzed && "Should be analyzable!")((!NotAnalyzed && "Should be analyzable!") ? static_cast <void> (0) : __assert_fail ("!NotAnalyzed && \"Should be analyzable!\"" , "/tmp/buildd/llvm-toolchain-snapshot-3.7~svn236768/lib/Target/Hexagon/HexagonHardwareLoops.cpp" , 1522, __PRETTY_FUNCTION__)); | |||
1523 | if (TB != Header && (Tmp2.empty() || FB != Header)) | |||
1524 | TII->InsertBranch(*PB, NewPH, nullptr, EmptyCond, DL); | |||
1525 | PB->ReplaceUsesOfBlockWith(Header, NewPH); | |||
1526 | } | |||
1527 | } | |||
1528 | ||||
1529 | // It can happen that the latch block will fall through into the header. | |||
1530 | // Insert an unconditional branch to the header. | |||
1531 | TB = FB = nullptr; | |||
1532 | bool LatchNotAnalyzed = TII->AnalyzeBranch(*Latch, TB, FB, Tmp2, false); | |||
1533 | (void)LatchNotAnalyzed; // suppress compiler warning | |||
1534 | assert (!LatchNotAnalyzed && "Should be analyzable!")((!LatchNotAnalyzed && "Should be analyzable!") ? static_cast <void> (0) : __assert_fail ("!LatchNotAnalyzed && \"Should be analyzable!\"" , "/tmp/buildd/llvm-toolchain-snapshot-3.7~svn236768/lib/Target/Hexagon/HexagonHardwareLoops.cpp" , 1534, __PRETTY_FUNCTION__)); | |||
1535 | if (!TB && !FB) | |||
1536 | TII->InsertBranch(*Latch, Header, nullptr, EmptyCond, DL); | |||
1537 | ||||
1538 | // Finally, the branch from the preheader to the header. | |||
1539 | TII->InsertBranch(*NewPH, Header, nullptr, EmptyCond, DL); | |||
1540 | NewPH->addSuccessor(Header); | |||
1541 | ||||
1542 | return NewPH; | |||
1543 | } |