Bug Summary

File:lib/Target/Hexagon/HexagonHardwareLoops.cpp
Location:line 655, column 24
Description:Division by zero

Annotated Source Code

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
47using namespace llvm;
48
49#define DEBUG_TYPE"hwloops" "hwloops"
50
51#ifndef NDEBUG
52static cl::opt<int> HWLoopLimit("max-hwloop", cl::Hidden, cl::init(-1));
53#endif
54
55STATISTIC(NumHWLoops, "Number of loops converted to hardware loops")static llvm::Statistic NumHWLoops = { "hwloops", "Number of loops converted to hardware loops"
, 0, 0 }
;
56
57namespace llvm {
58 void initializeHexagonHardwareLoopsPass(PassRegistry&);
59}
60
61namespace {
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
274INITIALIZE_PASS_BEGIN(HexagonHardwareLoops, "hwloops",static void* initializeHexagonHardwareLoopsPassOnce(PassRegistry
&Registry) {
275 "Hexagon Hardware Loops", false, false)static void* initializeHexagonHardwareLoopsPassOnce(PassRegistry
&Registry) {
276INITIALIZE_PASS_DEPENDENCY(MachineDominatorTree)initializeMachineDominatorTreePass(Registry);
277INITIALIZE_PASS_DEPENDENCY(MachineLoopInfo)initializeMachineLoopInfoPass(Registry);
278INITIALIZE_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.
283static bool isHardwareLoop(const MachineInstr *MI) {
284 return MI->getOpcode() == Hexagon::J2_loop0r ||
285 MI->getOpcode() == Hexagon::J2_loop0i;
286}
287
288FunctionPass *llvm::createHexagonHardwareLoops() {
289 return new HexagonHardwareLoops();
290}
291
292
293bool 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
314bool 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.
425CountValue *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.
607CountValue *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)
1
Assuming 'Cmp' is not equal to EQ
2
Taking false branch
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()) {
3
Taking false branch
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()) {
4
Taking false branch
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)
5
Assuming 'IVBump' is >= 0
6
Taking false branch
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)
7
Assuming 'IVBump' is <= 0
8
Taking false branch
645 return nullptr;
646
647 if (Start->isImm() && End->isImm()) {
9
Taking true branch
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)
10
Assuming 'Dist' is not equal to 0
11
Taking false branch
653 return nullptr;
654
655 bool Exact = (Dist % IVBump) == 0;
12
Division by zero
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.
841bool 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.
868bool 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.
887bool 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
935void 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.
979bool 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
1144bool 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
1185MachineInstr *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
1199int64_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
1213void 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
1239bool 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.
1408MachineBasicBlock *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}