Bug Summary

File:lib/Target/Hexagon/HexagonHardwareLoops.cpp
Warning:line 762, column 24
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 function calls in loops.
25//
26//===----------------------------------------------------------------------===//
27
28#include "HexagonInstrInfo.h"
29#include "HexagonSubtarget.h"
30#include "llvm/ADT/SmallSet.h"
31#include "llvm/ADT/SmallVector.h"
32#include "llvm/ADT/Statistic.h"
33#include "llvm/ADT/StringRef.h"
34#include "llvm/CodeGen/MachineBasicBlock.h"
35#include "llvm/CodeGen/MachineDominators.h"
36#include "llvm/CodeGen/MachineFunction.h"
37#include "llvm/CodeGen/MachineFunctionPass.h"
38#include "llvm/CodeGen/MachineInstr.h"
39#include "llvm/CodeGen/MachineInstrBuilder.h"
40#include "llvm/CodeGen/MachineLoopInfo.h"
41#include "llvm/CodeGen/MachineOperand.h"
42#include "llvm/CodeGen/MachineRegisterInfo.h"
43#include "llvm/IR/Constants.h"
44#include "llvm/IR/DebugLoc.h"
45#include "llvm/Pass.h"
46#include "llvm/Support/CommandLine.h"
47#include "llvm/Support/Debug.h"
48#include "llvm/Support/ErrorHandling.h"
49#include "llvm/Support/MathExtras.h"
50#include "llvm/Support/raw_ostream.h"
51#include "llvm/Target/TargetRegisterInfo.h"
52#include <cassert>
53#include <cstdint>
54#include <cstdlib>
55#include <iterator>
56#include <map>
57#include <set>
58#include <utility>
59#include <vector>
60
61using namespace llvm;
62
63#define DEBUG_TYPE"hwloops" "hwloops"
64
65#ifndef NDEBUG
66static cl::opt<int> HWLoopLimit("hexagon-max-hwloop", cl::Hidden, cl::init(-1));
67
68// Option to create preheader only for a specific function.
69static cl::opt<std::string> PHFn("hexagon-hwloop-phfn", cl::Hidden,
70 cl::init(""));
71#endif
72
73// Option to create a preheader if one doesn't exist.
74static cl::opt<bool> HWCreatePreheader("hexagon-hwloop-preheader",
75 cl::Hidden, cl::init(true),
76 cl::desc("Add a preheader to a hardware loop if one doesn't exist"));
77
78// Turn it off by default. If a preheader block is not created here, the
79// software pipeliner may be unable to find a block suitable to serve as
80// a preheader. In that case SWP will not run.
81static cl::opt<bool> SpecPreheader("hwloop-spec-preheader", cl::init(false),
82 cl::Hidden, cl::ZeroOrMore, cl::desc("Allow speculation of preheader "
83 "instructions"));
84
85STATISTIC(NumHWLoops, "Number of loops converted to hardware loops")static llvm::Statistic NumHWLoops = {"hwloops", "NumHWLoops",
"Number of loops converted to hardware loops", {0}, false}
;
86
87namespace llvm {
88
89 FunctionPass *createHexagonHardwareLoops();
90 void initializeHexagonHardwareLoopsPass(PassRegistry&);
91
92} // end namespace llvm
93
94namespace {
95
96 class CountValue;
97
98 struct HexagonHardwareLoops : public MachineFunctionPass {
99 MachineLoopInfo *MLI;
100 MachineRegisterInfo *MRI;
101 MachineDominatorTree *MDT;
102 const HexagonInstrInfo *TII;
103 const HexagonRegisterInfo *TRI;
104#ifndef NDEBUG
105 static int Counter;
106#endif
107
108 public:
109 static char ID;
110
111 HexagonHardwareLoops() : MachineFunctionPass(ID) {
112 initializeHexagonHardwareLoopsPass(*PassRegistry::getPassRegistry());
113 }
114
115 bool runOnMachineFunction(MachineFunction &MF) override;
116
117 StringRef getPassName() const override { return "Hexagon Hardware Loops"; }
118
119 void getAnalysisUsage(AnalysisUsage &AU) const override {
120 AU.addRequired<MachineDominatorTree>();
121 AU.addRequired<MachineLoopInfo>();
122 MachineFunctionPass::getAnalysisUsage(AU);
123 }
124
125 private:
126 typedef std::map<unsigned, MachineInstr *> LoopFeederMap;
127
128 /// Kinds of comparisons in the compare instructions.
129 struct Comparison {
130 enum Kind {
131 EQ = 0x01,
132 NE = 0x02,
133 L = 0x04,
134 G = 0x08,
135 U = 0x40,
136 LTs = L,
137 LEs = L | EQ,
138 GTs = G,
139 GEs = G | EQ,
140 LTu = L | U,
141 LEu = L | EQ | U,
142 GTu = G | U,
143 GEu = G | EQ | U
144 };
145
146 static Kind getSwappedComparison(Kind Cmp) {
147 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-5.0~svn298304/lib/Target/Hexagon/HexagonHardwareLoops.cpp"
, 147, __PRETTY_FUNCTION__))
;
148 if ((Cmp & L) || (Cmp & G))
149 return (Kind)(Cmp ^ (L|G));
150 return Cmp;
151 }
152
153 static Kind getNegatedComparison(Kind Cmp) {
154 if ((Cmp & L) || (Cmp & G))
155 return (Kind)((Cmp ^ (L | G)) ^ EQ);
156 if ((Cmp & NE) || (Cmp & EQ))
157 return (Kind)(Cmp ^ (EQ | NE));
158 return (Kind)0;
159 }
160
161 static bool isSigned(Kind Cmp) {
162 return (Cmp & (L | G) && !(Cmp & U));
163 }
164
165 static bool isUnsigned(Kind Cmp) {
166 return (Cmp & U);
167 }
168 };
169
170 /// \brief Find the register that contains the loop controlling
171 /// induction variable.
172 /// If successful, it will return true and set the \p Reg, \p IVBump
173 /// and \p IVOp arguments. Otherwise it will return false.
174 /// The returned induction register is the register R that follows the
175 /// following induction pattern:
176 /// loop:
177 /// R = phi ..., [ R.next, LatchBlock ]
178 /// R.next = R + #bump
179 /// if (R.next < #N) goto loop
180 /// IVBump is the immediate value added to R, and IVOp is the instruction
181 /// "R.next = R + #bump".
182 bool findInductionRegister(MachineLoop *L, unsigned &Reg,
183 int64_t &IVBump, MachineInstr *&IVOp) const;
184
185 /// \brief Return the comparison kind for the specified opcode.
186 Comparison::Kind getComparisonKind(unsigned CondOpc,
187 MachineOperand *InitialValue,
188 const MachineOperand *Endvalue,
189 int64_t IVBump) const;
190
191 /// \brief Analyze the statements in a loop to determine if the loop
192 /// has a computable trip count and, if so, return a value that represents
193 /// the trip count expression.
194 CountValue *getLoopTripCount(MachineLoop *L,
195 SmallVectorImpl<MachineInstr *> &OldInsts);
196
197 /// \brief Return the expression that represents the number of times
198 /// a loop iterates. The function takes the operands that represent the
199 /// loop start value, loop end value, and induction value. Based upon
200 /// these operands, the function attempts to compute the trip count.
201 /// If the trip count is not directly available (as an immediate value,
202 /// or a register), the function will attempt to insert computation of it
203 /// to the loop's preheader.
204 CountValue *computeCount(MachineLoop *Loop, const MachineOperand *Start,
205 const MachineOperand *End, unsigned IVReg,
206 int64_t IVBump, Comparison::Kind Cmp) const;
207
208 /// \brief Return true if the instruction is not valid within a hardware
209 /// loop.
210 bool isInvalidLoopOperation(const MachineInstr *MI,
211 bool IsInnerHWLoop) const;
212
213 /// \brief Return true if the loop contains an instruction that inhibits
214 /// using the hardware loop.
215 bool containsInvalidInstruction(MachineLoop *L, bool IsInnerHWLoop) const;
216
217 /// \brief Given a loop, check if we can convert it to a hardware loop.
218 /// If so, then perform the conversion and return true.
219 bool convertToHardwareLoop(MachineLoop *L, bool &L0used, bool &L1used);
220
221 /// \brief Return true if the instruction is now dead.
222 bool isDead(const MachineInstr *MI,
223 SmallVectorImpl<MachineInstr *> &DeadPhis) const;
224
225 /// \brief Remove the instruction if it is now dead.
226 void removeIfDead(MachineInstr *MI);
227
228 /// \brief Make sure that the "bump" instruction executes before the
229 /// compare. We need that for the IV fixup, so that the compare
230 /// instruction would not use a bumped value that has not yet been
231 /// defined. If the instructions are out of order, try to reorder them.
232 bool orderBumpCompare(MachineInstr *BumpI, MachineInstr *CmpI);
233
234 /// \brief Return true if MO and MI pair is visited only once. If visited
235 /// more than once, this indicates there is recursion. In such a case,
236 /// return false.
237 bool isLoopFeeder(MachineLoop *L, MachineBasicBlock *A, MachineInstr *MI,
238 const MachineOperand *MO,
239 LoopFeederMap &LoopFeederPhi) const;
240
241 /// \brief Return true if the Phi may generate a value that may underflow,
242 /// or may wrap.
243 bool phiMayWrapOrUnderflow(MachineInstr *Phi, const MachineOperand *EndVal,
244 MachineBasicBlock *MBB, MachineLoop *L,
245 LoopFeederMap &LoopFeederPhi) const;
246
247 /// \brief Return true if the induction variable may underflow an unsigned
248 /// value in the first iteration.
249 bool loopCountMayWrapOrUnderFlow(const MachineOperand *InitVal,
250 const MachineOperand *EndVal,
251 MachineBasicBlock *MBB, MachineLoop *L,
252 LoopFeederMap &LoopFeederPhi) const;
253
254 /// \brief Check if the given operand has a compile-time known constant
255 /// value. Return true if yes, and false otherwise. When returning true, set
256 /// Val to the corresponding constant value.
257 bool checkForImmediate(const MachineOperand &MO, int64_t &Val) const;
258
259 /// \brief Check if the operand has a compile-time known constant value.
260 bool isImmediate(const MachineOperand &MO) const {
261 int64_t V;
262 return checkForImmediate(MO, V);
263 }
264
265 /// \brief Return the immediate for the specified operand.
266 int64_t getImmediate(const MachineOperand &MO) const {
267 int64_t V;
268 if (!checkForImmediate(MO, V))
269 llvm_unreachable("Invalid operand")::llvm::llvm_unreachable_internal("Invalid operand", "/tmp/buildd/llvm-toolchain-snapshot-5.0~svn298304/lib/Target/Hexagon/HexagonHardwareLoops.cpp"
, 269)
;
270 return V;
271 }
272
273 /// \brief Reset the given machine operand to now refer to a new immediate
274 /// value. Assumes that the operand was already referencing an immediate
275 /// value, either directly, or via a register.
276 void setImmediate(MachineOperand &MO, int64_t Val);
277
278 /// \brief Fix the data flow of the induction varible.
279 /// The desired flow is: phi ---> bump -+-> comparison-in-latch.
280 /// |
281 /// +-> back to phi
282 /// where "bump" is the increment of the induction variable:
283 /// iv = iv + #const.
284 /// Due to some prior code transformations, the actual flow may look
285 /// like this:
286 /// phi -+-> bump ---> back to phi
287 /// |
288 /// +-> comparison-in-latch (against upper_bound-bump),
289 /// i.e. the comparison that controls the loop execution may be using
290 /// the value of the induction variable from before the increment.
291 ///
292 /// Return true if the loop's flow is the desired one (i.e. it's
293 /// either been fixed, or no fixing was necessary).
294 /// Otherwise, return false. This can happen if the induction variable
295 /// couldn't be identified, or if the value in the latch's comparison
296 /// cannot be adjusted to reflect the post-bump value.
297 bool fixupInductionVariable(MachineLoop *L);
298
299 /// \brief Given a loop, if it does not have a preheader, create one.
300 /// Return the block that is the preheader.
301 MachineBasicBlock *createPreheaderForLoop(MachineLoop *L);
302 };
303
304 char HexagonHardwareLoops::ID = 0;
305#ifndef NDEBUG
306 int HexagonHardwareLoops::Counter = 0;
307#endif
308
309 /// \brief Abstraction for a trip count of a loop. A smaller version
310 /// of the MachineOperand class without the concerns of changing the
311 /// operand representation.
312 class CountValue {
313 public:
314 enum CountValueType {
315 CV_Register,
316 CV_Immediate
317 };
318
319 private:
320 CountValueType Kind;
321 union Values {
322 struct {
323 unsigned Reg;
324 unsigned Sub;
325 } R;
326 unsigned ImmVal;
327 } Contents;
328
329 public:
330 explicit CountValue(CountValueType t, unsigned v, unsigned u = 0) {
331 Kind = t;
332 if (Kind == CV_Register) {
333 Contents.R.Reg = v;
334 Contents.R.Sub = u;
335 } else {
336 Contents.ImmVal = v;
337 }
338 }
339
340 bool isReg() const { return Kind == CV_Register; }
341 bool isImm() const { return Kind == CV_Immediate; }
342
343 unsigned getReg() const {
344 assert(isReg() && "Wrong CountValue accessor")((isReg() && "Wrong CountValue accessor") ? static_cast
<void> (0) : __assert_fail ("isReg() && \"Wrong CountValue accessor\""
, "/tmp/buildd/llvm-toolchain-snapshot-5.0~svn298304/lib/Target/Hexagon/HexagonHardwareLoops.cpp"
, 344, __PRETTY_FUNCTION__))
;
345 return Contents.R.Reg;
346 }
347 unsigned getSubReg() const {
348 assert(isReg() && "Wrong CountValue accessor")((isReg() && "Wrong CountValue accessor") ? static_cast
<void> (0) : __assert_fail ("isReg() && \"Wrong CountValue accessor\""
, "/tmp/buildd/llvm-toolchain-snapshot-5.0~svn298304/lib/Target/Hexagon/HexagonHardwareLoops.cpp"
, 348, __PRETTY_FUNCTION__))
;
349 return Contents.R.Sub;
350 }
351 unsigned getImm() const {
352 assert(isImm() && "Wrong CountValue accessor")((isImm() && "Wrong CountValue accessor") ? static_cast
<void> (0) : __assert_fail ("isImm() && \"Wrong CountValue accessor\""
, "/tmp/buildd/llvm-toolchain-snapshot-5.0~svn298304/lib/Target/Hexagon/HexagonHardwareLoops.cpp"
, 352, __PRETTY_FUNCTION__))
;
353 return Contents.ImmVal;
354 }
355
356 void print(raw_ostream &OS, const TargetRegisterInfo *TRI = nullptr) const {
357 if (isReg()) { OS << PrintReg(Contents.R.Reg, TRI, Contents.R.Sub); }
358 if (isImm()) { OS << Contents.ImmVal; }
359 }
360 };
361
362} // end anonymous namespace
363
364INITIALIZE_PASS_BEGIN(HexagonHardwareLoops, "hwloops",static void *initializeHexagonHardwareLoopsPassOnce(PassRegistry
&Registry) {
365 "Hexagon Hardware Loops", false, false)static void *initializeHexagonHardwareLoopsPassOnce(PassRegistry
&Registry) {
366INITIALIZE_PASS_DEPENDENCY(MachineDominatorTree)initializeMachineDominatorTreePass(Registry);
367INITIALIZE_PASS_DEPENDENCY(MachineLoopInfo)initializeMachineLoopInfoPass(Registry);
368INITIALIZE_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; } static llvm::once_flag InitializeHexagonHardwareLoopsPassFlag
; void llvm::initializeHexagonHardwareLoopsPass(PassRegistry &
Registry) { llvm::call_once(InitializeHexagonHardwareLoopsPassFlag
, initializeHexagonHardwareLoopsPassOnce, std::ref(Registry))
; }
369 "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; } static llvm::once_flag InitializeHexagonHardwareLoopsPassFlag
; void llvm::initializeHexagonHardwareLoopsPass(PassRegistry &
Registry) { llvm::call_once(InitializeHexagonHardwareLoopsPassFlag
, initializeHexagonHardwareLoopsPassOnce, std::ref(Registry))
; }
370
371FunctionPass *llvm::createHexagonHardwareLoops() {
372 return new HexagonHardwareLoops();
373}
374
375bool HexagonHardwareLoops::runOnMachineFunction(MachineFunction &MF) {
376 DEBUG(dbgs() << "********* Hexagon Hardware Loops *********\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("hwloops")) { dbgs() << "********* Hexagon Hardware Loops *********\n"
; } } while (false)
;
377 if (skipFunction(*MF.getFunction()))
378 return false;
379
380 bool Changed = false;
381
382 MLI = &getAnalysis<MachineLoopInfo>();
383 MRI = &MF.getRegInfo();
384 MDT = &getAnalysis<MachineDominatorTree>();
385 const HexagonSubtarget &HST = MF.getSubtarget<HexagonSubtarget>();
386 TII = HST.getInstrInfo();
387 TRI = HST.getRegisterInfo();
388
389 for (auto &L : *MLI)
390 if (!L->getParentLoop()) {
391 bool L0Used = false;
392 bool L1Used = false;
393 Changed |= convertToHardwareLoop(L, L0Used, L1Used);
394 }
395
396 return Changed;
397}
398
399bool HexagonHardwareLoops::findInductionRegister(MachineLoop *L,
400 unsigned &Reg,
401 int64_t &IVBump,
402 MachineInstr *&IVOp
403 ) const {
404 MachineBasicBlock *Header = L->getHeader();
405 MachineBasicBlock *Preheader = MLI->findLoopPreheader(L, SpecPreheader);
406 MachineBasicBlock *Latch = L->getLoopLatch();
407 MachineBasicBlock *ExitingBlock = L->findLoopControlBlock();
408 if (!Header || !Preheader || !Latch || !ExitingBlock)
409 return false;
410
411 // This pair represents an induction register together with an immediate
412 // value that will be added to it in each loop iteration.
413 typedef std::pair<unsigned,int64_t> RegisterBump;
414
415 // Mapping: R.next -> (R, bump), where R, R.next and bump are derived
416 // from an induction operation
417 // R.next = R + bump
418 // where bump is an immediate value.
419 typedef std::map<unsigned,RegisterBump> InductionMap;
420
421 InductionMap IndMap;
422
423 typedef MachineBasicBlock::instr_iterator instr_iterator;
424 for (instr_iterator I = Header->instr_begin(), E = Header->instr_end();
425 I != E && I->isPHI(); ++I) {
426 MachineInstr *Phi = &*I;
427
428 // Have a PHI instruction. Get the operand that corresponds to the
429 // latch block, and see if is a result of an addition of form "reg+imm",
430 // where the "reg" is defined by the PHI node we are looking at.
431 for (unsigned i = 1, n = Phi->getNumOperands(); i < n; i += 2) {
432 if (Phi->getOperand(i+1).getMBB() != Latch)
433 continue;
434
435 unsigned PhiOpReg = Phi->getOperand(i).getReg();
436 MachineInstr *DI = MRI->getVRegDef(PhiOpReg);
437
438 if (DI->getDesc().isAdd()) {
439 // If the register operand to the add is the PHI we're looking at, this
440 // meets the induction pattern.
441 unsigned IndReg = DI->getOperand(1).getReg();
442 MachineOperand &Opnd2 = DI->getOperand(2);
443 int64_t V;
444 if (MRI->getVRegDef(IndReg) == Phi && checkForImmediate(Opnd2, V)) {
445 unsigned UpdReg = DI->getOperand(0).getReg();
446 IndMap.insert(std::make_pair(UpdReg, std::make_pair(IndReg, V)));
447 }
448 }
449 } // for (i)
450 } // for (instr)
451
452 SmallVector<MachineOperand,2> Cond;
453 MachineBasicBlock *TB = nullptr, *FB = nullptr;
454 bool NotAnalyzed = TII->analyzeBranch(*ExitingBlock, TB, FB, Cond, false);
455 if (NotAnalyzed)
456 return false;
457
458 unsigned PredR, PredPos, PredRegFlags;
459 if (!TII->getPredReg(Cond, PredR, PredPos, PredRegFlags))
460 return false;
461
462 MachineInstr *PredI = MRI->getVRegDef(PredR);
463 if (!PredI->isCompare())
464 return false;
465
466 unsigned CmpReg1 = 0, CmpReg2 = 0;
467 int CmpImm = 0, CmpMask = 0;
468 bool CmpAnalyzed =
469 TII->analyzeCompare(*PredI, CmpReg1, CmpReg2, CmpMask, CmpImm);
470 // Fail if the compare was not analyzed, or it's not comparing a register
471 // with an immediate value. Not checking the mask here, since we handle
472 // the individual compare opcodes (including A4_cmpb*) later on.
473 if (!CmpAnalyzed)
474 return false;
475
476 // Exactly one of the input registers to the comparison should be among
477 // the induction registers.
478 InductionMap::iterator IndMapEnd = IndMap.end();
479 InductionMap::iterator F = IndMapEnd;
480 if (CmpReg1 != 0) {
481 InductionMap::iterator F1 = IndMap.find(CmpReg1);
482 if (F1 != IndMapEnd)
483 F = F1;
484 }
485 if (CmpReg2 != 0) {
486 InductionMap::iterator F2 = IndMap.find(CmpReg2);
487 if (F2 != IndMapEnd) {
488 if (F != IndMapEnd)
489 return false;
490 F = F2;
491 }
492 }
493 if (F == IndMapEnd)
494 return false;
495
496 Reg = F->second.first;
497 IVBump = F->second.second;
498 IVOp = MRI->getVRegDef(F->first);
499 return true;
500}
501
502// Return the comparison kind for the specified opcode.
503HexagonHardwareLoops::Comparison::Kind
504HexagonHardwareLoops::getComparisonKind(unsigned CondOpc,
505 MachineOperand *InitialValue,
506 const MachineOperand *EndValue,
507 int64_t IVBump) const {
508 Comparison::Kind Cmp = (Comparison::Kind)0;
509 switch (CondOpc) {
510 case Hexagon::C2_cmpeqi:
511 case Hexagon::C2_cmpeq:
512 case Hexagon::C2_cmpeqp:
513 Cmp = Comparison::EQ;
514 break;
515 case Hexagon::C4_cmpneq:
516 case Hexagon::C4_cmpneqi:
517 Cmp = Comparison::NE;
518 break;
519 case Hexagon::C4_cmplte:
520 Cmp = Comparison::LEs;
521 break;
522 case Hexagon::C4_cmplteu:
523 Cmp = Comparison::LEu;
524 break;
525 case Hexagon::C2_cmpgtui:
526 case Hexagon::C2_cmpgtu:
527 case Hexagon::C2_cmpgtup:
528 Cmp = Comparison::GTu;
529 break;
530 case Hexagon::C2_cmpgti:
531 case Hexagon::C2_cmpgt:
532 case Hexagon::C2_cmpgtp:
533 Cmp = Comparison::GTs;
534 break;
535 default:
536 return (Comparison::Kind)0;
537 }
538 return Cmp;
539}
540
541/// \brief Analyze the statements in a loop to determine if the loop has
542/// a computable trip count and, if so, return a value that represents
543/// the trip count expression.
544///
545/// This function iterates over the phi nodes in the loop to check for
546/// induction variable patterns that are used in the calculation for
547/// the number of time the loop is executed.
548CountValue *HexagonHardwareLoops::getLoopTripCount(MachineLoop *L,
549 SmallVectorImpl<MachineInstr *> &OldInsts) {
550 MachineBasicBlock *TopMBB = L->getTopBlock();
551 MachineBasicBlock::pred_iterator PI = TopMBB->pred_begin();
552 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-5.0~svn298304/lib/Target/Hexagon/HexagonHardwareLoops.cpp"
, 553, __PRETTY_FUNCTION__))
553 "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-5.0~svn298304/lib/Target/Hexagon/HexagonHardwareLoops.cpp"
, 553, __PRETTY_FUNCTION__))
;
554 MachineBasicBlock *Backedge = *PI++;
555 if (PI == TopMBB->pred_end()) // dead loop?
556 return nullptr;
557 MachineBasicBlock *Incoming = *PI++;
558 if (PI != TopMBB->pred_end()) // multiple backedges?
559 return nullptr;
560
561 // Make sure there is one incoming and one backedge and determine which
562 // is which.
563 if (L->contains(Incoming)) {
564 if (L->contains(Backedge))
565 return nullptr;
566 std::swap(Incoming, Backedge);
567 } else if (!L->contains(Backedge))
568 return nullptr;
569
570 // Look for the cmp instruction to determine if we can get a useful trip
571 // count. The trip count can be either a register or an immediate. The
572 // location of the value depends upon the type (reg or imm).
573 MachineBasicBlock *ExitingBlock = L->findLoopControlBlock();
574 if (!ExitingBlock)
575 return nullptr;
576
577 unsigned IVReg = 0;
578 int64_t IVBump = 0;
579 MachineInstr *IVOp;
580 bool FoundIV = findInductionRegister(L, IVReg, IVBump, IVOp);
581 if (!FoundIV)
582 return nullptr;
583
584 MachineBasicBlock *Preheader = MLI->findLoopPreheader(L, SpecPreheader);
585
586 MachineOperand *InitialValue = nullptr;
587 MachineInstr *IV_Phi = MRI->getVRegDef(IVReg);
588 MachineBasicBlock *Latch = L->getLoopLatch();
589 for (unsigned i = 1, n = IV_Phi->getNumOperands(); i < n; i += 2) {
590 MachineBasicBlock *MBB = IV_Phi->getOperand(i+1).getMBB();
591 if (MBB == Preheader)
592 InitialValue = &IV_Phi->getOperand(i);
593 else if (MBB == Latch)
594 IVReg = IV_Phi->getOperand(i).getReg(); // Want IV reg after bump.
595 }
596 if (!InitialValue)
597 return nullptr;
598
599 SmallVector<MachineOperand,2> Cond;
600 MachineBasicBlock *TB = nullptr, *FB = nullptr;
601 bool NotAnalyzed = TII->analyzeBranch(*ExitingBlock, TB, FB, Cond, false);
602 if (NotAnalyzed)
603 return nullptr;
604
605 MachineBasicBlock *Header = L->getHeader();
606 // TB must be non-null. If FB is also non-null, one of them must be
607 // the header. Otherwise, branch to TB could be exiting the loop, and
608 // the fall through can go to the header.
609 assert (TB && "Exit block without a branch?")((TB && "Exit block without a branch?") ? static_cast
<void> (0) : __assert_fail ("TB && \"Exit block without a branch?\""
, "/tmp/buildd/llvm-toolchain-snapshot-5.0~svn298304/lib/Target/Hexagon/HexagonHardwareLoops.cpp"
, 609, __PRETTY_FUNCTION__))
;
610 if (ExitingBlock != Latch && (TB == Latch || FB == Latch)) {
611 MachineBasicBlock *LTB = nullptr, *LFB = nullptr;
612 SmallVector<MachineOperand,2> LCond;
613 bool NotAnalyzed = TII->analyzeBranch(*Latch, LTB, LFB, LCond, false);
614 if (NotAnalyzed)
615 return nullptr;
616 if (TB == Latch)
617 TB = (LTB == Header) ? LTB : LFB;
618 else
619 FB = (LTB == Header) ? LTB: LFB;
620 }
621 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-5.0~svn298304/lib/Target/Hexagon/HexagonHardwareLoops.cpp"
, 621, __PRETTY_FUNCTION__))
;
622 if (!TB || (FB && TB != Header && FB != Header))
623 return nullptr;
624
625 // Branches of form "if (!P) ..." cause HexagonInstrInfo::AnalyzeBranch
626 // to put imm(0), followed by P in the vector Cond.
627 // If TB is not the header, it means that the "not-taken" path must lead
628 // to the header.
629 bool Negated = TII->predOpcodeHasNot(Cond) ^ (TB != Header);
630 unsigned PredReg, PredPos, PredRegFlags;
631 if (!TII->getPredReg(Cond, PredReg, PredPos, PredRegFlags))
632 return nullptr;
633 MachineInstr *CondI = MRI->getVRegDef(PredReg);
634 unsigned CondOpc = CondI->getOpcode();
635
636 unsigned CmpReg1 = 0, CmpReg2 = 0;
637 int Mask = 0, ImmValue = 0;
638 bool AnalyzedCmp =
639 TII->analyzeCompare(*CondI, CmpReg1, CmpReg2, Mask, ImmValue);
640 if (!AnalyzedCmp)
641 return nullptr;
642
643 // The comparison operator type determines how we compute the loop
644 // trip count.
645 OldInsts.push_back(CondI);
646 OldInsts.push_back(IVOp);
647
648 // Sadly, the following code gets information based on the position
649 // of the operands in the compare instruction. This has to be done
650 // this way, because the comparisons check for a specific relationship
651 // between the operands (e.g. is-less-than), rather than to find out
652 // what relationship the operands are in (as on PPC).
653 Comparison::Kind Cmp;
654 bool isSwapped = false;
655 const MachineOperand &Op1 = CondI->getOperand(1);
656 const MachineOperand &Op2 = CondI->getOperand(2);
657 const MachineOperand *EndValue = nullptr;
658
659 if (Op1.isReg()) {
660 if (Op2.isImm() || Op1.getReg() == IVReg)
661 EndValue = &Op2;
662 else {
663 EndValue = &Op1;
664 isSwapped = true;
665 }
666 }
667
668 if (!EndValue)
669 return nullptr;
670
671 Cmp = getComparisonKind(CondOpc, InitialValue, EndValue, IVBump);
672 if (!Cmp)
673 return nullptr;
674 if (Negated)
675 Cmp = Comparison::getNegatedComparison(Cmp);
676 if (isSwapped)
677 Cmp = Comparison::getSwappedComparison(Cmp);
678
679 if (InitialValue->isReg()) {
680 unsigned R = InitialValue->getReg();
681 MachineBasicBlock *DefBB = MRI->getVRegDef(R)->getParent();
682 if (!MDT->properlyDominates(DefBB, Header))
683 return nullptr;
684 OldInsts.push_back(MRI->getVRegDef(R));
685 }
686 if (EndValue->isReg()) {
687 unsigned R = EndValue->getReg();
688 MachineBasicBlock *DefBB = MRI->getVRegDef(R)->getParent();
689 if (!MDT->properlyDominates(DefBB, Header))
690 return nullptr;
691 OldInsts.push_back(MRI->getVRegDef(R));
692 }
693
694 return computeCount(L, InitialValue, EndValue, IVReg, IVBump, Cmp);
695}
696
697/// \brief Helper function that returns the expression that represents the
698/// number of times a loop iterates. The function takes the operands that
699/// represent the loop start value, loop end value, and induction value.
700/// Based upon these operands, the function attempts to compute the trip count.
701CountValue *HexagonHardwareLoops::computeCount(MachineLoop *Loop,
702 const MachineOperand *Start,
703 const MachineOperand *End,
704 unsigned IVReg,
705 int64_t IVBump,
706 Comparison::Kind Cmp) const {
707 // Cannot handle comparison EQ, i.e. while (A == B).
708 if (Cmp == Comparison::EQ)
1
Assuming 'Cmp' is not equal to EQ
2
Taking false branch
709 return nullptr;
710
711 // Check if either the start or end values are an assignment of an immediate.
712 // If so, use the immediate value rather than the register.
713 if (Start->isReg()) {
3
Taking false branch
714 const MachineInstr *StartValInstr = MRI->getVRegDef(Start->getReg());
715 if (StartValInstr && (StartValInstr->getOpcode() == Hexagon::A2_tfrsi ||
716 StartValInstr->getOpcode() == Hexagon::A2_tfrpi))
717 Start = &StartValInstr->getOperand(1);
718 }
719 if (End->isReg()) {
4
Taking false branch
720 const MachineInstr *EndValInstr = MRI->getVRegDef(End->getReg());
721 if (EndValInstr && (EndValInstr->getOpcode() == Hexagon::A2_tfrsi ||
722 EndValInstr->getOpcode() == Hexagon::A2_tfrpi))
723 End = &EndValInstr->getOperand(1);
724 }
725
726 if (!Start->isReg() && !Start->isImm())
5
Taking false branch
727 return nullptr;
728 if (!End->isReg() && !End->isImm())
6
Taking false branch
729 return nullptr;
730
731 bool CmpLess = Cmp & Comparison::L;
732 bool CmpGreater = Cmp & Comparison::G;
733 bool CmpHasEqual = Cmp & Comparison::EQ;
734
735 // Avoid certain wrap-arounds. This doesn't detect all wrap-arounds.
736 if (CmpLess && IVBump < 0)
7
Assuming 'CmpLess' is not equal to 0
8
Assuming 'IVBump' is >= 0
9
Taking false branch
737 // Loop going while iv is "less" with the iv value going down. Must wrap.
738 return nullptr;
739
740 if (CmpGreater && IVBump > 0)
10
Assuming 'CmpGreater' is not equal to 0
11
Assuming 'IVBump' is <= 0
12
Taking false branch
741 // Loop going while iv is "greater" with the iv value going up. Must wrap.
742 return nullptr;
743
744 // Phis that may feed into the loop.
745 LoopFeederMap LoopFeederPhi;
746
747 // Check if the initial value may be zero and can be decremented in the first
748 // iteration. If the value is zero, the endloop instruction will not decrement
749 // the loop counter, so we shouldn't generate a hardware loop in this case.
750 if (loopCountMayWrapOrUnderFlow(Start, End, Loop->getLoopPreheader(), Loop,
13
Taking false branch
751 LoopFeederPhi))
752 return nullptr;
753
754 if (Start->isImm() && End->isImm()) {
14
Taking true branch
755 // Both, start and end are immediates.
756 int64_t StartV = Start->getImm();
757 int64_t EndV = End->getImm();
758 int64_t Dist = EndV - StartV;
759 if (Dist == 0)
15
Assuming 'Dist' is not equal to 0
16
Taking false branch
760 return nullptr;
761
762 bool Exact = (Dist % IVBump) == 0;
17
Division by zero
763
764 if (Cmp == Comparison::NE) {
765 if (!Exact)
766 return nullptr;
767 if ((Dist < 0) ^ (IVBump < 0))
768 return nullptr;
769 }
770
771 // For comparisons that include the final value (i.e. include equality
772 // with the final value), we need to increase the distance by 1.
773 if (CmpHasEqual)
774 Dist = Dist > 0 ? Dist+1 : Dist-1;
775
776 // For the loop to iterate, CmpLess should imply Dist > 0. Similarly,
777 // CmpGreater should imply Dist < 0. These conditions could actually
778 // fail, for example, in unreachable code (which may still appear to be
779 // reachable in the CFG).
780 if ((CmpLess && Dist < 0) || (CmpGreater && Dist > 0))
781 return nullptr;
782
783 // "Normalized" distance, i.e. with the bump set to +-1.
784 int64_t Dist1 = (IVBump > 0) ? (Dist + (IVBump - 1)) / IVBump
785 : (-Dist + (-IVBump - 1)) / (-IVBump);
786 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-5.0~svn298304/lib/Target/Hexagon/HexagonHardwareLoops.cpp"
, 786, __PRETTY_FUNCTION__))
;
787
788 uint64_t Count = Dist1;
789
790 if (Count > 0xFFFFFFFFULL)
791 return nullptr;
792
793 return new CountValue(CountValue::CV_Immediate, Count);
794 }
795
796 // A general case: Start and End are some values, but the actual
797 // iteration count may not be available. If it is not, insert
798 // a computation of it into the preheader.
799
800 // If the induction variable bump is not a power of 2, quit.
801 // Othwerise we'd need a general integer division.
802 if (!isPowerOf2_64(std::abs(IVBump)))
803 return nullptr;
804
805 MachineBasicBlock *PH = MLI->findLoopPreheader(Loop, SpecPreheader);
806 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-5.0~svn298304/lib/Target/Hexagon/HexagonHardwareLoops.cpp"
, 806, __PRETTY_FUNCTION__))
;
807 MachineBasicBlock::iterator InsertPos = PH->getFirstTerminator();
808 DebugLoc DL;
809 if (InsertPos != PH->end())
810 DL = InsertPos->getDebugLoc();
811
812 // If Start is an immediate and End is a register, the trip count
813 // will be "reg - imm". Hexagon's "subtract immediate" instruction
814 // is actually "reg + -imm".
815
816 // If the loop IV is going downwards, i.e. if the bump is negative,
817 // then the iteration count (computed as End-Start) will need to be
818 // negated. To avoid the negation, just swap Start and End.
819 if (IVBump < 0) {
820 std::swap(Start, End);
821 IVBump = -IVBump;
822 }
823 // Cmp may now have a wrong direction, e.g. LEs may now be GEs.
824 // Signedness, and "including equality" are preserved.
825
826 bool RegToImm = Start->isReg() && End->isImm(); // for (reg..imm)
827 bool RegToReg = Start->isReg() && End->isReg(); // for (reg..reg)
828
829 int64_t StartV = 0, EndV = 0;
830 if (Start->isImm())
831 StartV = Start->getImm();
832 if (End->isImm())
833 EndV = End->getImm();
834
835 int64_t AdjV = 0;
836 // To compute the iteration count, we would need this computation:
837 // Count = (End - Start + (IVBump-1)) / IVBump
838 // or, when CmpHasEqual:
839 // Count = (End - Start + (IVBump-1)+1) / IVBump
840 // The "IVBump-1" part is the adjustment (AdjV). We can avoid
841 // generating an instruction specifically to add it if we can adjust
842 // the immediate values for Start or End.
843
844 if (CmpHasEqual) {
845 // Need to add 1 to the total iteration count.
846 if (Start->isImm())
847 StartV--;
848 else if (End->isImm())
849 EndV++;
850 else
851 AdjV += 1;
852 }
853
854 if (Cmp != Comparison::NE) {
855 if (Start->isImm())
856 StartV -= (IVBump-1);
857 else if (End->isImm())
858 EndV += (IVBump-1);
859 else
860 AdjV += (IVBump-1);
861 }
862
863 unsigned R = 0, SR = 0;
864 if (Start->isReg()) {
865 R = Start->getReg();
866 SR = Start->getSubReg();
867 } else {
868 R = End->getReg();
869 SR = End->getSubReg();
870 }
871 const TargetRegisterClass *RC = MRI->getRegClass(R);
872 // Hardware loops cannot handle 64-bit registers. If it's a double
873 // register, it has to have a subregister.
874 if (!SR && RC == &Hexagon::DoubleRegsRegClass)
875 return nullptr;
876 const TargetRegisterClass *IntRC = &Hexagon::IntRegsRegClass;
877
878 // Compute DistR (register with the distance between Start and End).
879 unsigned DistR, DistSR;
880
881 // Avoid special case, where the start value is an imm(0).
882 if (Start->isImm() && StartV == 0) {
883 DistR = End->getReg();
884 DistSR = End->getSubReg();
885 } else {
886 const MCInstrDesc &SubD = RegToReg ? TII->get(Hexagon::A2_sub) :
887 (RegToImm ? TII->get(Hexagon::A2_subri) :
888 TII->get(Hexagon::A2_addi));
889 if (RegToReg || RegToImm) {
890 unsigned SubR = MRI->createVirtualRegister(IntRC);
891 MachineInstrBuilder SubIB =
892 BuildMI(*PH, InsertPos, DL, SubD, SubR);
893
894 if (RegToReg)
895 SubIB.addReg(End->getReg(), 0, End->getSubReg())
896 .addReg(Start->getReg(), 0, Start->getSubReg());
897 else
898 SubIB.addImm(EndV)
899 .addReg(Start->getReg(), 0, Start->getSubReg());
900 DistR = SubR;
901 } else {
902 // If the loop has been unrolled, we should use the original loop count
903 // instead of recalculating the value. This will avoid additional
904 // 'Add' instruction.
905 const MachineInstr *EndValInstr = MRI->getVRegDef(End->getReg());
906 if (EndValInstr->getOpcode() == Hexagon::A2_addi &&
907 EndValInstr->getOperand(2).getImm() == StartV) {
908 DistR = EndValInstr->getOperand(1).getReg();
909 } else {
910 unsigned SubR = MRI->createVirtualRegister(IntRC);
911 MachineInstrBuilder SubIB =
912 BuildMI(*PH, InsertPos, DL, SubD, SubR);
913 SubIB.addReg(End->getReg(), 0, End->getSubReg())
914 .addImm(-StartV);
915 DistR = SubR;
916 }
917 }
918 DistSR = 0;
919 }
920
921 // From DistR, compute AdjR (register with the adjusted distance).
922 unsigned AdjR, AdjSR;
923
924 if (AdjV == 0) {
925 AdjR = DistR;
926 AdjSR = DistSR;
927 } else {
928 // Generate CountR = ADD DistR, AdjVal
929 unsigned AddR = MRI->createVirtualRegister(IntRC);
930 MCInstrDesc const &AddD = TII->get(Hexagon::A2_addi);
931 BuildMI(*PH, InsertPos, DL, AddD, AddR)
932 .addReg(DistR, 0, DistSR)
933 .addImm(AdjV);
934
935 AdjR = AddR;
936 AdjSR = 0;
937 }
938
939 // From AdjR, compute CountR (register with the final count).
940 unsigned CountR, CountSR;
941
942 if (IVBump == 1) {
943 CountR = AdjR;
944 CountSR = AdjSR;
945 } else {
946 // The IV bump is a power of two. Log_2(IV bump) is the shift amount.
947 unsigned Shift = Log2_32(IVBump);
948
949 // Generate NormR = LSR DistR, Shift.
950 unsigned LsrR = MRI->createVirtualRegister(IntRC);
951 const MCInstrDesc &LsrD = TII->get(Hexagon::S2_lsr_i_r);
952 BuildMI(*PH, InsertPos, DL, LsrD, LsrR)
953 .addReg(AdjR, 0, AdjSR)
954 .addImm(Shift);
955
956 CountR = LsrR;
957 CountSR = 0;
958 }
959
960 return new CountValue(CountValue::CV_Register, CountR, CountSR);
961}
962
963/// \brief Return true if the operation is invalid within hardware loop.
964bool HexagonHardwareLoops::isInvalidLoopOperation(const MachineInstr *MI,
965 bool IsInnerHWLoop) const {
966 // Call is not allowed because the callee may use a hardware loop except for
967 // the case when the call never returns.
968 if (MI->getDesc().isCall())
969 return !TII->doesNotReturn(*MI);
970
971 // Check if the instruction defines a hardware loop register.
972 using namespace Hexagon;
973 static const unsigned Regs01[] = { LC0, SA0, LC1, SA1 };
974 static const unsigned Regs1[] = { LC1, SA1 };
975 auto CheckRegs = IsInnerHWLoop ? makeArrayRef(Regs01, array_lengthof(Regs01))
976 : makeArrayRef(Regs1, array_lengthof(Regs1));
977 for (unsigned R : CheckRegs)
978 if (MI->modifiesRegister(R, TRI))
979 return true;
980
981 return false;
982}
983
984/// \brief Return true if the loop contains an instruction that inhibits
985/// the use of the hardware loop instruction.
986bool HexagonHardwareLoops::containsInvalidInstruction(MachineLoop *L,
987 bool IsInnerHWLoop) const {
988 const std::vector<MachineBasicBlock *> &Blocks = L->getBlocks();
989 DEBUG(dbgs() << "\nhw_loop head, BB#" << Blocks[0]->getNumber();)do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("hwloops")) { dbgs() << "\nhw_loop head, BB#" <<
Blocks[0]->getNumber();; } } while (false)
;
990 for (unsigned i = 0, e = Blocks.size(); i != e; ++i) {
991 MachineBasicBlock *MBB = Blocks[i];
992 for (MachineBasicBlock::iterator
993 MII = MBB->begin(), E = MBB->end(); MII != E; ++MII) {
994 const MachineInstr *MI = &*MII;
995 if (isInvalidLoopOperation(MI, IsInnerHWLoop)) {
996 DEBUG(dbgs()<< "\nCannot convert to hw_loop due to:"; MI->dump();)do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("hwloops")) { dbgs()<< "\nCannot convert to hw_loop due to:"
; MI->dump();; } } while (false)
;
997 return true;
998 }
999 }
1000 }
1001 return false;
1002}
1003
1004/// \brief Returns true if the instruction is dead. This was essentially
1005/// copied from DeadMachineInstructionElim::isDead, but with special cases
1006/// for inline asm, physical registers and instructions with side effects
1007/// removed.
1008bool HexagonHardwareLoops::isDead(const MachineInstr *MI,
1009 SmallVectorImpl<MachineInstr *> &DeadPhis) const {
1010 // Examine each operand.
1011 for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) {
1012 const MachineOperand &MO = MI->getOperand(i);
1013 if (!MO.isReg() || !MO.isDef())
1014 continue;
1015
1016 unsigned Reg = MO.getReg();
1017 if (MRI->use_nodbg_empty(Reg))
1018 continue;
1019
1020 typedef MachineRegisterInfo::use_nodbg_iterator use_nodbg_iterator;
1021
1022 // This instruction has users, but if the only user is the phi node for the
1023 // parent block, and the only use of that phi node is this instruction, then
1024 // this instruction is dead: both it (and the phi node) can be removed.
1025 use_nodbg_iterator I = MRI->use_nodbg_begin(Reg);
1026 use_nodbg_iterator End = MRI->use_nodbg_end();
1027 if (std::next(I) != End || !I->getParent()->isPHI())
1028 return false;
1029
1030 MachineInstr *OnePhi = I->getParent();
1031 for (unsigned j = 0, f = OnePhi->getNumOperands(); j != f; ++j) {
1032 const MachineOperand &OPO = OnePhi->getOperand(j);
1033 if (!OPO.isReg() || !OPO.isDef())
1034 continue;
1035
1036 unsigned OPReg = OPO.getReg();
1037 use_nodbg_iterator nextJ;
1038 for (use_nodbg_iterator J = MRI->use_nodbg_begin(OPReg);
1039 J != End; J = nextJ) {
1040 nextJ = std::next(J);
1041 MachineOperand &Use = *J;
1042 MachineInstr *UseMI = Use.getParent();
1043
1044 // If the phi node has a user that is not MI, bail.
1045 if (MI != UseMI)
1046 return false;
1047 }
1048 }
1049 DeadPhis.push_back(OnePhi);
1050 }
1051
1052 // If there are no defs with uses, the instruction is dead.
1053 return true;
1054}
1055
1056void HexagonHardwareLoops::removeIfDead(MachineInstr *MI) {
1057 // This procedure was essentially copied from DeadMachineInstructionElim.
1058
1059 SmallVector<MachineInstr*, 1> DeadPhis;
1060 if (isDead(MI, DeadPhis)) {
1061 DEBUG(dbgs() << "HW looping will remove: " << *MI)do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("hwloops")) { dbgs() << "HW looping will remove: " <<
*MI; } } while (false)
;
1062
1063 // It is possible that some DBG_VALUE instructions refer to this
1064 // instruction. Examine each def operand for such references;
1065 // if found, mark the DBG_VALUE as undef (but don't delete it).
1066 for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) {
1067 const MachineOperand &MO = MI->getOperand(i);
1068 if (!MO.isReg() || !MO.isDef())
1069 continue;
1070 unsigned Reg = MO.getReg();
1071 MachineRegisterInfo::use_iterator nextI;
1072 for (MachineRegisterInfo::use_iterator I = MRI->use_begin(Reg),
1073 E = MRI->use_end(); I != E; I = nextI) {
1074 nextI = std::next(I); // I is invalidated by the setReg
1075 MachineOperand &Use = *I;
1076 MachineInstr *UseMI = I->getParent();
1077 if (UseMI == MI)
1078 continue;
1079 if (Use.isDebug())
1080 UseMI->getOperand(0).setReg(0U);
1081 }
1082 }
1083
1084 MI->eraseFromParent();
1085 for (unsigned i = 0; i < DeadPhis.size(); ++i)
1086 DeadPhis[i]->eraseFromParent();
1087 }
1088}
1089
1090/// \brief Check if the loop is a candidate for converting to a hardware
1091/// loop. If so, then perform the transformation.
1092///
1093/// This function works on innermost loops first. A loop can be converted
1094/// if it is a counting loop; either a register value or an immediate.
1095///
1096/// The code makes several assumptions about the representation of the loop
1097/// in llvm.
1098bool HexagonHardwareLoops::convertToHardwareLoop(MachineLoop *L,
1099 bool &RecL0used,
1100 bool &RecL1used) {
1101 // This is just for sanity.
1102 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-5.0~svn298304/lib/Target/Hexagon/HexagonHardwareLoops.cpp"
, 1102, __PRETTY_FUNCTION__))
;
1103
1104 bool Changed = false;
1105 bool L0Used = false;
1106 bool L1Used = false;
1107
1108 // Process nested loops first.
1109 for (MachineLoop::iterator I = L->begin(), E = L->end(); I != E; ++I) {
1110 Changed |= convertToHardwareLoop(*I, RecL0used, RecL1used);
1111 L0Used |= RecL0used;
1112 L1Used |= RecL1used;
1113 }
1114
1115 // If a nested loop has been converted, then we can't convert this loop.
1116 if (Changed && L0Used && L1Used)
1117 return Changed;
1118
1119 unsigned LOOP_i;
1120 unsigned LOOP_r;
1121 unsigned ENDLOOP;
1122
1123 // Flag used to track loopN instruction:
1124 // 1 - Hardware loop is being generated for the inner most loop.
1125 // 0 - Hardware loop is being generated for the outer loop.
1126 unsigned IsInnerHWLoop = 1;
1127
1128 if (L0Used) {
1129 LOOP_i = Hexagon::J2_loop1i;
1130 LOOP_r = Hexagon::J2_loop1r;
1131 ENDLOOP = Hexagon::ENDLOOP1;
1132 IsInnerHWLoop = 0;
1133 } else {
1134 LOOP_i = Hexagon::J2_loop0i;
1135 LOOP_r = Hexagon::J2_loop0r;
1136 ENDLOOP = Hexagon::ENDLOOP0;
1137 }
1138
1139#ifndef NDEBUG
1140 // Stop trying after reaching the limit (if any).
1141 int Limit = HWLoopLimit;
1142 if (Limit >= 0) {
1143 if (Counter >= HWLoopLimit)
1144 return false;
1145 Counter++;
1146 }
1147#endif
1148
1149 // Does the loop contain any invalid instructions?
1150 if (containsInvalidInstruction(L, IsInnerHWLoop))
1151 return false;
1152
1153 MachineBasicBlock *LastMBB = L->findLoopControlBlock();
1154 // Don't generate hw loop if the loop has more than one exit.
1155 if (!LastMBB)
1156 return false;
1157
1158 MachineBasicBlock::iterator LastI = LastMBB->getFirstTerminator();
1159 if (LastI == LastMBB->end())
1160 return false;
1161
1162 // Is the induction variable bump feeding the latch condition?
1163 if (!fixupInductionVariable(L))
1164 return false;
1165
1166 // Ensure the loop has a preheader: the loop instruction will be
1167 // placed there.
1168 MachineBasicBlock *Preheader = MLI->findLoopPreheader(L, SpecPreheader);
1169 if (!Preheader) {
1170 Preheader = createPreheaderForLoop(L);
1171 if (!Preheader)
1172 return false;
1173 }
1174
1175 MachineBasicBlock::iterator InsertPos = Preheader->getFirstTerminator();
1176
1177 SmallVector<MachineInstr*, 2> OldInsts;
1178 // Are we able to determine the trip count for the loop?
1179 CountValue *TripCount = getLoopTripCount(L, OldInsts);
1180 if (!TripCount)
1181 return false;
1182
1183 // Is the trip count available in the preheader?
1184 if (TripCount->isReg()) {
1185 // There will be a use of the register inserted into the preheader,
1186 // so make sure that the register is actually defined at that point.
1187 MachineInstr *TCDef = MRI->getVRegDef(TripCount->getReg());
1188 MachineBasicBlock *BBDef = TCDef->getParent();
1189 if (!MDT->dominates(BBDef, Preheader))
1190 return false;
1191 }
1192
1193 // Determine the loop start.
1194 MachineBasicBlock *TopBlock = L->getTopBlock();
1195 MachineBasicBlock *ExitingBlock = L->findLoopControlBlock();
1196 MachineBasicBlock *LoopStart = nullptr;
1197 if (ExitingBlock != L->getLoopLatch()) {
1198 MachineBasicBlock *TB = nullptr, *FB = nullptr;
1199 SmallVector<MachineOperand, 2> Cond;
1200
1201 if (TII->analyzeBranch(*ExitingBlock, TB, FB, Cond, false))
1202 return false;
1203
1204 if (L->contains(TB))
1205 LoopStart = TB;
1206 else if (L->contains(FB))
1207 LoopStart = FB;
1208 else
1209 return false;
1210 }
1211 else
1212 LoopStart = TopBlock;
1213
1214 // Convert the loop to a hardware loop.
1215 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 (false)
;
1216 DebugLoc DL;
1217 if (InsertPos != Preheader->end())
1218 DL = InsertPos->getDebugLoc();
1219
1220 if (TripCount->isReg()) {
1221 // Create a copy of the loop count register.
1222 unsigned CountReg = MRI->createVirtualRegister(&Hexagon::IntRegsRegClass);
1223 BuildMI(*Preheader, InsertPos, DL, TII->get(TargetOpcode::COPY), CountReg)
1224 .addReg(TripCount->getReg(), 0, TripCount->getSubReg());
1225 // Add the Loop instruction to the beginning of the loop.
1226 BuildMI(*Preheader, InsertPos, DL, TII->get(LOOP_r)).addMBB(LoopStart)
1227 .addReg(CountReg);
1228 } else {
1229 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-5.0~svn298304/lib/Target/Hexagon/HexagonHardwareLoops.cpp"
, 1229, __PRETTY_FUNCTION__))
;
1230 // Add the Loop immediate instruction to the beginning of the loop,
1231 // if the immediate fits in the instructions. Otherwise, we need to
1232 // create a new virtual register.
1233 int64_t CountImm = TripCount->getImm();
1234 if (!TII->isValidOffset(LOOP_i, CountImm)) {
1235 unsigned CountReg = MRI->createVirtualRegister(&Hexagon::IntRegsRegClass);
1236 BuildMI(*Preheader, InsertPos, DL, TII->get(Hexagon::A2_tfrsi), CountReg)
1237 .addImm(CountImm);
1238 BuildMI(*Preheader, InsertPos, DL, TII->get(LOOP_r))
1239 .addMBB(LoopStart).addReg(CountReg);
1240 } else
1241 BuildMI(*Preheader, InsertPos, DL, TII->get(LOOP_i))
1242 .addMBB(LoopStart).addImm(CountImm);
1243 }
1244
1245 // Make sure the loop start always has a reference in the CFG. We need
1246 // to create a BlockAddress operand to get this mechanism to work both the
1247 // MachineBasicBlock and BasicBlock objects need the flag set.
1248 LoopStart->setHasAddressTaken();
1249 // This line is needed to set the hasAddressTaken flag on the BasicBlock
1250 // object.
1251 BlockAddress::get(const_cast<BasicBlock *>(LoopStart->getBasicBlock()));
1252
1253 // Replace the loop branch with an endloop instruction.
1254 DebugLoc LastIDL = LastI->getDebugLoc();
1255 BuildMI(*LastMBB, LastI, LastIDL, TII->get(ENDLOOP)).addMBB(LoopStart);
1256
1257 // The loop ends with either:
1258 // - a conditional branch followed by an unconditional branch, or
1259 // - a conditional branch to the loop start.
1260 if (LastI->getOpcode() == Hexagon::J2_jumpt ||
1261 LastI->getOpcode() == Hexagon::J2_jumpf) {
1262 // Delete one and change/add an uncond. branch to out of the loop.
1263 MachineBasicBlock *BranchTarget = LastI->getOperand(1).getMBB();
1264 LastI = LastMBB->erase(LastI);
1265 if (!L->contains(BranchTarget)) {
1266 if (LastI != LastMBB->end())
1267 LastI = LastMBB->erase(LastI);
1268 SmallVector<MachineOperand, 0> Cond;
1269 TII->insertBranch(*LastMBB, BranchTarget, nullptr, Cond, LastIDL);
1270 }
1271 } else {
1272 // Conditional branch to loop start; just delete it.
1273 LastMBB->erase(LastI);
1274 }
1275 delete TripCount;
1276
1277 // The induction operation and the comparison may now be
1278 // unneeded. If these are unneeded, then remove them.
1279 for (unsigned i = 0; i < OldInsts.size(); ++i)
1280 removeIfDead(OldInsts[i]);
1281
1282 ++NumHWLoops;
1283
1284 // Set RecL1used and RecL0used only after hardware loop has been
1285 // successfully generated. Doing it earlier can cause wrong loop instruction
1286 // to be used.
1287 if (L0Used) // Loop0 was already used. So, the correct loop must be loop1.
1288 RecL1used = true;
1289 else
1290 RecL0used = true;
1291
1292 return true;
1293}
1294
1295bool HexagonHardwareLoops::orderBumpCompare(MachineInstr *BumpI,
1296 MachineInstr *CmpI) {
1297 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-5.0~svn298304/lib/Target/Hexagon/HexagonHardwareLoops.cpp"
, 1297, __PRETTY_FUNCTION__))
;
1298
1299 MachineBasicBlock *BB = BumpI->getParent();
1300 if (CmpI->getParent() != BB)
1301 return false;
1302
1303 typedef MachineBasicBlock::instr_iterator instr_iterator;
1304 // Check if things are in order to begin with.
1305 for (instr_iterator I(BumpI), E = BB->instr_end(); I != E; ++I)
1306 if (&*I == CmpI)
1307 return true;
1308
1309 // Out of order.
1310 unsigned PredR = CmpI->getOperand(0).getReg();
1311 bool FoundBump = false;
1312 instr_iterator CmpIt = CmpI->getIterator(), NextIt = std::next(CmpIt);
1313 for (instr_iterator I = NextIt, E = BB->instr_end(); I != E; ++I) {
1314 MachineInstr *In = &*I;
1315 for (unsigned i = 0, n = In->getNumOperands(); i < n; ++i) {
1316 MachineOperand &MO = In->getOperand(i);
1317 if (MO.isReg() && MO.isUse()) {
1318 if (MO.getReg() == PredR) // Found an intervening use of PredR.
1319 return false;
1320 }
1321 }
1322
1323 if (In == BumpI) {
1324 BB->splice(++BumpI->getIterator(), BB, CmpI->getIterator());
1325 FoundBump = true;
1326 break;
1327 }
1328 }
1329 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-5.0~svn298304/lib/Target/Hexagon/HexagonHardwareLoops.cpp"
, 1329, __PRETTY_FUNCTION__))
;
1330 return FoundBump;
1331}
1332
1333/// This function is required to break recursion. Visiting phis in a loop may
1334/// result in recursion during compilation. We break the recursion by making
1335/// sure that we visit a MachineOperand and its definition in a
1336/// MachineInstruction only once. If we attempt to visit more than once, then
1337/// there is recursion, and will return false.
1338bool HexagonHardwareLoops::isLoopFeeder(MachineLoop *L, MachineBasicBlock *A,
1339 MachineInstr *MI,
1340 const MachineOperand *MO,
1341 LoopFeederMap &LoopFeederPhi) const {
1342 if (LoopFeederPhi.find(MO->getReg()) == LoopFeederPhi.end()) {
1343 const std::vector<MachineBasicBlock *> &Blocks = L->getBlocks();
1344 DEBUG(dbgs() << "\nhw_loop head, BB#" << Blocks[0]->getNumber();)do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("hwloops")) { dbgs() << "\nhw_loop head, BB#" <<
Blocks[0]->getNumber();; } } while (false)
;
1345 // Ignore all BBs that form Loop.
1346 for (unsigned i = 0, e = Blocks.size(); i != e; ++i) {
1347 MachineBasicBlock *MBB = Blocks[i];
1348 if (A == MBB)
1349 return false;
1350 }
1351 MachineInstr *Def = MRI->getVRegDef(MO->getReg());
1352 LoopFeederPhi.insert(std::make_pair(MO->getReg(), Def));
1353 return true;
1354 } else
1355 // Already visited node.
1356 return false;
1357}
1358
1359/// Return true if a Phi may generate a value that can underflow.
1360/// This function calls loopCountMayWrapOrUnderFlow for each Phi operand.
1361bool HexagonHardwareLoops::phiMayWrapOrUnderflow(
1362 MachineInstr *Phi, const MachineOperand *EndVal, MachineBasicBlock *MBB,
1363 MachineLoop *L, LoopFeederMap &LoopFeederPhi) const {
1364 assert(Phi->isPHI() && "Expecting a Phi.")((Phi->isPHI() && "Expecting a Phi.") ? static_cast
<void> (0) : __assert_fail ("Phi->isPHI() && \"Expecting a Phi.\""
, "/tmp/buildd/llvm-toolchain-snapshot-5.0~svn298304/lib/Target/Hexagon/HexagonHardwareLoops.cpp"
, 1364, __PRETTY_FUNCTION__))
;
1365 // Walk through each Phi, and its used operands. Make sure that
1366 // if there is recursion in Phi, we won't generate hardware loops.
1367 for (int i = 1, n = Phi->getNumOperands(); i < n; i += 2)
1368 if (isLoopFeeder(L, MBB, Phi, &(Phi->getOperand(i)), LoopFeederPhi))
1369 if (loopCountMayWrapOrUnderFlow(&(Phi->getOperand(i)), EndVal,
1370 Phi->getParent(), L, LoopFeederPhi))
1371 return true;
1372 return false;
1373}
1374
1375/// Return true if the induction variable can underflow in the first iteration.
1376/// An example, is an initial unsigned value that is 0 and is decrement in the
1377/// first itertion of a do-while loop. In this case, we cannot generate a
1378/// hardware loop because the endloop instruction does not decrement the loop
1379/// counter if it is <= 1. We only need to perform this analysis if the
1380/// initial value is a register.
1381///
1382/// This function assumes the initial value may underfow unless proven
1383/// otherwise. If the type is signed, then we don't care because signed
1384/// underflow is undefined. We attempt to prove the initial value is not
1385/// zero by perfoming a crude analysis of the loop counter. This function
1386/// checks if the initial value is used in any comparison prior to the loop
1387/// and, if so, assumes the comparison is a range check. This is inexact,
1388/// but will catch the simple cases.
1389bool HexagonHardwareLoops::loopCountMayWrapOrUnderFlow(
1390 const MachineOperand *InitVal, const MachineOperand *EndVal,
1391 MachineBasicBlock *MBB, MachineLoop *L,
1392 LoopFeederMap &LoopFeederPhi) const {
1393 // Only check register values since they are unknown.
1394 if (!InitVal->isReg())
1395 return false;
1396
1397 if (!EndVal->isImm())
1398 return false;
1399
1400 // A register value that is assigned an immediate is a known value, and it
1401 // won't underflow in the first iteration.
1402 int64_t Imm;
1403 if (checkForImmediate(*InitVal, Imm))
1404 return (EndVal->getImm() == Imm);
1405
1406 unsigned Reg = InitVal->getReg();
1407
1408 // We don't know the value of a physical register.
1409 if (!TargetRegisterInfo::isVirtualRegister(Reg))
1410 return true;
1411
1412 MachineInstr *Def = MRI->getVRegDef(Reg);
1413 if (!Def)
1414 return true;
1415
1416 // If the initial value is a Phi or copy and the operands may not underflow,
1417 // then the definition cannot be underflow either.
1418 if (Def->isPHI() && !phiMayWrapOrUnderflow(Def, EndVal, Def->getParent(),
1419 L, LoopFeederPhi))
1420 return false;
1421 if (Def->isCopy() && !loopCountMayWrapOrUnderFlow(&(Def->getOperand(1)),
1422 EndVal, Def->getParent(),
1423 L, LoopFeederPhi))
1424 return false;
1425
1426 // Iterate over the uses of the initial value. If the initial value is used
1427 // in a compare, then we assume this is a range check that ensures the loop
1428 // doesn't underflow. This is not an exact test and should be improved.
1429 for (MachineRegisterInfo::use_instr_nodbg_iterator I = MRI->use_instr_nodbg_begin(Reg),
1430 E = MRI->use_instr_nodbg_end(); I != E; ++I) {
1431 MachineInstr *MI = &*I;
1432 unsigned CmpReg1 = 0, CmpReg2 = 0;
1433 int CmpMask = 0, CmpValue = 0;
1434
1435 if (!TII->analyzeCompare(*MI, CmpReg1, CmpReg2, CmpMask, CmpValue))
1436 continue;
1437
1438 MachineBasicBlock *TBB = nullptr, *FBB = nullptr;
1439 SmallVector<MachineOperand, 2> Cond;
1440 if (TII->analyzeBranch(*MI->getParent(), TBB, FBB, Cond, false))
1441 continue;
1442
1443 Comparison::Kind Cmp =
1444 getComparisonKind(MI->getOpcode(), nullptr, nullptr, 0);
1445 if (Cmp == 0)
1446 continue;
1447 if (TII->predOpcodeHasNot(Cond) ^ (TBB != MBB))
1448 Cmp = Comparison::getNegatedComparison(Cmp);
1449 if (CmpReg2 != 0 && CmpReg2 == Reg)
1450 Cmp = Comparison::getSwappedComparison(Cmp);
1451
1452 // Signed underflow is undefined.
1453 if (Comparison::isSigned(Cmp))
1454 return false;
1455
1456 // Check if there is a comparison of the initial value. If the initial value
1457 // is greater than or not equal to another value, then assume this is a
1458 // range check.
1459 if ((Cmp & Comparison::G) || Cmp == Comparison::NE)
1460 return false;
1461 }
1462
1463 // OK - this is a hack that needs to be improved. We really need to analyze
1464 // the instructions performed on the initial value. This works on the simplest
1465 // cases only.
1466 if (!Def->isCopy() && !Def->isPHI())
1467 return false;
1468
1469 return true;
1470}
1471
1472bool HexagonHardwareLoops::checkForImmediate(const MachineOperand &MO,
1473 int64_t &Val) const {
1474 if (MO.isImm()) {
1475 Val = MO.getImm();
1476 return true;
1477 }
1478 if (!MO.isReg())
1479 return false;
1480
1481 // MO is a register. Check whether it is defined as an immediate value,
1482 // and if so, get the value of it in TV. That value will then need to be
1483 // processed to handle potential subregisters in MO.
1484 int64_t TV;
1485
1486 unsigned R = MO.getReg();
1487 if (!TargetRegisterInfo::isVirtualRegister(R))
1488 return false;
1489 MachineInstr *DI = MRI->getVRegDef(R);
1490 unsigned DOpc = DI->getOpcode();
1491 switch (DOpc) {
1492 case TargetOpcode::COPY:
1493 case Hexagon::A2_tfrsi:
1494 case Hexagon::A2_tfrpi:
1495 case Hexagon::CONST32:
1496 case Hexagon::CONST64: {
1497 // Call recursively to avoid an extra check whether operand(1) is
1498 // indeed an immediate (it could be a global address, for example),
1499 // plus we can handle COPY at the same time.
1500 if (!checkForImmediate(DI->getOperand(1), TV))
1501 return false;
1502 break;
1503 }
1504 case Hexagon::A2_combineii:
1505 case Hexagon::A4_combineir:
1506 case Hexagon::A4_combineii:
1507 case Hexagon::A4_combineri:
1508 case Hexagon::A2_combinew: {
1509 const MachineOperand &S1 = DI->getOperand(1);
1510 const MachineOperand &S2 = DI->getOperand(2);
1511 int64_t V1, V2;
1512 if (!checkForImmediate(S1, V1) || !checkForImmediate(S2, V2))
1513 return false;
1514 TV = V2 | (static_cast<uint64_t>(V1) << 32);
1515 break;
1516 }
1517 case TargetOpcode::REG_SEQUENCE: {
1518 const MachineOperand &S1 = DI->getOperand(1);
1519 const MachineOperand &S3 = DI->getOperand(3);
1520 int64_t V1, V3;
1521 if (!checkForImmediate(S1, V1) || !checkForImmediate(S3, V3))
1522 return false;
1523 unsigned Sub2 = DI->getOperand(2).getImm();
1524 unsigned Sub4 = DI->getOperand(4).getImm();
1525 if (Sub2 == Hexagon::isub_lo && Sub4 == Hexagon::isub_hi)
1526 TV = V1 | (V3 << 32);
1527 else if (Sub2 == Hexagon::isub_hi && Sub4 == Hexagon::isub_lo)
1528 TV = V3 | (V1 << 32);
1529 else
1530 llvm_unreachable("Unexpected form of REG_SEQUENCE")::llvm::llvm_unreachable_internal("Unexpected form of REG_SEQUENCE"
, "/tmp/buildd/llvm-toolchain-snapshot-5.0~svn298304/lib/Target/Hexagon/HexagonHardwareLoops.cpp"
, 1530)
;
1531 break;
1532 }
1533
1534 default:
1535 return false;
1536 }
1537
1538 // By now, we should have successfully obtained the immediate value defining
1539 // the register referenced in MO. Handle a potential use of a subregister.
1540 switch (MO.getSubReg()) {
1541 case Hexagon::isub_lo:
1542 Val = TV & 0xFFFFFFFFULL;
1543 break;
1544 case Hexagon::isub_hi:
1545 Val = (TV >> 32) & 0xFFFFFFFFULL;
1546 break;
1547 default:
1548 Val = TV;
1549 break;
1550 }
1551 return true;
1552}
1553
1554void HexagonHardwareLoops::setImmediate(MachineOperand &MO, int64_t Val) {
1555 if (MO.isImm()) {
1556 MO.setImm(Val);
1557 return;
1558 }
1559
1560 assert(MO.isReg())((MO.isReg()) ? static_cast<void> (0) : __assert_fail (
"MO.isReg()", "/tmp/buildd/llvm-toolchain-snapshot-5.0~svn298304/lib/Target/Hexagon/HexagonHardwareLoops.cpp"
, 1560, __PRETTY_FUNCTION__))
;
1561 unsigned R = MO.getReg();
1562 MachineInstr *DI = MRI->getVRegDef(R);
1563
1564 const TargetRegisterClass *RC = MRI->getRegClass(R);
1565 unsigned NewR = MRI->createVirtualRegister(RC);
1566 MachineBasicBlock &B = *DI->getParent();
1567 DebugLoc DL = DI->getDebugLoc();
1568 BuildMI(B, DI, DL, TII->get(DI->getOpcode()), NewR).addImm(Val);
1569 MO.setReg(NewR);
1570}
1571
1572static bool isImmValidForOpcode(unsigned CmpOpc, int64_t Imm) {
1573 // These two instructions are not extendable.
1574 if (CmpOpc == Hexagon::A4_cmpbeqi)
1575 return isUInt<8>(Imm);
1576 if (CmpOpc == Hexagon::A4_cmpbgti)
1577 return isInt<8>(Imm);
1578 // The rest of the comparison-with-immediate instructions are extendable.
1579 return true;
1580}
1581
1582bool HexagonHardwareLoops::fixupInductionVariable(MachineLoop *L) {
1583 MachineBasicBlock *Header = L->getHeader();
1584 MachineBasicBlock *Latch = L->getLoopLatch();
1585 MachineBasicBlock *ExitingBlock = L->findLoopControlBlock();
1586
1587 if (!(Header && Latch && ExitingBlock))
1588 return false;
1589
1590 // These data structures follow the same concept as the corresponding
1591 // ones in findInductionRegister (where some comments are).
1592 typedef std::pair<unsigned,int64_t> RegisterBump;
1593 typedef std::pair<unsigned,RegisterBump> RegisterInduction;
1594 typedef std::set<RegisterInduction> RegisterInductionSet;
1595
1596 // Register candidates for induction variables, with their associated bumps.
1597 RegisterInductionSet IndRegs;
1598
1599 // Look for induction patterns:
1600 // vreg1 = PHI ..., [ latch, vreg2 ]
1601 // vreg2 = ADD vreg1, imm
1602 typedef MachineBasicBlock::instr_iterator instr_iterator;
1603 for (instr_iterator I = Header->instr_begin(), E = Header->instr_end();
1604 I != E && I->isPHI(); ++I) {
1605 MachineInstr *Phi = &*I;
1606
1607 // Have a PHI instruction.
1608 for (unsigned i = 1, n = Phi->getNumOperands(); i < n; i += 2) {
1609 if (Phi->getOperand(i+1).getMBB() != Latch)
1610 continue;
1611
1612 unsigned PhiReg = Phi->getOperand(i).getReg();
1613 MachineInstr *DI = MRI->getVRegDef(PhiReg);
1614
1615 if (DI->getDesc().isAdd()) {
1616 // If the register operand to the add/sub is the PHI we are looking
1617 // at, this meets the induction pattern.
1618 unsigned IndReg = DI->getOperand(1).getReg();
1619 MachineOperand &Opnd2 = DI->getOperand(2);
1620 int64_t V;
1621 if (MRI->getVRegDef(IndReg) == Phi && checkForImmediate(Opnd2, V)) {
1622 unsigned UpdReg = DI->getOperand(0).getReg();
1623 IndRegs.insert(std::make_pair(UpdReg, std::make_pair(IndReg, V)));
1624 }
1625 }
1626 } // for (i)
1627 } // for (instr)
1628
1629 if (IndRegs.empty())
1630 return false;
1631
1632 MachineBasicBlock *TB = nullptr, *FB = nullptr;
1633 SmallVector<MachineOperand,2> Cond;
1634 // AnalyzeBranch returns true if it fails to analyze branch.
1635 bool NotAnalyzed = TII->analyzeBranch(*ExitingBlock, TB, FB, Cond, false);
1636 if (NotAnalyzed || Cond.empty())
1637 return false;
1638
1639 if (ExitingBlock != Latch && (TB == Latch || FB == Latch)) {
1640 MachineBasicBlock *LTB = nullptr, *LFB = nullptr;
1641 SmallVector<MachineOperand,2> LCond;
1642 bool NotAnalyzed = TII->analyzeBranch(*Latch, LTB, LFB, LCond, false);
1643 if (NotAnalyzed)
1644 return false;
1645
1646 // Since latch is not the exiting block, the latch branch should be an
1647 // unconditional branch to the loop header.
1648 if (TB == Latch)
1649 TB = (LTB == Header) ? LTB : LFB;
1650 else
1651 FB = (LTB == Header) ? LTB : LFB;
1652 }
1653 if (TB != Header) {
1654 if (FB != Header) {
1655 // The latch/exit block does not go back to the header.
1656 return false;
1657 }
1658 // FB is the header (i.e., uncond. jump to branch header)
1659 // In this case, the LoopBody -> TB should not be a back edge otherwise
1660 // it could result in an infinite loop after conversion to hw_loop.
1661 // This case can happen when the Latch has two jumps like this:
1662 // Jmp_c OuterLoopHeader <-- TB
1663 // Jmp InnerLoopHeader <-- FB
1664 if (MDT->dominates(TB, FB))
1665 return false;
1666 }
1667
1668 // Expecting a predicate register as a condition. It won't be a hardware
1669 // predicate register at this point yet, just a vreg.
1670 // HexagonInstrInfo::AnalyzeBranch for negated branches inserts imm(0)
1671 // into Cond, followed by the predicate register. For non-negated branches
1672 // it's just the register.
1673 unsigned CSz = Cond.size();
1674 if (CSz != 1 && CSz != 2)
1675 return false;
1676
1677 if (!Cond[CSz-1].isReg())
1678 return false;
1679
1680 unsigned P = Cond[CSz-1].getReg();
1681 MachineInstr *PredDef = MRI->getVRegDef(P);
1682
1683 if (!PredDef->isCompare())
1684 return false;
1685
1686 SmallSet<unsigned,2> CmpRegs;
1687 MachineOperand *CmpImmOp = nullptr;
1688
1689 // Go over all operands to the compare and look for immediate and register
1690 // operands. Assume that if the compare has a single register use and a
1691 // single immediate operand, then the register is being compared with the
1692 // immediate value.
1693 for (unsigned i = 0, n = PredDef->getNumOperands(); i < n; ++i) {
1694 MachineOperand &MO = PredDef->getOperand(i);
1695 if (MO.isReg()) {
1696 // Skip all implicit references. In one case there was:
1697 // %vreg140<def> = FCMPUGT32_rr %vreg138, %vreg139, %USR<imp-use>
1698 if (MO.isImplicit())
1699 continue;
1700 if (MO.isUse()) {
1701 if (!isImmediate(MO)) {
1702 CmpRegs.insert(MO.getReg());
1703 continue;
1704 }
1705 // Consider the register to be the "immediate" operand.
1706 if (CmpImmOp)
1707 return false;
1708 CmpImmOp = &MO;
1709 }
1710 } else if (MO.isImm()) {
1711 if (CmpImmOp) // A second immediate argument? Confusing. Bail out.
1712 return false;
1713 CmpImmOp = &MO;
1714 }
1715 }
1716
1717 if (CmpRegs.empty())
1718 return false;
1719
1720 // Check if the compared register follows the order we want. Fix if needed.
1721 for (RegisterInductionSet::iterator I = IndRegs.begin(), E = IndRegs.end();
1722 I != E; ++I) {
1723 // This is a success. If the register used in the comparison is one that
1724 // we have identified as a bumped (updated) induction register, there is
1725 // nothing to do.
1726 if (CmpRegs.count(I->first))
1727 return true;
1728
1729 // Otherwise, if the register being compared comes out of a PHI node,
1730 // and has been recognized as following the induction pattern, and is
1731 // compared against an immediate, we can fix it.
1732 const RegisterBump &RB = I->second;
1733 if (CmpRegs.count(RB.first)) {
1734 if (!CmpImmOp) {
1735 // If both operands to the compare instruction are registers, see if
1736 // it can be changed to use induction register as one of the operands.
1737 MachineInstr *IndI = nullptr;
1738 MachineInstr *nonIndI = nullptr;
1739 MachineOperand *IndMO = nullptr;
1740 MachineOperand *nonIndMO = nullptr;
1741
1742 for (unsigned i = 1, n = PredDef->getNumOperands(); i < n; ++i) {
1743 MachineOperand &MO = PredDef->getOperand(i);
1744 if (MO.isReg() && MO.getReg() == RB.first) {
1745 DEBUG(dbgs() << "\n DefMI(" << i << ") = "do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("hwloops")) { dbgs() << "\n DefMI(" << i <<
") = " << *(MRI->getVRegDef(I->first)); } } while
(false)
1746 << *(MRI->getVRegDef(I->first)))do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("hwloops")) { dbgs() << "\n DefMI(" << i <<
") = " << *(MRI->getVRegDef(I->first)); } } while
(false)
;
1747 if (IndI)
1748 return false;
1749
1750 IndI = MRI->getVRegDef(I->first);
1751 IndMO = &MO;
1752 } else if (MO.isReg()) {
1753 DEBUG(dbgs() << "\n DefMI(" << i << ") = "do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("hwloops")) { dbgs() << "\n DefMI(" << i <<
") = " << *(MRI->getVRegDef(MO.getReg())); } } while
(false)
1754 << *(MRI->getVRegDef(MO.getReg())))do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("hwloops")) { dbgs() << "\n DefMI(" << i <<
") = " << *(MRI->getVRegDef(MO.getReg())); } } while
(false)
;
1755 if (nonIndI)
1756 return false;
1757
1758 nonIndI = MRI->getVRegDef(MO.getReg());
1759 nonIndMO = &MO;
1760 }
1761 }
1762 if (IndI && nonIndI &&
1763 nonIndI->getOpcode() == Hexagon::A2_addi &&
1764 nonIndI->getOperand(2).isImm() &&
1765 nonIndI->getOperand(2).getImm() == - RB.second) {
1766 bool Order = orderBumpCompare(IndI, PredDef);
1767 if (Order) {
1768 IndMO->setReg(I->first);
1769 nonIndMO->setReg(nonIndI->getOperand(1).getReg());
1770 return true;
1771 }
1772 }
1773 return false;
1774 }
1775
1776 // It is not valid to do this transformation on an unsigned comparison
1777 // because it may underflow.
1778 Comparison::Kind Cmp =
1779 getComparisonKind(PredDef->getOpcode(), nullptr, nullptr, 0);
1780 if (!Cmp || Comparison::isUnsigned(Cmp))
1781 return false;
1782
1783 // If the register is being compared against an immediate, try changing
1784 // the compare instruction to use induction register and adjust the
1785 // immediate operand.
1786 int64_t CmpImm = getImmediate(*CmpImmOp);
1787 int64_t V = RB.second;
1788 // Handle Overflow (64-bit).
1789 if (((V > 0) && (CmpImm > INT64_MAX(9223372036854775807L) - V)) ||
1790 ((V < 0) && (CmpImm < INT64_MIN(-9223372036854775807L -1) - V)))
1791 return false;
1792 CmpImm += V;
1793 // Most comparisons of register against an immediate value allow
1794 // the immediate to be constant-extended. There are some exceptions
1795 // though. Make sure the new combination will work.
1796 if (CmpImmOp->isImm())
1797 if (!isImmValidForOpcode(PredDef->getOpcode(), CmpImm))
1798 return false;
1799
1800 // Make sure that the compare happens after the bump. Otherwise,
1801 // after the fixup, the compare would use a yet-undefined register.
1802 MachineInstr *BumpI = MRI->getVRegDef(I->first);
1803 bool Order = orderBumpCompare(BumpI, PredDef);
1804 if (!Order)
1805 return false;
1806
1807 // Finally, fix the compare instruction.
1808 setImmediate(*CmpImmOp, CmpImm);
1809 for (unsigned i = 0, n = PredDef->getNumOperands(); i < n; ++i) {
1810 MachineOperand &MO = PredDef->getOperand(i);
1811 if (MO.isReg() && MO.getReg() == RB.first) {
1812 MO.setReg(I->first);
1813 return true;
1814 }
1815 }
1816 }
1817 }
1818
1819 return false;
1820}
1821
1822/// createPreheaderForLoop - Create a preheader for a given loop.
1823MachineBasicBlock *HexagonHardwareLoops::createPreheaderForLoop(
1824 MachineLoop *L) {
1825 if (MachineBasicBlock *TmpPH = MLI->findLoopPreheader(L, SpecPreheader))
1826 return TmpPH;
1827 if (!HWCreatePreheader)
1828 return nullptr;
1829
1830 MachineBasicBlock *Header = L->getHeader();
1831 MachineBasicBlock *Latch = L->getLoopLatch();
1832 MachineBasicBlock *ExitingBlock = L->findLoopControlBlock();
1833 MachineFunction *MF = Header->getParent();
1834 DebugLoc DL;
1835
1836#ifndef NDEBUG
1837 if ((PHFn != "") && (PHFn != MF->getName()))
1838 return nullptr;
1839#endif
1840
1841 if (!Latch || !ExitingBlock || Header->hasAddressTaken())
1842 return nullptr;
1843
1844 typedef MachineBasicBlock::instr_iterator instr_iterator;
1845
1846 // Verify that all existing predecessors have analyzable branches
1847 // (or no branches at all).
1848 typedef std::vector<MachineBasicBlock*> MBBVector;
1849 MBBVector Preds(Header->pred_begin(), Header->pred_end());
1850 SmallVector<MachineOperand,2> Tmp1;
1851 MachineBasicBlock *TB = nullptr, *FB = nullptr;
1852
1853 if (TII->analyzeBranch(*ExitingBlock, TB, FB, Tmp1, false))
1854 return nullptr;
1855
1856 for (MBBVector::iterator I = Preds.begin(), E = Preds.end(); I != E; ++I) {
1857 MachineBasicBlock *PB = *I;
1858 bool NotAnalyzed = TII->analyzeBranch(*PB, TB, FB, Tmp1, false);
1859 if (NotAnalyzed)
1860 return nullptr;
1861 }
1862
1863 MachineBasicBlock *NewPH = MF->CreateMachineBasicBlock();
1864 MF->insert(Header->getIterator(), NewPH);
1865
1866 if (Header->pred_size() > 2) {
1867 // Ensure that the header has only two predecessors: the preheader and
1868 // the loop latch. Any additional predecessors of the header should
1869 // join at the newly created preheader. Inspect all PHI nodes from the
1870 // header and create appropriate corresponding PHI nodes in the preheader.
1871
1872 for (instr_iterator I = Header->instr_begin(), E = Header->instr_end();
1873 I != E && I->isPHI(); ++I) {
1874 MachineInstr *PN = &*I;
1875
1876 const MCInstrDesc &PD = TII->get(TargetOpcode::PHI);
1877 MachineInstr *NewPN = MF->CreateMachineInstr(PD, DL);
1878 NewPH->insert(NewPH->end(), NewPN);
1879
1880 unsigned PR = PN->getOperand(0).getReg();
1881 const TargetRegisterClass *RC = MRI->getRegClass(PR);
1882 unsigned NewPR = MRI->createVirtualRegister(RC);
1883 NewPN->addOperand(MachineOperand::CreateReg(NewPR, true));
1884
1885 // Copy all non-latch operands of a header's PHI node to the newly
1886 // created PHI node in the preheader.
1887 for (unsigned i = 1, n = PN->getNumOperands(); i < n; i += 2) {
1888 unsigned PredR = PN->getOperand(i).getReg();
1889 unsigned PredRSub = PN->getOperand(i).getSubReg();
1890 MachineBasicBlock *PredB = PN->getOperand(i+1).getMBB();
1891 if (PredB == Latch)
1892 continue;
1893
1894 MachineOperand MO = MachineOperand::CreateReg(PredR, false);
1895 MO.setSubReg(PredRSub);
1896 NewPN->addOperand(MO);
1897 NewPN->addOperand(MachineOperand::CreateMBB(PredB));
1898 }
1899
1900 // Remove copied operands from the old PHI node and add the value
1901 // coming from the preheader's PHI.
1902 for (int i = PN->getNumOperands()-2; i > 0; i -= 2) {
1903 MachineBasicBlock *PredB = PN->getOperand(i+1).getMBB();
1904 if (PredB != Latch) {
1905 PN->RemoveOperand(i+1);
1906 PN->RemoveOperand(i);
1907 }
1908 }
1909 PN->addOperand(MachineOperand::CreateReg(NewPR, false));
1910 PN->addOperand(MachineOperand::CreateMBB(NewPH));
1911 }
1912 } else {
1913 assert(Header->pred_size() == 2)((Header->pred_size() == 2) ? static_cast<void> (0) :
__assert_fail ("Header->pred_size() == 2", "/tmp/buildd/llvm-toolchain-snapshot-5.0~svn298304/lib/Target/Hexagon/HexagonHardwareLoops.cpp"
, 1913, __PRETTY_FUNCTION__))
;
1914
1915 // The header has only two predecessors, but the non-latch predecessor
1916 // is not a preheader (e.g. it has other successors, etc.)
1917 // In such a case we don't need any extra PHI nodes in the new preheader,
1918 // all we need is to adjust existing PHIs in the header to now refer to
1919 // the new preheader.
1920 for (instr_iterator I = Header->instr_begin(), E = Header->instr_end();
1921 I != E && I->isPHI(); ++I) {
1922 MachineInstr *PN = &*I;
1923 for (unsigned i = 1, n = PN->getNumOperands(); i < n; i += 2) {
1924 MachineOperand &MO = PN->getOperand(i+1);
1925 if (MO.getMBB() != Latch)
1926 MO.setMBB(NewPH);
1927 }
1928 }
1929 }
1930
1931 // "Reroute" the CFG edges to link in the new preheader.
1932 // If any of the predecessors falls through to the header, insert a branch
1933 // to the new preheader in that place.
1934 SmallVector<MachineOperand,1> Tmp2;
1935 SmallVector<MachineOperand,1> EmptyCond;
1936
1937 TB = FB = nullptr;
1938
1939 for (MBBVector::iterator I = Preds.begin(), E = Preds.end(); I != E; ++I) {
1940 MachineBasicBlock *PB = *I;
1941 if (PB != Latch) {
1942 Tmp2.clear();
1943 bool NotAnalyzed = TII->analyzeBranch(*PB, TB, FB, Tmp2, false);
1944 (void)NotAnalyzed; // suppress compiler warning
1945 assert (!NotAnalyzed && "Should be analyzable!")((!NotAnalyzed && "Should be analyzable!") ? static_cast
<void> (0) : __assert_fail ("!NotAnalyzed && \"Should be analyzable!\""
, "/tmp/buildd/llvm-toolchain-snapshot-5.0~svn298304/lib/Target/Hexagon/HexagonHardwareLoops.cpp"
, 1945, __PRETTY_FUNCTION__))
;
1946 if (TB != Header && (Tmp2.empty() || FB != Header))
1947 TII->insertBranch(*PB, NewPH, nullptr, EmptyCond, DL);
1948 PB->ReplaceUsesOfBlockWith(Header, NewPH);
1949 }
1950 }
1951
1952 // It can happen that the latch block will fall through into the header.
1953 // Insert an unconditional branch to the header.
1954 TB = FB = nullptr;
1955 bool LatchNotAnalyzed = TII->analyzeBranch(*Latch, TB, FB, Tmp2, false);
1956 (void)LatchNotAnalyzed; // suppress compiler warning
1957 assert (!LatchNotAnalyzed && "Should be analyzable!")((!LatchNotAnalyzed && "Should be analyzable!") ? static_cast
<void> (0) : __assert_fail ("!LatchNotAnalyzed && \"Should be analyzable!\""
, "/tmp/buildd/llvm-toolchain-snapshot-5.0~svn298304/lib/Target/Hexagon/HexagonHardwareLoops.cpp"
, 1957, __PRETTY_FUNCTION__))
;
1958 if (!TB && !FB)
1959 TII->insertBranch(*Latch, Header, nullptr, EmptyCond, DL);
1960
1961 // Finally, the branch from the preheader to the header.
1962 TII->insertBranch(*NewPH, Header, nullptr, EmptyCond, DL);
1963 NewPH->addSuccessor(Header);
1964
1965 MachineLoop *ParentLoop = L->getParentLoop();
1966 if (ParentLoop)
1967 ParentLoop->addBasicBlockToLoop(NewPH, MLI->getBase());
1968
1969 // Update the dominator information with the new preheader.
1970 if (MDT) {
1971 if (MachineDomTreeNode *HN = MDT->getNode(Header)) {
1972 if (MachineDomTreeNode *DHN = HN->getIDom()) {
1973 MDT->addNewBlock(NewPH, DHN->getBlock());
1974 MDT->changeImmediateDominator(Header, NewPH);
1975 }
1976 }
1977 }
1978
1979 return NewPH;
1980}