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