Bug Summary

File:build/llvm-toolchain-snapshot-16~++20221003111214+1fa2019828ca/llvm/lib/Target/Hexagon/HexagonHardwareLoops.cpp
Warning:line 786, column 24
Division by zero

Annotated Source Code

Press '?' to see keyboard shortcuts

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