Bug Summary

File:lib/Target/Hexagon/HexagonHardwareLoops.cpp
Warning:line 786, column 24
Division by zero

Annotated Source Code

Press '?' to see keyboard shortcuts

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