lib/CodeGen/MachineLICM.cpp

   1 //===-- MachineLICM.cpp - Machine Loop Invariant Code Motion Pass ---------===//
   2 //
   3 //                     The LLVM Compiler Infrastructure
   4 //
   5 // This file was developed by Bill Wendling and is distributed under the
   6 // University of Illinois Open Source 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 //===----------------------------------------------------------------------===//
  14
  15 #define DEBUG_TYPE "machine-licm"
  16 #include "llvm/ADT/IndexedMap.h"
  17 #include "llvm/ADT/SmallVector.h"
  18 #include "llvm/ADT/Statistic.h"
  19 #include "llvm/CodeGen/MachineBasicBlock.h"
  20 #include "llvm/CodeGen/MachineDominators.h"
  21 #include "llvm/CodeGen/MachineInstr.h"
  22 #include "llvm/CodeGen/MachineLoopInfo.h"
  23 #include "llvm/CodeGen/Passes.h"
  24 #include "llvm/Target/TargetInstrInfo.h"
  25 #include "llvm/Support/CFG.h"
  26 #include "llvm/Support/CommandLine.h"
  27 #include "llvm/Support/Compiler.h"
  28 #include "llvm/Support/Debug.h"
  29 #include "llvm/Target/MRegisterInfo.h"
  30 #include "llvm/Target/TargetMachine.h"
  31
  32 using namespace llvm;
  33
  34 namespace {
  35   // Hidden options to help debugging
  36   cl::opt<bool>
  37   PerformLICM("machine-licm",
  38               cl::init(false), cl::Hidden,
  39               cl::desc("Perform loop-invariant code motion on machine code"));
  40 }
  41
  42 STATISTIC(NumHoisted, "Number of machine instructions hoisted out of loops");
  43
  44 namespace {
  45   class VISIBILITY_HIDDEN MachineLICM : public MachineFunctionPass {
  46     // Various analyses that we use...
  47     MachineLoopInfo      *LI;   // Current MachineLoopInfo
  48     MachineDominatorTree *DT;   // Machine dominator tree for the current Loop
  49
  50     const TargetInstrInfo *TII;
  51
  52     // State that is updated as we process loops
  53     bool         Changed;       // True if a loop is changed.
  54     MachineLoop *CurLoop;       // The current loop we are working on.
  55
  56     // Map the def of a virtual register to the machine instruction.
  57     IndexedMap<const MachineInstr*, VirtReg2IndexFunctor> VRegDefs;
  58   public:
  59     static char ID; // Pass identification, replacement for typeid
  60     MachineLICM() : MachineFunctionPass((intptr_t)&ID) {}
  61
  62     virtual bool runOnMachineFunction(MachineFunction &MF);
  63
  64     /// FIXME: Loop preheaders?
  65     ///
  66     virtual void getAnalysisUsage(AnalysisUsage &AU) const {
  67       AU.setPreservesCFG();
  68       AU.addRequired<MachineLoopInfo>();
  69       AU.addRequired<MachineDominatorTree>();
  70     }
  71   private:
  72     /// VisitAllLoops - Visit all of the loops in depth first order and try to
  73     /// hoist invariant instructions from them.
  74     ///
  75     void VisitAllLoops(MachineLoop *L) {
  76       const std::vector<MachineLoop*> &SubLoops = L->getSubLoops();
  77
  78       for (MachineLoop::iterator
  79              I = SubLoops.begin(), E = SubLoops.end(); I != E; ++I) {
  80         MachineLoop *ML = *I;
  81
  82         // Traverse the body of the loop in depth first order on the dominator
  83         // tree so that we are guaranteed to see definitions before we see uses.
  84         VisitAllLoops(ML);
  85         HoistRegion(DT->getNode(ML->getHeader()));
  86       }
  87
  88       HoistRegion(DT->getNode(L->getHeader()));
  89     }
  90
  91     /// MapVirtualRegisterDefs - Create a map of which machine instruction
  92     /// defines a virtual register.
  93     ///
  94     void MapVirtualRegisterDefs(const MachineFunction &MF);
  95
  96     /// IsInSubLoop - A little predicate that returns true if the specified
  97     /// basic block is in a subloop of the current one, not the current one
  98     /// itself.
  99     ///
 100     bool IsInSubLoop(MachineBasicBlock *BB) {
 101       assert(CurLoop->contains(BB) && "Only valid if BB is IN the loop");
 102
 103       for (MachineLoop::iterator
 104              I = CurLoop->begin(), E = CurLoop->end(); I != E; ++I)
 105         if ((*I)->contains(BB))
 106           return true;  // A subloop actually contains this block!
 107
 108       return false;
 109     }
 110
 111     /// CanHoistInst - Checks that this instructions is one that can be hoisted
 112     /// out of the loop. I.e., it has no side effects, isn't a control flow
 113     /// instr, etc.
 114     ///
 115     bool CanHoistInst(MachineInstr &I) const {
 116       const TargetInstrDescriptor *TID = I.getInstrDescriptor();
 117
 118       // Don't hoist if this instruction implicitly reads physical registers or
 119       // doesn't take any operands.
 120       if (TID->ImplicitUses || !I.getNumOperands()) return false;
 121
 122       MachineOpCode Opcode = TID->Opcode;
 123       return TII->isTriviallyReMaterializable(&I) &&
 124         // FIXME: Below necessary?
 125         !(TII->isReturn(Opcode) ||
 126           TII->isTerminatorInstr(Opcode) ||
 127           TII->isBranch(Opcode) ||
 128           TII->isIndirectBranch(Opcode) ||
 129           TII->isBarrier(Opcode) ||
 130           TII->isCall(Opcode) ||
 131           TII->isLoad(Opcode) || // TODO: Do loads and stores.
 132           TII->isStore(Opcode));
 133     }
 134
 135     /// IsLoopInvariantInst - Returns true if the instruction is loop
 136     /// invariant. I.e., all virtual register operands are defined outside of
 137     /// the loop, physical registers aren't accessed (explicitly or implicitly),
 138     /// and the instruction is hoistable.
 139     ///
 140     bool IsLoopInvariantInst(MachineInstr &I);
 141
 142     /// FindPredecessors - Get all of the predecessors of the loop that are not
 143     /// back-edges.
 144     ///
 145     void FindPredecessors(std::vector<MachineBasicBlock*> &Preds){
 146       const MachineBasicBlock *Header = CurLoop->getHeader();
 147
 148       for (MachineBasicBlock::const_pred_iterator
 149              I = Header->pred_begin(), E = Header->pred_end(); I != E; ++I)
 150         if (!CurLoop->contains(*I))
 151           Preds.push_back(*I);
 152     }
 153
 154     /// MoveInstToEndOfBlock - Moves the machine instruction to the bottom of
 155     /// the predecessor basic block (but before the terminator instructions).
 156     ///
 157     void MoveInstToEndOfBlock(MachineBasicBlock *MBB, MachineInstr *MI) {
 158       MachineBasicBlock::iterator Iter = MBB->getFirstTerminator();
 159       MBB->insert(Iter, MI);
 160       ++NumHoisted;
 161     }
 162
 163     /// HoistRegion - Walk the specified region of the CFG (defined by all
 164     /// blocks dominated by the specified block, and that are in the current
 165     /// loop) in depth first order w.r.t the DominatorTree. This allows us to
 166     /// visit definitions before uses, allowing us to hoist a loop body in one
 167     /// pass without iteration.
 168     ///
 169     void HoistRegion(MachineDomTreeNode *N);
 170
 171     /// Hoist - When an instruction is found to only use loop invariant operands
 172     /// that is safe to hoist, this instruction is called to do the dirty work.
 173     ///
 174     void Hoist(MachineInstr &MI);
 175   };
 176
 177   char MachineLICM::ID = 0;
 178   RegisterPass<MachineLICM> X("machine-licm",
 179                               "Machine Loop Invariant Code Motion");
 180 } // end anonymous namespace
 181
 182 FunctionPass *llvm::createMachineLICMPass() { return new MachineLICM(); }
 183
 184 /// Hoist expressions out of the specified loop. Note, alias info for inner loop
 185 /// is not preserved so it is not a good idea to run LICM multiple times on one
 186 /// loop.
 187 ///
 188 bool MachineLICM::runOnMachineFunction(MachineFunction &MF) {
 189   if (!PerformLICM) return false; // For debugging.
 190
 191   Changed = false;
 192   TII = MF.getTarget().getInstrInfo();
 193
 194   // Get our Loop information...
 195   LI = &getAnalysis<MachineLoopInfo>();
 196   DT = &getAnalysis<MachineDominatorTree>();
 197
 198   for (MachineLoopInfo::iterator
 199          I = LI->begin(), E = LI->end(); I != E; ++I) {
 200     MachineLoop *L = *I;
 201     CurLoop = L;
 202
 203     // Visit all of the instructions of the loop. We want to visit the subloops
 204     // first, though, so that we can hoist their invariants first into their
 205     // containing loop before we process that loop.
 206     VisitAllLoops(L);
 207   }
 208
 209   return Changed;
 210 }
 211
 212 /// MapVirtualRegisterDefs - Create a map of which machine instruction defines a
 213 /// virtual register.
 214 ///
 215 void MachineLICM::MapVirtualRegisterDefs(const MachineFunction &MF) {
 216   for (MachineFunction::const_iterator
 217          I = MF.begin(), E = MF.end(); I != E; ++I) {
 218     const MachineBasicBlock &MBB = *I;
 219
 220     for (MachineBasicBlock::const_iterator
 221            II = MBB.begin(), IE = MBB.end(); II != IE; ++II) {
 222       const MachineInstr &MI = *II;
 223
 224       for (unsigned i = 0, e = MI.getNumOperands(); i != e; ++i) {
 225         const MachineOperand &MO = MI.getOperand(0);
 226
 227         if (MO.isRegister() && MO.isDef() &&
 228             MRegisterInfo::isVirtualRegister(MO.getReg()))
 229           VRegDefs[MO.getReg()] = &MI;
 230       }
 231     }
 232   }
 233 }
 234
 235 /// HoistRegion - Walk the specified region of the CFG (defined by all blocks
 236 /// dominated by the specified block, and that are in the current loop) in depth
 237 /// first order w.r.t the DominatorTree. This allows us to visit definitions
 238 /// before uses, allowing us to hoist a loop body in one pass without iteration.
 239 ///
 240 void MachineLICM::HoistRegion(MachineDomTreeNode *N) {
 241   assert(N != 0 && "Null dominator tree node?");
 242   MachineBasicBlock *BB = N->getBlock();
 243
 244   // If this subregion is not in the top level loop at all, exit.
 245   if (!CurLoop->contains(BB)) return;
 246
 247   // Only need to process the contents of this block if it is not part of a
 248   // subloop (which would already have been processed).
 249   if (!IsInSubLoop(BB))
 250     for (MachineBasicBlock::iterator
 251            I = BB->begin(), E = BB->end(); I != E; ) {
 252       MachineInstr &MI = *I++;
 253
 254       // Try hoisting the instruction out of the loop. We can only do this if
 255       // all of the operands of the instruction are loop invariant and if it is
 256       // safe to hoist the instruction.
 257       Hoist(MI);
 258     }
 259
 260   const std::vector<MachineDomTreeNode*> &Children = N->getChildren();
 261
 262   for (unsigned I = 0, E = Children.size(); I != E; ++I)
 263     HoistRegion(Children[I]);
 264 }
 265
 266 /// IsLoopInvariantInst - Returns true if the instruction is loop
 267 /// invariant. I.e., all virtual register operands are defined outside of the
 268 /// loop, physical registers aren't accessed (explicitly or implicitly), and the
 269 /// instruction is hoistable.
 270 ///
 271 bool MachineLICM::IsLoopInvariantInst(MachineInstr &I) {
 272   if (!CanHoistInst(I)) return false;
 273
 274   // The instruction is loop invariant if all of its operands are loop-invariant
 275   for (unsigned i = 0, e = I.getNumOperands(); i != e; ++i) {
 276     const MachineOperand &MO = I.getOperand(i);
 277
 278     if (!MO.isRegister() || !MO.isUse())
 279       continue;
 280
 281     unsigned Reg = MO.getReg();
 282
 283     // Don't hoist instructions that access physical registers.
 284     if (!MRegisterInfo::isVirtualRegister(Reg))
 285       return false;
 286
 287     assert(VRegDefs[Reg] && "Machine instr not mapped for this vreg?");
 288
 289     // If the loop contains the definition of an operand, then the instruction
 290     // isn't loop invariant.
 291     if (CurLoop->contains(VRegDefs[Reg]->getParent()))
 292       return false;
 293   }
 294
 295   // If we got this far, the instruction is loop invariant!
 296   return true;
 297 }
 298
 299 /// Hoist - When an instruction is found to only use loop invariant operands
 300 /// that is safe to hoist, this instruction is called to do the dirty work.
 301 ///
 302 void MachineLICM::Hoist(MachineInstr &MI) {
 303   if (!IsLoopInvariantInst(MI)) return;
 304
 305   std::vector<MachineBasicBlock*> Preds;
 306
 307   // Non-back-edge predecessors.
 308   FindPredecessors(Preds);
 309
 310   // Either we don't have any predecessors(?!) or we have more than one, which
 311   // is forbidden.
 312   if (Preds.empty() || Preds.size() != 1) return;
 313
 314   // Check that the predecessor is qualified to take the hoisted
 315   // instruction. I.e., there is only one edge from the predecessor, and it's to
 316   // the loop header.
 317   MachineBasicBlock *MBB = Preds.front();
 318
 319   // FIXME: We are assuming at first that the basic block coming into this loop
 320   // has only one successor. This isn't the case in general because we haven't
 321   // broken critical edges or added preheaders.
 322   if (MBB->succ_size() != 1) return;
 323   assert(*MBB->succ_begin() == CurLoop->getHeader() &&
 324          "The predecessor doesn't feed directly into the loop header!");
 325
 326   // Now move the instructions to the predecessor.
 327   MoveInstToEndOfBlock(MBB, MI.clone());
 328
 329   // Hoisting was successful! Remove bothersome instruction now.
 330   MI.getParent()->remove(&MI);
 331   Changed = true;
 332 }