1 //===-- ARMLowOverheadLoops.cpp - CodeGen Low-overhead Loops ---*- C++ -*-===// 2 // 3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. 4 // See https://llvm.org/LICENSE.txt for license information. 5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception 6 // 7 //===----------------------------------------------------------------------===// 8 /// \file 9 /// Finalize v8.1-m low-overhead loops by converting the associated pseudo 10 /// instructions into machine operations. 11 /// The expectation is that the loop contains three pseudo instructions: 12 /// - t2*LoopStart - placed in the preheader or pre-preheader. The do-loop 13 /// form should be in the preheader, whereas the while form should be in the 14 /// preheaders only predecessor. 15 /// - t2LoopDec - placed within in the loop body. 16 /// - t2LoopEnd - the loop latch terminator. 17 /// 18 /// In addition to this, we also look for the presence of the VCTP instruction, 19 /// which determines whether we can generated the tail-predicated low-overhead 20 /// loop form. 21 /// 22 /// Assumptions and Dependencies: 23 /// Low-overhead loops are constructed and executed using a setup instruction: 24 /// DLS, WLS, DLSTP or WLSTP and an instruction that loops back: LE or LETP. 25 /// WLS(TP) and LE(TP) are branching instructions with a (large) limited range 26 /// but fixed polarity: WLS can only branch forwards and LE can only branch 27 /// backwards. These restrictions mean that this pass is dependent upon block 28 /// layout and block sizes, which is why it's the last pass to run. The same is 29 /// true for ConstantIslands, but this pass does not increase the size of the 30 /// basic blocks, nor does it change the CFG. Instructions are mainly removed 31 /// during the transform and pseudo instructions are replaced by real ones. In 32 /// some cases, when we have to revert to a 'normal' loop, we have to introduce 33 /// multiple instructions for a single pseudo (see RevertWhile and 34 /// RevertLoopEnd). To handle this situation, t2WhileLoopStart and t2LoopEnd 35 /// are defined to be as large as this maximum sequence of replacement 36 /// instructions. 37 /// 38 /// A note on VPR.P0 (the lane mask): 39 /// VPT, VCMP, VPNOT and VCTP won't overwrite VPR.P0 when they update it in a 40 /// "VPT Active" context (which includes low-overhead loops and vpt blocks). 41 /// They will simply "and" the result of their calculation with the current 42 /// value of VPR.P0. You can think of it like this: 43 /// \verbatim 44 /// if VPT active: ; Between a DLSTP/LETP, or for predicated instrs 45 /// VPR.P0 &= Value 46 /// else 47 /// VPR.P0 = Value 48 /// \endverbatim 49 /// When we're inside the low-overhead loop (between DLSTP and LETP), we always 50 /// fall in the "VPT active" case, so we can consider that all VPR writes by 51 /// one of those instruction is actually a "and". 52 //===----------------------------------------------------------------------===// 53 54 #include "ARM.h" 55 #include "ARMBaseInstrInfo.h" 56 #include "ARMBaseRegisterInfo.h" 57 #include "ARMBasicBlockInfo.h" 58 #include "ARMSubtarget.h" 59 #include "Thumb2InstrInfo.h" 60 #include "llvm/ADT/SetOperations.h" 61 #include "llvm/ADT/SmallSet.h" 62 #include "llvm/CodeGen/LivePhysRegs.h" 63 #include "llvm/CodeGen/MachineFunctionPass.h" 64 #include "llvm/CodeGen/MachineLoopInfo.h" 65 #include "llvm/CodeGen/MachineLoopUtils.h" 66 #include "llvm/CodeGen/MachineRegisterInfo.h" 67 #include "llvm/CodeGen/Passes.h" 68 #include "llvm/CodeGen/ReachingDefAnalysis.h" 69 #include "llvm/MC/MCInstrDesc.h" 70 71 using namespace llvm; 72 73 #define DEBUG_TYPE "arm-low-overhead-loops" 74 #define ARM_LOW_OVERHEAD_LOOPS_NAME "ARM Low Overhead Loops pass" 75 76 namespace { 77 78 using InstSet = SmallPtrSetImpl<MachineInstr *>; 79 80 class PostOrderLoopTraversal { 81 MachineLoop &ML; 82 MachineLoopInfo &MLI; 83 SmallPtrSet<MachineBasicBlock*, 4> Visited; 84 SmallVector<MachineBasicBlock*, 4> Order; 85 86 public: 87 PostOrderLoopTraversal(MachineLoop &ML, MachineLoopInfo &MLI) 88 : ML(ML), MLI(MLI) { } 89 90 const SmallVectorImpl<MachineBasicBlock*> &getOrder() const { 91 return Order; 92 } 93 94 // Visit all the blocks within the loop, as well as exit blocks and any 95 // blocks properly dominating the header. 96 void ProcessLoop() { 97 std::function<void(MachineBasicBlock*)> Search = [this, &Search] 98 (MachineBasicBlock *MBB) -> void { 99 if (Visited.count(MBB)) 100 return; 101 102 Visited.insert(MBB); 103 for (auto *Succ : MBB->successors()) { 104 if (!ML.contains(Succ)) 105 continue; 106 Search(Succ); 107 } 108 Order.push_back(MBB); 109 }; 110 111 // Insert exit blocks. 112 SmallVector<MachineBasicBlock*, 2> ExitBlocks; 113 ML.getExitBlocks(ExitBlocks); 114 for (auto *MBB : ExitBlocks) 115 Order.push_back(MBB); 116 117 // Then add the loop body. 118 Search(ML.getHeader()); 119 120 // Then try the preheader and its predecessors. 121 std::function<void(MachineBasicBlock*)> GetPredecessor = 122 [this, &GetPredecessor] (MachineBasicBlock *MBB) -> void { 123 Order.push_back(MBB); 124 if (MBB->pred_size() == 1) 125 GetPredecessor(*MBB->pred_begin()); 126 }; 127 128 if (auto *Preheader = ML.getLoopPreheader()) 129 GetPredecessor(Preheader); 130 else if (auto *Preheader = MLI.findLoopPreheader(&ML, true)) 131 GetPredecessor(Preheader); 132 } 133 }; 134 135 struct PredicatedMI { 136 MachineInstr *MI = nullptr; 137 SetVector<MachineInstr*> Predicates; 138 139 public: 140 PredicatedMI(MachineInstr *I, SetVector<MachineInstr *> &Preds) : MI(I) { 141 assert(I && "Instruction must not be null!"); 142 Predicates.insert(Preds.begin(), Preds.end()); 143 } 144 }; 145 146 // Represent a VPT block, a list of instructions that begins with a VPT/VPST 147 // and has a maximum of four proceeding instructions. All instructions within 148 // the block are predicated upon the vpr and we allow instructions to define 149 // the vpr within in the block too. 150 class VPTBlock { 151 // The predicate then instruction, which is either a VPT, or a VPST 152 // instruction. 153 std::unique_ptr<PredicatedMI> PredicateThen; 154 PredicatedMI *Divergent = nullptr; 155 SmallVector<PredicatedMI, 4> Insts; 156 157 public: 158 VPTBlock(MachineInstr *MI, SetVector<MachineInstr*> &Preds) { 159 PredicateThen = std::make_unique<PredicatedMI>(MI, Preds); 160 } 161 162 void addInst(MachineInstr *MI, SetVector<MachineInstr*> &Preds) { 163 LLVM_DEBUG(dbgs() << "ARM Loops: Adding predicated MI: " << *MI); 164 if (!Divergent && !set_difference(Preds, PredicateThen->Predicates).empty()) { 165 Divergent = &Insts.back(); 166 LLVM_DEBUG(dbgs() << " - has divergent predicate: " << *Divergent->MI); 167 } 168 Insts.emplace_back(MI, Preds); 169 assert(Insts.size() <= 4 && "Too many instructions in VPT block!"); 170 } 171 172 // Have we found an instruction within the block which defines the vpr? If 173 // so, not all the instructions in the block will have the same predicate. 174 bool HasNonUniformPredicate() const { 175 return Divergent != nullptr; 176 } 177 178 // Is the given instruction part of the predicate set controlling the entry 179 // to the block. 180 bool IsPredicatedOn(MachineInstr *MI) const { 181 return PredicateThen->Predicates.count(MI); 182 } 183 184 // Returns true if this is a VPT instruction. 185 bool isVPT() const { return !isVPST(); } 186 187 // Returns true if this is a VPST instruction. 188 bool isVPST() const { 189 return PredicateThen->MI->getOpcode() == ARM::MVE_VPST; 190 } 191 192 // Is the given instruction the only predicate which controls the entry to 193 // the block. 194 bool IsOnlyPredicatedOn(MachineInstr *MI) const { 195 return IsPredicatedOn(MI) && PredicateThen->Predicates.size() == 1; 196 } 197 198 unsigned size() const { return Insts.size(); } 199 SmallVectorImpl<PredicatedMI> &getInsts() { return Insts; } 200 MachineInstr *getPredicateThen() const { return PredicateThen->MI; } 201 PredicatedMI *getDivergent() const { return Divergent; } 202 }; 203 204 struct Reduction { 205 MachineInstr *Init; 206 MachineInstr &Copy; 207 MachineInstr &Reduce; 208 MachineInstr &VPSEL; 209 210 Reduction(MachineInstr *Init, MachineInstr *Mov, MachineInstr *Add, 211 MachineInstr *Sel) 212 : Init(Init), Copy(*Mov), Reduce(*Add), VPSEL(*Sel) { } 213 }; 214 215 struct LowOverheadLoop { 216 217 MachineLoop &ML; 218 MachineBasicBlock *Preheader = nullptr; 219 MachineLoopInfo &MLI; 220 ReachingDefAnalysis &RDA; 221 const TargetRegisterInfo &TRI; 222 const ARMBaseInstrInfo &TII; 223 MachineFunction *MF = nullptr; 224 MachineInstr *InsertPt = nullptr; 225 MachineInstr *Start = nullptr; 226 MachineInstr *Dec = nullptr; 227 MachineInstr *End = nullptr; 228 MachineInstr *VCTP = nullptr; 229 SmallPtrSet<MachineInstr*, 4> SecondaryVCTPs; 230 VPTBlock *CurrentBlock = nullptr; 231 SetVector<MachineInstr*> CurrentPredicate; 232 SmallVector<VPTBlock, 4> VPTBlocks; 233 SmallPtrSet<MachineInstr*, 4> ToRemove; 234 SmallVector<std::unique_ptr<Reduction>, 1> Reductions; 235 SmallPtrSet<MachineInstr*, 4> BlockMasksToRecompute; 236 bool Revert = false; 237 bool CannotTailPredicate = false; 238 239 LowOverheadLoop(MachineLoop &ML, MachineLoopInfo &MLI, 240 ReachingDefAnalysis &RDA, const TargetRegisterInfo &TRI, 241 const ARMBaseInstrInfo &TII) 242 : ML(ML), MLI(MLI), RDA(RDA), TRI(TRI), TII(TII) { 243 MF = ML.getHeader()->getParent(); 244 if (auto *MBB = ML.getLoopPreheader()) 245 Preheader = MBB; 246 else if (auto *MBB = MLI.findLoopPreheader(&ML, true)) 247 Preheader = MBB; 248 } 249 250 // If this is an MVE instruction, check that we know how to use tail 251 // predication with it. Record VPT blocks and return whether the 252 // instruction is valid for tail predication. 253 bool ValidateMVEInst(MachineInstr *MI); 254 255 void AnalyseMVEInst(MachineInstr *MI) { 256 CannotTailPredicate = !ValidateMVEInst(MI); 257 } 258 259 bool IsTailPredicationLegal() const { 260 // For now, let's keep things really simple and only support a single 261 // block for tail predication. 262 return !Revert && FoundAllComponents() && VCTP && 263 !CannotTailPredicate && ML.getNumBlocks() == 1; 264 } 265 266 // Check that the predication in the loop will be equivalent once we 267 // perform the conversion. Also ensure that we can provide the number 268 // of elements to the loop start instruction. 269 bool ValidateTailPredicate(MachineInstr *StartInsertPt); 270 271 // See whether the live-out instructions are a reduction that we can fixup 272 // later. 273 bool FindValidReduction(InstSet &LiveMIs, InstSet &LiveOutUsers); 274 275 // Check that any values available outside of the loop will be the same 276 // after tail predication conversion. 277 bool ValidateLiveOuts(); 278 279 // Is it safe to define LR with DLS/WLS? 280 // LR can be defined if it is the operand to start, because it's the same 281 // value, or if it's going to be equivalent to the operand to Start. 282 MachineInstr *isSafeToDefineLR(); 283 284 // Check the branch targets are within range and we satisfy our 285 // restrictions. 286 void CheckLegality(ARMBasicBlockUtils *BBUtils); 287 288 bool FoundAllComponents() const { 289 return Start && Dec && End; 290 } 291 292 SmallVectorImpl<VPTBlock> &getVPTBlocks() { return VPTBlocks; } 293 294 // Return the loop iteration count, or the number of elements if we're tail 295 // predicating. 296 MachineOperand &getCount() { 297 return IsTailPredicationLegal() ? 298 VCTP->getOperand(1) : Start->getOperand(0); 299 } 300 301 unsigned getStartOpcode() const { 302 bool IsDo = Start->getOpcode() == ARM::t2DoLoopStart; 303 if (!IsTailPredicationLegal()) 304 return IsDo ? ARM::t2DLS : ARM::t2WLS; 305 306 return VCTPOpcodeToLSTP(VCTP->getOpcode(), IsDo); 307 } 308 309 void dump() const { 310 if (Start) dbgs() << "ARM Loops: Found Loop Start: " << *Start; 311 if (Dec) dbgs() << "ARM Loops: Found Loop Dec: " << *Dec; 312 if (End) dbgs() << "ARM Loops: Found Loop End: " << *End; 313 if (VCTP) dbgs() << "ARM Loops: Found VCTP: " << *VCTP; 314 if (!FoundAllComponents()) 315 dbgs() << "ARM Loops: Not a low-overhead loop.\n"; 316 else if (!(Start && Dec && End)) 317 dbgs() << "ARM Loops: Failed to find all loop components.\n"; 318 } 319 }; 320 321 class ARMLowOverheadLoops : public MachineFunctionPass { 322 MachineFunction *MF = nullptr; 323 MachineLoopInfo *MLI = nullptr; 324 ReachingDefAnalysis *RDA = nullptr; 325 const ARMBaseInstrInfo *TII = nullptr; 326 MachineRegisterInfo *MRI = nullptr; 327 const TargetRegisterInfo *TRI = nullptr; 328 std::unique_ptr<ARMBasicBlockUtils> BBUtils = nullptr; 329 330 public: 331 static char ID; 332 333 ARMLowOverheadLoops() : MachineFunctionPass(ID) { } 334 335 void getAnalysisUsage(AnalysisUsage &AU) const override { 336 AU.setPreservesCFG(); 337 AU.addRequired<MachineLoopInfo>(); 338 AU.addRequired<ReachingDefAnalysis>(); 339 MachineFunctionPass::getAnalysisUsage(AU); 340 } 341 342 bool runOnMachineFunction(MachineFunction &MF) override; 343 344 MachineFunctionProperties getRequiredProperties() const override { 345 return MachineFunctionProperties().set( 346 MachineFunctionProperties::Property::NoVRegs).set( 347 MachineFunctionProperties::Property::TracksLiveness); 348 } 349 350 StringRef getPassName() const override { 351 return ARM_LOW_OVERHEAD_LOOPS_NAME; 352 } 353 354 private: 355 bool ProcessLoop(MachineLoop *ML); 356 357 bool RevertNonLoops(); 358 359 void RevertWhile(MachineInstr *MI) const; 360 361 bool RevertLoopDec(MachineInstr *MI) const; 362 363 void RevertLoopEnd(MachineInstr *MI, bool SkipCmp = false) const; 364 365 void ConvertVPTBlocks(LowOverheadLoop &LoLoop); 366 367 void FixupReductions(LowOverheadLoop &LoLoop) const; 368 369 MachineInstr *ExpandLoopStart(LowOverheadLoop &LoLoop); 370 371 void Expand(LowOverheadLoop &LoLoop); 372 373 void IterationCountDCE(LowOverheadLoop &LoLoop); 374 }; 375 } 376 377 char ARMLowOverheadLoops::ID = 0; 378 379 INITIALIZE_PASS(ARMLowOverheadLoops, DEBUG_TYPE, ARM_LOW_OVERHEAD_LOOPS_NAME, 380 false, false) 381 382 MachineInstr *LowOverheadLoop::isSafeToDefineLR() { 383 // We can define LR because LR already contains the same value. 384 if (Start->getOperand(0).getReg() == ARM::LR) 385 return Start; 386 387 unsigned CountReg = Start->getOperand(0).getReg(); 388 auto IsMoveLR = [&CountReg](MachineInstr *MI) { 389 return MI->getOpcode() == ARM::tMOVr && 390 MI->getOperand(0).getReg() == ARM::LR && 391 MI->getOperand(1).getReg() == CountReg && 392 MI->getOperand(2).getImm() == ARMCC::AL; 393 }; 394 395 MachineBasicBlock *MBB = Start->getParent(); 396 397 // Find an insertion point: 398 // - Is there a (mov lr, Count) before Start? If so, and nothing else writes 399 // to Count before Start, we can insert at that mov. 400 if (auto *LRDef = RDA.getUniqueReachingMIDef(Start, ARM::LR)) 401 if (IsMoveLR(LRDef) && RDA.hasSameReachingDef(Start, LRDef, CountReg)) 402 return LRDef; 403 404 // - Is there a (mov lr, Count) after Start? If so, and nothing else writes 405 // to Count after Start, we can insert at that mov. 406 if (auto *LRDef = RDA.getLocalLiveOutMIDef(MBB, ARM::LR)) 407 if (IsMoveLR(LRDef) && RDA.hasSameReachingDef(Start, LRDef, CountReg)) 408 return LRDef; 409 410 // We've found no suitable LR def and Start doesn't use LR directly. Can we 411 // just define LR anyway? 412 return RDA.isSafeToDefRegAt(Start, ARM::LR) ? Start : nullptr; 413 } 414 415 bool LowOverheadLoop::ValidateTailPredicate(MachineInstr *StartInsertPt) { 416 assert(VCTP && "VCTP instruction expected but is not set"); 417 // All predication within the loop should be based on vctp. If the block 418 // isn't predicated on entry, check whether the vctp is within the block 419 // and that all other instructions are then predicated on it. 420 for (auto &Block : VPTBlocks) { 421 if (Block.IsPredicatedOn(VCTP)) 422 continue; 423 if (Block.HasNonUniformPredicate() && !isVCTP(Block.getDivergent()->MI)) { 424 LLVM_DEBUG(dbgs() << "ARM Loops: Found unsupported diverging predicate: " 425 << *Block.getDivergent()->MI); 426 return false; 427 } 428 SmallVectorImpl<PredicatedMI> &Insts = Block.getInsts(); 429 for (auto &PredMI : Insts) { 430 // Check the instructions in the block and only allow: 431 // - VCTPs 432 // - Instructions predicated on the main VCTP 433 // - Any VCMP 434 // - VCMPs just "and" their result with VPR.P0. Whether they are 435 // located before/after the VCTP is irrelevant - the end result will 436 // be the same in both cases, so there's no point in requiring them 437 // to be located after the VCTP! 438 if (PredMI.Predicates.count(VCTP) || isVCTP(PredMI.MI) || 439 VCMPOpcodeToVPT(PredMI.MI->getOpcode()) != 0) 440 continue; 441 LLVM_DEBUG(dbgs() << "ARM Loops: Can't convert: " << *PredMI.MI 442 << " - which is predicated on:\n"; 443 for (auto *MI : PredMI.Predicates) 444 dbgs() << " - " << *MI); 445 return false; 446 } 447 } 448 449 if (!ValidateLiveOuts()) 450 return false; 451 452 // For tail predication, we need to provide the number of elements, instead 453 // of the iteration count, to the loop start instruction. The number of 454 // elements is provided to the vctp instruction, so we need to check that 455 // we can use this register at InsertPt. 456 Register NumElements = VCTP->getOperand(1).getReg(); 457 458 // If the register is defined within loop, then we can't perform TP. 459 // TODO: Check whether this is just a mov of a register that would be 460 // available. 461 if (RDA.hasLocalDefBefore(VCTP, NumElements)) { 462 LLVM_DEBUG(dbgs() << "ARM Loops: VCTP operand is defined in the loop.\n"); 463 return false; 464 } 465 466 // The element count register maybe defined after InsertPt, in which case we 467 // need to try to move either InsertPt or the def so that the [w|d]lstp can 468 // use the value. 469 // TODO: On failing to move an instruction, check if the count is provided by 470 // a mov and whether we can use the mov operand directly. 471 MachineBasicBlock *InsertBB = StartInsertPt->getParent(); 472 if (!RDA.isReachingDefLiveOut(StartInsertPt, NumElements)) { 473 if (auto *ElemDef = RDA.getLocalLiveOutMIDef(InsertBB, NumElements)) { 474 if (RDA.isSafeToMoveForwards(ElemDef, StartInsertPt)) { 475 ElemDef->removeFromParent(); 476 InsertBB->insert(MachineBasicBlock::iterator(StartInsertPt), ElemDef); 477 LLVM_DEBUG(dbgs() << "ARM Loops: Moved element count def: " 478 << *ElemDef); 479 } else if (RDA.isSafeToMoveBackwards(StartInsertPt, ElemDef)) { 480 StartInsertPt->removeFromParent(); 481 InsertBB->insertAfter(MachineBasicBlock::iterator(ElemDef), 482 StartInsertPt); 483 LLVM_DEBUG(dbgs() << "ARM Loops: Moved start past: " << *ElemDef); 484 } else { 485 LLVM_DEBUG(dbgs() << "ARM Loops: Unable to move element count to loop " 486 << "start instruction.\n"); 487 return false; 488 } 489 } 490 } 491 492 // Especially in the case of while loops, InsertBB may not be the 493 // preheader, so we need to check that the register isn't redefined 494 // before entering the loop. 495 auto CannotProvideElements = [this](MachineBasicBlock *MBB, 496 Register NumElements) { 497 // NumElements is redefined in this block. 498 if (RDA.hasLocalDefBefore(&MBB->back(), NumElements)) 499 return true; 500 501 // Don't continue searching up through multiple predecessors. 502 if (MBB->pred_size() > 1) 503 return true; 504 505 return false; 506 }; 507 508 // First, find the block that looks like the preheader. 509 MachineBasicBlock *MBB = Preheader; 510 if (!MBB) { 511 LLVM_DEBUG(dbgs() << "ARM Loops: Didn't find preheader.\n"); 512 return false; 513 } 514 515 // Then search backwards for a def, until we get to InsertBB. 516 while (MBB != InsertBB) { 517 if (CannotProvideElements(MBB, NumElements)) { 518 LLVM_DEBUG(dbgs() << "ARM Loops: Unable to provide element count.\n"); 519 return false; 520 } 521 MBB = *MBB->pred_begin(); 522 } 523 524 // Check that the value change of the element count is what we expect and 525 // that the predication will be equivalent. For this we need: 526 // NumElements = NumElements - VectorWidth. The sub will be a sub immediate 527 // and we can also allow register copies within the chain too. 528 auto IsValidSub = [](MachineInstr *MI, int ExpectedVecWidth) { 529 return -getAddSubImmediate(*MI) == ExpectedVecWidth; 530 }; 531 532 MBB = VCTP->getParent(); 533 if (auto *Def = RDA.getUniqueReachingMIDef(&MBB->back(), NumElements)) { 534 SmallPtrSet<MachineInstr*, 2> ElementChain; 535 SmallPtrSet<MachineInstr*, 2> Ignore = { VCTP }; 536 unsigned ExpectedVectorWidth = getTailPredVectorWidth(VCTP->getOpcode()); 537 538 Ignore.insert(SecondaryVCTPs.begin(), SecondaryVCTPs.end()); 539 540 if (RDA.isSafeToRemove(Def, ElementChain, Ignore)) { 541 bool FoundSub = false; 542 543 for (auto *MI : ElementChain) { 544 if (isMovRegOpcode(MI->getOpcode())) 545 continue; 546 547 if (isSubImmOpcode(MI->getOpcode())) { 548 if (FoundSub || !IsValidSub(MI, ExpectedVectorWidth)) 549 return false; 550 FoundSub = true; 551 } else 552 return false; 553 } 554 555 LLVM_DEBUG(dbgs() << "ARM Loops: Will remove element count chain:\n"; 556 for (auto *MI : ElementChain) 557 dbgs() << " - " << *MI); 558 ToRemove.insert(ElementChain.begin(), ElementChain.end()); 559 } 560 } 561 return true; 562 } 563 564 static bool isVectorPredicated(MachineInstr *MI) { 565 int PIdx = llvm::findFirstVPTPredOperandIdx(*MI); 566 return PIdx != -1 && MI->getOperand(PIdx + 1).getReg() == ARM::VPR; 567 } 568 569 static bool isRegInClass(const MachineOperand &MO, 570 const TargetRegisterClass *Class) { 571 return MO.isReg() && MO.getReg() && Class->contains(MO.getReg()); 572 } 573 574 // MVE 'narrowing' operate on half a lane, reading from half and writing 575 // to half, which are referred to has the top and bottom half. The other 576 // half retains its previous value. 577 static bool retainsPreviousHalfElement(const MachineInstr &MI) { 578 const MCInstrDesc &MCID = MI.getDesc(); 579 uint64_t Flags = MCID.TSFlags; 580 return (Flags & ARMII::RetainsPreviousHalfElement) != 0; 581 } 582 583 // Some MVE instructions read from the top/bottom halves of their operand(s) 584 // and generate a vector result with result elements that are double the 585 // width of the input. 586 static bool producesDoubleWidthResult(const MachineInstr &MI) { 587 const MCInstrDesc &MCID = MI.getDesc(); 588 uint64_t Flags = MCID.TSFlags; 589 return (Flags & ARMII::DoubleWidthResult) != 0; 590 } 591 592 static bool isHorizontalReduction(const MachineInstr &MI) { 593 const MCInstrDesc &MCID = MI.getDesc(); 594 uint64_t Flags = MCID.TSFlags; 595 return (Flags & ARMII::HorizontalReduction) != 0; 596 } 597 598 // Can this instruction generate a non-zero result when given only zeroed 599 // operands? This allows us to know that, given operands with false bytes 600 // zeroed by masked loads, that the result will also contain zeros in those 601 // bytes. 602 static bool canGenerateNonZeros(const MachineInstr &MI) { 603 604 // Check for instructions which can write into a larger element size, 605 // possibly writing into a previous zero'd lane. 606 if (producesDoubleWidthResult(MI)) 607 return true; 608 609 switch (MI.getOpcode()) { 610 default: 611 break; 612 // FIXME: VNEG FP and -0? I think we'll need to handle this once we allow 613 // fp16 -> fp32 vector conversions. 614 // Instructions that perform a NOT will generate 1s from 0s. 615 case ARM::MVE_VMVN: 616 case ARM::MVE_VORN: 617 // Count leading zeros will do just that! 618 case ARM::MVE_VCLZs8: 619 case ARM::MVE_VCLZs16: 620 case ARM::MVE_VCLZs32: 621 return true; 622 } 623 return false; 624 } 625 626 627 // Look at its register uses to see if it only can only receive zeros 628 // into its false lanes which would then produce zeros. Also check that 629 // the output register is also defined by an FalseLanesZero instruction 630 // so that if tail-predication happens, the lanes that aren't updated will 631 // still be zeros. 632 static bool producesFalseLanesZero(MachineInstr &MI, 633 const TargetRegisterClass *QPRs, 634 const ReachingDefAnalysis &RDA, 635 InstSet &FalseLanesZero) { 636 if (canGenerateNonZeros(MI)) 637 return false; 638 639 bool AllowScalars = isHorizontalReduction(MI); 640 for (auto &MO : MI.operands()) { 641 if (!MO.isReg() || !MO.getReg()) 642 continue; 643 if (!isRegInClass(MO, QPRs) && AllowScalars) 644 continue; 645 if (auto *OpDef = RDA.getMIOperand(&MI, MO)) 646 if (FalseLanesZero.count(OpDef)) 647 continue; 648 return false; 649 } 650 LLVM_DEBUG(dbgs() << "ARM Loops: Always False Zeros: " << MI); 651 return true; 652 } 653 654 bool 655 LowOverheadLoop::FindValidReduction(InstSet &LiveMIs, InstSet &LiveOutUsers) { 656 // Also check for reductions where the operation needs to be merging values 657 // from the last and previous loop iterations. This means an instruction 658 // producing a value and a vmov storing the value calculated in the previous 659 // iteration. So we can have two live-out regs, one produced by a vmov and 660 // both being consumed by a vpsel. 661 LLVM_DEBUG(dbgs() << "ARM Loops: Looking for reduction live-outs:\n"; 662 for (auto *MI : LiveMIs) 663 dbgs() << " - " << *MI); 664 665 if (!Preheader) 666 return false; 667 668 // Expect a vmov, a vadd and a single vpsel user. 669 // TODO: This means we can't currently support multiple reductions in the 670 // loop. 671 if (LiveMIs.size() != 2 || LiveOutUsers.size() != 1) 672 return false; 673 674 MachineInstr *VPSEL = *LiveOutUsers.begin(); 675 if (VPSEL->getOpcode() != ARM::MVE_VPSEL) 676 return false; 677 678 unsigned VPRIdx = llvm::findFirstVPTPredOperandIdx(*VPSEL) + 1; 679 MachineInstr *Pred = RDA.getMIOperand(VPSEL, VPRIdx); 680 if (!Pred || Pred != VCTP) { 681 LLVM_DEBUG(dbgs() << "ARM Loops: Not using equivalent predicate.\n"); 682 return false; 683 } 684 685 MachineInstr *Reduce = RDA.getMIOperand(VPSEL, 1); 686 if (!Reduce) 687 return false; 688 689 assert(LiveMIs.count(Reduce) && "Expected MI to be live-out"); 690 691 // TODO: Support more operations than VADD. 692 switch (VCTP->getOpcode()) { 693 default: 694 return false; 695 case ARM::MVE_VCTP8: 696 if (Reduce->getOpcode() != ARM::MVE_VADDi8) 697 return false; 698 break; 699 case ARM::MVE_VCTP16: 700 if (Reduce->getOpcode() != ARM::MVE_VADDi16) 701 return false; 702 break; 703 case ARM::MVE_VCTP32: 704 if (Reduce->getOpcode() != ARM::MVE_VADDi32) 705 return false; 706 break; 707 } 708 709 // Test that the reduce op is overwriting ones of its operands. 710 if (Reduce->getOperand(0).getReg() != Reduce->getOperand(1).getReg() && 711 Reduce->getOperand(0).getReg() != Reduce->getOperand(2).getReg()) { 712 LLVM_DEBUG(dbgs() << "ARM Loops: Reducing op isn't overwriting itself.\n"); 713 return false; 714 } 715 716 // Check that the VORR is actually a VMOV. 717 MachineInstr *Copy = RDA.getMIOperand(VPSEL, 2); 718 if (!Copy || Copy->getOpcode() != ARM::MVE_VORR || 719 !Copy->getOperand(1).isReg() || !Copy->getOperand(2).isReg() || 720 Copy->getOperand(1).getReg() != Copy->getOperand(2).getReg()) 721 return false; 722 723 assert(LiveMIs.count(Copy) && "Expected MI to be live-out"); 724 725 // Check that the vadd and vmov are only used by each other and the vpsel. 726 SmallPtrSet<MachineInstr*, 2> CopyUsers; 727 RDA.getGlobalUses(Copy, Copy->getOperand(0).getReg(), CopyUsers); 728 if (CopyUsers.size() > 2 || !CopyUsers.count(Reduce)) { 729 LLVM_DEBUG(dbgs() << "ARM Loops: Copy users unsupported.\n"); 730 return false; 731 } 732 733 SmallPtrSet<MachineInstr*, 2> ReduceUsers; 734 RDA.getGlobalUses(Reduce, Reduce->getOperand(0).getReg(), ReduceUsers); 735 if (ReduceUsers.size() > 2 || !ReduceUsers.count(Copy)) { 736 LLVM_DEBUG(dbgs() << "ARM Loops: Reduce users unsupported.\n"); 737 return false; 738 } 739 740 // Then find whether there's an instruction initialising the register that 741 // is storing the reduction. 742 SmallPtrSet<MachineInstr*, 2> Incoming; 743 RDA.getLiveOuts(Preheader, Copy->getOperand(1).getReg(), Incoming); 744 if (Incoming.size() > 1) 745 return false; 746 747 MachineInstr *Init = Incoming.empty() ? nullptr : *Incoming.begin(); 748 LLVM_DEBUG(dbgs() << "ARM Loops: Found a reduction:\n" 749 << " - " << *Copy 750 << " - " << *Reduce 751 << " - " << *VPSEL); 752 Reductions.push_back(std::make_unique<Reduction>(Init, Copy, Reduce, VPSEL)); 753 return true; 754 } 755 756 bool LowOverheadLoop::ValidateLiveOuts() { 757 // We want to find out if the tail-predicated version of this loop will 758 // produce the same values as the loop in its original form. For this to 759 // be true, the newly inserted implicit predication must not change the 760 // the (observable) results. 761 // We're doing this because many instructions in the loop will not be 762 // predicated and so the conversion from VPT predication to tail-predication 763 // can result in different values being produced; due to the tail-predication 764 // preventing many instructions from updating their falsely predicated 765 // lanes. This analysis assumes that all the instructions perform lane-wise 766 // operations and don't perform any exchanges. 767 // A masked load, whether through VPT or tail predication, will write zeros 768 // to any of the falsely predicated bytes. So, from the loads, we know that 769 // the false lanes are zeroed and here we're trying to track that those false 770 // lanes remain zero, or where they change, the differences are masked away 771 // by their user(s). 772 // All MVE loads and stores have to be predicated, so we know that any load 773 // operands, or stored results are equivalent already. Other explicitly 774 // predicated instructions will perform the same operation in the original 775 // loop and the tail-predicated form too. Because of this, we can insert 776 // loads, stores and other predicated instructions into our Predicated 777 // set and build from there. 778 const TargetRegisterClass *QPRs = TRI.getRegClass(ARM::MQPRRegClassID); 779 SetVector<MachineInstr *> FalseLanesUnknown; 780 SmallPtrSet<MachineInstr *, 4> FalseLanesZero; 781 SmallPtrSet<MachineInstr *, 4> Predicated; 782 MachineBasicBlock *Header = ML.getHeader(); 783 784 for (auto &MI : *Header) { 785 const MCInstrDesc &MCID = MI.getDesc(); 786 uint64_t Flags = MCID.TSFlags; 787 if ((Flags & ARMII::DomainMask) != ARMII::DomainMVE) 788 continue; 789 790 if (isVCTP(&MI) || isVPTOpcode(MI.getOpcode())) 791 continue; 792 793 // Predicated loads will write zeros to the falsely predicated bytes of the 794 // destination register. 795 if (isVectorPredicated(&MI)) { 796 if (MI.mayLoad()) 797 FalseLanesZero.insert(&MI); 798 Predicated.insert(&MI); 799 continue; 800 } 801 802 if (MI.getNumDefs() == 0) 803 continue; 804 805 if (!producesFalseLanesZero(MI, QPRs, RDA, FalseLanesZero)) { 806 // We require retaining and horizontal operations to operate upon zero'd 807 // false lanes to ensure the conversion doesn't change the output. 808 if (retainsPreviousHalfElement(MI) || isHorizontalReduction(MI)) 809 return false; 810 // Otherwise we need to evaluate this instruction later to see whether 811 // unknown false lanes will get masked away by their user(s). 812 FalseLanesUnknown.insert(&MI); 813 } else if (!isHorizontalReduction(MI)) 814 FalseLanesZero.insert(&MI); 815 } 816 817 auto HasPredicatedUsers = [this](MachineInstr *MI, const MachineOperand &MO, 818 SmallPtrSetImpl<MachineInstr *> &Predicated) { 819 SmallPtrSet<MachineInstr *, 2> Uses; 820 RDA.getGlobalUses(MI, MO.getReg(), Uses); 821 for (auto *Use : Uses) { 822 if (Use != MI && !Predicated.count(Use)) 823 return false; 824 } 825 return true; 826 }; 827 828 // Visit the unknowns in reverse so that we can start at the values being 829 // stored and then we can work towards the leaves, hopefully adding more 830 // instructions to Predicated. Successfully terminating the loop means that 831 // all the unknown values have to found to be masked by predicated user(s). 832 // For any unpredicated values, we store them in NonPredicated so that we 833 // can later check whether these form a reduction. 834 SmallPtrSet<MachineInstr*, 2> NonPredicated; 835 for (auto *MI : reverse(FalseLanesUnknown)) { 836 for (auto &MO : MI->operands()) { 837 if (!isRegInClass(MO, QPRs) || !MO.isDef()) 838 continue; 839 if (!HasPredicatedUsers(MI, MO, Predicated)) { 840 LLVM_DEBUG(dbgs() << "ARM Loops: Found an unknown def of : " 841 << TRI.getRegAsmName(MO.getReg()) << " at " << *MI); 842 NonPredicated.insert(MI); 843 continue; 844 } 845 } 846 // Any unknown false lanes have been masked away by the user(s). 847 Predicated.insert(MI); 848 } 849 850 SmallPtrSet<MachineInstr *, 2> LiveOutMIs; 851 SmallPtrSet<MachineInstr*, 2> LiveOutUsers; 852 SmallVector<MachineBasicBlock *, 2> ExitBlocks; 853 ML.getExitBlocks(ExitBlocks); 854 assert(ML.getNumBlocks() == 1 && "Expected single block loop!"); 855 assert(ExitBlocks.size() == 1 && "Expected a single exit block"); 856 MachineBasicBlock *ExitBB = ExitBlocks.front(); 857 for (const MachineBasicBlock::RegisterMaskPair &RegMask : ExitBB->liveins()) { 858 // Check Q-regs that are live in the exit blocks. We don't collect scalars 859 // because they won't be affected by lane predication. 860 if (QPRs->contains(RegMask.PhysReg)) { 861 if (auto *MI = RDA.getLocalLiveOutMIDef(Header, RegMask.PhysReg)) 862 LiveOutMIs.insert(MI); 863 RDA.getLiveInUses(ExitBB, RegMask.PhysReg, LiveOutUsers); 864 } 865 } 866 867 // If we have any non-predicated live-outs, they need to be part of a 868 // reduction that we can fixup later. The reduction that the form of an 869 // operation that uses its previous values through a vmov and then a vpsel 870 // resides in the exit blocks to select the final bytes from n and n-1 871 // iterations. 872 if (!NonPredicated.empty() && 873 !FindValidReduction(NonPredicated, LiveOutUsers)) 874 return false; 875 876 // We've already validated that any VPT predication within the loop will be 877 // equivalent when we perform the predication transformation; so we know that 878 // any VPT predicated instruction is predicated upon VCTP. Any live-out 879 // instruction needs to be predicated, so check this here. The instructions 880 // in NonPredicated have been found to be a reduction that we can ensure its 881 // legality. 882 for (auto *MI : LiveOutMIs) 883 if (!isVectorPredicated(MI) && !NonPredicated.count(MI)) 884 return false; 885 886 return true; 887 } 888 889 void LowOverheadLoop::CheckLegality(ARMBasicBlockUtils *BBUtils) { 890 if (Revert) 891 return; 892 893 if (!End->getOperand(1).isMBB()) 894 report_fatal_error("Expected LoopEnd to target basic block"); 895 896 // TODO Maybe there's cases where the target doesn't have to be the header, 897 // but for now be safe and revert. 898 if (End->getOperand(1).getMBB() != ML.getHeader()) { 899 LLVM_DEBUG(dbgs() << "ARM Loops: LoopEnd is not targetting header.\n"); 900 Revert = true; 901 return; 902 } 903 904 // The WLS and LE instructions have 12-bits for the label offset. WLS 905 // requires a positive offset, while LE uses negative. 906 if (BBUtils->getOffsetOf(End) < BBUtils->getOffsetOf(ML.getHeader()) || 907 !BBUtils->isBBInRange(End, ML.getHeader(), 4094)) { 908 LLVM_DEBUG(dbgs() << "ARM Loops: LE offset is out-of-range\n"); 909 Revert = true; 910 return; 911 } 912 913 if (Start->getOpcode() == ARM::t2WhileLoopStart && 914 (BBUtils->getOffsetOf(Start) > 915 BBUtils->getOffsetOf(Start->getOperand(1).getMBB()) || 916 !BBUtils->isBBInRange(Start, Start->getOperand(1).getMBB(), 4094))) { 917 LLVM_DEBUG(dbgs() << "ARM Loops: WLS offset is out-of-range!\n"); 918 Revert = true; 919 return; 920 } 921 922 InsertPt = Revert ? nullptr : isSafeToDefineLR(); 923 if (!InsertPt) { 924 LLVM_DEBUG(dbgs() << "ARM Loops: Unable to find safe insertion point.\n"); 925 Revert = true; 926 return; 927 } else 928 LLVM_DEBUG(dbgs() << "ARM Loops: Start insertion point: " << *InsertPt); 929 930 if (!IsTailPredicationLegal()) { 931 LLVM_DEBUG(if (!VCTP) 932 dbgs() << "ARM Loops: Didn't find a VCTP instruction.\n"; 933 dbgs() << "ARM Loops: Tail-predication is not valid.\n"); 934 return; 935 } 936 937 assert(ML.getBlocks().size() == 1 && 938 "Shouldn't be processing a loop with more than one block"); 939 CannotTailPredicate = !ValidateTailPredicate(InsertPt); 940 LLVM_DEBUG(if (CannotTailPredicate) 941 dbgs() << "ARM Loops: Couldn't validate tail predicate.\n"); 942 } 943 944 bool LowOverheadLoop::ValidateMVEInst(MachineInstr* MI) { 945 if (CannotTailPredicate) 946 return false; 947 948 if (isVCTP(MI)) { 949 // If we find another VCTP, check whether it uses the same value as the main VCTP. 950 // If it does, store it in the SecondaryVCTPs set, else refuse it. 951 if (VCTP) { 952 if (!VCTP->getOperand(1).isIdenticalTo(MI->getOperand(1)) || 953 !RDA.hasSameReachingDef(VCTP, MI, MI->getOperand(1).getReg())) { 954 LLVM_DEBUG(dbgs() << "ARM Loops: Found VCTP with a different reaching " 955 "definition from the main VCTP"); 956 return false; 957 } 958 LLVM_DEBUG(dbgs() << "ARM Loops: Found secondary VCTP: " << *MI); 959 SecondaryVCTPs.insert(MI); 960 } else { 961 LLVM_DEBUG(dbgs() << "ARM Loops: Found 'main' VCTP: " << *MI); 962 VCTP = MI; 963 } 964 } else if (isVPTOpcode(MI->getOpcode())) { 965 if (MI->getOpcode() != ARM::MVE_VPST) { 966 assert(MI->findRegisterDefOperandIdx(ARM::VPR) != -1 && 967 "VPT does not implicitly define VPR?!"); 968 CurrentPredicate.insert(MI); 969 } 970 971 VPTBlocks.emplace_back(MI, CurrentPredicate); 972 CurrentBlock = &VPTBlocks.back(); 973 return true; 974 } else if (MI->getOpcode() == ARM::MVE_VPSEL || 975 MI->getOpcode() == ARM::MVE_VPNOT) { 976 // TODO: Allow VPSEL and VPNOT, we currently cannot because: 977 // 1) It will use the VPR as a predicate operand, but doesn't have to be 978 // instead a VPT block, which means we can assert while building up 979 // the VPT block because we don't find another VPT or VPST to being a new 980 // one. 981 // 2) VPSEL still requires a VPR operand even after tail predicating, 982 // which means we can't remove it unless there is another 983 // instruction, such as vcmp, that can provide the VPR def. 984 return false; 985 } 986 987 bool IsUse = false; 988 bool IsDef = false; 989 const MCInstrDesc &MCID = MI->getDesc(); 990 for (int i = MI->getNumOperands() - 1; i >= 0; --i) { 991 const MachineOperand &MO = MI->getOperand(i); 992 if (!MO.isReg() || MO.getReg() != ARM::VPR) 993 continue; 994 995 if (MO.isDef()) { 996 CurrentPredicate.insert(MI); 997 IsDef = true; 998 } else if (ARM::isVpred(MCID.OpInfo[i].OperandType)) { 999 CurrentBlock->addInst(MI, CurrentPredicate); 1000 IsUse = true; 1001 } else { 1002 LLVM_DEBUG(dbgs() << "ARM Loops: Found instruction using vpr: " << *MI); 1003 return false; 1004 } 1005 } 1006 1007 // If we find a vpr def that is not already predicated on the vctp, we've 1008 // got disjoint predicates that may not be equivalent when we do the 1009 // conversion. 1010 if (IsDef && !IsUse && VCTP && !isVCTP(MI)) { 1011 LLVM_DEBUG(dbgs() << "ARM Loops: Found disjoint vpr def: " << *MI); 1012 return false; 1013 } 1014 1015 uint64_t Flags = MCID.TSFlags; 1016 if ((Flags & ARMII::DomainMask) != ARMII::DomainMVE) 1017 return true; 1018 1019 // If we find an instruction that has been marked as not valid for tail 1020 // predication, only allow the instruction if it's contained within a valid 1021 // VPT block. 1022 if ((Flags & ARMII::ValidForTailPredication) == 0 && !IsUse) { 1023 LLVM_DEBUG(dbgs() << "ARM Loops: Can't tail predicate: " << *MI); 1024 return false; 1025 } 1026 1027 // If the instruction is already explicitly predicated, then the conversion 1028 // will be fine, but ensure that all memory operations are predicated. 1029 return !IsUse && MI->mayLoadOrStore() ? false : true; 1030 } 1031 1032 bool ARMLowOverheadLoops::runOnMachineFunction(MachineFunction &mf) { 1033 const ARMSubtarget &ST = static_cast<const ARMSubtarget&>(mf.getSubtarget()); 1034 if (!ST.hasLOB()) 1035 return false; 1036 1037 MF = &mf; 1038 LLVM_DEBUG(dbgs() << "ARM Loops on " << MF->getName() << " ------------- \n"); 1039 1040 MLI = &getAnalysis<MachineLoopInfo>(); 1041 RDA = &getAnalysis<ReachingDefAnalysis>(); 1042 MF->getProperties().set(MachineFunctionProperties::Property::TracksLiveness); 1043 MRI = &MF->getRegInfo(); 1044 TII = static_cast<const ARMBaseInstrInfo*>(ST.getInstrInfo()); 1045 TRI = ST.getRegisterInfo(); 1046 BBUtils = std::unique_ptr<ARMBasicBlockUtils>(new ARMBasicBlockUtils(*MF)); 1047 BBUtils->computeAllBlockSizes(); 1048 BBUtils->adjustBBOffsetsAfter(&MF->front()); 1049 1050 bool Changed = false; 1051 for (auto ML : *MLI) { 1052 if (!ML->getParentLoop()) 1053 Changed |= ProcessLoop(ML); 1054 } 1055 Changed |= RevertNonLoops(); 1056 return Changed; 1057 } 1058 1059 bool ARMLowOverheadLoops::ProcessLoop(MachineLoop *ML) { 1060 1061 bool Changed = false; 1062 1063 // Process inner loops first. 1064 for (auto I = ML->begin(), E = ML->end(); I != E; ++I) 1065 Changed |= ProcessLoop(*I); 1066 1067 LLVM_DEBUG(dbgs() << "ARM Loops: Processing loop containing:\n"; 1068 if (auto *Preheader = ML->getLoopPreheader()) 1069 dbgs() << " - " << Preheader->getName() << "\n"; 1070 else if (auto *Preheader = MLI->findLoopPreheader(ML)) 1071 dbgs() << " - " << Preheader->getName() << "\n"; 1072 else if (auto *Preheader = MLI->findLoopPreheader(ML, true)) 1073 dbgs() << " - " << Preheader->getName() << "\n"; 1074 for (auto *MBB : ML->getBlocks()) 1075 dbgs() << " - " << MBB->getName() << "\n"; 1076 ); 1077 1078 // Search the given block for a loop start instruction. If one isn't found, 1079 // and there's only one predecessor block, search that one too. 1080 std::function<MachineInstr*(MachineBasicBlock*)> SearchForStart = 1081 [&SearchForStart](MachineBasicBlock *MBB) -> MachineInstr* { 1082 for (auto &MI : *MBB) { 1083 if (isLoopStart(MI)) 1084 return &MI; 1085 } 1086 if (MBB->pred_size() == 1) 1087 return SearchForStart(*MBB->pred_begin()); 1088 return nullptr; 1089 }; 1090 1091 LowOverheadLoop LoLoop(*ML, *MLI, *RDA, *TRI, *TII); 1092 // Search the preheader for the start intrinsic. 1093 // FIXME: I don't see why we shouldn't be supporting multiple predecessors 1094 // with potentially multiple set.loop.iterations, so we need to enable this. 1095 if (LoLoop.Preheader) 1096 LoLoop.Start = SearchForStart(LoLoop.Preheader); 1097 else 1098 return false; 1099 1100 // Find the low-overhead loop components and decide whether or not to fall 1101 // back to a normal loop. Also look for a vctp instructions and decide 1102 // whether we can convert that predicate using tail predication. 1103 for (auto *MBB : reverse(ML->getBlocks())) { 1104 for (auto &MI : *MBB) { 1105 if (MI.isDebugValue()) 1106 continue; 1107 else if (MI.getOpcode() == ARM::t2LoopDec) 1108 LoLoop.Dec = &MI; 1109 else if (MI.getOpcode() == ARM::t2LoopEnd) 1110 LoLoop.End = &MI; 1111 else if (isLoopStart(MI)) 1112 LoLoop.Start = &MI; 1113 else if (MI.getDesc().isCall()) { 1114 // TODO: Though the call will require LE to execute again, does this 1115 // mean we should revert? Always executing LE hopefully should be 1116 // faster than performing a sub,cmp,br or even subs,br. 1117 LoLoop.Revert = true; 1118 LLVM_DEBUG(dbgs() << "ARM Loops: Found call.\n"); 1119 } else { 1120 // Record VPR defs and build up their corresponding vpt blocks. 1121 // Check we know how to tail predicate any mve instructions. 1122 LoLoop.AnalyseMVEInst(&MI); 1123 } 1124 } 1125 } 1126 1127 LLVM_DEBUG(LoLoop.dump()); 1128 if (!LoLoop.FoundAllComponents()) { 1129 LLVM_DEBUG(dbgs() << "ARM Loops: Didn't find loop start, update, end\n"); 1130 return false; 1131 } 1132 1133 // Check that the only instruction using LoopDec is LoopEnd. 1134 // TODO: Check for copy chains that really have no effect. 1135 SmallPtrSet<MachineInstr*, 2> Uses; 1136 RDA->getReachingLocalUses(LoLoop.Dec, ARM::LR, Uses); 1137 if (Uses.size() > 1 || !Uses.count(LoLoop.End)) { 1138 LLVM_DEBUG(dbgs() << "ARM Loops: Unable to remove LoopDec.\n"); 1139 LoLoop.Revert = true; 1140 } 1141 LoLoop.CheckLegality(BBUtils.get()); 1142 Expand(LoLoop); 1143 return true; 1144 } 1145 1146 // WhileLoopStart holds the exit block, so produce a cmp lr, 0 and then a 1147 // beq that branches to the exit branch. 1148 // TODO: We could also try to generate a cbz if the value in LR is also in 1149 // another low register. 1150 void ARMLowOverheadLoops::RevertWhile(MachineInstr *MI) const { 1151 LLVM_DEBUG(dbgs() << "ARM Loops: Reverting to cmp: " << *MI); 1152 MachineBasicBlock *MBB = MI->getParent(); 1153 MachineInstrBuilder MIB = BuildMI(*MBB, MI, MI->getDebugLoc(), 1154 TII->get(ARM::t2CMPri)); 1155 MIB.add(MI->getOperand(0)); 1156 MIB.addImm(0); 1157 MIB.addImm(ARMCC::AL); 1158 MIB.addReg(ARM::NoRegister); 1159 1160 MachineBasicBlock *DestBB = MI->getOperand(1).getMBB(); 1161 unsigned BrOpc = BBUtils->isBBInRange(MI, DestBB, 254) ? 1162 ARM::tBcc : ARM::t2Bcc; 1163 1164 MIB = BuildMI(*MBB, MI, MI->getDebugLoc(), TII->get(BrOpc)); 1165 MIB.add(MI->getOperand(1)); // branch target 1166 MIB.addImm(ARMCC::EQ); // condition code 1167 MIB.addReg(ARM::CPSR); 1168 MI->eraseFromParent(); 1169 } 1170 1171 bool ARMLowOverheadLoops::RevertLoopDec(MachineInstr *MI) const { 1172 LLVM_DEBUG(dbgs() << "ARM Loops: Reverting to sub: " << *MI); 1173 MachineBasicBlock *MBB = MI->getParent(); 1174 SmallPtrSet<MachineInstr*, 1> Ignore; 1175 for (auto I = MachineBasicBlock::iterator(MI), E = MBB->end(); I != E; ++I) { 1176 if (I->getOpcode() == ARM::t2LoopEnd) { 1177 Ignore.insert(&*I); 1178 break; 1179 } 1180 } 1181 1182 // If nothing defines CPSR between LoopDec and LoopEnd, use a t2SUBS. 1183 bool SetFlags = RDA->isSafeToDefRegAt(MI, ARM::CPSR, Ignore); 1184 1185 MachineInstrBuilder MIB = BuildMI(*MBB, MI, MI->getDebugLoc(), 1186 TII->get(ARM::t2SUBri)); 1187 MIB.addDef(ARM::LR); 1188 MIB.add(MI->getOperand(1)); 1189 MIB.add(MI->getOperand(2)); 1190 MIB.addImm(ARMCC::AL); 1191 MIB.addReg(0); 1192 1193 if (SetFlags) { 1194 MIB.addReg(ARM::CPSR); 1195 MIB->getOperand(5).setIsDef(true); 1196 } else 1197 MIB.addReg(0); 1198 1199 MI->eraseFromParent(); 1200 return SetFlags; 1201 } 1202 1203 // Generate a subs, or sub and cmp, and a branch instead of an LE. 1204 void ARMLowOverheadLoops::RevertLoopEnd(MachineInstr *MI, bool SkipCmp) const { 1205 LLVM_DEBUG(dbgs() << "ARM Loops: Reverting to cmp, br: " << *MI); 1206 1207 MachineBasicBlock *MBB = MI->getParent(); 1208 // Create cmp 1209 if (!SkipCmp) { 1210 MachineInstrBuilder MIB = BuildMI(*MBB, MI, MI->getDebugLoc(), 1211 TII->get(ARM::t2CMPri)); 1212 MIB.addReg(ARM::LR); 1213 MIB.addImm(0); 1214 MIB.addImm(ARMCC::AL); 1215 MIB.addReg(ARM::NoRegister); 1216 } 1217 1218 MachineBasicBlock *DestBB = MI->getOperand(1).getMBB(); 1219 unsigned BrOpc = BBUtils->isBBInRange(MI, DestBB, 254) ? 1220 ARM::tBcc : ARM::t2Bcc; 1221 1222 // Create bne 1223 MachineInstrBuilder MIB = 1224 BuildMI(*MBB, MI, MI->getDebugLoc(), TII->get(BrOpc)); 1225 MIB.add(MI->getOperand(1)); // branch target 1226 MIB.addImm(ARMCC::NE); // condition code 1227 MIB.addReg(ARM::CPSR); 1228 MI->eraseFromParent(); 1229 } 1230 1231 // Perform dead code elimation on the loop iteration count setup expression. 1232 // If we are tail-predicating, the number of elements to be processed is the 1233 // operand of the VCTP instruction in the vector body, see getCount(), which is 1234 // register $r3 in this example: 1235 // 1236 // $lr = big-itercount-expression 1237 // .. 1238 // t2DoLoopStart renamable $lr 1239 // vector.body: 1240 // .. 1241 // $vpr = MVE_VCTP32 renamable $r3 1242 // renamable $lr = t2LoopDec killed renamable $lr, 1 1243 // t2LoopEnd renamable $lr, %vector.body 1244 // tB %end 1245 // 1246 // What we would like achieve here is to replace the do-loop start pseudo 1247 // instruction t2DoLoopStart with: 1248 // 1249 // $lr = MVE_DLSTP_32 killed renamable $r3 1250 // 1251 // Thus, $r3 which defines the number of elements, is written to $lr, 1252 // and then we want to delete the whole chain that used to define $lr, 1253 // see the comment below how this chain could look like. 1254 // 1255 void ARMLowOverheadLoops::IterationCountDCE(LowOverheadLoop &LoLoop) { 1256 if (!LoLoop.IsTailPredicationLegal()) 1257 return; 1258 1259 LLVM_DEBUG(dbgs() << "ARM Loops: Trying DCE on loop iteration count.\n"); 1260 1261 MachineInstr *Def = RDA->getMIOperand(LoLoop.Start, 0); 1262 if (!Def) { 1263 LLVM_DEBUG(dbgs() << "ARM Loops: Couldn't find iteration count.\n"); 1264 return; 1265 } 1266 1267 // Collect and remove the users of iteration count. 1268 SmallPtrSet<MachineInstr*, 4> Killed = { LoLoop.Start, LoLoop.Dec, 1269 LoLoop.End, LoLoop.InsertPt }; 1270 SmallPtrSet<MachineInstr*, 2> Remove; 1271 if (RDA->isSafeToRemove(Def, Remove, Killed)) 1272 LoLoop.ToRemove.insert(Remove.begin(), Remove.end()); 1273 else { 1274 LLVM_DEBUG(dbgs() << "ARM Loops: Unsafe to remove loop iteration count.\n"); 1275 return; 1276 } 1277 1278 // Collect the dead code and the MBBs in which they reside. 1279 RDA->collectKilledOperands(Def, Killed); 1280 SmallPtrSet<MachineBasicBlock*, 2> BasicBlocks; 1281 for (auto *MI : Killed) 1282 BasicBlocks.insert(MI->getParent()); 1283 1284 // Collect IT blocks in all affected basic blocks. 1285 std::map<MachineInstr *, SmallPtrSet<MachineInstr *, 2>> ITBlocks; 1286 for (auto *MBB : BasicBlocks) { 1287 for (auto &MI : *MBB) { 1288 if (MI.getOpcode() != ARM::t2IT) 1289 continue; 1290 RDA->getReachingLocalUses(&MI, ARM::ITSTATE, ITBlocks[&MI]); 1291 } 1292 } 1293 1294 // If we're removing all of the instructions within an IT block, then 1295 // also remove the IT instruction. 1296 SmallPtrSet<MachineInstr*, 2> ModifiedITs; 1297 for (auto *MI : Killed) { 1298 if (MachineOperand *MO = MI->findRegisterUseOperand(ARM::ITSTATE)) { 1299 MachineInstr *IT = RDA->getMIOperand(MI, *MO); 1300 auto &CurrentBlock = ITBlocks[IT]; 1301 CurrentBlock.erase(MI); 1302 if (CurrentBlock.empty()) 1303 ModifiedITs.erase(IT); 1304 else 1305 ModifiedITs.insert(IT); 1306 } 1307 } 1308 1309 // Delete the killed instructions only if we don't have any IT blocks that 1310 // need to be modified because we need to fixup the mask. 1311 // TODO: Handle cases where IT blocks are modified. 1312 if (ModifiedITs.empty()) { 1313 LLVM_DEBUG(dbgs() << "ARM Loops: Will remove iteration count:\n"; 1314 for (auto *MI : Killed) 1315 dbgs() << " - " << *MI); 1316 LoLoop.ToRemove.insert(Killed.begin(), Killed.end()); 1317 } else 1318 LLVM_DEBUG(dbgs() << "ARM Loops: Would need to modify IT block(s).\n"); 1319 } 1320 1321 MachineInstr* ARMLowOverheadLoops::ExpandLoopStart(LowOverheadLoop &LoLoop) { 1322 LLVM_DEBUG(dbgs() << "ARM Loops: Expanding LoopStart.\n"); 1323 // When using tail-predication, try to delete the dead code that was used to 1324 // calculate the number of loop iterations. 1325 IterationCountDCE(LoLoop); 1326 1327 MachineInstr *InsertPt = LoLoop.InsertPt; 1328 MachineInstr *Start = LoLoop.Start; 1329 MachineBasicBlock *MBB = InsertPt->getParent(); 1330 bool IsDo = Start->getOpcode() == ARM::t2DoLoopStart; 1331 unsigned Opc = LoLoop.getStartOpcode(); 1332 MachineOperand &Count = LoLoop.getCount(); 1333 1334 MachineInstrBuilder MIB = 1335 BuildMI(*MBB, InsertPt, InsertPt->getDebugLoc(), TII->get(Opc)); 1336 1337 MIB.addDef(ARM::LR); 1338 MIB.add(Count); 1339 if (!IsDo) 1340 MIB.add(Start->getOperand(1)); 1341 1342 // If we're inserting at a mov lr, then remove it as it's redundant. 1343 if (InsertPt != Start) 1344 LoLoop.ToRemove.insert(InsertPt); 1345 LoLoop.ToRemove.insert(Start); 1346 LLVM_DEBUG(dbgs() << "ARM Loops: Inserted start: " << *MIB); 1347 return &*MIB; 1348 } 1349 1350 void ARMLowOverheadLoops::FixupReductions(LowOverheadLoop &LoLoop) const { 1351 LLVM_DEBUG(dbgs() << "ARM Loops: Fixing up reduction(s).\n"); 1352 auto BuildMov = [this](MachineInstr &InsertPt, Register To, Register From) { 1353 MachineBasicBlock *MBB = InsertPt.getParent(); 1354 MachineInstrBuilder MIB = 1355 BuildMI(*MBB, &InsertPt, InsertPt.getDebugLoc(), TII->get(ARM::MVE_VORR)); 1356 MIB.addDef(To); 1357 MIB.addReg(From); 1358 MIB.addReg(From); 1359 MIB.addImm(0); 1360 MIB.addReg(0); 1361 MIB.addReg(To); 1362 LLVM_DEBUG(dbgs() << "ARM Loops: Inserted VMOV: " << *MIB); 1363 }; 1364 1365 for (auto &Reduction : LoLoop.Reductions) { 1366 MachineInstr &Copy = Reduction->Copy; 1367 MachineInstr &Reduce = Reduction->Reduce; 1368 Register DestReg = Copy.getOperand(0).getReg(); 1369 1370 // Change the initialiser if present 1371 if (Reduction->Init) { 1372 MachineInstr *Init = Reduction->Init; 1373 1374 for (unsigned i = 0; i < Init->getNumOperands(); ++i) { 1375 MachineOperand &MO = Init->getOperand(i); 1376 if (MO.isReg() && MO.isUse() && MO.isTied() && 1377 Init->findTiedOperandIdx(i) == 0) 1378 Init->getOperand(i).setReg(DestReg); 1379 } 1380 Init->getOperand(0).setReg(DestReg); 1381 LLVM_DEBUG(dbgs() << "ARM Loops: Changed init regs: " << *Init); 1382 } else 1383 BuildMov(LoLoop.Preheader->instr_back(), DestReg, Copy.getOperand(1).getReg()); 1384 1385 // Change the reducing op to write to the register that is used to copy 1386 // its value on the next iteration. Also update the tied-def operand. 1387 Reduce.getOperand(0).setReg(DestReg); 1388 Reduce.getOperand(5).setReg(DestReg); 1389 LLVM_DEBUG(dbgs() << "ARM Loops: Changed reduction regs: " << Reduce); 1390 1391 // Instead of a vpsel, just copy the register into the necessary one. 1392 MachineInstr &VPSEL = Reduction->VPSEL; 1393 if (VPSEL.getOperand(0).getReg() != DestReg) 1394 BuildMov(VPSEL, VPSEL.getOperand(0).getReg(), DestReg); 1395 1396 // Remove the unnecessary instructions. 1397 LLVM_DEBUG(dbgs() << "ARM Loops: Removing:\n" 1398 << " - " << Copy 1399 << " - " << VPSEL << "\n"); 1400 Copy.eraseFromParent(); 1401 VPSEL.eraseFromParent(); 1402 } 1403 } 1404 1405 void ARMLowOverheadLoops::ConvertVPTBlocks(LowOverheadLoop &LoLoop) { 1406 auto RemovePredicate = [](MachineInstr *MI) { 1407 LLVM_DEBUG(dbgs() << "ARM Loops: Removing predicate from: " << *MI); 1408 if (int PIdx = llvm::findFirstVPTPredOperandIdx(*MI)) { 1409 assert(MI->getOperand(PIdx).getImm() == ARMVCC::Then && 1410 "Expected Then predicate!"); 1411 MI->getOperand(PIdx).setImm(ARMVCC::None); 1412 MI->getOperand(PIdx+1).setReg(0); 1413 } else 1414 llvm_unreachable("trying to unpredicate a non-predicated instruction"); 1415 }; 1416 1417 // There are a few scenarios which we have to fix up: 1418 // 1. VPT Blocks with non-uniform predicates: 1419 // - a. When the divergent instruction is a vctp 1420 // - b. When the block uses a vpst, and is only predicated on the vctp 1421 // - c. When the block uses a vpt and (optionally) contains one or more 1422 // vctp. 1423 // 2. VPT Blocks with uniform predicates: 1424 // - a. The block uses a vpst, and is only predicated on the vctp 1425 for (auto &Block : LoLoop.getVPTBlocks()) { 1426 SmallVectorImpl<PredicatedMI> &Insts = Block.getInsts(); 1427 if (Block.HasNonUniformPredicate()) { 1428 PredicatedMI *Divergent = Block.getDivergent(); 1429 if (isVCTP(Divergent->MI)) { 1430 // The vctp will be removed, so the block mask of the vp(s)t will need 1431 // to be recomputed. 1432 LoLoop.BlockMasksToRecompute.insert(Block.getPredicateThen()); 1433 } else if (Block.isVPST() && Block.IsOnlyPredicatedOn(LoLoop.VCTP)) { 1434 // The VPT block has a non-uniform predicate but it uses a vpst and its 1435 // entry is guarded only by a vctp, which means we: 1436 // - Need to remove the original vpst. 1437 // - Then need to unpredicate any following instructions, until 1438 // we come across the divergent vpr def. 1439 // - Insert a new vpst to predicate the instruction(s) that following 1440 // the divergent vpr def. 1441 // TODO: We could be producing more VPT blocks than necessary and could 1442 // fold the newly created one into a proceeding one. 1443 for (auto I = ++MachineBasicBlock::iterator(Block.getPredicateThen()), 1444 E = ++MachineBasicBlock::iterator(Divergent->MI); I != E; ++I) 1445 RemovePredicate(&*I); 1446 1447 unsigned Size = 0; 1448 auto E = MachineBasicBlock::reverse_iterator(Divergent->MI); 1449 auto I = MachineBasicBlock::reverse_iterator(Insts.back().MI); 1450 MachineInstr *InsertAt = nullptr; 1451 while (I != E) { 1452 InsertAt = &*I; 1453 ++Size; 1454 ++I; 1455 } 1456 // Create a VPST (with a null mask for now, we'll recompute it later). 1457 MachineInstrBuilder MIB = BuildMI(*InsertAt->getParent(), InsertAt, 1458 InsertAt->getDebugLoc(), 1459 TII->get(ARM::MVE_VPST)); 1460 MIB.addImm(0); 1461 LLVM_DEBUG(dbgs() << "ARM Loops: Removing VPST: " << *Block.getPredicateThen()); 1462 LLVM_DEBUG(dbgs() << "ARM Loops: Created VPST: " << *MIB); 1463 LoLoop.ToRemove.insert(Block.getPredicateThen()); 1464 LoLoop.BlockMasksToRecompute.insert(MIB.getInstr()); 1465 } 1466 // Else, if the block uses a vpt, iterate over the block, removing the 1467 // extra VCTPs it may contain. 1468 else if (Block.isVPT()) { 1469 bool RemovedVCTP = false; 1470 for (PredicatedMI &Elt : Block.getInsts()) { 1471 MachineInstr *MI = Elt.MI; 1472 if (isVCTP(MI)) { 1473 LLVM_DEBUG(dbgs() << "ARM Loops: Removing VCTP: " << *MI); 1474 LoLoop.ToRemove.insert(MI); 1475 RemovedVCTP = true; 1476 continue; 1477 } 1478 } 1479 if (RemovedVCTP) 1480 LoLoop.BlockMasksToRecompute.insert(Block.getPredicateThen()); 1481 } 1482 } else if (Block.IsOnlyPredicatedOn(LoLoop.VCTP) && Block.isVPST()) { 1483 // A vpt block starting with VPST, is only predicated upon vctp and has no 1484 // internal vpr defs: 1485 // - Remove vpst. 1486 // - Unpredicate the remaining instructions. 1487 LLVM_DEBUG(dbgs() << "ARM Loops: Removing VPST: " << *Block.getPredicateThen()); 1488 LoLoop.ToRemove.insert(Block.getPredicateThen()); 1489 for (auto &PredMI : Insts) 1490 RemovePredicate(PredMI.MI); 1491 } 1492 } 1493 LLVM_DEBUG(dbgs() << "ARM Loops: Removing remaining VCTPs...\n"); 1494 // Remove the "main" VCTP 1495 LoLoop.ToRemove.insert(LoLoop.VCTP); 1496 LLVM_DEBUG(dbgs() << " " << *LoLoop.VCTP); 1497 // Remove remaining secondary VCTPs 1498 for (MachineInstr *VCTP : LoLoop.SecondaryVCTPs) { 1499 // All VCTPs that aren't marked for removal yet should be unpredicated ones. 1500 // The predicated ones should have already been marked for removal when 1501 // visiting the VPT blocks. 1502 if (LoLoop.ToRemove.insert(VCTP).second) { 1503 assert(getVPTInstrPredicate(*VCTP) == ARMVCC::None && 1504 "Removing Predicated VCTP without updating the block mask!"); 1505 LLVM_DEBUG(dbgs() << " " << *VCTP); 1506 } 1507 } 1508 } 1509 1510 void ARMLowOverheadLoops::Expand(LowOverheadLoop &LoLoop) { 1511 1512 // Combine the LoopDec and LoopEnd instructions into LE(TP). 1513 auto ExpandLoopEnd = [this](LowOverheadLoop &LoLoop) { 1514 MachineInstr *End = LoLoop.End; 1515 MachineBasicBlock *MBB = End->getParent(); 1516 unsigned Opc = LoLoop.IsTailPredicationLegal() ? 1517 ARM::MVE_LETP : ARM::t2LEUpdate; 1518 MachineInstrBuilder MIB = BuildMI(*MBB, End, End->getDebugLoc(), 1519 TII->get(Opc)); 1520 MIB.addDef(ARM::LR); 1521 MIB.add(End->getOperand(0)); 1522 MIB.add(End->getOperand(1)); 1523 LLVM_DEBUG(dbgs() << "ARM Loops: Inserted LE: " << *MIB); 1524 LoLoop.ToRemove.insert(LoLoop.Dec); 1525 LoLoop.ToRemove.insert(End); 1526 return &*MIB; 1527 }; 1528 1529 // TODO: We should be able to automatically remove these branches before we 1530 // get here - probably by teaching analyzeBranch about the pseudo 1531 // instructions. 1532 // If there is an unconditional branch, after I, that just branches to the 1533 // next block, remove it. 1534 auto RemoveDeadBranch = [](MachineInstr *I) { 1535 MachineBasicBlock *BB = I->getParent(); 1536 MachineInstr *Terminator = &BB->instr_back(); 1537 if (Terminator->isUnconditionalBranch() && I != Terminator) { 1538 MachineBasicBlock *Succ = Terminator->getOperand(0).getMBB(); 1539 if (BB->isLayoutSuccessor(Succ)) { 1540 LLVM_DEBUG(dbgs() << "ARM Loops: Removing branch: " << *Terminator); 1541 Terminator->eraseFromParent(); 1542 } 1543 } 1544 }; 1545 1546 if (LoLoop.Revert) { 1547 if (LoLoop.Start->getOpcode() == ARM::t2WhileLoopStart) 1548 RevertWhile(LoLoop.Start); 1549 else 1550 LoLoop.Start->eraseFromParent(); 1551 bool FlagsAlreadySet = RevertLoopDec(LoLoop.Dec); 1552 RevertLoopEnd(LoLoop.End, FlagsAlreadySet); 1553 } else { 1554 LoLoop.Start = ExpandLoopStart(LoLoop); 1555 RemoveDeadBranch(LoLoop.Start); 1556 LoLoop.End = ExpandLoopEnd(LoLoop); 1557 RemoveDeadBranch(LoLoop.End); 1558 if (LoLoop.IsTailPredicationLegal()) { 1559 ConvertVPTBlocks(LoLoop); 1560 FixupReductions(LoLoop); 1561 } 1562 for (auto *I : LoLoop.ToRemove) { 1563 LLVM_DEBUG(dbgs() << "ARM Loops: Erasing " << *I); 1564 I->eraseFromParent(); 1565 } 1566 for (auto *I : LoLoop.BlockMasksToRecompute) { 1567 LLVM_DEBUG(dbgs() << "ARM Loops: Recomputing VPT/VPST Block Mask: " << *I); 1568 recomputeVPTBlockMask(*I); 1569 LLVM_DEBUG(dbgs() << " ... done: " << *I); 1570 } 1571 } 1572 1573 PostOrderLoopTraversal DFS(LoLoop.ML, *MLI); 1574 DFS.ProcessLoop(); 1575 const SmallVectorImpl<MachineBasicBlock*> &PostOrder = DFS.getOrder(); 1576 for (auto *MBB : PostOrder) { 1577 recomputeLiveIns(*MBB); 1578 // FIXME: For some reason, the live-in print order is non-deterministic for 1579 // our tests and I can't out why... So just sort them. 1580 MBB->sortUniqueLiveIns(); 1581 } 1582 1583 for (auto *MBB : reverse(PostOrder)) 1584 recomputeLivenessFlags(*MBB); 1585 1586 // We've moved, removed and inserted new instructions, so update RDA. 1587 RDA->reset(); 1588 } 1589 1590 bool ARMLowOverheadLoops::RevertNonLoops() { 1591 LLVM_DEBUG(dbgs() << "ARM Loops: Reverting any remaining pseudos...\n"); 1592 bool Changed = false; 1593 1594 for (auto &MBB : *MF) { 1595 SmallVector<MachineInstr*, 4> Starts; 1596 SmallVector<MachineInstr*, 4> Decs; 1597 SmallVector<MachineInstr*, 4> Ends; 1598 1599 for (auto &I : MBB) { 1600 if (isLoopStart(I)) 1601 Starts.push_back(&I); 1602 else if (I.getOpcode() == ARM::t2LoopDec) 1603 Decs.push_back(&I); 1604 else if (I.getOpcode() == ARM::t2LoopEnd) 1605 Ends.push_back(&I); 1606 } 1607 1608 if (Starts.empty() && Decs.empty() && Ends.empty()) 1609 continue; 1610 1611 Changed = true; 1612 1613 for (auto *Start : Starts) { 1614 if (Start->getOpcode() == ARM::t2WhileLoopStart) 1615 RevertWhile(Start); 1616 else 1617 Start->eraseFromParent(); 1618 } 1619 for (auto *Dec : Decs) 1620 RevertLoopDec(Dec); 1621 1622 for (auto *End : Ends) 1623 RevertLoopEnd(End); 1624 } 1625 return Changed; 1626 } 1627 1628 FunctionPass *llvm::createARMLowOverheadLoopsPass() { 1629 return new ARMLowOverheadLoops(); 1630 } 1631