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~svn329677/build-llvm/lib/Target/Hexagon -I /build/llvm-toolchain-snapshot-7~svn329677/lib/Target/Hexagon -I /build/llvm-toolchain-snapshot-7~svn329677/build-llvm/include -I /build/llvm-toolchain-snapshot-7~svn329677/include -U NDEBUG -internal-isystem /usr/lib/gcc/x86_64-linux-gnu/7.3.0/../../../../include/c++/7.3.0 -internal-isystem /usr/lib/gcc/x86_64-linux-gnu/7.3.0/../../../../include/x86_64-linux-gnu/c++/7.3.0 -internal-isystem /usr/lib/gcc/x86_64-linux-gnu/7.3.0/../../../../include/x86_64-linux-gnu/c++/7.3.0 -internal-isystem /usr/lib/gcc/x86_64-linux-gnu/7.3.0/../../../../include/c++/7.3.0/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/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-comment -std=c++11 -fdeprecated-macro -fdebug-compilation-dir /build/llvm-toolchain-snapshot-7~svn329677/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-checker optin.performance.Padding -analyzer-output=html -analyzer-config stable-report-filename=true -o /tmp/scan-build-2018-04-11-031539-24776-1 -x c++ /build/llvm-toolchain-snapshot-7~svn329677/lib/Target/Hexagon/HexagonHardwareLoops.cpp
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~svn329677/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 /// \brief 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 /// \brief 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 /// \brief 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 /// \brief 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 /// \brief 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 /// \brief 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 /// \brief 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 /// \brief Return true if the instruction is now dead.
223 bool isDead(const MachineInstr *MI,
224 SmallVectorImpl<MachineInstr *> &DeadPhis) const;
225
226 /// \brief Remove the instruction if it is now dead.
227 void removeIfDead(MachineInstr *MI);
228
229 /// \brief 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 /// \brief 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 /// \brief 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 /// \brief 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 /// \brief 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 /// \brief 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 /// \brief 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~svn329677/lib/Target/Hexagon/HexagonHardwareLoops.cpp"
, 270)
;
271 return V;
272 }
273
274 /// \brief 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 /// \brief 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 /// \brief 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 /// \brief 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~svn329677/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~svn329677/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~svn329677/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 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/// \brief 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~svn329677/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~svn329677/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~svn329677/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~svn329677/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/// \brief 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~svn329677/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~svn329677/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/// \brief 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/// \brief 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 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 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)
;
1023 return true;
1024 }
1025 }
1026 }
1027 return false;
1028}
1029
1030/// \brief Returns true if the instruction is dead. This was essentially
1031/// copied from DeadMachineInstructionElim::isDead, but with special cases
1032/// for inline asm, physical registers and instructions with side effects
1033/// removed.
1034bool HexagonHardwareLoops::isDead(const MachineInstr *MI,
1035 SmallVectorImpl<MachineInstr *> &DeadPhis) const {
1036 // Examine each operand.
1037 for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) {
1038 const MachineOperand &MO = MI->getOperand(i);
1039 if (!MO.isReg() || !MO.isDef())
1040 continue;
1041
1042 unsigned Reg = MO.getReg();
1043 if (MRI->use_nodbg_empty(Reg))
1044 continue;
1045
1046 using use_nodbg_iterator = MachineRegisterInfo::use_nodbg_iterator;
1047
1048 // This instruction has users, but if the only user is the phi node for the
1049 // parent block, and the only use of that phi node is this instruction, then
1050 // this instruction is dead: both it (and the phi node) can be removed.
1051 use_nodbg_iterator I = MRI->use_nodbg_begin(Reg);
1052 use_nodbg_iterator End = MRI->use_nodbg_end();
1053 if (std::next(I) != End || !I->getParent()->isPHI())
1054 return false;
1055
1056 MachineInstr *OnePhi = I->getParent();
1057 for (unsigned j = 0, f = OnePhi->getNumOperands(); j != f; ++j) {
1058 const MachineOperand &OPO = OnePhi->getOperand(j);
1059 if (!OPO.isReg() || !OPO.isDef())
1060 continue;
1061
1062 unsigned OPReg = OPO.getReg();
1063 use_nodbg_iterator nextJ;
1064 for (use_nodbg_iterator J = MRI->use_nodbg_begin(OPReg);
1065 J != End; J = nextJ) {
1066 nextJ = std::next(J);
1067 MachineOperand &Use = *J;
1068 MachineInstr *UseMI = Use.getParent();
1069
1070 // If the phi node has a user that is not MI, bail.
1071 if (MI != UseMI)
1072 return false;
1073 }
1074 }
1075 DeadPhis.push_back(OnePhi);
1076 }
1077
1078 // If there are no defs with uses, the instruction is dead.
1079 return true;
1080}
1081
1082void HexagonHardwareLoops::removeIfDead(MachineInstr *MI) {
1083 // This procedure was essentially copied from DeadMachineInstructionElim.
1084
1085 SmallVector<MachineInstr*, 1> DeadPhis;
1086 if (isDead(MI, DeadPhis)) {
1087 DEBUG(dbgs() << "HW looping will remove: " << *MI)do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("hwloops")) { dbgs() << "HW looping will remove: " <<
*MI; } } while (false)
;
1088
1089 // It is possible that some DBG_VALUE instructions refer to this
1090 // instruction. Examine each def operand for such references;
1091 // if found, mark the DBG_VALUE as undef (but don't delete it).
1092 for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) {
1093 const MachineOperand &MO = MI->getOperand(i);
1094 if (!MO.isReg() || !MO.isDef())
1095 continue;
1096 unsigned Reg = MO.getReg();
1097 MachineRegisterInfo::use_iterator nextI;
1098 for (MachineRegisterInfo::use_iterator I = MRI->use_begin(Reg),
1099 E = MRI->use_end(); I != E; I = nextI) {
1100 nextI = std::next(I); // I is invalidated by the setReg
1101 MachineOperand &Use = *I;
1102 MachineInstr *UseMI = I->getParent();
1103 if (UseMI == MI)
1104 continue;
1105 if (Use.isDebug())
1106 UseMI->getOperand(0).setReg(0U);
1107 }
1108 }
1109
1110 MI->eraseFromParent();
1111 for (unsigned i = 0; i < DeadPhis.size(); ++i)
1112 DeadPhis[i]->eraseFromParent();
1113 }
1114}
1115
1116/// \brief Check if the loop is a candidate for converting to a hardware
1117/// loop. If so, then perform the transformation.
1118///
1119/// This function works on innermost loops first. A loop can be converted
1120/// if it is a counting loop; either a register value or an immediate.
1121///
1122/// The code makes several assumptions about the representation of the loop
1123/// in llvm.
1124bool HexagonHardwareLoops::convertToHardwareLoop(MachineLoop *L,
1125 bool &RecL0used,
1126 bool &RecL1used) {
1127 // This is just for sanity.
1128 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~svn329677/lib/Target/Hexagon/HexagonHardwareLoops.cpp"
, 1128, __extension__ __PRETTY_FUNCTION__))
;
1129
1130 bool Changed = false;
1131 bool L0Used = false;
1132 bool L1Used = false;
1133
1134 // Process nested loops first.
1135 for (MachineLoop::iterator I = L->begin(), E = L->end(); I != E; ++I) {
1136 Changed |= convertToHardwareLoop(*I, RecL0used, RecL1used);
1137 L0Used |= RecL0used;
1138 L1Used |= RecL1used;
1139 }
1140
1141 // If a nested loop has been converted, then we can't convert this loop.
1142 if (Changed && L0Used && L1Used)
1143 return Changed;
1144
1145 unsigned LOOP_i;
1146 unsigned LOOP_r;
1147 unsigned ENDLOOP;
1148
1149 // Flag used to track loopN instruction:
1150 // 1 - Hardware loop is being generated for the inner most loop.
1151 // 0 - Hardware loop is being generated for the outer loop.
1152 unsigned IsInnerHWLoop = 1;
1153
1154 if (L0Used) {
1155 LOOP_i = Hexagon::J2_loop1i;
1156 LOOP_r = Hexagon::J2_loop1r;
1157 ENDLOOP = Hexagon::ENDLOOP1;
1158 IsInnerHWLoop = 0;
1159 } else {
1160 LOOP_i = Hexagon::J2_loop0i;
1161 LOOP_r = Hexagon::J2_loop0r;
1162 ENDLOOP = Hexagon::ENDLOOP0;
1163 }
1164
1165#ifndef NDEBUG
1166 // Stop trying after reaching the limit (if any).
1167 int Limit = HWLoopLimit;
1168 if (Limit >= 0) {
1169 if (Counter >= HWLoopLimit)
1170 return false;
1171 Counter++;
1172 }
1173#endif
1174
1175 // Does the loop contain any invalid instructions?
1176 if (containsInvalidInstruction(L, IsInnerHWLoop))
1177 return false;
1178
1179 MachineBasicBlock *LastMBB = L->findLoopControlBlock();
1180 // Don't generate hw loop if the loop has more than one exit.
1181 if (!LastMBB)
1182 return false;
1183
1184 MachineBasicBlock::iterator LastI = LastMBB->getFirstTerminator();
1185 if (LastI == LastMBB->end())
1186 return false;
1187
1188 // Is the induction variable bump feeding the latch condition?
1189 if (!fixupInductionVariable(L))
1190 return false;
1191
1192 // Ensure the loop has a preheader: the loop instruction will be
1193 // placed there.
1194 MachineBasicBlock *Preheader = MLI->findLoopPreheader(L, SpecPreheader);
1195 if (!Preheader) {
1196 Preheader = createPreheaderForLoop(L);
1197 if (!Preheader)
1198 return false;
1199 }
1200
1201 MachineBasicBlock::iterator InsertPos = Preheader->getFirstTerminator();
1202
1203 SmallVector<MachineInstr*, 2> OldInsts;
1204 // Are we able to determine the trip count for the loop?
1205 CountValue *TripCount = getLoopTripCount(L, OldInsts);
1206 if (!TripCount)
1207 return false;
1208
1209 // Is the trip count available in the preheader?
1210 if (TripCount->isReg()) {
1211 // There will be a use of the register inserted into the preheader,
1212 // so make sure that the register is actually defined at that point.
1213 MachineInstr *TCDef = MRI->getVRegDef(TripCount->getReg());
1214 MachineBasicBlock *BBDef = TCDef->getParent();
1215 if (!MDT->dominates(BBDef, Preheader))
1216 return false;
1217 }
1218
1219 // Determine the loop start.
1220 MachineBasicBlock *TopBlock = L->getTopBlock();
1221 MachineBasicBlock *ExitingBlock = L->findLoopControlBlock();
1222 MachineBasicBlock *LoopStart = nullptr;
1223 if (ExitingBlock != L->getLoopLatch()) {
1224 MachineBasicBlock *TB = nullptr, *FB = nullptr;
1225 SmallVector<MachineOperand, 2> Cond;
1226
1227 if (TII->analyzeBranch(*ExitingBlock, TB, FB, Cond, false))
1228 return false;
1229
1230 if (L->contains(TB))
1231 LoopStart = TB;
1232 else if (L->contains(FB))
1233 LoopStart = FB;
1234 else
1235 return false;
1236 }
1237 else
1238 LoopStart = TopBlock;
1239
1240 // Convert the loop to a hardware loop.
1241 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)
;
1242 DebugLoc DL;
1243 if (InsertPos != Preheader->end())
1244 DL = InsertPos->getDebugLoc();
1245
1246 if (TripCount->isReg()) {
1247 // Create a copy of the loop count register.
1248 unsigned CountReg = MRI->createVirtualRegister(&Hexagon::IntRegsRegClass);
1249 BuildMI(*Preheader, InsertPos, DL, TII->get(TargetOpcode::COPY), CountReg)
1250 .addReg(TripCount->getReg(), 0, TripCount->getSubReg());
1251 // Add the Loop instruction to the beginning of the loop.
1252 BuildMI(*Preheader, InsertPos, DL, TII->get(LOOP_r)).addMBB(LoopStart)
1253 .addReg(CountReg);
1254 } else {
1255 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~svn329677/lib/Target/Hexagon/HexagonHardwareLoops.cpp"
, 1255, __extension__ __PRETTY_FUNCTION__))
;
1256 // Add the Loop immediate instruction to the beginning of the loop,
1257 // if the immediate fits in the instructions. Otherwise, we need to
1258 // create a new virtual register.
1259 int64_t CountImm = TripCount->getImm();
1260 if (!TII->isValidOffset(LOOP_i, CountImm, TRI)) {
1261 unsigned CountReg = MRI->createVirtualRegister(&Hexagon::IntRegsRegClass);
1262 BuildMI(*Preheader, InsertPos, DL, TII->get(Hexagon::A2_tfrsi), CountReg)
1263 .addImm(CountImm);
1264 BuildMI(*Preheader, InsertPos, DL, TII->get(LOOP_r))
1265 .addMBB(LoopStart).addReg(CountReg);
1266 } else
1267 BuildMI(*Preheader, InsertPos, DL, TII->get(LOOP_i))
1268 .addMBB(LoopStart).addImm(CountImm);
1269 }
1270
1271 // Make sure the loop start always has a reference in the CFG. We need
1272 // to create a BlockAddress operand to get this mechanism to work both the
1273 // MachineBasicBlock and BasicBlock objects need the flag set.
1274 LoopStart->setHasAddressTaken();
1275 // This line is needed to set the hasAddressTaken flag on the BasicBlock
1276 // object.
1277 BlockAddress::get(const_cast<BasicBlock *>(LoopStart->getBasicBlock()));
1278
1279 // Replace the loop branch with an endloop instruction.
1280 DebugLoc LastIDL = LastI->getDebugLoc();
1281 BuildMI(*LastMBB, LastI, LastIDL, TII->get(ENDLOOP)).addMBB(LoopStart);
1282
1283 // The loop ends with either:
1284 // - a conditional branch followed by an unconditional branch, or
1285 // - a conditional branch to the loop start.
1286 if (LastI->getOpcode() == Hexagon::J2_jumpt ||
1287 LastI->getOpcode() == Hexagon::J2_jumpf) {
1288 // Delete one and change/add an uncond. branch to out of the loop.
1289 MachineBasicBlock *BranchTarget = LastI->getOperand(1).getMBB();
1290 LastI = LastMBB->erase(LastI);
1291 if (!L->contains(BranchTarget)) {
1292 if (LastI != LastMBB->end())
1293 LastI = LastMBB->erase(LastI);
1294 SmallVector<MachineOperand, 0> Cond;
1295 TII->insertBranch(*LastMBB, BranchTarget, nullptr, Cond, LastIDL);
1296 }
1297 } else {
1298 // Conditional branch to loop start; just delete it.
1299 LastMBB->erase(LastI);
1300 }
1301 delete TripCount;
1302
1303 // The induction operation and the comparison may now be
1304 // unneeded. If these are unneeded, then remove them.
1305 for (unsigned i = 0; i < OldInsts.size(); ++i)
1306 removeIfDead(OldInsts[i]);
1307
1308 ++NumHWLoops;
1309
1310 // Set RecL1used and RecL0used only after hardware loop has been
1311 // successfully generated. Doing it earlier can cause wrong loop instruction
1312 // to be used.
1313 if (L0Used) // Loop0 was already used. So, the correct loop must be loop1.
1314 RecL1used = true;
1315 else
1316 RecL0used = true;
1317
1318 return true;
1319}
1320
1321bool HexagonHardwareLoops::orderBumpCompare(MachineInstr *BumpI,
1322 MachineInstr *CmpI) {
1323 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~svn329677/lib/Target/Hexagon/HexagonHardwareLoops.cpp"
, 1323, __extension__ __PRETTY_FUNCTION__))
;
1324
1325 MachineBasicBlock *BB = BumpI->getParent();
1326 if (CmpI->getParent() != BB)
1327 return false;
1328
1329 using instr_iterator = MachineBasicBlock::instr_iterator;
1330
1331 // Check if things are in order to begin with.
1332 for (instr_iterator I(BumpI), E = BB->instr_end(); I != E; ++I)
1333 if (&*I == CmpI)
1334 return true;
1335
1336 // Out of order.
1337 unsigned PredR = CmpI->getOperand(0).getReg();
1338 bool FoundBump = false;
1339 instr_iterator CmpIt = CmpI->getIterator(), NextIt = std::next(CmpIt);
1340 for (instr_iterator I = NextIt, E = BB->instr_end(); I != E; ++I) {
1341 MachineInstr *In = &*I;
1342 for (unsigned i = 0, n = In->getNumOperands(); i < n; ++i) {
1343 MachineOperand &MO = In->getOperand(i);
1344 if (MO.isReg() && MO.isUse()) {
1345 if (MO.getReg() == PredR) // Found an intervening use of PredR.
1346 return false;
1347 }
1348 }
1349
1350 if (In == BumpI) {
1351 BB->splice(++BumpI->getIterator(), BB, CmpI->getIterator());
1352 FoundBump = true;
1353 break;
1354 }
1355 }
1356 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~svn329677/lib/Target/Hexagon/HexagonHardwareLoops.cpp"
, 1356, __extension__ __PRETTY_FUNCTION__))
;
1357 return FoundBump;
1358}
1359
1360/// This function is required to break recursion. Visiting phis in a loop may
1361/// result in recursion during compilation. We break the recursion by making
1362/// sure that we visit a MachineOperand and its definition in a
1363/// MachineInstruction only once. If we attempt to visit more than once, then
1364/// there is recursion, and will return false.
1365bool HexagonHardwareLoops::isLoopFeeder(MachineLoop *L, MachineBasicBlock *A,
1366 MachineInstr *MI,
1367 const MachineOperand *MO,
1368 LoopFeederMap &LoopFeederPhi) const {
1369 if (LoopFeederPhi.find(MO->getReg()) == LoopFeederPhi.end()) {
1370 const std::vector<MachineBasicBlock *> &Blocks = L->getBlocks();
1371 DEBUG(dbgs() << "\nhw_loop head, " << printMBBReference(*Blocks[0]))do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("hwloops")) { dbgs() << "\nhw_loop head, " << printMBBReference
(*Blocks[0]); } } while (false)
;
1372 // Ignore all BBs that form Loop.
1373 for (unsigned i = 0, e = Blocks.size(); i != e; ++i) {
1374 MachineBasicBlock *MBB = Blocks[i];
1375 if (A == MBB)
1376 return false;
1377 }
1378 MachineInstr *Def = MRI->getVRegDef(MO->getReg());
1379 LoopFeederPhi.insert(std::make_pair(MO->getReg(), Def));
1380 return true;
1381 } else
1382 // Already visited node.
1383 return false;
1384}
1385
1386/// Return true if a Phi may generate a value that can underflow.
1387/// This function calls loopCountMayWrapOrUnderFlow for each Phi operand.
1388bool HexagonHardwareLoops::phiMayWrapOrUnderflow(
1389 MachineInstr *Phi, const MachineOperand *EndVal, MachineBasicBlock *MBB,
1390 MachineLoop *L, LoopFeederMap &LoopFeederPhi) const {
1391 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~svn329677/lib/Target/Hexagon/HexagonHardwareLoops.cpp"
, 1391, __extension__ __PRETTY_FUNCTION__))
;
1392 // Walk through each Phi, and its used operands. Make sure that
1393 // if there is recursion in Phi, we won't generate hardware loops.
1394 for (int i = 1, n = Phi->getNumOperands(); i < n; i += 2)
1395 if (isLoopFeeder(L, MBB, Phi, &(Phi->getOperand(i)), LoopFeederPhi))
1396 if (loopCountMayWrapOrUnderFlow(&(Phi->getOperand(i)), EndVal,
1397 Phi->getParent(), L, LoopFeederPhi))
1398 return true;
1399 return false;
1400}
1401
1402/// Return true if the induction variable can underflow in the first iteration.
1403/// An example, is an initial unsigned value that is 0 and is decrement in the
1404/// first itertion of a do-while loop. In this case, we cannot generate a
1405/// hardware loop because the endloop instruction does not decrement the loop
1406/// counter if it is <= 1. We only need to perform this analysis if the
1407/// initial value is a register.
1408///
1409/// This function assumes the initial value may underfow unless proven
1410/// otherwise. If the type is signed, then we don't care because signed
1411/// underflow is undefined. We attempt to prove the initial value is not
1412/// zero by perfoming a crude analysis of the loop counter. This function
1413/// checks if the initial value is used in any comparison prior to the loop
1414/// and, if so, assumes the comparison is a range check. This is inexact,
1415/// but will catch the simple cases.
1416bool HexagonHardwareLoops::loopCountMayWrapOrUnderFlow(
1417 const MachineOperand *InitVal, const MachineOperand *EndVal,
1418 MachineBasicBlock *MBB, MachineLoop *L,
1419 LoopFeederMap &LoopFeederPhi) const {
1420 // Only check register values since they are unknown.
1421 if (!InitVal->isReg())
1422 return false;
1423
1424 if (!EndVal->isImm())
1425 return false;
1426
1427 // A register value that is assigned an immediate is a known value, and it
1428 // won't underflow in the first iteration.
1429 int64_t Imm;
1430 if (checkForImmediate(*InitVal, Imm))
1431 return (EndVal->getImm() == Imm);
1432
1433 unsigned Reg = InitVal->getReg();
1434
1435 // We don't know the value of a physical register.
1436 if (!TargetRegisterInfo::isVirtualRegister(Reg))
1437 return true;
1438
1439 MachineInstr *Def = MRI->getVRegDef(Reg);
1440 if (!Def)
1441 return true;
1442
1443 // If the initial value is a Phi or copy and the operands may not underflow,
1444 // then the definition cannot be underflow either.
1445 if (Def->isPHI() && !phiMayWrapOrUnderflow(Def, EndVal, Def->getParent(),
1446 L, LoopFeederPhi))
1447 return false;
1448 if (Def->isCopy() && !loopCountMayWrapOrUnderFlow(&(Def->getOperand(1)),
1449 EndVal, Def->getParent(),
1450 L, LoopFeederPhi))
1451 return false;
1452
1453 // Iterate over the uses of the initial value. If the initial value is used
1454 // in a compare, then we assume this is a range check that ensures the loop
1455 // doesn't underflow. This is not an exact test and should be improved.
1456 for (MachineRegisterInfo::use_instr_nodbg_iterator I = MRI->use_instr_nodbg_begin(Reg),
1457 E = MRI->use_instr_nodbg_end(); I != E; ++I) {
1458 MachineInstr *MI = &*I;
1459 unsigned CmpReg1 = 0, CmpReg2 = 0;
1460 int CmpMask = 0, CmpValue = 0;
1461
1462 if (!TII->analyzeCompare(*MI, CmpReg1, CmpReg2, CmpMask, CmpValue))
1463 continue;
1464
1465 MachineBasicBlock *TBB = nullptr, *FBB = nullptr;
1466 SmallVector<MachineOperand, 2> Cond;
1467 if (TII->analyzeBranch(*MI->getParent(), TBB, FBB, Cond, false))
1468 continue;
1469
1470 Comparison::Kind Cmp =
1471 getComparisonKind(MI->getOpcode(), nullptr, nullptr, 0);
1472 if (Cmp == 0)
1473 continue;
1474 if (TII->predOpcodeHasNot(Cond) ^ (TBB != MBB))
1475 Cmp = Comparison::getNegatedComparison(Cmp);
1476 if (CmpReg2 != 0 && CmpReg2 == Reg)
1477 Cmp = Comparison::getSwappedComparison(Cmp);
1478
1479 // Signed underflow is undefined.
1480 if (Comparison::isSigned(Cmp))
1481 return false;
1482
1483 // Check if there is a comparison of the initial value. If the initial value
1484 // is greater than or not equal to another value, then assume this is a
1485 // range check.
1486 if ((Cmp & Comparison::G) || Cmp == Comparison::NE)
1487 return false;
1488 }
1489
1490 // OK - this is a hack that needs to be improved. We really need to analyze
1491 // the instructions performed on the initial value. This works on the simplest
1492 // cases only.
1493 if (!Def->isCopy() && !Def->isPHI())
1494 return false;
1495
1496 return true;
1497}
1498
1499bool HexagonHardwareLoops::checkForImmediate(const MachineOperand &MO,
1500 int64_t &Val) const {
1501 if (MO.isImm()) {
1502 Val = MO.getImm();
1503 return true;
1504 }
1505 if (!MO.isReg())
1506 return false;
1507
1508 // MO is a register. Check whether it is defined as an immediate value,
1509 // and if so, get the value of it in TV. That value will then need to be
1510 // processed to handle potential subregisters in MO.
1511 int64_t TV;
1512
1513 unsigned R = MO.getReg();
1514 if (!TargetRegisterInfo::isVirtualRegister(R))
1515 return false;
1516 MachineInstr *DI = MRI->getVRegDef(R);
1517 unsigned DOpc = DI->getOpcode();
1518 switch (DOpc) {
1519 case TargetOpcode::COPY:
1520 case Hexagon::A2_tfrsi:
1521 case Hexagon::A2_tfrpi:
1522 case Hexagon::CONST32:
1523 case Hexagon::CONST64:
1524 // Call recursively to avoid an extra check whether operand(1) is
1525 // indeed an immediate (it could be a global address, for example),
1526 // plus we can handle COPY at the same time.
1527 if (!checkForImmediate(DI->getOperand(1), TV))
1528 return false;
1529 break;
1530 case Hexagon::A2_combineii:
1531 case Hexagon::A4_combineir:
1532 case Hexagon::A4_combineii:
1533 case Hexagon::A4_combineri:
1534 case Hexagon::A2_combinew: {
1535 const MachineOperand &S1 = DI->getOperand(1);
1536 const MachineOperand &S2 = DI->getOperand(2);
1537 int64_t V1, V2;
1538 if (!checkForImmediate(S1, V1) || !checkForImmediate(S2, V2))
1539 return false;
1540 TV = V2 | (static_cast<uint64_t>(V1) << 32);
1541 break;
1542 }
1543 case TargetOpcode::REG_SEQUENCE: {
1544 const MachineOperand &S1 = DI->getOperand(1);
1545 const MachineOperand &S3 = DI->getOperand(3);
1546 int64_t V1, V3;
1547 if (!checkForImmediate(S1, V1) || !checkForImmediate(S3, V3))
1548 return false;
1549 unsigned Sub2 = DI->getOperand(2).getImm();
1550 unsigned Sub4 = DI->getOperand(4).getImm();
1551 if (Sub2 == Hexagon::isub_lo && Sub4 == Hexagon::isub_hi)
1552 TV = V1 | (V3 << 32);
1553 else if (Sub2 == Hexagon::isub_hi && Sub4 == Hexagon::isub_lo)
1554 TV = V3 | (V1 << 32);
1555 else
1556 llvm_unreachable("Unexpected form of REG_SEQUENCE")::llvm::llvm_unreachable_internal("Unexpected form of REG_SEQUENCE"
, "/build/llvm-toolchain-snapshot-7~svn329677/lib/Target/Hexagon/HexagonHardwareLoops.cpp"
, 1556)
;
1557 break;
1558 }
1559
1560 default:
1561 return false;
1562 }
1563
1564 // By now, we should have successfully obtained the immediate value defining
1565 // the register referenced in MO. Handle a potential use of a subregister.
1566 switch (MO.getSubReg()) {
1567 case Hexagon::isub_lo:
1568 Val = TV & 0xFFFFFFFFULL;
1569 break;
1570 case Hexagon::isub_hi:
1571 Val = (TV >> 32) & 0xFFFFFFFFULL;
1572 break;
1573 default:
1574 Val = TV;
1575 break;
1576 }
1577 return true;
1578}
1579
1580void HexagonHardwareLoops::setImmediate(MachineOperand &MO, int64_t Val) {
1581 if (MO.isImm()) {
1582 MO.setImm(Val);
1583 return;
1584 }
1585
1586 assert(MO.isReg())(static_cast <bool> (MO.isReg()) ? void (0) : __assert_fail
("MO.isReg()", "/build/llvm-toolchain-snapshot-7~svn329677/lib/Target/Hexagon/HexagonHardwareLoops.cpp"
, 1586, __extension__ __PRETTY_FUNCTION__))
;
1587 unsigned R = MO.getReg();
1588 MachineInstr *DI = MRI->getVRegDef(R);
1589
1590 const TargetRegisterClass *RC = MRI->getRegClass(R);
1591 unsigned NewR = MRI->createVirtualRegister(RC);
1592 MachineBasicBlock &B = *DI->getParent();
1593 DebugLoc DL = DI->getDebugLoc();
1594 BuildMI(B, DI, DL, TII->get(DI->getOpcode()), NewR).addImm(Val);
1595 MO.setReg(NewR);
1596}
1597
1598static bool isImmValidForOpcode(unsigned CmpOpc, int64_t Imm) {
1599 // These two instructions are not extendable.
1600 if (CmpOpc == Hexagon::A4_cmpbeqi)
1601 return isUInt<8>(Imm);
1602 if (CmpOpc == Hexagon::A4_cmpbgti)
1603 return isInt<8>(Imm);
1604 // The rest of the comparison-with-immediate instructions are extendable.
1605 return true;
1606}
1607
1608bool HexagonHardwareLoops::fixupInductionVariable(MachineLoop *L) {
1609 MachineBasicBlock *Header = L->getHeader();
1610 MachineBasicBlock *Latch = L->getLoopLatch();
1611 MachineBasicBlock *ExitingBlock = L->findLoopControlBlock();
1612
1613 if (!(Header && Latch && ExitingBlock))
1614 return false;
1615
1616 // These data structures follow the same concept as the corresponding
1617 // ones in findInductionRegister (where some comments are).
1618 using RegisterBump = std::pair<unsigned, int64_t>;
1619 using RegisterInduction = std::pair<unsigned, RegisterBump>;
1620 using RegisterInductionSet = std::set<RegisterInduction>;
1621
1622 // Register candidates for induction variables, with their associated bumps.
1623 RegisterInductionSet IndRegs;
1624
1625 // Look for induction patterns:
1626 // %1 = PHI ..., [ latch, %2 ]
1627 // %2 = ADD %1, imm
1628 using instr_iterator = MachineBasicBlock::instr_iterator;
1629
1630 for (instr_iterator I = Header->instr_begin(), E = Header->instr_end();
1631 I != E && I->isPHI(); ++I) {
1632 MachineInstr *Phi = &*I;
1633
1634 // Have a PHI instruction.
1635 for (unsigned i = 1, n = Phi->getNumOperands(); i < n; i += 2) {
1636 if (Phi->getOperand(i+1).getMBB() != Latch)
1637 continue;
1638
1639 unsigned PhiReg = Phi->getOperand(i).getReg();
1640 MachineInstr *DI = MRI->getVRegDef(PhiReg);
1641
1642 if (DI->getDesc().isAdd()) {
1643 // If the register operand to the add/sub is the PHI we are looking
1644 // at, this meets the induction pattern.
1645 unsigned IndReg = DI->getOperand(1).getReg();
1646 MachineOperand &Opnd2 = DI->getOperand(2);
1647 int64_t V;
1648 if (MRI->getVRegDef(IndReg) == Phi && checkForImmediate(Opnd2, V)) {
1649 unsigned UpdReg = DI->getOperand(0).getReg();
1650 IndRegs.insert(std::make_pair(UpdReg, std::make_pair(IndReg, V)));
1651 }
1652 }
1653 } // for (i)
1654 } // for (instr)
1655
1656 if (IndRegs.empty())
1657 return false;
1658
1659 MachineBasicBlock *TB = nullptr, *FB = nullptr;
1660 SmallVector<MachineOperand,2> Cond;
1661 // AnalyzeBranch returns true if it fails to analyze branch.
1662 bool NotAnalyzed = TII->analyzeBranch(*ExitingBlock, TB, FB, Cond, false);
1663 if (NotAnalyzed || Cond.empty())
1664 return false;
1665
1666 if (ExitingBlock != Latch && (TB == Latch || FB == Latch)) {
1667 MachineBasicBlock *LTB = nullptr, *LFB = nullptr;
1668 SmallVector<MachineOperand,2> LCond;
1669 bool NotAnalyzed = TII->analyzeBranch(*Latch, LTB, LFB, LCond, false);
1670 if (NotAnalyzed)
1671 return false;
1672
1673 // Since latch is not the exiting block, the latch branch should be an
1674 // unconditional branch to the loop header.
1675 if (TB == Latch)
1676 TB = (LTB == Header) ? LTB : LFB;
1677 else
1678 FB = (LTB == Header) ? LTB : LFB;
1679 }
1680 if (TB != Header) {
1681 if (FB != Header) {
1682 // The latch/exit block does not go back to the header.
1683 return false;
1684 }
1685 // FB is the header (i.e., uncond. jump to branch header)
1686 // In this case, the LoopBody -> TB should not be a back edge otherwise
1687 // it could result in an infinite loop after conversion to hw_loop.
1688 // This case can happen when the Latch has two jumps like this:
1689 // Jmp_c OuterLoopHeader <-- TB
1690 // Jmp InnerLoopHeader <-- FB
1691 if (MDT->dominates(TB, FB))
1692 return false;
1693 }
1694
1695 // Expecting a predicate register as a condition. It won't be a hardware
1696 // predicate register at this point yet, just a vreg.
1697 // HexagonInstrInfo::AnalyzeBranch for negated branches inserts imm(0)
1698 // into Cond, followed by the predicate register. For non-negated branches
1699 // it's just the register.
1700 unsigned CSz = Cond.size();
1701 if (CSz != 1 && CSz != 2)
1702 return false;
1703
1704 if (!Cond[CSz-1].isReg())
1705 return false;
1706
1707 unsigned P = Cond[CSz-1].getReg();
1708 MachineInstr *PredDef = MRI->getVRegDef(P);
1709
1710 if (!PredDef->isCompare())
1711 return false;
1712
1713 SmallSet<unsigned,2> CmpRegs;
1714 MachineOperand *CmpImmOp = nullptr;
1715
1716 // Go over all operands to the compare and look for immediate and register
1717 // operands. Assume that if the compare has a single register use and a
1718 // single immediate operand, then the register is being compared with the
1719 // immediate value.
1720 for (unsigned i = 0, n = PredDef->getNumOperands(); i < n; ++i) {
1721 MachineOperand &MO = PredDef->getOperand(i);
1722 if (MO.isReg()) {
1723 // Skip all implicit references. In one case there was:
1724 // %140 = FCMPUGT32_rr %138, %139, implicit %usr
1725 if (MO.isImplicit())
1726 continue;
1727 if (MO.isUse()) {
1728 if (!isImmediate(MO)) {
1729 CmpRegs.insert(MO.getReg());
1730 continue;
1731 }
1732 // Consider the register to be the "immediate" operand.
1733 if (CmpImmOp)
1734 return false;
1735 CmpImmOp = &MO;
1736 }
1737 } else if (MO.isImm()) {
1738 if (CmpImmOp) // A second immediate argument? Confusing. Bail out.
1739 return false;
1740 CmpImmOp = &MO;
1741 }
1742 }
1743
1744 if (CmpRegs.empty())
1745 return false;
1746
1747 // Check if the compared register follows the order we want. Fix if needed.
1748 for (RegisterInductionSet::iterator I = IndRegs.begin(), E = IndRegs.end();
1749 I != E; ++I) {
1750 // This is a success. If the register used in the comparison is one that
1751 // we have identified as a bumped (updated) induction register, there is
1752 // nothing to do.
1753 if (CmpRegs.count(I->first))
1754 return true;
1755
1756 // Otherwise, if the register being compared comes out of a PHI node,
1757 // and has been recognized as following the induction pattern, and is
1758 // compared against an immediate, we can fix it.
1759 const RegisterBump &RB = I->second;
1760 if (CmpRegs.count(RB.first)) {
1761 if (!CmpImmOp) {
1762 // If both operands to the compare instruction are registers, see if
1763 // it can be changed to use induction register as one of the operands.
1764 MachineInstr *IndI = nullptr;
1765 MachineInstr *nonIndI = nullptr;
1766 MachineOperand *IndMO = nullptr;
1767 MachineOperand *nonIndMO = nullptr;
1768
1769 for (unsigned i = 1, n = PredDef->getNumOperands(); i < n; ++i) {
1770 MachineOperand &MO = PredDef->getOperand(i);
1771 if (MO.isReg() && MO.getReg() == RB.first) {
1772 DEBUG(dbgs() << "\n DefMI(" << i << ") = "do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("hwloops")) { dbgs() << "\n DefMI(" << i <<
") = " << *(MRI->getVRegDef(I->first)); } } while
(false)
1773 << *(MRI->getVRegDef(I->first)))do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("hwloops")) { dbgs() << "\n DefMI(" << i <<
") = " << *(MRI->getVRegDef(I->first)); } } while
(false)
;
1774 if (IndI)
1775 return false;
1776
1777 IndI = MRI->getVRegDef(I->first);
1778 IndMO = &MO;
1779 } else if (MO.isReg()) {
1780 DEBUG(dbgs() << "\n DefMI(" << i << ") = "do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("hwloops")) { dbgs() << "\n DefMI(" << i <<
") = " << *(MRI->getVRegDef(MO.getReg())); } } while
(false)
1781 << *(MRI->getVRegDef(MO.getReg())))do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("hwloops")) { dbgs() << "\n DefMI(" << i <<
") = " << *(MRI->getVRegDef(MO.getReg())); } } while
(false)
;
1782 if (nonIndI)
1783 return false;
1784
1785 nonIndI = MRI->getVRegDef(MO.getReg());
1786 nonIndMO = &MO;
1787 }
1788 }
1789 if (IndI && nonIndI &&
1790 nonIndI->getOpcode() == Hexagon::A2_addi &&
1791 nonIndI->getOperand(2).isImm() &&
1792 nonIndI->getOperand(2).getImm() == - RB.second) {
1793 bool Order = orderBumpCompare(IndI, PredDef);
1794 if (Order) {
1795 IndMO->setReg(I->first);
1796 nonIndMO->setReg(nonIndI->getOperand(1).getReg());
1797 return true;
1798 }
1799 }
1800 return false;
1801 }
1802
1803 // It is not valid to do this transformation on an unsigned comparison
1804 // because it may underflow.
1805 Comparison::Kind Cmp =
1806 getComparisonKind(PredDef->getOpcode(), nullptr, nullptr, 0);
1807 if (!Cmp || Comparison::isUnsigned(Cmp))
1808 return false;
1809
1810 // If the register is being compared against an immediate, try changing
1811 // the compare instruction to use induction register and adjust the
1812 // immediate operand.
1813 int64_t CmpImm = getImmediate(*CmpImmOp);
1814 int64_t V = RB.second;
1815 // Handle Overflow (64-bit).
1816 if (((V > 0) && (CmpImm > INT64_MAX(9223372036854775807L) - V)) ||
1817 ((V < 0) && (CmpImm < INT64_MIN(-9223372036854775807L -1) - V)))
1818 return false;
1819 CmpImm += V;
1820 // Most comparisons of register against an immediate value allow
1821 // the immediate to be constant-extended. There are some exceptions
1822 // though. Make sure the new combination will work.
1823 if (CmpImmOp->isImm())
1824 if (!isImmValidForOpcode(PredDef->getOpcode(), CmpImm))
1825 return false;
1826
1827 // Make sure that the compare happens after the bump. Otherwise,
1828 // after the fixup, the compare would use a yet-undefined register.
1829 MachineInstr *BumpI = MRI->getVRegDef(I->first);
1830 bool Order = orderBumpCompare(BumpI, PredDef);
1831 if (!Order)
1832 return false;
1833
1834 // Finally, fix the compare instruction.
1835 setImmediate(*CmpImmOp, CmpImm);
1836 for (unsigned i = 0, n = PredDef->getNumOperands(); i < n; ++i) {
1837 MachineOperand &MO = PredDef->getOperand(i);
1838 if (MO.isReg() && MO.getReg() == RB.first) {
1839 MO.setReg(I->first);
1840 return true;
1841 }
1842 }
1843 }
1844 }
1845
1846 return false;
1847}
1848
1849/// createPreheaderForLoop - Create a preheader for a given loop.
1850MachineBasicBlock *HexagonHardwareLoops::createPreheaderForLoop(
1851 MachineLoop *L) {
1852 if (MachineBasicBlock *TmpPH = MLI->findLoopPreheader(L, SpecPreheader))
1853 return TmpPH;
1854 if (!HWCreatePreheader)
1855 return nullptr;
1856
1857 MachineBasicBlock *Header = L->getHeader();
1858 MachineBasicBlock *Latch = L->getLoopLatch();
1859 MachineBasicBlock *ExitingBlock = L->findLoopControlBlock();
1860 MachineFunction *MF = Header->getParent();
1861 DebugLoc DL;
1862
1863#ifndef NDEBUG
1864 if ((!PHFn.empty()) && (PHFn != MF->getName()))
1865 return nullptr;
1866#endif
1867
1868 if (!Latch || !ExitingBlock || Header->hasAddressTaken())
1869 return nullptr;
1870
1871 using instr_iterator = MachineBasicBlock::instr_iterator;
1872
1873 // Verify that all existing predecessors have analyzable branches
1874 // (or no branches at all).
1875 using MBBVector = std::vector<MachineBasicBlock *>;
1876
1877 MBBVector Preds(Header->pred_begin(), Header->pred_end());
1878 SmallVector<MachineOperand,2> Tmp1;
1879 MachineBasicBlock *TB = nullptr, *FB = nullptr;
1880
1881 if (TII->analyzeBranch(*ExitingBlock, TB, FB, Tmp1, false))
1882 return nullptr;
1883
1884 for (MBBVector::iterator I = Preds.begin(), E = Preds.end(); I != E; ++I) {
1885 MachineBasicBlock *PB = *I;
1886 bool NotAnalyzed = TII->analyzeBranch(*PB, TB, FB, Tmp1, false);
1887 if (NotAnalyzed)
1888 return nullptr;
1889 }
1890
1891 MachineBasicBlock *NewPH = MF->CreateMachineBasicBlock();
1892 MF->insert(Header->getIterator(), NewPH);
1893
1894 if (Header->pred_size() > 2) {
1895 // Ensure that the header has only two predecessors: the preheader and
1896 // the loop latch. Any additional predecessors of the header should
1897 // join at the newly created preheader. Inspect all PHI nodes from the
1898 // header and create appropriate corresponding PHI nodes in the preheader.
1899
1900 for (instr_iterator I = Header->instr_begin(), E = Header->instr_end();
1901 I != E && I->isPHI(); ++I) {
1902 MachineInstr *PN = &*I;
1903
1904 const MCInstrDesc &PD = TII->get(TargetOpcode::PHI);
1905 MachineInstr *NewPN = MF->CreateMachineInstr(PD, DL);
1906 NewPH->insert(NewPH->end(), NewPN);
1907
1908 unsigned PR = PN->getOperand(0).getReg();
1909 const TargetRegisterClass *RC = MRI->getRegClass(PR);
1910 unsigned NewPR = MRI->createVirtualRegister(RC);
1911 NewPN->addOperand(MachineOperand::CreateReg(NewPR, true));
1912
1913 // Copy all non-latch operands of a header's PHI node to the newly
1914 // created PHI node in the preheader.
1915 for (unsigned i = 1, n = PN->getNumOperands(); i < n; i += 2) {
1916 unsigned PredR = PN->getOperand(i).getReg();
1917 unsigned PredRSub = PN->getOperand(i).getSubReg();
1918 MachineBasicBlock *PredB = PN->getOperand(i+1).getMBB();
1919 if (PredB == Latch)
1920 continue;
1921
1922 MachineOperand MO = MachineOperand::CreateReg(PredR, false);
1923 MO.setSubReg(PredRSub);
1924 NewPN->addOperand(MO);
1925 NewPN->addOperand(MachineOperand::CreateMBB(PredB));
1926 }
1927
1928 // Remove copied operands from the old PHI node and add the value
1929 // coming from the preheader's PHI.
1930 for (int i = PN->getNumOperands()-2; i > 0; i -= 2) {
1931 MachineBasicBlock *PredB = PN->getOperand(i+1).getMBB();
1932 if (PredB != Latch) {
1933 PN->RemoveOperand(i+1);
1934 PN->RemoveOperand(i);
1935 }
1936 }
1937 PN->addOperand(MachineOperand::CreateReg(NewPR, false));
1938 PN->addOperand(MachineOperand::CreateMBB(NewPH));
1939 }
1940 } else {
1941 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~svn329677/lib/Target/Hexagon/HexagonHardwareLoops.cpp"
, 1941, __extension__ __PRETTY_FUNCTION__))
;
1942
1943 // The header has only two predecessors, but the non-latch predecessor
1944 // is not a preheader (e.g. it has other successors, etc.)
1945 // In such a case we don't need any extra PHI nodes in the new preheader,
1946 // all we need is to adjust existing PHIs in the header to now refer to
1947 // the new preheader.
1948 for (instr_iterator I = Header->instr_begin(), E = Header->instr_end();
1949 I != E && I->isPHI(); ++I) {
1950 MachineInstr *PN = &*I;
1951 for (unsigned i = 1, n = PN->getNumOperands(); i < n; i += 2) {
1952 MachineOperand &MO = PN->getOperand(i+1);
1953 if (MO.getMBB() != Latch)
1954 MO.setMBB(NewPH);
1955 }
1956 }
1957 }
1958
1959 // "Reroute" the CFG edges to link in the new preheader.
1960 // If any of the predecessors falls through to the header, insert a branch
1961 // to the new preheader in that place.
1962 SmallVector<MachineOperand,1> Tmp2;
1963 SmallVector<MachineOperand,1> EmptyCond;
1964
1965 TB = FB = nullptr;
1966
1967 for (MBBVector::iterator I = Preds.begin(), E = Preds.end(); I != E; ++I) {
1968 MachineBasicBlock *PB = *I;
1969 if (PB != Latch) {
1970 Tmp2.clear();
1971 bool NotAnalyzed = TII->analyzeBranch(*PB, TB, FB, Tmp2, false);
1972 (void)NotAnalyzed; // suppress compiler warning
1973 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~svn329677/lib/Target/Hexagon/HexagonHardwareLoops.cpp"
, 1973, __extension__ __PRETTY_FUNCTION__))
;
1974 if (TB != Header && (Tmp2.empty() || FB != Header))
1975 TII->insertBranch(*PB, NewPH, nullptr, EmptyCond, DL);
1976 PB->ReplaceUsesOfBlockWith(Header, NewPH);
1977 }
1978 }
1979
1980 // It can happen that the latch block will fall through into the header.
1981 // Insert an unconditional branch to the header.
1982 TB = FB = nullptr;
1983 bool LatchNotAnalyzed = TII->analyzeBranch(*Latch, TB, FB, Tmp2, false);
1984 (void)LatchNotAnalyzed; // suppress compiler warning
1985 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~svn329677/lib/Target/Hexagon/HexagonHardwareLoops.cpp"
, 1985, __extension__ __PRETTY_FUNCTION__))
;
1986 if (!TB && !FB)
1987 TII->insertBranch(*Latch, Header, nullptr, EmptyCond, DL);
1988
1989 // Finally, the branch from the preheader to the header.
1990 TII->insertBranch(*NewPH, Header, nullptr, EmptyCond, DL);
1991 NewPH->addSuccessor(Header);
1992
1993 MachineLoop *ParentLoop = L->getParentLoop();
1994 if (ParentLoop)
1995 ParentLoop->addBasicBlockToLoop(NewPH, MLI->getBase());
1996
1997 // Update the dominator information with the new preheader.
1998 if (MDT) {
1999 if (MachineDomTreeNode *HN = MDT->getNode(Header)) {
2000 if (MachineDomTreeNode *DHN = HN->getIDom()) {
2001 MDT->addNewBlock(NewPH, DHN->getBlock());
2002 MDT->changeImmediateDominator(Header, NewPH);
2003 }
2004 }
2005 }
2006
2007 return NewPH;
2008}