llvm/lib/CodeGen/MachineLoopInfo.cpp

   1 //===- MachineLoopInfo.cpp - Natural Loop Calculator ----------------------===//
   2 //
   3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
   4 // See https://llvm.org/LICENSE.txt for license information.
   5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
   6 //
   7 //===----------------------------------------------------------------------===//
   8 //
   9 // This file defines the MachineLoopInfo class that is used to identify natural
  10 // loops and determine the loop depth of various nodes of the CFG.  Note that
  11 // the loops identified may actually be several natural loops that share the
  12 // same header node... not just a single natural loop.
  13 //
  14 //===----------------------------------------------------------------------===//
  15
  16 #include "llvm/CodeGen/MachineLoopInfo.h"
  17 #include "llvm/CodeGen/MachineDominators.h"
  18 #include "llvm/CodeGen/MachineRegisterInfo.h"
  19 #include "llvm/CodeGen/TargetInstrInfo.h"
  20 #include "llvm/CodeGen/TargetSubtargetInfo.h"
  21 #include "llvm/Config/llvm-config.h"
  22 #include "llvm/InitializePasses.h"
  23 #include "llvm/Pass.h"
  24 #include "llvm/PassRegistry.h"
  25 #include "llvm/Support/GenericLoopInfoImpl.h"
  26
  27 using namespace llvm;
  28
  29 // Explicitly instantiate methods in LoopInfoImpl.h for MI-level Loops.
  30 template class llvm::LoopBase<MachineBasicBlock, MachineLoop>;
  31 template class llvm::LoopInfoBase<MachineBasicBlock, MachineLoop>;
  32
  33 AnalysisKey MachineLoopAnalysis::Key;
  34
  35 MachineLoopAnalysis::Result
  36 MachineLoopAnalysis::run(MachineFunction &MF,
  37                          MachineFunctionAnalysisManager &MFAM) {
  38   return MachineLoopInfo(MFAM.getResult<MachineDominatorTreeAnalysis>(MF));
  39 }
  40
  41 PreservedAnalyses
  42 MachineLoopPrinterPass::run(MachineFunction &MF,
  43                             MachineFunctionAnalysisManager &MFAM) {
  44   OS << "Machine loop info for machine function '" << MF.getName() << "':\n";
  45   MFAM.getResult<MachineLoopAnalysis>(MF).print(OS);
  46   return PreservedAnalyses::all();
  47 }
  48
  49 char MachineLoopInfoWrapperPass::ID = 0;
  50 MachineLoopInfoWrapperPass::MachineLoopInfoWrapperPass()
  51     : MachineFunctionPass(ID) {
  52   initializeMachineLoopInfoWrapperPassPass(*PassRegistry::getPassRegistry());
  53 }
  54 INITIALIZE_PASS_BEGIN(MachineLoopInfoWrapperPass, "machine-loops",
  55                       "Machine Natural Loop Construction", true, true)
  56 INITIALIZE_PASS_DEPENDENCY(MachineDominatorTreeWrapperPass)
  57 INITIALIZE_PASS_END(MachineLoopInfoWrapperPass, "machine-loops",
  58                     "Machine Natural Loop Construction", true, true)
  59
  60 char &llvm::MachineLoopInfoID = MachineLoopInfoWrapperPass::ID;
  61
  62 bool MachineLoopInfoWrapperPass::runOnMachineFunction(MachineFunction &) {
  63   LI.calculate(getAnalysis<MachineDominatorTreeWrapperPass>().getDomTree());
  64   return false;
  65 }
  66
  67 bool MachineLoopInfo::invalidate(
  68     MachineFunction &, const PreservedAnalyses &PA,
  69     MachineFunctionAnalysisManager::Invalidator &) {
  70   // Check whether the analysis, all analyses on functions, or the function's
  71   // CFG have been preserved.
  72   auto PAC = PA.getChecker<MachineLoopAnalysis>();
  73   return !PAC.preserved() &&
  74          !PAC.preservedSet<AllAnalysesOn<MachineFunction>>() &&
  75          !PAC.preservedSet<CFGAnalyses>();
  76 }
  77
  78 void MachineLoopInfo::calculate(MachineDominatorTree &MDT) {
  79   releaseMemory();
  80   analyze(MDT.getBase());
  81 }
  82
  83 void MachineLoopInfoWrapperPass::getAnalysisUsage(AnalysisUsage &AU) const {
  84   AU.setPreservesAll();
  85   AU.addRequired<MachineDominatorTreeWrapperPass>();
  86   MachineFunctionPass::getAnalysisUsage(AU);
  87 }
  88
  89 MachineBasicBlock *MachineLoop::getTopBlock() {
  90   MachineBasicBlock *TopMBB = getHeader();
  91   MachineFunction::iterator Begin = TopMBB->getParent()->begin();
  92   if (TopMBB->getIterator() != Begin) {
  93     MachineBasicBlock *PriorMBB = &*std::prev(TopMBB->getIterator());
  94     while (contains(PriorMBB)) {
  95       TopMBB = PriorMBB;
  96       if (TopMBB->getIterator() == Begin)
  97         break;
  98       PriorMBB = &*std::prev(TopMBB->getIterator());
  99     }
 100   }
 101   return TopMBB;
 102 }
 103
 104 MachineBasicBlock *MachineLoop::getBottomBlock() {
 105   MachineBasicBlock *BotMBB = getHeader();
 106   MachineFunction::iterator End = BotMBB->getParent()->end();
 107   if (BotMBB->getIterator() != std::prev(End)) {
 108     MachineBasicBlock *NextMBB = &*std::next(BotMBB->getIterator());
 109     while (contains(NextMBB)) {
 110       BotMBB = NextMBB;
 111       if (BotMBB == &*std::next(BotMBB->getIterator()))
 112         break;
 113       NextMBB = &*std::next(BotMBB->getIterator());
 114     }
 115   }
 116   return BotMBB;
 117 }
 118
 119 MachineBasicBlock *MachineLoop::findLoopControlBlock() const {
 120   if (MachineBasicBlock *Latch = getLoopLatch()) {
 121     if (isLoopExiting(Latch))
 122       return Latch;
 123     else
 124       return getExitingBlock();
 125   }
 126   return nullptr;
 127 }
 128
 129 DebugLoc MachineLoop::getStartLoc() const {
 130   // Try the pre-header first.
 131   if (MachineBasicBlock *PHeadMBB = getLoopPreheader())
 132     if (const BasicBlock *PHeadBB = PHeadMBB->getBasicBlock())
 133       if (DebugLoc DL = PHeadBB->getTerminator()->getDebugLoc())
 134         return DL;
 135
 136   // If we have no pre-header or there are no instructions with debug
 137   // info in it, try the header.
 138   if (MachineBasicBlock *HeadMBB = getHeader())
 139     if (const BasicBlock *HeadBB = HeadMBB->getBasicBlock())
 140       return HeadBB->getTerminator()->getDebugLoc();
 141
 142   return DebugLoc();
 143 }
 144
 145 MachineBasicBlock *
 146 MachineLoopInfo::findLoopPreheader(MachineLoop *L, bool SpeculativePreheader,
 147                                    bool FindMultiLoopPreheader) const {
 148   if (MachineBasicBlock *PB = L->getLoopPreheader())
 149     return PB;
 150
 151   if (!SpeculativePreheader)
 152     return nullptr;
 153
 154   MachineBasicBlock *HB = L->getHeader(), *LB = L->getLoopLatch();
 155   if (HB->pred_size() != 2 || HB->hasAddressTaken())
 156     return nullptr;
 157   // Find the predecessor of the header that is not the latch block.
 158   MachineBasicBlock *Preheader = nullptr;
 159   for (MachineBasicBlock *P : HB->predecessors()) {
 160     if (P == LB)
 161       continue;
 162     // Sanity.
 163     if (Preheader)
 164       return nullptr;
 165     Preheader = P;
 166   }
 167
 168   // Check if the preheader candidate is a successor of any other loop
 169   // headers. We want to avoid having two loop setups in the same block.
 170   if (!FindMultiLoopPreheader) {
 171     for (MachineBasicBlock *S : Preheader->successors()) {
 172       if (S == HB)
 173         continue;
 174       MachineLoop *T = getLoopFor(S);
 175       if (T && T->getHeader() == S)
 176         return nullptr;
 177     }
 178   }
 179   return Preheader;
 180 }
 181
 182 MDNode *MachineLoop::getLoopID() const {
 183   MDNode *LoopID = nullptr;
 184   if (const auto *MBB = findLoopControlBlock()) {
 185     // If there is a single latch block, then the metadata
 186     // node is attached to its terminating instruction.
 187     const auto *BB = MBB->getBasicBlock();
 188     if (!BB)
 189       return nullptr;
 190     if (const auto *TI = BB->getTerminator())
 191       LoopID = TI->getMetadata(LLVMContext::MD_loop);
 192   } else if (const auto *MBB = getHeader()) {
 193     // There seem to be multiple latch blocks, so we have to
 194     // visit all predecessors of the loop header and check
 195     // their terminating instructions for the metadata.
 196     if (const auto *Header = MBB->getBasicBlock()) {
 197       // Walk over all blocks in the loop.
 198       for (const auto *MBB : this->blocks()) {
 199         const auto *BB = MBB->getBasicBlock();
 200         if (!BB)
 201           return nullptr;
 202         const auto *TI = BB->getTerminator();
 203         if (!TI)
 204           return nullptr;
 205         MDNode *MD = nullptr;
 206         // Check if this terminating instruction jumps to the loop header.
 207         for (const auto *Succ : successors(TI)) {
 208           if (Succ == Header) {
 209             // This is a jump to the header - gather the metadata from it.
 210             MD = TI->getMetadata(LLVMContext::MD_loop);
 211             break;
 212           }
 213         }
 214         if (!MD)
 215           return nullptr;
 216         if (!LoopID)
 217           LoopID = MD;
 218         else if (MD != LoopID)
 219           return nullptr;
 220       }
 221     }
 222   }
 223   if (LoopID &&
 224       (LoopID->getNumOperands() == 0 || LoopID->getOperand(0) != LoopID))
 225     LoopID = nullptr;
 226   return LoopID;
 227 }
 228
 229 bool MachineLoop::isLoopInvariantImplicitPhysReg(Register Reg) const {
 230   MachineFunction *MF = getHeader()->getParent();
 231   MachineRegisterInfo *MRI = &MF->getRegInfo();
 232
 233   if (MRI->isConstantPhysReg(Reg))
 234     return true;
 235
 236   if (!MF->getSubtarget()
 237            .getRegisterInfo()
 238            ->shouldAnalyzePhysregInMachineLoopInfo(Reg))
 239     return false;
 240
 241   return !llvm::any_of(
 242       MRI->def_instructions(Reg),
 243       [this](const MachineInstr &MI) { return this->contains(&MI); });
 244 }
 245
 246 bool MachineLoop::isLoopInvariant(MachineInstr &I,
 247                                   const Register ExcludeReg) const {
 248   MachineFunction *MF = I.getParent()->getParent();
 249   MachineRegisterInfo *MRI = &MF->getRegInfo();
 250   const TargetSubtargetInfo &ST = MF->getSubtarget();
 251   const TargetRegisterInfo *TRI = ST.getRegisterInfo();
 252   const TargetInstrInfo *TII = ST.getInstrInfo();
 253
 254   // The instruction is loop invariant if all of its operands are.
 255   for (const MachineOperand &MO : I.operands()) {
 256     if (!MO.isReg())
 257       continue;
 258
 259     Register Reg = MO.getReg();
 260     if (Reg == 0) continue;
 261
 262     if (ExcludeReg == Reg)
 263       continue;
 264
 265     // An instruction that uses or defines a physical register can't e.g. be
 266     // hoisted, so mark this as not invariant.
 267     if (Reg.isPhysical()) {
 268       if (MO.isUse()) {
 269         // If the physreg has no defs anywhere, it's just an ambient register
 270         // and we can freely move its uses. Alternatively, if it's allocatable,
 271         // it could get allocated to something with a def during allocation.
 272         // However, if the physreg is known to always be caller saved/restored
 273         // then this use is safe to hoist.
 274         if (!isLoopInvariantImplicitPhysReg(Reg) &&
 275             !(TRI->isCallerPreservedPhysReg(Reg.asMCReg(), *I.getMF())) &&
 276             !TII->isIgnorableUse(MO))
 277           return false;
 278         // Otherwise it's safe to move.
 279         continue;
 280       } else if (!MO.isDead()) {
 281         // A def that isn't dead can't be moved.
 282         return false;
 283       } else if (getHeader()->isLiveIn(Reg)) {
 284         // If the reg is live into the loop, we can't hoist an instruction
 285         // which would clobber it.
 286         return false;
 287       }
 288     }
 289
 290     if (!MO.isUse())
 291       continue;
 292
 293     assert(MRI->getVRegDef(Reg) &&
 294            "Machine instr not mapped for this vreg?!");
 295
 296     // If the loop contains the definition of an operand, then the instruction
 297     // isn't loop invariant.
 298     if (contains(MRI->getVRegDef(Reg)))
 299       return false;
 300   }
 301
 302   // If we got this far, the instruction is loop invariant!
 303   return true;
 304 }
 305
 306 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
 307 LLVM_DUMP_METHOD void MachineLoop::dump() const {
 308   print(dbgs());
 309 }
 310 #endif