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