1234285Sdim//===-- HexagonHardwareLoops.cpp - Identify and generate hardware loops ---===// 2234285Sdim// 3234285Sdim// The LLVM Compiler Infrastructure 4234285Sdim// 5234285Sdim// This file is distributed under the University of Illinois Open Source 6234285Sdim// License. See LICENSE.TXT for details. 7234285Sdim// 8234285Sdim//===----------------------------------------------------------------------===// 9234285Sdim// 10234285Sdim// This pass identifies loops where we can generate the Hexagon hardware 11234285Sdim// loop instruction. The hardware loop can perform loop branches with a 12234285Sdim// zero-cycle overhead. 13234285Sdim// 14234285Sdim// The pattern that defines the induction variable can changed depending on 15234285Sdim// prior optimizations. For example, the IndVarSimplify phase run by 'opt' 16234285Sdim// normalizes induction variables, and the Loop Strength Reduction pass 17234285Sdim// run by 'llc' may also make changes to the induction variable. 18234285Sdim// The pattern detected by this phase is due to running Strength Reduction. 19234285Sdim// 20234285Sdim// Criteria for hardware loops: 21234285Sdim// - Countable loops (w/ ind. var for a trip count) 22234285Sdim// - Assumes loops are normalized by IndVarSimplify 23234285Sdim// - Try inner-most loops first 24234285Sdim// - No nested hardware loops. 25234285Sdim// - No function calls in loops. 26234285Sdim// 27234285Sdim//===----------------------------------------------------------------------===// 28234285Sdim 29234285Sdim#define DEBUG_TYPE "hwloops" 30249423Sdim#include "llvm/ADT/SmallSet.h" 31234285Sdim#include "llvm/ADT/Statistic.h" 32234285Sdim#include "llvm/CodeGen/MachineDominators.h" 33234285Sdim#include "llvm/CodeGen/MachineFunction.h" 34234285Sdim#include "llvm/CodeGen/MachineFunctionPass.h" 35234285Sdim#include "llvm/CodeGen/MachineInstrBuilder.h" 36234285Sdim#include "llvm/CodeGen/MachineLoopInfo.h" 37234285Sdim#include "llvm/CodeGen/MachineRegisterInfo.h" 38249423Sdim#include "llvm/PassSupport.h" 39249423Sdim#include "llvm/Support/CommandLine.h" 40234285Sdim#include "llvm/Support/Debug.h" 41234285Sdim#include "llvm/Support/raw_ostream.h" 42234285Sdim#include "llvm/Target/TargetInstrInfo.h" 43249423Sdim#include "Hexagon.h" 44249423Sdim#include "HexagonTargetMachine.h" 45249423Sdim 46234285Sdim#include <algorithm> 47249423Sdim#include <vector> 48234285Sdim 49234285Sdimusing namespace llvm; 50234285Sdim 51249423Sdim#ifndef NDEBUG 52249423Sdimstatic cl::opt<int> HWLoopLimit("max-hwloop", cl::Hidden, cl::init(-1)); 53249423Sdim#endif 54249423Sdim 55234285SdimSTATISTIC(NumHWLoops, "Number of loops converted to hardware loops"); 56234285Sdim 57249423Sdimnamespace llvm { 58249423Sdim void initializeHexagonHardwareLoopsPass(PassRegistry&); 59249423Sdim} 60249423Sdim 61234285Sdimnamespace { 62234285Sdim class CountValue; 63234285Sdim struct HexagonHardwareLoops : public MachineFunctionPass { 64249423Sdim MachineLoopInfo *MLI; 65249423Sdim MachineRegisterInfo *MRI; 66249423Sdim MachineDominatorTree *MDT; 67249423Sdim const HexagonTargetMachine *TM; 68249423Sdim const HexagonInstrInfo *TII; 69249423Sdim const HexagonRegisterInfo *TRI; 70249423Sdim#ifndef NDEBUG 71249423Sdim static int Counter; 72249423Sdim#endif 73234285Sdim 74234285Sdim public: 75249423Sdim static char ID; 76234285Sdim 77249423Sdim HexagonHardwareLoops() : MachineFunctionPass(ID) { 78249423Sdim initializeHexagonHardwareLoopsPass(*PassRegistry::getPassRegistry()); 79249423Sdim } 80234285Sdim 81234285Sdim virtual bool runOnMachineFunction(MachineFunction &MF); 82234285Sdim 83234285Sdim const char *getPassName() const { return "Hexagon Hardware Loops"; } 84234285Sdim 85234285Sdim virtual void getAnalysisUsage(AnalysisUsage &AU) const { 86234285Sdim AU.addRequired<MachineDominatorTree>(); 87234285Sdim AU.addRequired<MachineLoopInfo>(); 88234285Sdim MachineFunctionPass::getAnalysisUsage(AU); 89234285Sdim } 90234285Sdim 91234285Sdim private: 92249423Sdim /// Kinds of comparisons in the compare instructions. 93249423Sdim struct Comparison { 94249423Sdim enum Kind { 95249423Sdim EQ = 0x01, 96249423Sdim NE = 0x02, 97249423Sdim L = 0x04, // Less-than property. 98249423Sdim G = 0x08, // Greater-than property. 99249423Sdim U = 0x40, // Unsigned property. 100249423Sdim LTs = L, 101249423Sdim LEs = L | EQ, 102249423Sdim GTs = G, 103249423Sdim GEs = G | EQ, 104249423Sdim LTu = L | U, 105249423Sdim LEu = L | EQ | U, 106249423Sdim GTu = G | U, 107249423Sdim GEu = G | EQ | U 108249423Sdim }; 109249423Sdim 110249423Sdim static Kind getSwappedComparison(Kind Cmp) { 111249423Sdim assert ((!((Cmp & L) && (Cmp & G))) && "Malformed comparison operator"); 112249423Sdim if ((Cmp & L) || (Cmp & G)) 113249423Sdim return (Kind)(Cmp ^ (L|G)); 114249423Sdim return Cmp; 115249423Sdim } 116249423Sdim }; 117249423Sdim 118249423Sdim /// \brief Find the register that contains the loop controlling 119234285Sdim /// induction variable. 120249423Sdim /// If successful, it will return true and set the \p Reg, \p IVBump 121249423Sdim /// and \p IVOp arguments. Otherwise it will return false. 122249423Sdim /// The returned induction register is the register R that follows the 123249423Sdim /// following induction pattern: 124249423Sdim /// loop: 125249423Sdim /// R = phi ..., [ R.next, LatchBlock ] 126249423Sdim /// R.next = R + #bump 127249423Sdim /// if (R.next < #N) goto loop 128249423Sdim /// IVBump is the immediate value added to R, and IVOp is the instruction 129249423Sdim /// "R.next = R + #bump". 130249423Sdim bool findInductionRegister(MachineLoop *L, unsigned &Reg, 131249423Sdim int64_t &IVBump, MachineInstr *&IVOp) const; 132234285Sdim 133249423Sdim /// \brief Analyze the statements in a loop to determine if the loop 134249423Sdim /// has a computable trip count and, if so, return a value that represents 135249423Sdim /// the trip count expression. 136249423Sdim CountValue *getLoopTripCount(MachineLoop *L, 137263508Sdim SmallVectorImpl<MachineInstr *> &OldInsts); 138234285Sdim 139249423Sdim /// \brief Return the expression that represents the number of times 140249423Sdim /// a loop iterates. The function takes the operands that represent the 141249423Sdim /// loop start value, loop end value, and induction value. Based upon 142249423Sdim /// these operands, the function attempts to compute the trip count. 143249423Sdim /// If the trip count is not directly available (as an immediate value, 144249423Sdim /// or a register), the function will attempt to insert computation of it 145249423Sdim /// to the loop's preheader. 146249423Sdim CountValue *computeCount(MachineLoop *Loop, 147249423Sdim const MachineOperand *Start, 148249423Sdim const MachineOperand *End, 149249423Sdim unsigned IVReg, 150249423Sdim int64_t IVBump, 151249423Sdim Comparison::Kind Cmp) const; 152234285Sdim 153249423Sdim /// \brief Return true if the instruction is not valid within a hardware 154249423Sdim /// loop. 155234285Sdim bool isInvalidLoopOperation(const MachineInstr *MI) const; 156234285Sdim 157249423Sdim /// \brief Return true if the loop contains an instruction that inhibits 158249423Sdim /// using the hardware loop. 159234285Sdim bool containsInvalidInstruction(MachineLoop *L) const; 160234285Sdim 161249423Sdim /// \brief Given a loop, check if we can convert it to a hardware loop. 162249423Sdim /// If so, then perform the conversion and return true. 163234285Sdim bool convertToHardwareLoop(MachineLoop *L); 164234285Sdim 165249423Sdim /// \brief Return true if the instruction is now dead. 166249423Sdim bool isDead(const MachineInstr *MI, 167263508Sdim SmallVectorImpl<MachineInstr *> &DeadPhis) const; 168249423Sdim 169249423Sdim /// \brief Remove the instruction if it is now dead. 170249423Sdim void removeIfDead(MachineInstr *MI); 171249423Sdim 172249423Sdim /// \brief Make sure that the "bump" instruction executes before the 173249423Sdim /// compare. We need that for the IV fixup, so that the compare 174249423Sdim /// instruction would not use a bumped value that has not yet been 175249423Sdim /// defined. If the instructions are out of order, try to reorder them. 176249423Sdim bool orderBumpCompare(MachineInstr *BumpI, MachineInstr *CmpI); 177249423Sdim 178249423Sdim /// \brief Get the instruction that loads an immediate value into \p R, 179249423Sdim /// or 0 if such an instruction does not exist. 180249423Sdim MachineInstr *defWithImmediate(unsigned R); 181249423Sdim 182249423Sdim /// \brief Get the immediate value referenced to by \p MO, either for 183249423Sdim /// immediate operands, or for register operands, where the register 184249423Sdim /// was defined with an immediate value. 185249423Sdim int64_t getImmediate(MachineOperand &MO); 186249423Sdim 187249423Sdim /// \brief Reset the given machine operand to now refer to a new immediate 188249423Sdim /// value. Assumes that the operand was already referencing an immediate 189249423Sdim /// value, either directly, or via a register. 190249423Sdim void setImmediate(MachineOperand &MO, int64_t Val); 191249423Sdim 192249423Sdim /// \brief Fix the data flow of the induction varible. 193249423Sdim /// The desired flow is: phi ---> bump -+-> comparison-in-latch. 194249423Sdim /// | 195249423Sdim /// +-> back to phi 196249423Sdim /// where "bump" is the increment of the induction variable: 197249423Sdim /// iv = iv + #const. 198249423Sdim /// Due to some prior code transformations, the actual flow may look 199249423Sdim /// like this: 200249423Sdim /// phi -+-> bump ---> back to phi 201249423Sdim /// | 202249423Sdim /// +-> comparison-in-latch (against upper_bound-bump), 203249423Sdim /// i.e. the comparison that controls the loop execution may be using 204249423Sdim /// the value of the induction variable from before the increment. 205249423Sdim /// 206249423Sdim /// Return true if the loop's flow is the desired one (i.e. it's 207249423Sdim /// either been fixed, or no fixing was necessary). 208249423Sdim /// Otherwise, return false. This can happen if the induction variable 209249423Sdim /// couldn't be identified, or if the value in the latch's comparison 210249423Sdim /// cannot be adjusted to reflect the post-bump value. 211249423Sdim bool fixupInductionVariable(MachineLoop *L); 212249423Sdim 213249423Sdim /// \brief Given a loop, if it does not have a preheader, create one. 214249423Sdim /// Return the block that is the preheader. 215249423Sdim MachineBasicBlock *createPreheaderForLoop(MachineLoop *L); 216234285Sdim }; 217234285Sdim 218234285Sdim char HexagonHardwareLoops::ID = 0; 219249423Sdim#ifndef NDEBUG 220249423Sdim int HexagonHardwareLoops::Counter = 0; 221249423Sdim#endif 222234285Sdim 223249423Sdim /// \brief Abstraction for a trip count of a loop. A smaller vesrsion 224249423Sdim /// of the MachineOperand class without the concerns of changing the 225249423Sdim /// operand representation. 226234285Sdim class CountValue { 227234285Sdim public: 228234285Sdim enum CountValueType { 229234285Sdim CV_Register, 230234285Sdim CV_Immediate 231234285Sdim }; 232234285Sdim private: 233234285Sdim CountValueType Kind; 234234285Sdim union Values { 235249423Sdim struct { 236249423Sdim unsigned Reg; 237249423Sdim unsigned Sub; 238249423Sdim } R; 239249423Sdim unsigned ImmVal; 240234285Sdim } Contents; 241234285Sdim 242234285Sdim public: 243249423Sdim explicit CountValue(CountValueType t, unsigned v, unsigned u = 0) { 244249423Sdim Kind = t; 245249423Sdim if (Kind == CV_Register) { 246249423Sdim Contents.R.Reg = v; 247249423Sdim Contents.R.Sub = u; 248249423Sdim } else { 249249423Sdim Contents.ImmVal = v; 250249423Sdim } 251249423Sdim } 252234285Sdim bool isReg() const { return Kind == CV_Register; } 253234285Sdim bool isImm() const { return Kind == CV_Immediate; } 254234285Sdim 255234285Sdim unsigned getReg() const { 256234285Sdim assert(isReg() && "Wrong CountValue accessor"); 257249423Sdim return Contents.R.Reg; 258234285Sdim } 259249423Sdim unsigned getSubReg() const { 260249423Sdim assert(isReg() && "Wrong CountValue accessor"); 261249423Sdim return Contents.R.Sub; 262234285Sdim } 263249423Sdim unsigned getImm() const { 264234285Sdim assert(isImm() && "Wrong CountValue accessor"); 265234285Sdim return Contents.ImmVal; 266234285Sdim } 267234285Sdim 268234285Sdim void print(raw_ostream &OS, const TargetMachine *TM = 0) const { 269249423Sdim const TargetRegisterInfo *TRI = TM ? TM->getRegisterInfo() : 0; 270249423Sdim if (isReg()) { OS << PrintReg(Contents.R.Reg, TRI, Contents.R.Sub); } 271249423Sdim if (isImm()) { OS << Contents.ImmVal; } 272234285Sdim } 273234285Sdim }; 274249423Sdim} // end anonymous namespace 275234285Sdim 276234285Sdim 277249423SdimINITIALIZE_PASS_BEGIN(HexagonHardwareLoops, "hwloops", 278249423Sdim "Hexagon Hardware Loops", false, false) 279249423SdimINITIALIZE_PASS_DEPENDENCY(MachineDominatorTree) 280249423SdimINITIALIZE_PASS_DEPENDENCY(MachineLoopInfo) 281249423SdimINITIALIZE_PASS_END(HexagonHardwareLoops, "hwloops", 282249423Sdim "Hexagon Hardware Loops", false, false) 283234285Sdim 284234285Sdim 285249423Sdim/// \brief Returns true if the instruction is a hardware loop instruction. 286234285Sdimstatic bool isHardwareLoop(const MachineInstr *MI) { 287234285Sdim return MI->getOpcode() == Hexagon::LOOP0_r || 288234285Sdim MI->getOpcode() == Hexagon::LOOP0_i; 289234285Sdim} 290234285Sdim 291234285SdimFunctionPass *llvm::createHexagonHardwareLoops() { 292234285Sdim return new HexagonHardwareLoops(); 293234285Sdim} 294234285Sdim 295234285Sdim 296234285Sdimbool HexagonHardwareLoops::runOnMachineFunction(MachineFunction &MF) { 297234285Sdim DEBUG(dbgs() << "********* Hexagon Hardware Loops *********\n"); 298234285Sdim 299234285Sdim bool Changed = false; 300234285Sdim 301234285Sdim MLI = &getAnalysis<MachineLoopInfo>(); 302234285Sdim MRI = &MF.getRegInfo(); 303249423Sdim MDT = &getAnalysis<MachineDominatorTree>(); 304249423Sdim TM = static_cast<const HexagonTargetMachine*>(&MF.getTarget()); 305249423Sdim TII = static_cast<const HexagonInstrInfo*>(TM->getInstrInfo()); 306249423Sdim TRI = static_cast<const HexagonRegisterInfo*>(TM->getRegisterInfo()); 307234285Sdim 308234285Sdim for (MachineLoopInfo::iterator I = MLI->begin(), E = MLI->end(); 309234285Sdim I != E; ++I) { 310234285Sdim MachineLoop *L = *I; 311249423Sdim if (!L->getParentLoop()) 312234285Sdim Changed |= convertToHardwareLoop(L); 313234285Sdim } 314234285Sdim 315234285Sdim return Changed; 316234285Sdim} 317234285Sdim 318249423Sdim 319249423Sdimbool HexagonHardwareLoops::findInductionRegister(MachineLoop *L, 320249423Sdim unsigned &Reg, 321249423Sdim int64_t &IVBump, 322249423Sdim MachineInstr *&IVOp 323249423Sdim ) const { 324249423Sdim MachineBasicBlock *Header = L->getHeader(); 325249423Sdim MachineBasicBlock *Preheader = L->getLoopPreheader(); 326249423Sdim MachineBasicBlock *Latch = L->getLoopLatch(); 327249423Sdim if (!Header || !Preheader || !Latch) 328249423Sdim return false; 329249423Sdim 330249423Sdim // This pair represents an induction register together with an immediate 331249423Sdim // value that will be added to it in each loop iteration. 332249423Sdim typedef std::pair<unsigned,int64_t> RegisterBump; 333249423Sdim 334249423Sdim // Mapping: R.next -> (R, bump), where R, R.next and bump are derived 335249423Sdim // from an induction operation 336249423Sdim // R.next = R + bump 337249423Sdim // where bump is an immediate value. 338249423Sdim typedef std::map<unsigned,RegisterBump> InductionMap; 339249423Sdim 340249423Sdim InductionMap IndMap; 341249423Sdim 342249423Sdim typedef MachineBasicBlock::instr_iterator instr_iterator; 343249423Sdim for (instr_iterator I = Header->instr_begin(), E = Header->instr_end(); 344249423Sdim I != E && I->isPHI(); ++I) { 345249423Sdim MachineInstr *Phi = &*I; 346249423Sdim 347249423Sdim // Have a PHI instruction. Get the operand that corresponds to the 348249423Sdim // latch block, and see if is a result of an addition of form "reg+imm", 349249423Sdim // where the "reg" is defined by the PHI node we are looking at. 350249423Sdim for (unsigned i = 1, n = Phi->getNumOperands(); i < n; i += 2) { 351249423Sdim if (Phi->getOperand(i+1).getMBB() != Latch) 352249423Sdim continue; 353249423Sdim 354249423Sdim unsigned PhiOpReg = Phi->getOperand(i).getReg(); 355249423Sdim MachineInstr *DI = MRI->getVRegDef(PhiOpReg); 356249423Sdim unsigned UpdOpc = DI->getOpcode(); 357249423Sdim bool isAdd = (UpdOpc == Hexagon::ADD_ri); 358249423Sdim 359249423Sdim if (isAdd) { 360249423Sdim // If the register operand to the add is the PHI we're 361249423Sdim // looking at, this meets the induction pattern. 362249423Sdim unsigned IndReg = DI->getOperand(1).getReg(); 363249423Sdim if (MRI->getVRegDef(IndReg) == Phi) { 364249423Sdim unsigned UpdReg = DI->getOperand(0).getReg(); 365249423Sdim int64_t V = DI->getOperand(2).getImm(); 366249423Sdim IndMap.insert(std::make_pair(UpdReg, std::make_pair(IndReg, V))); 367249423Sdim } 368249423Sdim } 369249423Sdim } // for (i) 370249423Sdim } // for (instr) 371249423Sdim 372249423Sdim SmallVector<MachineOperand,2> Cond; 373249423Sdim MachineBasicBlock *TB = 0, *FB = 0; 374249423Sdim bool NotAnalyzed = TII->AnalyzeBranch(*Latch, TB, FB, Cond, false); 375249423Sdim if (NotAnalyzed) 376249423Sdim return false; 377249423Sdim 378249423Sdim unsigned CSz = Cond.size(); 379249423Sdim assert (CSz == 1 || CSz == 2); 380249423Sdim unsigned PredR = Cond[CSz-1].getReg(); 381249423Sdim 382249423Sdim MachineInstr *PredI = MRI->getVRegDef(PredR); 383249423Sdim if (!PredI->isCompare()) 384249423Sdim return false; 385249423Sdim 386249423Sdim unsigned CmpReg1 = 0, CmpReg2 = 0; 387249423Sdim int CmpImm = 0, CmpMask = 0; 388249423Sdim bool CmpAnalyzed = TII->analyzeCompare(PredI, CmpReg1, CmpReg2, 389249423Sdim CmpMask, CmpImm); 390249423Sdim // Fail if the compare was not analyzed, or it's not comparing a register 391249423Sdim // with an immediate value. Not checking the mask here, since we handle 392249423Sdim // the individual compare opcodes (including CMPb) later on. 393249423Sdim if (!CmpAnalyzed) 394249423Sdim return false; 395249423Sdim 396249423Sdim // Exactly one of the input registers to the comparison should be among 397249423Sdim // the induction registers. 398249423Sdim InductionMap::iterator IndMapEnd = IndMap.end(); 399249423Sdim InductionMap::iterator F = IndMapEnd; 400249423Sdim if (CmpReg1 != 0) { 401249423Sdim InductionMap::iterator F1 = IndMap.find(CmpReg1); 402249423Sdim if (F1 != IndMapEnd) 403249423Sdim F = F1; 404249423Sdim } 405249423Sdim if (CmpReg2 != 0) { 406249423Sdim InductionMap::iterator F2 = IndMap.find(CmpReg2); 407249423Sdim if (F2 != IndMapEnd) { 408249423Sdim if (F != IndMapEnd) 409249423Sdim return false; 410249423Sdim F = F2; 411249423Sdim } 412249423Sdim } 413249423Sdim if (F == IndMapEnd) 414249423Sdim return false; 415249423Sdim 416249423Sdim Reg = F->second.first; 417249423Sdim IVBump = F->second.second; 418249423Sdim IVOp = MRI->getVRegDef(F->first); 419249423Sdim return true; 420249423Sdim} 421249423Sdim 422249423Sdim 423249423Sdim/// \brief Analyze the statements in a loop to determine if the loop has 424249423Sdim/// a computable trip count and, if so, return a value that represents 425249423Sdim/// the trip count expression. 426234285Sdim/// 427249423Sdim/// This function iterates over the phi nodes in the loop to check for 428249423Sdim/// induction variable patterns that are used in the calculation for 429249423Sdim/// the number of time the loop is executed. 430249423SdimCountValue *HexagonHardwareLoops::getLoopTripCount(MachineLoop *L, 431263508Sdim SmallVectorImpl<MachineInstr *> &OldInsts) { 432234285Sdim MachineBasicBlock *TopMBB = L->getTopBlock(); 433234285Sdim MachineBasicBlock::pred_iterator PI = TopMBB->pred_begin(); 434234285Sdim assert(PI != TopMBB->pred_end() && 435234285Sdim "Loop must have more than one incoming edge!"); 436234285Sdim MachineBasicBlock *Backedge = *PI++; 437249423Sdim if (PI == TopMBB->pred_end()) // dead loop? 438249423Sdim return 0; 439234285Sdim MachineBasicBlock *Incoming = *PI++; 440249423Sdim if (PI != TopMBB->pred_end()) // multiple backedges? 441249423Sdim return 0; 442234285Sdim 443249423Sdim // Make sure there is one incoming and one backedge and determine which 444234285Sdim // is which. 445234285Sdim if (L->contains(Incoming)) { 446234285Sdim if (L->contains(Backedge)) 447234285Sdim return 0; 448234285Sdim std::swap(Incoming, Backedge); 449234285Sdim } else if (!L->contains(Backedge)) 450234285Sdim return 0; 451234285Sdim 452249423Sdim // Look for the cmp instruction to determine if we can get a useful trip 453249423Sdim // count. The trip count can be either a register or an immediate. The 454249423Sdim // location of the value depends upon the type (reg or imm). 455249423Sdim MachineBasicBlock *Latch = L->getLoopLatch(); 456249423Sdim if (!Latch) 457249423Sdim return 0; 458249423Sdim 459249423Sdim unsigned IVReg = 0; 460249423Sdim int64_t IVBump = 0; 461249423Sdim MachineInstr *IVOp; 462249423Sdim bool FoundIV = findInductionRegister(L, IVReg, IVBump, IVOp); 463249423Sdim if (!FoundIV) 464249423Sdim return 0; 465249423Sdim 466249423Sdim MachineBasicBlock *Preheader = L->getLoopPreheader(); 467249423Sdim 468249423Sdim MachineOperand *InitialValue = 0; 469249423Sdim MachineInstr *IV_Phi = MRI->getVRegDef(IVReg); 470249423Sdim for (unsigned i = 1, n = IV_Phi->getNumOperands(); i < n; i += 2) { 471249423Sdim MachineBasicBlock *MBB = IV_Phi->getOperand(i+1).getMBB(); 472249423Sdim if (MBB == Preheader) 473249423Sdim InitialValue = &IV_Phi->getOperand(i); 474249423Sdim else if (MBB == Latch) 475249423Sdim IVReg = IV_Phi->getOperand(i).getReg(); // Want IV reg after bump. 476234285Sdim } 477249423Sdim if (!InitialValue) 478249423Sdim return 0; 479234285Sdim 480249423Sdim SmallVector<MachineOperand,2> Cond; 481249423Sdim MachineBasicBlock *TB = 0, *FB = 0; 482249423Sdim bool NotAnalyzed = TII->AnalyzeBranch(*Latch, TB, FB, Cond, false); 483249423Sdim if (NotAnalyzed) 484249423Sdim return 0; 485234285Sdim 486249423Sdim MachineBasicBlock *Header = L->getHeader(); 487249423Sdim // TB must be non-null. If FB is also non-null, one of them must be 488249423Sdim // the header. Otherwise, branch to TB could be exiting the loop, and 489249423Sdim // the fall through can go to the header. 490249423Sdim assert (TB && "Latch block without a branch?"); 491249423Sdim assert ((!FB || TB == Header || FB == Header) && "Branches not to header?"); 492249423Sdim if (!TB || (FB && TB != Header && FB != Header)) 493249423Sdim return 0; 494249423Sdim 495249423Sdim // Branches of form "if (!P) ..." cause HexagonInstrInfo::AnalyzeBranch 496249423Sdim // to put imm(0), followed by P in the vector Cond. 497249423Sdim // If TB is not the header, it means that the "not-taken" path must lead 498249423Sdim // to the header. 499249423Sdim bool Negated = (Cond.size() > 1) ^ (TB != Header); 500249423Sdim unsigned PredReg = Cond[Cond.size()-1].getReg(); 501249423Sdim MachineInstr *CondI = MRI->getVRegDef(PredReg); 502249423Sdim unsigned CondOpc = CondI->getOpcode(); 503249423Sdim 504249423Sdim unsigned CmpReg1 = 0, CmpReg2 = 0; 505249423Sdim int Mask = 0, ImmValue = 0; 506249423Sdim bool AnalyzedCmp = TII->analyzeCompare(CondI, CmpReg1, CmpReg2, 507249423Sdim Mask, ImmValue); 508249423Sdim if (!AnalyzedCmp) 509249423Sdim return 0; 510249423Sdim 511249423Sdim // The comparison operator type determines how we compute the loop 512249423Sdim // trip count. 513249423Sdim OldInsts.push_back(CondI); 514249423Sdim OldInsts.push_back(IVOp); 515249423Sdim 516249423Sdim // Sadly, the following code gets information based on the position 517249423Sdim // of the operands in the compare instruction. This has to be done 518249423Sdim // this way, because the comparisons check for a specific relationship 519249423Sdim // between the operands (e.g. is-less-than), rather than to find out 520249423Sdim // what relationship the operands are in (as on PPC). 521249423Sdim Comparison::Kind Cmp; 522249423Sdim bool isSwapped = false; 523249423Sdim const MachineOperand &Op1 = CondI->getOperand(1); 524249423Sdim const MachineOperand &Op2 = CondI->getOperand(2); 525249423Sdim const MachineOperand *EndValue = 0; 526249423Sdim 527249423Sdim if (Op1.isReg()) { 528249423Sdim if (Op2.isImm() || Op1.getReg() == IVReg) 529249423Sdim EndValue = &Op2; 530249423Sdim else { 531249423Sdim EndValue = &Op1; 532249423Sdim isSwapped = true; 533249423Sdim } 534234285Sdim } 535234285Sdim 536249423Sdim if (!EndValue) 537249423Sdim return 0; 538234285Sdim 539249423Sdim switch (CondOpc) { 540249423Sdim case Hexagon::CMPEQri: 541249423Sdim case Hexagon::CMPEQrr: 542249423Sdim Cmp = !Negated ? Comparison::EQ : Comparison::NE; 543249423Sdim break; 544249423Sdim case Hexagon::CMPGTUri: 545249423Sdim case Hexagon::CMPGTUrr: 546249423Sdim Cmp = !Negated ? Comparison::GTu : Comparison::LEu; 547249423Sdim break; 548249423Sdim case Hexagon::CMPGTri: 549249423Sdim case Hexagon::CMPGTrr: 550249423Sdim Cmp = !Negated ? Comparison::GTs : Comparison::LEs; 551249423Sdim break; 552249423Sdim // Very limited support for byte/halfword compares. 553249423Sdim case Hexagon::CMPbEQri_V4: 554249423Sdim case Hexagon::CMPhEQri_V4: { 555249423Sdim if (IVBump != 1) 556249423Sdim return 0; 557234285Sdim 558249423Sdim int64_t InitV, EndV; 559249423Sdim // Since the comparisons are "ri", the EndValue should be an 560249423Sdim // immediate. Check it just in case. 561249423Sdim assert(EndValue->isImm() && "Unrecognized latch comparison"); 562249423Sdim EndV = EndValue->getImm(); 563249423Sdim // Allow InitialValue to be a register defined with an immediate. 564249423Sdim if (InitialValue->isReg()) { 565249423Sdim if (!defWithImmediate(InitialValue->getReg())) 566234285Sdim return 0; 567249423Sdim InitV = getImmediate(*InitialValue); 568234285Sdim } else { 569249423Sdim assert(InitialValue->isImm()); 570249423Sdim InitV = InitialValue->getImm(); 571234285Sdim } 572249423Sdim if (InitV >= EndV) 573249423Sdim return 0; 574249423Sdim if (CondOpc == Hexagon::CMPbEQri_V4) { 575249423Sdim if (!isInt<8>(InitV) || !isInt<8>(EndV)) 576249423Sdim return 0; 577249423Sdim } else { // Hexagon::CMPhEQri_V4 578249423Sdim if (!isInt<16>(InitV) || !isInt<16>(EndV)) 579249423Sdim return 0; 580249423Sdim } 581249423Sdim Cmp = !Negated ? Comparison::EQ : Comparison::NE; 582249423Sdim break; 583234285Sdim } 584249423Sdim default: 585249423Sdim return 0; 586234285Sdim } 587249423Sdim 588249423Sdim if (isSwapped) 589249423Sdim Cmp = Comparison::getSwappedComparison(Cmp); 590249423Sdim 591249423Sdim if (InitialValue->isReg()) { 592249423Sdim unsigned R = InitialValue->getReg(); 593249423Sdim MachineBasicBlock *DefBB = MRI->getVRegDef(R)->getParent(); 594249423Sdim if (!MDT->properlyDominates(DefBB, Header)) 595249423Sdim return 0; 596249423Sdim OldInsts.push_back(MRI->getVRegDef(R)); 597249423Sdim } 598249423Sdim if (EndValue->isReg()) { 599249423Sdim unsigned R = EndValue->getReg(); 600249423Sdim MachineBasicBlock *DefBB = MRI->getVRegDef(R)->getParent(); 601249423Sdim if (!MDT->properlyDominates(DefBB, Header)) 602249423Sdim return 0; 603249423Sdim } 604249423Sdim 605249423Sdim return computeCount(L, InitialValue, EndValue, IVReg, IVBump, Cmp); 606234285Sdim} 607234285Sdim 608249423Sdim/// \brief Helper function that returns the expression that represents the 609249423Sdim/// number of times a loop iterates. The function takes the operands that 610249423Sdim/// represent the loop start value, loop end value, and induction value. 611249423Sdim/// Based upon these operands, the function attempts to compute the trip count. 612249423SdimCountValue *HexagonHardwareLoops::computeCount(MachineLoop *Loop, 613249423Sdim const MachineOperand *Start, 614249423Sdim const MachineOperand *End, 615249423Sdim unsigned IVReg, 616249423Sdim int64_t IVBump, 617249423Sdim Comparison::Kind Cmp) const { 618249423Sdim // Cannot handle comparison EQ, i.e. while (A == B). 619249423Sdim if (Cmp == Comparison::EQ) 620249423Sdim return 0; 621249423Sdim 622249423Sdim // Check if either the start or end values are an assignment of an immediate. 623249423Sdim // If so, use the immediate value rather than the register. 624249423Sdim if (Start->isReg()) { 625249423Sdim const MachineInstr *StartValInstr = MRI->getVRegDef(Start->getReg()); 626249423Sdim if (StartValInstr && StartValInstr->getOpcode() == Hexagon::TFRI) 627249423Sdim Start = &StartValInstr->getOperand(1); 628249423Sdim } 629249423Sdim if (End->isReg()) { 630249423Sdim const MachineInstr *EndValInstr = MRI->getVRegDef(End->getReg()); 631249423Sdim if (EndValInstr && EndValInstr->getOpcode() == Hexagon::TFRI) 632249423Sdim End = &EndValInstr->getOperand(1); 633249423Sdim } 634249423Sdim 635249423Sdim assert (Start->isReg() || Start->isImm()); 636249423Sdim assert (End->isReg() || End->isImm()); 637249423Sdim 638249423Sdim bool CmpLess = Cmp & Comparison::L; 639249423Sdim bool CmpGreater = Cmp & Comparison::G; 640249423Sdim bool CmpHasEqual = Cmp & Comparison::EQ; 641249423Sdim 642249423Sdim // Avoid certain wrap-arounds. This doesn't detect all wrap-arounds. 643249423Sdim // If loop executes while iv is "less" with the iv value going down, then 644249423Sdim // the iv must wrap. 645249423Sdim if (CmpLess && IVBump < 0) 646249423Sdim return 0; 647249423Sdim // If loop executes while iv is "greater" with the iv value going up, then 648249423Sdim // the iv must wrap. 649249423Sdim if (CmpGreater && IVBump > 0) 650249423Sdim return 0; 651249423Sdim 652249423Sdim if (Start->isImm() && End->isImm()) { 653249423Sdim // Both, start and end are immediates. 654249423Sdim int64_t StartV = Start->getImm(); 655249423Sdim int64_t EndV = End->getImm(); 656249423Sdim int64_t Dist = EndV - StartV; 657249423Sdim if (Dist == 0) 658249423Sdim return 0; 659249423Sdim 660249423Sdim bool Exact = (Dist % IVBump) == 0; 661249423Sdim 662249423Sdim if (Cmp == Comparison::NE) { 663249423Sdim if (!Exact) 664249423Sdim return 0; 665249423Sdim if ((Dist < 0) ^ (IVBump < 0)) 666249423Sdim return 0; 667249423Sdim } 668249423Sdim 669249423Sdim // For comparisons that include the final value (i.e. include equality 670249423Sdim // with the final value), we need to increase the distance by 1. 671249423Sdim if (CmpHasEqual) 672249423Sdim Dist = Dist > 0 ? Dist+1 : Dist-1; 673249423Sdim 674249423Sdim // assert (CmpLess => Dist > 0); 675249423Sdim assert ((!CmpLess || Dist > 0) && "Loop should never iterate!"); 676249423Sdim // assert (CmpGreater => Dist < 0); 677249423Sdim assert ((!CmpGreater || Dist < 0) && "Loop should never iterate!"); 678249423Sdim 679249423Sdim // "Normalized" distance, i.e. with the bump set to +-1. 680249423Sdim int64_t Dist1 = (IVBump > 0) ? (Dist + (IVBump-1)) / IVBump 681249423Sdim : (-Dist + (-IVBump-1)) / (-IVBump); 682249423Sdim assert (Dist1 > 0 && "Fishy thing. Both operands have the same sign."); 683249423Sdim 684249423Sdim uint64_t Count = Dist1; 685249423Sdim 686249423Sdim if (Count > 0xFFFFFFFFULL) 687249423Sdim return 0; 688249423Sdim 689249423Sdim return new CountValue(CountValue::CV_Immediate, Count); 690249423Sdim } 691249423Sdim 692249423Sdim // A general case: Start and End are some values, but the actual 693249423Sdim // iteration count may not be available. If it is not, insert 694249423Sdim // a computation of it into the preheader. 695249423Sdim 696249423Sdim // If the induction variable bump is not a power of 2, quit. 697249423Sdim // Othwerise we'd need a general integer division. 698249423Sdim if (!isPowerOf2_64(abs64(IVBump))) 699249423Sdim return 0; 700249423Sdim 701249423Sdim MachineBasicBlock *PH = Loop->getLoopPreheader(); 702249423Sdim assert (PH && "Should have a preheader by now"); 703249423Sdim MachineBasicBlock::iterator InsertPos = PH->getFirstTerminator(); 704249423Sdim DebugLoc DL = (InsertPos != PH->end()) ? InsertPos->getDebugLoc() 705249423Sdim : DebugLoc(); 706249423Sdim 707249423Sdim // If Start is an immediate and End is a register, the trip count 708249423Sdim // will be "reg - imm". Hexagon's "subtract immediate" instruction 709249423Sdim // is actually "reg + -imm". 710249423Sdim 711249423Sdim // If the loop IV is going downwards, i.e. if the bump is negative, 712249423Sdim // then the iteration count (computed as End-Start) will need to be 713249423Sdim // negated. To avoid the negation, just swap Start and End. 714249423Sdim if (IVBump < 0) { 715249423Sdim std::swap(Start, End); 716249423Sdim IVBump = -IVBump; 717249423Sdim } 718249423Sdim // Cmp may now have a wrong direction, e.g. LEs may now be GEs. 719249423Sdim // Signedness, and "including equality" are preserved. 720249423Sdim 721249423Sdim bool RegToImm = Start->isReg() && End->isImm(); // for (reg..imm) 722249423Sdim bool RegToReg = Start->isReg() && End->isReg(); // for (reg..reg) 723249423Sdim 724249423Sdim int64_t StartV = 0, EndV = 0; 725249423Sdim if (Start->isImm()) 726249423Sdim StartV = Start->getImm(); 727249423Sdim if (End->isImm()) 728249423Sdim EndV = End->getImm(); 729249423Sdim 730249423Sdim int64_t AdjV = 0; 731249423Sdim // To compute the iteration count, we would need this computation: 732249423Sdim // Count = (End - Start + (IVBump-1)) / IVBump 733249423Sdim // or, when CmpHasEqual: 734249423Sdim // Count = (End - Start + (IVBump-1)+1) / IVBump 735249423Sdim // The "IVBump-1" part is the adjustment (AdjV). We can avoid 736249423Sdim // generating an instruction specifically to add it if we can adjust 737249423Sdim // the immediate values for Start or End. 738249423Sdim 739249423Sdim if (CmpHasEqual) { 740249423Sdim // Need to add 1 to the total iteration count. 741249423Sdim if (Start->isImm()) 742249423Sdim StartV--; 743249423Sdim else if (End->isImm()) 744249423Sdim EndV++; 745249423Sdim else 746249423Sdim AdjV += 1; 747249423Sdim } 748249423Sdim 749249423Sdim if (Cmp != Comparison::NE) { 750249423Sdim if (Start->isImm()) 751249423Sdim StartV -= (IVBump-1); 752249423Sdim else if (End->isImm()) 753249423Sdim EndV += (IVBump-1); 754249423Sdim else 755249423Sdim AdjV += (IVBump-1); 756249423Sdim } 757249423Sdim 758249423Sdim unsigned R = 0, SR = 0; 759249423Sdim if (Start->isReg()) { 760249423Sdim R = Start->getReg(); 761249423Sdim SR = Start->getSubReg(); 762249423Sdim } else { 763249423Sdim R = End->getReg(); 764249423Sdim SR = End->getSubReg(); 765249423Sdim } 766249423Sdim const TargetRegisterClass *RC = MRI->getRegClass(R); 767249423Sdim // Hardware loops cannot handle 64-bit registers. If it's a double 768249423Sdim // register, it has to have a subregister. 769249423Sdim if (!SR && RC == &Hexagon::DoubleRegsRegClass) 770249423Sdim return 0; 771249423Sdim const TargetRegisterClass *IntRC = &Hexagon::IntRegsRegClass; 772249423Sdim 773249423Sdim // Compute DistR (register with the distance between Start and End). 774249423Sdim unsigned DistR, DistSR; 775249423Sdim 776249423Sdim // Avoid special case, where the start value is an imm(0). 777249423Sdim if (Start->isImm() && StartV == 0) { 778249423Sdim DistR = End->getReg(); 779249423Sdim DistSR = End->getSubReg(); 780249423Sdim } else { 781249423Sdim const MCInstrDesc &SubD = RegToReg ? TII->get(Hexagon::SUB_rr) : 782249423Sdim (RegToImm ? TII->get(Hexagon::SUB_ri) : 783249423Sdim TII->get(Hexagon::ADD_ri)); 784249423Sdim unsigned SubR = MRI->createVirtualRegister(IntRC); 785249423Sdim MachineInstrBuilder SubIB = 786249423Sdim BuildMI(*PH, InsertPos, DL, SubD, SubR); 787249423Sdim 788249423Sdim if (RegToReg) { 789249423Sdim SubIB.addReg(End->getReg(), 0, End->getSubReg()) 790249423Sdim .addReg(Start->getReg(), 0, Start->getSubReg()); 791249423Sdim } else if (RegToImm) { 792249423Sdim SubIB.addImm(EndV) 793249423Sdim .addReg(Start->getReg(), 0, Start->getSubReg()); 794249423Sdim } else { // ImmToReg 795249423Sdim SubIB.addReg(End->getReg(), 0, End->getSubReg()) 796249423Sdim .addImm(-StartV); 797249423Sdim } 798249423Sdim DistR = SubR; 799249423Sdim DistSR = 0; 800249423Sdim } 801249423Sdim 802249423Sdim // From DistR, compute AdjR (register with the adjusted distance). 803249423Sdim unsigned AdjR, AdjSR; 804249423Sdim 805249423Sdim if (AdjV == 0) { 806249423Sdim AdjR = DistR; 807249423Sdim AdjSR = DistSR; 808249423Sdim } else { 809249423Sdim // Generate CountR = ADD DistR, AdjVal 810249423Sdim unsigned AddR = MRI->createVirtualRegister(IntRC); 811249423Sdim const MCInstrDesc &AddD = TII->get(Hexagon::ADD_ri); 812249423Sdim BuildMI(*PH, InsertPos, DL, AddD, AddR) 813249423Sdim .addReg(DistR, 0, DistSR) 814249423Sdim .addImm(AdjV); 815249423Sdim 816249423Sdim AdjR = AddR; 817249423Sdim AdjSR = 0; 818249423Sdim } 819249423Sdim 820249423Sdim // From AdjR, compute CountR (register with the final count). 821249423Sdim unsigned CountR, CountSR; 822249423Sdim 823249423Sdim if (IVBump == 1) { 824249423Sdim CountR = AdjR; 825249423Sdim CountSR = AdjSR; 826249423Sdim } else { 827249423Sdim // The IV bump is a power of two. Log_2(IV bump) is the shift amount. 828249423Sdim unsigned Shift = Log2_32(IVBump); 829249423Sdim 830249423Sdim // Generate NormR = LSR DistR, Shift. 831249423Sdim unsigned LsrR = MRI->createVirtualRegister(IntRC); 832249423Sdim const MCInstrDesc &LsrD = TII->get(Hexagon::LSR_ri); 833249423Sdim BuildMI(*PH, InsertPos, DL, LsrD, LsrR) 834249423Sdim .addReg(AdjR, 0, AdjSR) 835249423Sdim .addImm(Shift); 836249423Sdim 837249423Sdim CountR = LsrR; 838249423Sdim CountSR = 0; 839249423Sdim } 840249423Sdim 841249423Sdim return new CountValue(CountValue::CV_Register, CountR, CountSR); 842234285Sdim} 843234285Sdim 844234285Sdim 845249423Sdim/// \brief Return true if the operation is invalid within hardware loop. 846249423Sdimbool HexagonHardwareLoops::isInvalidLoopOperation( 847249423Sdim const MachineInstr *MI) const { 848249423Sdim 849234285Sdim // call is not allowed because the callee may use a hardware loop 850249423Sdim if (MI->getDesc().isCall()) 851234285Sdim return true; 852249423Sdim 853234285Sdim // do not allow nested hardware loops 854249423Sdim if (isHardwareLoop(MI)) 855234285Sdim return true; 856249423Sdim 857234285Sdim // check if the instruction defines a hardware loop register 858234285Sdim for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) { 859234285Sdim const MachineOperand &MO = MI->getOperand(i); 860249423Sdim if (!MO.isReg() || !MO.isDef()) 861249423Sdim continue; 862249423Sdim unsigned R = MO.getReg(); 863249423Sdim if (R == Hexagon::LC0 || R == Hexagon::LC1 || 864249423Sdim R == Hexagon::SA0 || R == Hexagon::SA1) 865234285Sdim return true; 866234285Sdim } 867234285Sdim return false; 868234285Sdim} 869234285Sdim 870249423Sdim 871249423Sdim/// \brief - Return true if the loop contains an instruction that inhibits 872249423Sdim/// the use of the hardware loop function. 873234285Sdimbool HexagonHardwareLoops::containsInvalidInstruction(MachineLoop *L) const { 874263508Sdim const std::vector<MachineBasicBlock *> &Blocks = L->getBlocks(); 875234285Sdim for (unsigned i = 0, e = Blocks.size(); i != e; ++i) { 876234285Sdim MachineBasicBlock *MBB = Blocks[i]; 877234285Sdim for (MachineBasicBlock::iterator 878234285Sdim MII = MBB->begin(), E = MBB->end(); MII != E; ++MII) { 879234285Sdim const MachineInstr *MI = &*MII; 880249423Sdim if (isInvalidLoopOperation(MI)) 881234285Sdim return true; 882234285Sdim } 883234285Sdim } 884234285Sdim return false; 885234285Sdim} 886234285Sdim 887249423Sdim 888249423Sdim/// \brief Returns true if the instruction is dead. This was essentially 889249423Sdim/// copied from DeadMachineInstructionElim::isDead, but with special cases 890249423Sdim/// for inline asm, physical registers and instructions with side effects 891249423Sdim/// removed. 892249423Sdimbool HexagonHardwareLoops::isDead(const MachineInstr *MI, 893263508Sdim SmallVectorImpl<MachineInstr *> &DeadPhis) const { 894249423Sdim // Examine each operand. 895249423Sdim for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) { 896249423Sdim const MachineOperand &MO = MI->getOperand(i); 897249423Sdim if (!MO.isReg() || !MO.isDef()) 898249423Sdim continue; 899249423Sdim 900249423Sdim unsigned Reg = MO.getReg(); 901249423Sdim if (MRI->use_nodbg_empty(Reg)) 902249423Sdim continue; 903249423Sdim 904249423Sdim typedef MachineRegisterInfo::use_nodbg_iterator use_nodbg_iterator; 905249423Sdim 906249423Sdim // This instruction has users, but if the only user is the phi node for the 907249423Sdim // parent block, and the only use of that phi node is this instruction, then 908249423Sdim // this instruction is dead: both it (and the phi node) can be removed. 909249423Sdim use_nodbg_iterator I = MRI->use_nodbg_begin(Reg); 910249423Sdim use_nodbg_iterator End = MRI->use_nodbg_end(); 911249423Sdim if (llvm::next(I) != End || !I.getOperand().getParent()->isPHI()) 912249423Sdim return false; 913249423Sdim 914249423Sdim MachineInstr *OnePhi = I.getOperand().getParent(); 915249423Sdim for (unsigned j = 0, f = OnePhi->getNumOperands(); j != f; ++j) { 916249423Sdim const MachineOperand &OPO = OnePhi->getOperand(j); 917249423Sdim if (!OPO.isReg() || !OPO.isDef()) 918249423Sdim continue; 919249423Sdim 920249423Sdim unsigned OPReg = OPO.getReg(); 921249423Sdim use_nodbg_iterator nextJ; 922249423Sdim for (use_nodbg_iterator J = MRI->use_nodbg_begin(OPReg); 923249423Sdim J != End; J = nextJ) { 924249423Sdim nextJ = llvm::next(J); 925249423Sdim MachineOperand &Use = J.getOperand(); 926249423Sdim MachineInstr *UseMI = Use.getParent(); 927249423Sdim 928249423Sdim // If the phi node has a user that is not MI, bail... 929249423Sdim if (MI != UseMI) 930249423Sdim return false; 931249423Sdim } 932249423Sdim } 933249423Sdim DeadPhis.push_back(OnePhi); 934249423Sdim } 935249423Sdim 936249423Sdim // If there are no defs with uses, the instruction is dead. 937249423Sdim return true; 938249423Sdim} 939249423Sdim 940249423Sdimvoid HexagonHardwareLoops::removeIfDead(MachineInstr *MI) { 941249423Sdim // This procedure was essentially copied from DeadMachineInstructionElim. 942249423Sdim 943249423Sdim SmallVector<MachineInstr*, 1> DeadPhis; 944249423Sdim if (isDead(MI, DeadPhis)) { 945249423Sdim DEBUG(dbgs() << "HW looping will remove: " << *MI); 946249423Sdim 947249423Sdim // It is possible that some DBG_VALUE instructions refer to this 948249423Sdim // instruction. Examine each def operand for such references; 949249423Sdim // if found, mark the DBG_VALUE as undef (but don't delete it). 950249423Sdim for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) { 951249423Sdim const MachineOperand &MO = MI->getOperand(i); 952249423Sdim if (!MO.isReg() || !MO.isDef()) 953249423Sdim continue; 954249423Sdim unsigned Reg = MO.getReg(); 955249423Sdim MachineRegisterInfo::use_iterator nextI; 956249423Sdim for (MachineRegisterInfo::use_iterator I = MRI->use_begin(Reg), 957249423Sdim E = MRI->use_end(); I != E; I = nextI) { 958249423Sdim nextI = llvm::next(I); // I is invalidated by the setReg 959249423Sdim MachineOperand &Use = I.getOperand(); 960249423Sdim MachineInstr *UseMI = Use.getParent(); 961249423Sdim if (UseMI == MI) 962249423Sdim continue; 963249423Sdim if (Use.isDebug()) 964249423Sdim UseMI->getOperand(0).setReg(0U); 965249423Sdim // This may also be a "instr -> phi -> instr" case which can 966249423Sdim // be removed too. 967249423Sdim } 968249423Sdim } 969249423Sdim 970249423Sdim MI->eraseFromParent(); 971249423Sdim for (unsigned i = 0; i < DeadPhis.size(); ++i) 972249423Sdim DeadPhis[i]->eraseFromParent(); 973249423Sdim } 974249423Sdim} 975249423Sdim 976249423Sdim/// \brief Check if the loop is a candidate for converting to a hardware 977249423Sdim/// loop. If so, then perform the transformation. 978234285Sdim/// 979249423Sdim/// This function works on innermost loops first. A loop can be converted 980249423Sdim/// if it is a counting loop; either a register value or an immediate. 981234285Sdim/// 982249423Sdim/// The code makes several assumptions about the representation of the loop 983249423Sdim/// in llvm. 984234285Sdimbool HexagonHardwareLoops::convertToHardwareLoop(MachineLoop *L) { 985249423Sdim // This is just for sanity. 986249423Sdim assert(L->getHeader() && "Loop without a header?"); 987249423Sdim 988234285Sdim bool Changed = false; 989234285Sdim // Process nested loops first. 990249423Sdim for (MachineLoop::iterator I = L->begin(), E = L->end(); I != E; ++I) 991234285Sdim Changed |= convertToHardwareLoop(*I); 992249423Sdim 993234285Sdim // If a nested loop has been converted, then we can't convert this loop. 994249423Sdim if (Changed) 995234285Sdim return Changed; 996249423Sdim 997249423Sdim#ifndef NDEBUG 998249423Sdim // Stop trying after reaching the limit (if any). 999249423Sdim int Limit = HWLoopLimit; 1000249423Sdim if (Limit >= 0) { 1001249423Sdim if (Counter >= HWLoopLimit) 1002249423Sdim return false; 1003249423Sdim Counter++; 1004234285Sdim } 1005249423Sdim#endif 1006249423Sdim 1007234285Sdim // Does the loop contain any invalid instructions? 1008249423Sdim if (containsInvalidInstruction(L)) 1009234285Sdim return false; 1010249423Sdim 1011249423Sdim // Is the induction variable bump feeding the latch condition? 1012249423Sdim if (!fixupInductionVariable(L)) 1013234285Sdim return false; 1014234285Sdim 1015234285Sdim MachineBasicBlock *LastMBB = L->getExitingBlock(); 1016234285Sdim // Don't generate hw loop if the loop has more than one exit. 1017249423Sdim if (LastMBB == 0) 1018234285Sdim return false; 1019249423Sdim 1020234285Sdim MachineBasicBlock::iterator LastI = LastMBB->getFirstTerminator(); 1021249423Sdim if (LastI == LastMBB->end()) 1022249423Sdim return false; 1023234285Sdim 1024249423Sdim // Ensure the loop has a preheader: the loop instruction will be 1025249423Sdim // placed there. 1026249423Sdim bool NewPreheader = false; 1027249423Sdim MachineBasicBlock *Preheader = L->getLoopPreheader(); 1028249423Sdim if (!Preheader) { 1029249423Sdim Preheader = createPreheaderForLoop(L); 1030249423Sdim if (!Preheader) 1031249423Sdim return false; 1032249423Sdim NewPreheader = true; 1033249423Sdim } 1034249423Sdim MachineBasicBlock::iterator InsertPos = Preheader->getFirstTerminator(); 1035249423Sdim 1036249423Sdim SmallVector<MachineInstr*, 2> OldInsts; 1037249423Sdim // Are we able to determine the trip count for the loop? 1038249423Sdim CountValue *TripCount = getLoopTripCount(L, OldInsts); 1039249423Sdim if (TripCount == 0) 1040249423Sdim return false; 1041249423Sdim 1042249423Sdim // Is the trip count available in the preheader? 1043249423Sdim if (TripCount->isReg()) { 1044249423Sdim // There will be a use of the register inserted into the preheader, 1045249423Sdim // so make sure that the register is actually defined at that point. 1046249423Sdim MachineInstr *TCDef = MRI->getVRegDef(TripCount->getReg()); 1047249423Sdim MachineBasicBlock *BBDef = TCDef->getParent(); 1048249423Sdim if (!NewPreheader) { 1049249423Sdim if (!MDT->dominates(BBDef, Preheader)) 1050249423Sdim return false; 1051249423Sdim } else { 1052249423Sdim // If we have just created a preheader, the dominator tree won't be 1053249423Sdim // aware of it. Check if the definition of the register dominates 1054249423Sdim // the header, but is not the header itself. 1055249423Sdim if (!MDT->properlyDominates(BBDef, L->getHeader())) 1056249423Sdim return false; 1057249423Sdim } 1058249423Sdim } 1059249423Sdim 1060234285Sdim // Determine the loop start. 1061234285Sdim MachineBasicBlock *LoopStart = L->getTopBlock(); 1062234285Sdim if (L->getLoopLatch() != LastMBB) { 1063234285Sdim // When the exit and latch are not the same, use the latch block as the 1064234285Sdim // start. 1065249423Sdim // The loop start address is used only after the 1st iteration, and the 1066249423Sdim // loop latch may contains instrs. that need to be executed after the 1067249423Sdim // first iteration. 1068234285Sdim LoopStart = L->getLoopLatch(); 1069234285Sdim // Make sure the latch is a successor of the exit, otherwise it won't work. 1070249423Sdim if (!LastMBB->isSuccessor(LoopStart)) 1071234285Sdim return false; 1072234285Sdim } 1073234285Sdim 1074249423Sdim // Convert the loop to a hardware loop. 1075234285Sdim DEBUG(dbgs() << "Change to hardware loop at "; L->dump()); 1076249423Sdim DebugLoc DL; 1077249423Sdim if (InsertPos != Preheader->end()) 1078249423Sdim DL = InsertPos->getDebugLoc(); 1079234285Sdim 1080234285Sdim if (TripCount->isReg()) { 1081234285Sdim // Create a copy of the loop count register. 1082249423Sdim unsigned CountReg = MRI->createVirtualRegister(&Hexagon::IntRegsRegClass); 1083249423Sdim BuildMI(*Preheader, InsertPos, DL, TII->get(TargetOpcode::COPY), CountReg) 1084249423Sdim .addReg(TripCount->getReg(), 0, TripCount->getSubReg()); 1085239462Sdim // Add the Loop instruction to the beginning of the loop. 1086249423Sdim BuildMI(*Preheader, InsertPos, DL, TII->get(Hexagon::LOOP0_r)) 1087249423Sdim .addMBB(LoopStart) 1088249423Sdim .addReg(CountReg); 1089234285Sdim } else { 1090249423Sdim assert(TripCount->isImm() && "Expecting immediate value for trip count"); 1091249423Sdim // Add the Loop immediate instruction to the beginning of the loop, 1092249423Sdim // if the immediate fits in the instructions. Otherwise, we need to 1093249423Sdim // create a new virtual register. 1094234285Sdim int64_t CountImm = TripCount->getImm(); 1095249423Sdim if (!TII->isValidOffset(Hexagon::LOOP0_i, CountImm)) { 1096249423Sdim unsigned CountReg = MRI->createVirtualRegister(&Hexagon::IntRegsRegClass); 1097249423Sdim BuildMI(*Preheader, InsertPos, DL, TII->get(Hexagon::TFRI), CountReg) 1098249423Sdim .addImm(CountImm); 1099249423Sdim BuildMI(*Preheader, InsertPos, DL, TII->get(Hexagon::LOOP0_r)) 1100249423Sdim .addMBB(LoopStart).addReg(CountReg); 1101249423Sdim } else 1102249423Sdim BuildMI(*Preheader, InsertPos, DL, TII->get(Hexagon::LOOP0_i)) 1103249423Sdim .addMBB(LoopStart).addImm(CountImm); 1104234285Sdim } 1105234285Sdim 1106249423Sdim // Make sure the loop start always has a reference in the CFG. We need 1107249423Sdim // to create a BlockAddress operand to get this mechanism to work both the 1108234285Sdim // MachineBasicBlock and BasicBlock objects need the flag set. 1109234285Sdim LoopStart->setHasAddressTaken(); 1110234285Sdim // This line is needed to set the hasAddressTaken flag on the BasicBlock 1111249423Sdim // object. 1112234285Sdim BlockAddress::get(const_cast<BasicBlock *>(LoopStart->getBasicBlock())); 1113234285Sdim 1114234285Sdim // Replace the loop branch with an endloop instruction. 1115249423Sdim DebugLoc LastIDL = LastI->getDebugLoc(); 1116249423Sdim BuildMI(*LastMBB, LastI, LastIDL, 1117249423Sdim TII->get(Hexagon::ENDLOOP0)).addMBB(LoopStart); 1118234285Sdim 1119234285Sdim // The loop ends with either: 1120234285Sdim // - a conditional branch followed by an unconditional branch, or 1121234285Sdim // - a conditional branch to the loop start. 1122251662Sdim if (LastI->getOpcode() == Hexagon::JMP_t || 1123251662Sdim LastI->getOpcode() == Hexagon::JMP_f) { 1124249423Sdim // Delete one and change/add an uncond. branch to out of the loop. 1125234285Sdim MachineBasicBlock *BranchTarget = LastI->getOperand(1).getMBB(); 1126234285Sdim LastI = LastMBB->erase(LastI); 1127234285Sdim if (!L->contains(BranchTarget)) { 1128249423Sdim if (LastI != LastMBB->end()) 1129249423Sdim LastI = LastMBB->erase(LastI); 1130234285Sdim SmallVector<MachineOperand, 0> Cond; 1131249423Sdim TII->InsertBranch(*LastMBB, BranchTarget, 0, Cond, LastIDL); 1132234285Sdim } 1133234285Sdim } else { 1134234285Sdim // Conditional branch to loop start; just delete it. 1135234285Sdim LastMBB->erase(LastI); 1136234285Sdim } 1137234285Sdim delete TripCount; 1138234285Sdim 1139249423Sdim // The induction operation and the comparison may now be 1140249423Sdim // unneeded. If these are unneeded, then remove them. 1141249423Sdim for (unsigned i = 0; i < OldInsts.size(); ++i) 1142249423Sdim removeIfDead(OldInsts[i]); 1143249423Sdim 1144234285Sdim ++NumHWLoops; 1145234285Sdim return true; 1146234285Sdim} 1147234285Sdim 1148249423Sdim 1149249423Sdimbool HexagonHardwareLoops::orderBumpCompare(MachineInstr *BumpI, 1150249423Sdim MachineInstr *CmpI) { 1151249423Sdim assert (BumpI != CmpI && "Bump and compare in the same instruction?"); 1152249423Sdim 1153249423Sdim MachineBasicBlock *BB = BumpI->getParent(); 1154249423Sdim if (CmpI->getParent() != BB) 1155249423Sdim return false; 1156249423Sdim 1157249423Sdim typedef MachineBasicBlock::instr_iterator instr_iterator; 1158249423Sdim // Check if things are in order to begin with. 1159249423Sdim for (instr_iterator I = BumpI, E = BB->instr_end(); I != E; ++I) 1160249423Sdim if (&*I == CmpI) 1161249423Sdim return true; 1162249423Sdim 1163249423Sdim // Out of order. 1164249423Sdim unsigned PredR = CmpI->getOperand(0).getReg(); 1165249423Sdim bool FoundBump = false; 1166249423Sdim instr_iterator CmpIt = CmpI, NextIt = llvm::next(CmpIt); 1167249423Sdim for (instr_iterator I = NextIt, E = BB->instr_end(); I != E; ++I) { 1168249423Sdim MachineInstr *In = &*I; 1169249423Sdim for (unsigned i = 0, n = In->getNumOperands(); i < n; ++i) { 1170249423Sdim MachineOperand &MO = In->getOperand(i); 1171249423Sdim if (MO.isReg() && MO.isUse()) { 1172249423Sdim if (MO.getReg() == PredR) // Found an intervening use of PredR. 1173249423Sdim return false; 1174249423Sdim } 1175249423Sdim } 1176249423Sdim 1177249423Sdim if (In == BumpI) { 1178249423Sdim instr_iterator After = BumpI; 1179249423Sdim instr_iterator From = CmpI; 1180249423Sdim BB->splice(llvm::next(After), BB, From); 1181249423Sdim FoundBump = true; 1182249423Sdim break; 1183249423Sdim } 1184249423Sdim } 1185249423Sdim assert (FoundBump && "Cannot determine instruction order"); 1186249423Sdim return FoundBump; 1187234285Sdim} 1188234285Sdim 1189234285Sdim 1190249423SdimMachineInstr *HexagonHardwareLoops::defWithImmediate(unsigned R) { 1191249423Sdim MachineInstr *DI = MRI->getVRegDef(R); 1192249423Sdim unsigned DOpc = DI->getOpcode(); 1193249423Sdim switch (DOpc) { 1194249423Sdim case Hexagon::TFRI: 1195249423Sdim case Hexagon::TFRI64: 1196249423Sdim case Hexagon::CONST32_Int_Real: 1197249423Sdim case Hexagon::CONST64_Int_Real: 1198249423Sdim return DI; 1199249423Sdim } 1200249423Sdim return 0; 1201234285Sdim} 1202234285Sdim 1203234285Sdim 1204249423Sdimint64_t HexagonHardwareLoops::getImmediate(MachineOperand &MO) { 1205249423Sdim if (MO.isImm()) 1206249423Sdim return MO.getImm(); 1207249423Sdim assert(MO.isReg()); 1208249423Sdim unsigned R = MO.getReg(); 1209249423Sdim MachineInstr *DI = defWithImmediate(R); 1210249423Sdim assert(DI && "Need an immediate operand"); 1211249423Sdim // All currently supported "define-with-immediate" instructions have the 1212249423Sdim // actual immediate value in the operand(1). 1213249423Sdim int64_t v = DI->getOperand(1).getImm(); 1214249423Sdim return v; 1215249423Sdim} 1216234285Sdim 1217249423Sdim 1218249423Sdimvoid HexagonHardwareLoops::setImmediate(MachineOperand &MO, int64_t Val) { 1219249423Sdim if (MO.isImm()) { 1220249423Sdim MO.setImm(Val); 1221249423Sdim return; 1222234285Sdim } 1223234285Sdim 1224249423Sdim assert(MO.isReg()); 1225249423Sdim unsigned R = MO.getReg(); 1226249423Sdim MachineInstr *DI = defWithImmediate(R); 1227249423Sdim if (MRI->hasOneNonDBGUse(R)) { 1228249423Sdim // If R has only one use, then just change its defining instruction to 1229249423Sdim // the new immediate value. 1230249423Sdim DI->getOperand(1).setImm(Val); 1231249423Sdim return; 1232249423Sdim } 1233234285Sdim 1234249423Sdim const TargetRegisterClass *RC = MRI->getRegClass(R); 1235249423Sdim unsigned NewR = MRI->createVirtualRegister(RC); 1236249423Sdim MachineBasicBlock &B = *DI->getParent(); 1237249423Sdim DebugLoc DL = DI->getDebugLoc(); 1238249423Sdim BuildMI(B, DI, DL, TII->get(DI->getOpcode()), NewR) 1239249423Sdim .addImm(Val); 1240249423Sdim MO.setReg(NewR); 1241249423Sdim} 1242234285Sdim 1243249423Sdim 1244249423Sdimbool HexagonHardwareLoops::fixupInductionVariable(MachineLoop *L) { 1245249423Sdim MachineBasicBlock *Header = L->getHeader(); 1246249423Sdim MachineBasicBlock *Preheader = L->getLoopPreheader(); 1247249423Sdim MachineBasicBlock *Latch = L->getLoopLatch(); 1248249423Sdim 1249249423Sdim if (!Header || !Preheader || !Latch) 1250249423Sdim return false; 1251249423Sdim 1252249423Sdim // These data structures follow the same concept as the corresponding 1253249423Sdim // ones in findInductionRegister (where some comments are). 1254249423Sdim typedef std::pair<unsigned,int64_t> RegisterBump; 1255249423Sdim typedef std::pair<unsigned,RegisterBump> RegisterInduction; 1256249423Sdim typedef std::set<RegisterInduction> RegisterInductionSet; 1257249423Sdim 1258249423Sdim // Register candidates for induction variables, with their associated bumps. 1259249423Sdim RegisterInductionSet IndRegs; 1260249423Sdim 1261249423Sdim // Look for induction patterns: 1262249423Sdim // vreg1 = PHI ..., [ latch, vreg2 ] 1263249423Sdim // vreg2 = ADD vreg1, imm 1264249423Sdim typedef MachineBasicBlock::instr_iterator instr_iterator; 1265249423Sdim for (instr_iterator I = Header->instr_begin(), E = Header->instr_end(); 1266249423Sdim I != E && I->isPHI(); ++I) { 1267249423Sdim MachineInstr *Phi = &*I; 1268249423Sdim 1269249423Sdim // Have a PHI instruction. 1270249423Sdim for (unsigned i = 1, n = Phi->getNumOperands(); i < n; i += 2) { 1271249423Sdim if (Phi->getOperand(i+1).getMBB() != Latch) 1272249423Sdim continue; 1273249423Sdim 1274249423Sdim unsigned PhiReg = Phi->getOperand(i).getReg(); 1275249423Sdim MachineInstr *DI = MRI->getVRegDef(PhiReg); 1276249423Sdim unsigned UpdOpc = DI->getOpcode(); 1277249423Sdim bool isAdd = (UpdOpc == Hexagon::ADD_ri); 1278249423Sdim 1279249423Sdim if (isAdd) { 1280249423Sdim // If the register operand to the add/sub is the PHI we are looking 1281249423Sdim // at, this meets the induction pattern. 1282249423Sdim unsigned IndReg = DI->getOperand(1).getReg(); 1283249423Sdim if (MRI->getVRegDef(IndReg) == Phi) { 1284249423Sdim unsigned UpdReg = DI->getOperand(0).getReg(); 1285249423Sdim int64_t V = DI->getOperand(2).getImm(); 1286249423Sdim IndRegs.insert(std::make_pair(UpdReg, std::make_pair(IndReg, V))); 1287234285Sdim } 1288234285Sdim } 1289249423Sdim } // for (i) 1290249423Sdim } // for (instr) 1291249423Sdim 1292249423Sdim if (IndRegs.empty()) 1293249423Sdim return false; 1294249423Sdim 1295249423Sdim MachineBasicBlock *TB = 0, *FB = 0; 1296249423Sdim SmallVector<MachineOperand,2> Cond; 1297249423Sdim // AnalyzeBranch returns true if it fails to analyze branch. 1298249423Sdim bool NotAnalyzed = TII->AnalyzeBranch(*Latch, TB, FB, Cond, false); 1299249423Sdim if (NotAnalyzed) 1300249423Sdim return false; 1301249423Sdim 1302249423Sdim // Check if the latch branch is unconditional. 1303249423Sdim if (Cond.empty()) 1304249423Sdim return false; 1305249423Sdim 1306249423Sdim if (TB != Header && FB != Header) 1307249423Sdim // The latch does not go back to the header. Not a latch we know and love. 1308249423Sdim return false; 1309249423Sdim 1310249423Sdim // Expecting a predicate register as a condition. It won't be a hardware 1311249423Sdim // predicate register at this point yet, just a vreg. 1312249423Sdim // HexagonInstrInfo::AnalyzeBranch for negated branches inserts imm(0) 1313249423Sdim // into Cond, followed by the predicate register. For non-negated branches 1314249423Sdim // it's just the register. 1315249423Sdim unsigned CSz = Cond.size(); 1316249423Sdim if (CSz != 1 && CSz != 2) 1317249423Sdim return false; 1318249423Sdim 1319249423Sdim unsigned P = Cond[CSz-1].getReg(); 1320249423Sdim MachineInstr *PredDef = MRI->getVRegDef(P); 1321249423Sdim 1322249423Sdim if (!PredDef->isCompare()) 1323249423Sdim return false; 1324249423Sdim 1325249423Sdim SmallSet<unsigned,2> CmpRegs; 1326249423Sdim MachineOperand *CmpImmOp = 0; 1327249423Sdim 1328249423Sdim // Go over all operands to the compare and look for immediate and register 1329249423Sdim // operands. Assume that if the compare has a single register use and a 1330249423Sdim // single immediate operand, then the register is being compared with the 1331249423Sdim // immediate value. 1332249423Sdim for (unsigned i = 0, n = PredDef->getNumOperands(); i < n; ++i) { 1333249423Sdim MachineOperand &MO = PredDef->getOperand(i); 1334249423Sdim if (MO.isReg()) { 1335249423Sdim // Skip all implicit references. In one case there was: 1336249423Sdim // %vreg140<def> = FCMPUGT32_rr %vreg138, %vreg139, %USR<imp-use> 1337249423Sdim if (MO.isImplicit()) 1338249423Sdim continue; 1339249423Sdim if (MO.isUse()) { 1340249423Sdim unsigned R = MO.getReg(); 1341249423Sdim if (!defWithImmediate(R)) { 1342249423Sdim CmpRegs.insert(MO.getReg()); 1343249423Sdim continue; 1344249423Sdim } 1345249423Sdim // Consider the register to be the "immediate" operand. 1346249423Sdim if (CmpImmOp) 1347249423Sdim return false; 1348249423Sdim CmpImmOp = &MO; 1349249423Sdim } 1350249423Sdim } else if (MO.isImm()) { 1351249423Sdim if (CmpImmOp) // A second immediate argument? Confusing. Bail out. 1352249423Sdim return false; 1353249423Sdim CmpImmOp = &MO; 1354234285Sdim } 1355234285Sdim } 1356234285Sdim 1357249423Sdim if (CmpRegs.empty()) 1358249423Sdim return false; 1359234285Sdim 1360249423Sdim // Check if the compared register follows the order we want. Fix if needed. 1361249423Sdim for (RegisterInductionSet::iterator I = IndRegs.begin(), E = IndRegs.end(); 1362249423Sdim I != E; ++I) { 1363249423Sdim // This is a success. If the register used in the comparison is one that 1364249423Sdim // we have identified as a bumped (updated) induction register, there is 1365249423Sdim // nothing to do. 1366249423Sdim if (CmpRegs.count(I->first)) 1367249423Sdim return true; 1368249423Sdim 1369249423Sdim // Otherwise, if the register being compared comes out of a PHI node, 1370249423Sdim // and has been recognized as following the induction pattern, and is 1371249423Sdim // compared against an immediate, we can fix it. 1372249423Sdim const RegisterBump &RB = I->second; 1373249423Sdim if (CmpRegs.count(RB.first)) { 1374249423Sdim if (!CmpImmOp) 1375249423Sdim return false; 1376249423Sdim 1377249423Sdim int64_t CmpImm = getImmediate(*CmpImmOp); 1378249423Sdim int64_t V = RB.second; 1379249423Sdim if (V > 0 && CmpImm+V < CmpImm) // Overflow (64-bit). 1380249423Sdim return false; 1381249423Sdim if (V < 0 && CmpImm+V > CmpImm) // Overflow (64-bit). 1382249423Sdim return false; 1383249423Sdim CmpImm += V; 1384249423Sdim // Some forms of cmp-immediate allow u9 and s10. Assume the worst case 1385249423Sdim // scenario, i.e. an 8-bit value. 1386249423Sdim if (CmpImmOp->isImm() && !isInt<8>(CmpImm)) 1387249423Sdim return false; 1388249423Sdim 1389249423Sdim // Make sure that the compare happens after the bump. Otherwise, 1390249423Sdim // after the fixup, the compare would use a yet-undefined register. 1391249423Sdim MachineInstr *BumpI = MRI->getVRegDef(I->first); 1392249423Sdim bool Order = orderBumpCompare(BumpI, PredDef); 1393249423Sdim if (!Order) 1394249423Sdim return false; 1395249423Sdim 1396249423Sdim // Finally, fix the compare instruction. 1397249423Sdim setImmediate(*CmpImmOp, CmpImm); 1398249423Sdim for (unsigned i = 0, n = PredDef->getNumOperands(); i < n; ++i) { 1399249423Sdim MachineOperand &MO = PredDef->getOperand(i); 1400249423Sdim if (MO.isReg() && MO.getReg() == RB.first) { 1401249423Sdim MO.setReg(I->first); 1402249423Sdim return true; 1403249423Sdim } 1404249423Sdim } 1405249423Sdim } 1406249423Sdim } 1407249423Sdim 1408249423Sdim return false; 1409234285Sdim} 1410234285Sdim 1411234285Sdim 1412249423Sdim/// \brief Create a preheader for a given loop. 1413249423SdimMachineBasicBlock *HexagonHardwareLoops::createPreheaderForLoop( 1414249423Sdim MachineLoop *L) { 1415249423Sdim if (MachineBasicBlock *TmpPH = L->getLoopPreheader()) 1416249423Sdim return TmpPH; 1417249423Sdim 1418249423Sdim MachineBasicBlock *Header = L->getHeader(); 1419249423Sdim MachineBasicBlock *Latch = L->getLoopLatch(); 1420249423Sdim MachineFunction *MF = Header->getParent(); 1421249423Sdim DebugLoc DL; 1422249423Sdim 1423249423Sdim if (!Latch || Header->hasAddressTaken()) 1424249423Sdim return 0; 1425249423Sdim 1426249423Sdim typedef MachineBasicBlock::instr_iterator instr_iterator; 1427249423Sdim 1428249423Sdim // Verify that all existing predecessors have analyzable branches 1429249423Sdim // (or no branches at all). 1430249423Sdim typedef std::vector<MachineBasicBlock*> MBBVector; 1431249423Sdim MBBVector Preds(Header->pred_begin(), Header->pred_end()); 1432249423Sdim SmallVector<MachineOperand,2> Tmp1; 1433249423Sdim MachineBasicBlock *TB = 0, *FB = 0; 1434249423Sdim 1435249423Sdim if (TII->AnalyzeBranch(*Latch, TB, FB, Tmp1, false)) 1436249423Sdim return 0; 1437249423Sdim 1438249423Sdim for (MBBVector::iterator I = Preds.begin(), E = Preds.end(); I != E; ++I) { 1439249423Sdim MachineBasicBlock *PB = *I; 1440249423Sdim if (PB != Latch) { 1441249423Sdim bool NotAnalyzed = TII->AnalyzeBranch(*PB, TB, FB, Tmp1, false); 1442249423Sdim if (NotAnalyzed) 1443249423Sdim return 0; 1444249423Sdim } 1445249423Sdim } 1446249423Sdim 1447249423Sdim MachineBasicBlock *NewPH = MF->CreateMachineBasicBlock(); 1448249423Sdim MF->insert(Header, NewPH); 1449249423Sdim 1450249423Sdim if (Header->pred_size() > 2) { 1451249423Sdim // Ensure that the header has only two predecessors: the preheader and 1452249423Sdim // the loop latch. Any additional predecessors of the header should 1453249423Sdim // join at the newly created preheader. Inspect all PHI nodes from the 1454249423Sdim // header and create appropriate corresponding PHI nodes in the preheader. 1455249423Sdim 1456249423Sdim for (instr_iterator I = Header->instr_begin(), E = Header->instr_end(); 1457249423Sdim I != E && I->isPHI(); ++I) { 1458249423Sdim MachineInstr *PN = &*I; 1459249423Sdim 1460249423Sdim const MCInstrDesc &PD = TII->get(TargetOpcode::PHI); 1461249423Sdim MachineInstr *NewPN = MF->CreateMachineInstr(PD, DL); 1462249423Sdim NewPH->insert(NewPH->end(), NewPN); 1463249423Sdim 1464249423Sdim unsigned PR = PN->getOperand(0).getReg(); 1465249423Sdim const TargetRegisterClass *RC = MRI->getRegClass(PR); 1466249423Sdim unsigned NewPR = MRI->createVirtualRegister(RC); 1467249423Sdim NewPN->addOperand(MachineOperand::CreateReg(NewPR, true)); 1468249423Sdim 1469249423Sdim // Copy all non-latch operands of a header's PHI node to the newly 1470249423Sdim // created PHI node in the preheader. 1471249423Sdim for (unsigned i = 1, n = PN->getNumOperands(); i < n; i += 2) { 1472249423Sdim unsigned PredR = PN->getOperand(i).getReg(); 1473249423Sdim MachineBasicBlock *PredB = PN->getOperand(i+1).getMBB(); 1474249423Sdim if (PredB == Latch) 1475249423Sdim continue; 1476249423Sdim 1477249423Sdim NewPN->addOperand(MachineOperand::CreateReg(PredR, false)); 1478249423Sdim NewPN->addOperand(MachineOperand::CreateMBB(PredB)); 1479249423Sdim } 1480249423Sdim 1481249423Sdim // Remove copied operands from the old PHI node and add the value 1482249423Sdim // coming from the preheader's PHI. 1483249423Sdim for (int i = PN->getNumOperands()-2; i > 0; i -= 2) { 1484249423Sdim MachineBasicBlock *PredB = PN->getOperand(i+1).getMBB(); 1485249423Sdim if (PredB != Latch) { 1486249423Sdim PN->RemoveOperand(i+1); 1487249423Sdim PN->RemoveOperand(i); 1488249423Sdim } 1489249423Sdim } 1490249423Sdim PN->addOperand(MachineOperand::CreateReg(NewPR, false)); 1491249423Sdim PN->addOperand(MachineOperand::CreateMBB(NewPH)); 1492249423Sdim } 1493249423Sdim 1494234285Sdim } else { 1495249423Sdim assert(Header->pred_size() == 2); 1496249423Sdim 1497249423Sdim // The header has only two predecessors, but the non-latch predecessor 1498249423Sdim // is not a preheader (e.g. it has other successors, etc.) 1499249423Sdim // In such a case we don't need any extra PHI nodes in the new preheader, 1500249423Sdim // all we need is to adjust existing PHIs in the header to now refer to 1501249423Sdim // the new preheader. 1502249423Sdim for (instr_iterator I = Header->instr_begin(), E = Header->instr_end(); 1503249423Sdim I != E && I->isPHI(); ++I) { 1504249423Sdim MachineInstr *PN = &*I; 1505249423Sdim for (unsigned i = 1, n = PN->getNumOperands(); i < n; i += 2) { 1506249423Sdim MachineOperand &MO = PN->getOperand(i+1); 1507249423Sdim if (MO.getMBB() != Latch) 1508249423Sdim MO.setMBB(NewPH); 1509249423Sdim } 1510249423Sdim } 1511234285Sdim } 1512249423Sdim 1513249423Sdim // "Reroute" the CFG edges to link in the new preheader. 1514249423Sdim // If any of the predecessors falls through to the header, insert a branch 1515249423Sdim // to the new preheader in that place. 1516249423Sdim SmallVector<MachineOperand,1> Tmp2; 1517249423Sdim SmallVector<MachineOperand,1> EmptyCond; 1518249423Sdim 1519249423Sdim TB = FB = 0; 1520249423Sdim 1521249423Sdim for (MBBVector::iterator I = Preds.begin(), E = Preds.end(); I != E; ++I) { 1522249423Sdim MachineBasicBlock *PB = *I; 1523249423Sdim if (PB != Latch) { 1524249423Sdim Tmp2.clear(); 1525249423Sdim bool NotAnalyzed = TII->AnalyzeBranch(*PB, TB, FB, Tmp2, false); 1526249423Sdim (void)NotAnalyzed; // supress compiler warning 1527249423Sdim assert (!NotAnalyzed && "Should be analyzable!"); 1528249423Sdim if (TB != Header && (Tmp2.empty() || FB != Header)) 1529249423Sdim TII->InsertBranch(*PB, NewPH, 0, EmptyCond, DL); 1530249423Sdim PB->ReplaceUsesOfBlockWith(Header, NewPH); 1531249423Sdim } 1532249423Sdim } 1533249423Sdim 1534249423Sdim // It can happen that the latch block will fall through into the header. 1535249423Sdim // Insert an unconditional branch to the header. 1536249423Sdim TB = FB = 0; 1537249423Sdim bool LatchNotAnalyzed = TII->AnalyzeBranch(*Latch, TB, FB, Tmp2, false); 1538249423Sdim (void)LatchNotAnalyzed; // supress compiler warning 1539249423Sdim assert (!LatchNotAnalyzed && "Should be analyzable!"); 1540249423Sdim if (!TB && !FB) 1541249423Sdim TII->InsertBranch(*Latch, Header, 0, EmptyCond, DL); 1542249423Sdim 1543249423Sdim // Finally, the branch from the preheader to the header. 1544249423Sdim TII->InsertBranch(*NewPH, Header, 0, EmptyCond, DL); 1545249423Sdim NewPH->addSuccessor(Header); 1546249423Sdim 1547249423Sdim return NewPH; 1548234285Sdim} 1549