lib/CodeGen/MachineLICM.cpp

   1 //===-- MachineLICM.cpp - Machine Loop Invariant Code Motion Pass ---------===//
   2 //
   3 //                     The LLVM Compiler Infrastructure
   4 //
   5 // This file is distributed under the University of Illinois Open Source
   6 // License. See LICENSE.TXT for details.
   7 //
   8 //===----------------------------------------------------------------------===//
   9 //
  10 // This pass performs loop invariant code motion on machine instructions. We
  11 // attempt to remove as much code from the body of a loop as possible.
  12 //
  13 // This pass does not attempt to throttle itself to limit register pressure.
  14 // The register allocation phases are expected to perform rematerialization
  15 // to recover when register pressure is high.
  16 //
  17 // This pass is not intended to be a replacement or a complete alternative
  18 // for the LLVM-IR-level LICM pass. It is only designed to hoist simple
  19 // constructs that are not exposed before lowering and instruction selection.
  20 //
  21 //===----------------------------------------------------------------------===//
  22
  23 #define DEBUG_TYPE "machine-licm"
  24 #include "llvm/CodeGen/Passes.h"
  25 #include "llvm/CodeGen/MachineDominators.h"
  26 #include "llvm/CodeGen/MachineLoopInfo.h"
  27 #include "llvm/CodeGen/MachineRegisterInfo.h"
  28 #include "llvm/Target/TargetRegisterInfo.h"
  29 #include "llvm/Target/TargetInstrInfo.h"
  30 #include "llvm/Target/TargetMachine.h"
  31 #include "llvm/ADT/Statistic.h"
  32 #include "llvm/Support/CommandLine.h"
  33 #include "llvm/Support/Compiler.h"
  34 #include "llvm/Support/Debug.h"
  35
  36 using namespace llvm;
  37
  38 STATISTIC(NumHoisted, "Number of machine instructions hoisted out of loops");
  39
  40 namespace {
  41   class VISIBILITY_HIDDEN MachineLICM : public MachineFunctionPass {
  42     const TargetMachine   *TM;
  43     const TargetInstrInfo *TII;
  44
  45     // Various analyses that we use...
  46     MachineLoopInfo      *LI;      // Current MachineLoopInfo
  47     MachineDominatorTree *DT;      // Machine dominator tree for the cur loop
  48     MachineRegisterInfo  *RegInfo; // Machine register information
  49
  50     // State that is updated as we process loops
  51     bool         Changed;          // True if a loop is changed.
  52     MachineLoop *CurLoop;          // The current loop we are working on.
  53     MachineBasicBlock *CurPreheader; // The preheader for CurLoop.
  54   public:
  55     static char ID; // Pass identification, replacement for typeid
  56     MachineLICM() : MachineFunctionPass(&ID) {}
  57
  58     virtual bool runOnMachineFunction(MachineFunction &MF);
  59
  60     const char *getPassName() const { return "Machine Instruction LICM"; }
  61
  62     // FIXME: Loop preheaders?
  63     virtual void getAnalysisUsage(AnalysisUsage &AU) const {
  64       AU.setPreservesCFG();
  65       AU.addRequired<MachineLoopInfo>();
  66       AU.addRequired<MachineDominatorTree>();
  67       AU.addPreserved<MachineLoopInfo>();
  68       AU.addPreserved<MachineDominatorTree>();
  69       MachineFunctionPass::getAnalysisUsage(AU);
  70     }
  71   private:
  72     /// IsLoopInvariantInst - Returns true if the instruction is loop
  73     /// invariant. I.e., all virtual register operands are defined outside of
  74     /// the loop, physical registers aren't accessed (explicitly or implicitly),
  75     /// and the instruction is hoistable.
  76     ///
  77     bool IsLoopInvariantInst(MachineInstr &I);
  78
  79     /// IsProfitableToHoist - Return true if it is potentially profitable to
  80     /// hoist the given loop invariant.
  81     bool IsProfitableToHoist(MachineInstr &MI);
  82
  83     /// HoistRegion - Walk the specified region of the CFG (defined by all
  84     /// blocks dominated by the specified block, and that are in the current
  85     /// loop) in depth first order w.r.t the DominatorTree. This allows us to
  86     /// visit definitions before uses, allowing us to hoist a loop body in one
  87     /// pass without iteration.
  88     ///
  89     void HoistRegion(MachineDomTreeNode *N);
  90
  91     /// Hoist - When an instruction is found to only use loop invariant operands
  92     /// that is safe to hoist, this instruction is called to do the dirty work.
  93     ///
  94     void Hoist(MachineInstr &MI);
  95   };
  96 } // end anonymous namespace
  97
  98 char MachineLICM::ID = 0;
  99 static RegisterPass<MachineLICM>
 100 X("machinelicm", "Machine Loop Invariant Code Motion");
 101
 102 FunctionPass *llvm::createMachineLICMPass() { return new MachineLICM(); }
 103
 104 /// LoopIsOuterMostWithPreheader - Test if the given loop is the outer-most
 105 /// loop that has a preheader.
 106 static bool LoopIsOuterMostWithPreheader(MachineLoop *CurLoop) {
 107   for (MachineLoop *L = CurLoop->getParentLoop(); L; L = L->getParentLoop())
 108     if (L->getLoopPreheader())
 109       return false;
 110   return true;
 111 }
 112
 113 /// Hoist expressions out of the specified loop. Note, alias info for inner loop
 114 /// is not preserved so it is not a good idea to run LICM multiple times on one
 115 /// loop.
 116 ///
 117 bool MachineLICM::runOnMachineFunction(MachineFunction &MF) {
 118   DOUT << "******** Machine LICM ********\n";
 119
 120   Changed = false;
 121   TM = &MF.getTarget();
 122   TII = TM->getInstrInfo();
 123   RegInfo = &MF.getRegInfo();
 124
 125   // Get our Loop information...
 126   LI = &getAnalysis<MachineLoopInfo>();
 127   DT = &getAnalysis<MachineDominatorTree>();
 128
 129   for (MachineLoopInfo::iterator
 130          I = LI->begin(), E = LI->end(); I != E; ++I) {
 131     CurLoop = *I;
 132
 133     // Only visit outer-most preheader-sporting loops.
 134     if (!LoopIsOuterMostWithPreheader(CurLoop))
 135       continue;
 136
 137     // Determine the block to which to hoist instructions. If we can't find a
 138     // suitable loop preheader, we can't do any hoisting.
 139     //
 140     // FIXME: We are only hoisting if the basic block coming into this loop
 141     // has only one successor. This isn't the case in general because we haven't
 142     // broken critical edges or added preheaders.
 143     CurPreheader = CurLoop->getLoopPreheader();
 144     if (!CurPreheader)
 145       continue;
 146
 147     HoistRegion(DT->getNode(CurLoop->getHeader()));
 148   }
 149
 150   return Changed;
 151 }
 152
 153 /// HoistRegion - Walk the specified region of the CFG (defined by all blocks
 154 /// dominated by the specified block, and that are in the current loop) in depth
 155 /// first order w.r.t the DominatorTree. This allows us to visit definitions
 156 /// before uses, allowing us to hoist a loop body in one pass without iteration.
 157 ///
 158 void MachineLICM::HoistRegion(MachineDomTreeNode *N) {
 159   assert(N != 0 && "Null dominator tree node?");
 160   MachineBasicBlock *BB = N->getBlock();
 161
 162   // If this subregion is not in the top level loop at all, exit.
 163   if (!CurLoop->contains(BB)) return;
 164
 165   for (MachineBasicBlock::iterator
 166          I = BB->begin(), E = BB->end(); I != E; ) {
 167     MachineInstr &MI = *I++;
 168
 169     // Try hoisting the instruction out of the loop. We can only do this if
 170     // all of the operands of the instruction are loop invariant and if it is
 171     // safe to hoist the instruction.
 172     Hoist(MI);
 173   }
 174
 175   const std::vector<MachineDomTreeNode*> &Children = N->getChildren();
 176
 177   for (unsigned I = 0, E = Children.size(); I != E; ++I)
 178     HoistRegion(Children[I]);
 179 }
 180
 181 /// IsLoopInvariantInst - Returns true if the instruction is loop
 182 /// invariant. I.e., all virtual register operands are defined outside of the
 183 /// loop, physical registers aren't accessed explicitly, and there are no side
 184 /// effects that aren't captured by the operands or other flags.
 185 ///
 186 bool MachineLICM::IsLoopInvariantInst(MachineInstr &I) {
 187   const TargetInstrDesc &TID = I.getDesc();
 188
 189   // Ignore stuff that we obviously can't hoist.
 190   if (TID.mayStore() || TID.isCall() || TID.isTerminator() ||
 191       TID.hasUnmodeledSideEffects())
 192     return false;
 193
 194   if (TID.mayLoad()) {
 195     // Okay, this instruction does a load. As a refinement, we allow the target
 196     // to decide whether the loaded value is actually a constant. If so, we can
 197     // actually use it as a load.
 198     if (!TII->isInvariantLoad(&I))
 199       // FIXME: we should be able to sink loads with no other side effects if
 200       // there is nothing that can change memory from here until the end of
 201       // block. This is a trivial form of alias analysis.
 202       return false;
 203   }
 204
 205   DEBUG({
 206       DOUT << "--- Checking if we can hoist " << I;
 207       if (I.getDesc().getImplicitUses()) {
 208         DOUT << "  * Instruction has implicit uses:\n";
 209
 210         const TargetRegisterInfo *TRI = TM->getRegisterInfo();
 211         for (const unsigned *ImpUses = I.getDesc().getImplicitUses();
 212              *ImpUses; ++ImpUses)
 213           DOUT << "      -> " << TRI->getName(*ImpUses) << "\n";
 214       }
 215
 216       if (I.getDesc().getImplicitDefs()) {
 217         DOUT << "  * Instruction has implicit defines:\n";
 218
 219         const TargetRegisterInfo *TRI = TM->getRegisterInfo();
 220         for (const unsigned *ImpDefs = I.getDesc().getImplicitDefs();
 221              *ImpDefs; ++ImpDefs)
 222           DOUT << "      -> " << TRI->getName(*ImpDefs) << "\n";
 223       }
 224     });
 225
 226   if (I.getDesc().getImplicitDefs() || I.getDesc().getImplicitUses()) {
 227     DOUT << "Cannot hoist with implicit defines or uses\n";
 228     return false;
 229   }
 230
 231   // The instruction is loop invariant if all of its operands are.
 232   for (unsigned i = 0, e = I.getNumOperands(); i != e; ++i) {
 233     const MachineOperand &MO = I.getOperand(i);
 234
 235     if (!MO.isReg())
 236       continue;
 237
 238     unsigned Reg = MO.getReg();
 239     if (Reg == 0) continue;
 240
 241     // Don't hoist an instruction that uses or defines a physical register.
 242     if (TargetRegisterInfo::isPhysicalRegister(Reg))
 243       return false;
 244
 245     if (!MO.isUse())
 246       continue;
 247
 248     assert(RegInfo->getVRegDef(Reg) &&
 249            "Machine instr not mapped for this vreg?!");
 250
 251     // If the loop contains the definition of an operand, then the instruction
 252     // isn't loop invariant.
 253     if (CurLoop->contains(RegInfo->getVRegDef(Reg)->getParent()))
 254       return false;
 255   }
 256
 257   // If we got this far, the instruction is loop invariant!
 258   return true;
 259 }
 260
 261 /// HasOnlyPHIUses - Return true if the only uses of Reg are PHIs.
 262 static bool HasOnlyPHIUses(unsigned Reg, MachineRegisterInfo *RegInfo) {
 263   bool OnlyPHIUse = false;
 264   for (MachineRegisterInfo::use_iterator UI = RegInfo->use_begin(Reg),
 265          UE = RegInfo->use_end(); UI != UE; ++UI) {
 266     MachineInstr *UseMI = &*UI;
 267     if (UseMI->getOpcode() != TargetInstrInfo::PHI)
 268       return false;
 269     OnlyPHIUse = true;
 270   }
 271   return OnlyPHIUse;
 272 }
 273
 274 /// IsProfitableToHoist - Return true if it is potentially profitable to hoist
 275 /// the given loop invariant.
 276 bool MachineLICM::IsProfitableToHoist(MachineInstr &MI) {
 277   const TargetInstrDesc &TID = MI.getDesc();
 278
 279   // FIXME: For now, only hoist re-materilizable instructions. LICM will
 280   // increase register pressure. We want to make sure it doesn't increase
 281   // spilling.
 282   if (!TID.mayLoad() && (!TID.isRematerializable() ||
 283                          !TII->isTriviallyReMaterializable(&MI)))
 284     return false;
 285
 286   if (!TID.isAsCheapAsAMove())
 287     return true;
 288
 289   // If the instruction is "cheap" and the only uses of the register(s) defined
 290   // by this MI are PHIs, then don't hoist it. Otherwise we just end up with a
 291   // cheap instruction (e.g. constant) with long live interval feeeding into
 292   // copies that are not always coalesced away.
 293   bool OnlyPHIUses = false;
 294   for (unsigned i = 0, e = MI.getNumOperands(); i != e; ++i) {
 295     const MachineOperand &MO = MI.getOperand(i);
 296     if (!MO.isReg() || !MO.isDef())
 297       continue;
 298     OnlyPHIUses |= HasOnlyPHIUses(MO.getReg(), RegInfo);
 299   }
 300   return !OnlyPHIUses;
 301 }
 302
 303 /// Hoist - When an instruction is found to use only loop invariant operands
 304 /// that are safe to hoist, this instruction is called to do the dirty work.
 305 ///
 306 void MachineLICM::Hoist(MachineInstr &MI) {
 307   if (!IsLoopInvariantInst(MI)) return;
 308   if (!IsProfitableToHoist(MI)) return;
 309
 310   // Now move the instructions to the predecessor, inserting it before any
 311   // terminator instructions.
 312   DEBUG({
 313       DOUT << "Hoisting " << MI;
 314       if (CurPreheader->getBasicBlock())
 315         DOUT << " to MachineBasicBlock "
 316              << CurPreheader->getBasicBlock()->getName();
 317       if (MI.getParent()->getBasicBlock())
 318         DOUT << " from MachineBasicBlock "
 319              << MI.getParent()->getBasicBlock()->getName();
 320       DOUT << "\n";
 321     });
 322
 323   CurPreheader->splice(CurPreheader->getFirstTerminator(), MI.getParent(), &MI);
 324
 325   ++NumHoisted;
 326   Changed = true;
 327 }