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/Analysis/LoopInfoImpl.h"
  18 #include "llvm/CodeGen/MachineDominators.h"
  19 #include "llvm/CodeGen/MachineRegisterInfo.h"
  20 #include "llvm/CodeGen/Passes.h"
  21 #include "llvm/CodeGen/TargetInstrInfo.h"
  22 #include "llvm/CodeGen/TargetSubtargetInfo.h"
  23 #include "llvm/Config/llvm-config.h"
  24 #include "llvm/InitializePasses.h"
  25 #include "llvm/Support/Debug.h"
  26 #include "llvm/Support/raw_ostream.h"
  27
  28 using namespace llvm;
  29
  30 // Explicitly instantiate methods in LoopInfoImpl.h for MI-level Loops.
  31 template class llvm::LoopBase<MachineBasicBlock, MachineLoop>;
  32 template class llvm::LoopInfoBase<MachineBasicBlock, MachineLoop>;
  33
  34 char MachineLoopInfo::ID = 0;
  35 MachineLoopInfo::MachineLoopInfo() : MachineFunctionPass(ID) {
  36   initializeMachineLoopInfoPass(*PassRegistry::getPassRegistry());
  37 }
  38 INITIALIZE_PASS_BEGIN(MachineLoopInfo, "machine-loops",
  39                 "Machine Natural Loop Construction", true, true)
  40 INITIALIZE_PASS_DEPENDENCY(MachineDominatorTree)
  41 INITIALIZE_PASS_END(MachineLoopInfo, "machine-loops",
  42                 "Machine Natural Loop Construction", true, true)
  43
  44 char &llvm::MachineLoopInfoID = MachineLoopInfo::ID;
  45
  46 bool MachineLoopInfo::runOnMachineFunction(MachineFunction &) {
  47   calculate(getAnalysis<MachineDominatorTree>());
  48   return false;
  49 }
  50
  51 void MachineLoopInfo::calculate(MachineDominatorTree &MDT) {
  52   releaseMemory();
  53   LI.analyze(MDT.getBase());
  54 }
  55
  56 void MachineLoopInfo::getAnalysisUsage(AnalysisUsage &AU) const {
  57   AU.setPreservesAll();
  58   AU.addRequired<MachineDominatorTree>();
  59   MachineFunctionPass::getAnalysisUsage(AU);
  60 }
  61
  62 MachineBasicBlock *MachineLoop::getTopBlock() {
  63   MachineBasicBlock *TopMBB = getHeader();
  64   MachineFunction::iterator Begin = TopMBB->getParent()->begin();
  65   if (TopMBB->getIterator() != Begin) {
  66     MachineBasicBlock *PriorMBB = &*std::prev(TopMBB->getIterator());
  67     while (contains(PriorMBB)) {
  68       TopMBB = PriorMBB;
  69       if (TopMBB->getIterator() == Begin)
  70         break;
  71       PriorMBB = &*std::prev(TopMBB->getIterator());
  72     }
  73   }
  74   return TopMBB;
  75 }
  76
  77 MachineBasicBlock *MachineLoop::getBottomBlock() {
  78   MachineBasicBlock *BotMBB = getHeader();
  79   MachineFunction::iterator End = BotMBB->getParent()->end();
  80   if (BotMBB->getIterator() != std::prev(End)) {
  81     MachineBasicBlock *NextMBB = &*std::next(BotMBB->getIterator());
  82     while (contains(NextMBB)) {
  83       BotMBB = NextMBB;
  84       if (BotMBB == &*std::next(BotMBB->getIterator()))
  85         break;
  86       NextMBB = &*std::next(BotMBB->getIterator());
  87     }
  88   }
  89   return BotMBB;
  90 }
  91
  92 MachineBasicBlock *MachineLoop::findLoopControlBlock() {
  93   if (MachineBasicBlock *Latch = getLoopLatch()) {
  94     if (isLoopExiting(Latch))
  95       return Latch;
  96     else
  97       return getExitingBlock();
  98   }
  99   return nullptr;
 100 }
 101
 102 DebugLoc MachineLoop::getStartLoc() const {
 103   // Try the pre-header first.
 104   if (MachineBasicBlock *PHeadMBB = getLoopPreheader())
 105     if (const BasicBlock *PHeadBB = PHeadMBB->getBasicBlock())
 106       if (DebugLoc DL = PHeadBB->getTerminator()->getDebugLoc())
 107         return DL;
 108
 109   // If we have no pre-header or there are no instructions with debug
 110   // info in it, try the header.
 111   if (MachineBasicBlock *HeadMBB = getHeader())
 112     if (const BasicBlock *HeadBB = HeadMBB->getBasicBlock())
 113       return HeadBB->getTerminator()->getDebugLoc();
 114
 115   return DebugLoc();
 116 }
 117
 118 MachineBasicBlock *
 119 MachineLoopInfo::findLoopPreheader(MachineLoop *L, bool SpeculativePreheader,
 120                                    bool FindMultiLoopPreheader) const {
 121   if (MachineBasicBlock *PB = L->getLoopPreheader())
 122     return PB;
 123
 124   if (!SpeculativePreheader)
 125     return nullptr;
 126
 127   MachineBasicBlock *HB = L->getHeader(), *LB = L->getLoopLatch();
 128   if (HB->pred_size() != 2 || HB->hasAddressTaken())
 129     return nullptr;
 130   // Find the predecessor of the header that is not the latch block.
 131   MachineBasicBlock *Preheader = nullptr;
 132   for (MachineBasicBlock *P : HB->predecessors()) {
 133     if (P == LB)
 134       continue;
 135     // Sanity.
 136     if (Preheader)
 137       return nullptr;
 138     Preheader = P;
 139   }
 140
 141   // Check if the preheader candidate is a successor of any other loop
 142   // headers. We want to avoid having two loop setups in the same block.
 143   if (!FindMultiLoopPreheader) {
 144     for (MachineBasicBlock *S : Preheader->successors()) {
 145       if (S == HB)
 146         continue;
 147       MachineLoop *T = getLoopFor(S);
 148       if (T && T->getHeader() == S)
 149         return nullptr;
 150     }
 151   }
 152   return Preheader;
 153 }
 154
 155 bool MachineLoop::isLoopInvariant(MachineInstr &I) const {
 156   MachineFunction *MF = I.getParent()->getParent();
 157   MachineRegisterInfo *MRI = &MF->getRegInfo();
 158   const TargetSubtargetInfo &ST = MF->getSubtarget();
 159   const TargetRegisterInfo *TRI = ST.getRegisterInfo();
 160   const TargetInstrInfo *TII = ST.getInstrInfo();
 161
 162   // The instruction is loop invariant if all of its operands are.
 163   for (const MachineOperand &MO : I.operands()) {
 164     if (!MO.isReg())
 165       continue;
 166
 167     Register Reg = MO.getReg();
 168     if (Reg == 0) continue;
 169
 170     // An instruction that uses or defines a physical register can't e.g. be
 171     // hoisted, so mark this as not invariant.
 172     if (Register::isPhysicalRegister(Reg)) {
 173       if (MO.isUse()) {
 174         // If the physreg has no defs anywhere, it's just an ambient register
 175         // and we can freely move its uses. Alternatively, if it's allocatable,
 176         // it could get allocated to something with a def during allocation.
 177         // However, if the physreg is known to always be caller saved/restored
 178         // then this use is safe to hoist.
 179         if (!MRI->isConstantPhysReg(Reg) &&
 180             !(TRI->isCallerPreservedPhysReg(Reg.asMCReg(), *I.getMF())) &&
 181             !TII->isIgnorableUse(MO))
 182           return false;
 183         // Otherwise it's safe to move.
 184         continue;
 185       } else if (!MO.isDead()) {
 186         // A def that isn't dead can't be moved.
 187         return false;
 188       } else if (getHeader()->isLiveIn(Reg)) {
 189         // If the reg is live into the loop, we can't hoist an instruction
 190         // which would clobber it.
 191         return false;
 192       }
 193     }
 194
 195     if (!MO.isUse())
 196       continue;
 197
 198     assert(MRI->getVRegDef(Reg) &&
 199            "Machine instr not mapped for this vreg?!");
 200
 201     // If the loop contains the definition of an operand, then the instruction
 202     // isn't loop invariant.
 203     if (contains(MRI->getVRegDef(Reg)))
 204       return false;
 205   }
 206
 207   // If we got this far, the instruction is loop invariant!
 208   return true;
 209 }
 210
 211 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
 212 LLVM_DUMP_METHOD void MachineLoop::dump() const {
 213   print(dbgs());
 214 }
 215 #endif