diff options
Diffstat (limited to 'lib/CodeGen/MachineSink.cpp')
| -rw-r--r-- | lib/CodeGen/MachineSink.cpp | 102 |
1 files changed, 61 insertions, 41 deletions
diff --git a/lib/CodeGen/MachineSink.cpp b/lib/CodeGen/MachineSink.cpp index 1610e6c..61334fc 100644 --- a/lib/CodeGen/MachineSink.cpp +++ b/lib/CodeGen/MachineSink.cpp @@ -7,7 +7,7 @@ // //===----------------------------------------------------------------------===// // -// This pass moves instructions into successor blocks, when possible, so that +// This pass moves instructions into successor blocks when possible, so that // they aren't executed on paths where their results aren't needed. // // This pass is not intended to be a replacement or a complete alternative @@ -45,9 +45,9 @@ namespace { public: static char ID; // Pass identification MachineSinking() : MachineFunctionPass(&ID) {} - + virtual bool runOnMachineFunction(MachineFunction &MF); - + virtual void getAnalysisUsage(AnalysisUsage &AU) const { AU.setPreservesCFG(); MachineFunctionPass::getAnalysisUsage(AU); @@ -63,7 +63,7 @@ namespace { bool AllUsesDominatedByBlock(unsigned Reg, MachineBasicBlock *MBB) const; }; } // end anonymous namespace - + char MachineSinking::ID = 0; static RegisterPass<MachineSinking> X("machine-sink", "Machine code sinking"); @@ -72,7 +72,7 @@ FunctionPass *llvm::createMachineSinkingPass() { return new MachineSinking(); } /// AllUsesDominatedByBlock - Return true if all uses of the specified register /// occur in blocks dominated by the specified block. -bool MachineSinking::AllUsesDominatedByBlock(unsigned Reg, +bool MachineSinking::AllUsesDominatedByBlock(unsigned Reg, MachineBasicBlock *MBB) const { assert(TargetRegisterInfo::isVirtualRegister(Reg) && "Only makes sense for vregs"); @@ -80,27 +80,30 @@ bool MachineSinking::AllUsesDominatedByBlock(unsigned Reg, // This may leave a referencing dbg_value in the original block, before // the definition of the vreg. Dwarf generator handles this although the // user might not get the right info at runtime. - for (MachineRegisterInfo::use_nodbg_iterator I = - RegInfo->use_nodbg_begin(Reg), - E = RegInfo->use_nodbg_end(); I != E; ++I) { + for (MachineRegisterInfo::use_nodbg_iterator + I = RegInfo->use_nodbg_begin(Reg), E = RegInfo->use_nodbg_end(); + I != E; ++I) { // Determine the block of the use. MachineInstr *UseInst = &*I; MachineBasicBlock *UseBlock = UseInst->getParent(); + if (UseInst->isPHI()) { // PHI nodes use the operand in the predecessor block, not the block with // the PHI. UseBlock = UseInst->getOperand(I.getOperandNo()+1).getMBB(); } + // Check that it dominates. if (!DT->dominates(MBB, UseBlock)) return false; } + return true; } bool MachineSinking::runOnMachineFunction(MachineFunction &MF) { DEBUG(dbgs() << "******** Machine Sinking ********\n"); - + const TargetMachine &TM = MF.getTarget(); TII = TM.getInstrInfo(); TRI = TM.getRegisterInfo(); @@ -111,19 +114,19 @@ bool MachineSinking::runOnMachineFunction(MachineFunction &MF) { AllocatableSet = TRI->getAllocatableSet(MF); bool EverMadeChange = false; - + while (1) { bool MadeChange = false; // Process all basic blocks. - for (MachineFunction::iterator I = MF.begin(), E = MF.end(); + for (MachineFunction::iterator I = MF.begin(), E = MF.end(); I != E; ++I) MadeChange |= ProcessBlock(*I); - + // If this iteration over the code changed anything, keep iterating. if (!MadeChange) break; EverMadeChange = true; - } + } return EverMadeChange; } @@ -132,8 +135,8 @@ bool MachineSinking::ProcessBlock(MachineBasicBlock &MBB) { if (MBB.succ_size() <= 1 || MBB.empty()) return false; // Don't bother sinking code out of unreachable blocks. In addition to being - // unprofitable, it can also lead to infinite looping, because in an unreachable - // loop there may be nowhere to stop. + // unprofitable, it can also lead to infinite looping, because in an + // unreachable loop there may be nowhere to stop. if (!DT->isReachableFromEntry(&MBB)) return false; bool MadeChange = false; @@ -144,7 +147,7 @@ bool MachineSinking::ProcessBlock(MachineBasicBlock &MBB) { bool ProcessedBegin, SawStore = false; do { MachineInstr *MI = I; // The instruction to sink. - + // Predecrement I (if it's not begin) so that it isn't invalidated by // sinking. ProcessedBegin = I == MBB.begin(); @@ -156,10 +159,10 @@ bool MachineSinking::ProcessBlock(MachineBasicBlock &MBB) { if (SinkInstruction(MI, SawStore)) ++NumSunk, MadeChange = true; - + // If we just processed the first instruction in the block, we're done. } while (!ProcessedBegin); - + return MadeChange; } @@ -169,7 +172,7 @@ bool MachineSinking::SinkInstruction(MachineInstr *MI, bool &SawStore) { // Check if it's safe to move the instruction. if (!MI->isSafeToMove(TII, AA, SawStore)) return false; - + // FIXME: This should include support for sinking instructions within the // block they are currently in to shorten the live ranges. We often get // instructions sunk into the top of a large block, but it would be better to @@ -177,22 +180,22 @@ bool MachineSinking::SinkInstruction(MachineInstr *MI, bool &SawStore) { // be careful not to *increase* register pressure though, e.g. sinking // "x = y + z" down if it kills y and z would increase the live ranges of y // and z and only shrink the live range of x. - + // Loop over all the operands of the specified instruction. If there is // anything we can't handle, bail out. MachineBasicBlock *ParentBlock = MI->getParent(); - + // SuccToSinkTo - This is the successor to sink this instruction to, once we // decide. MachineBasicBlock *SuccToSinkTo = 0; - + for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) { const MachineOperand &MO = MI->getOperand(i); if (!MO.isReg()) continue; // Ignore non-register operands. - + unsigned Reg = MO.getReg(); if (Reg == 0) continue; - + if (TargetRegisterInfo::isPhysicalRegister(Reg)) { if (MO.isUse()) { // If the physreg has no defs anywhere, it's just an ambient register @@ -200,13 +203,16 @@ bool MachineSinking::SinkInstruction(MachineInstr *MI, bool &SawStore) { // it could get allocated to something with a def during allocation. if (!RegInfo->def_empty(Reg)) return false; + if (AllocatableSet.test(Reg)) return false; + // Check for a def among the register's aliases too. for (const unsigned *Alias = TRI->getAliasSet(Reg); *Alias; ++Alias) { unsigned AliasReg = *Alias; if (!RegInfo->def_empty(AliasReg)) return false; + if (AllocatableSet.test(AliasReg)) return false; } @@ -221,28 +227,31 @@ bool MachineSinking::SinkInstruction(MachineInstr *MI, bool &SawStore) { // If it's not safe to move defs of the register class, then abort. if (!TII->isSafeToMoveRegClassDefs(RegInfo->getRegClass(Reg))) return false; - + // FIXME: This picks a successor to sink into based on having one // successor that dominates all the uses. However, there are cases where // sinking can happen but where the sink point isn't a successor. For // example: + // // x = computation // if () {} else {} // use x - // the instruction could be sunk over the whole diamond for the + // + // the instruction could be sunk over the whole diamond for the // if/then/else (or loop, etc), allowing it to be sunk into other blocks // after that. - + // Virtual register defs can only be sunk if all their uses are in blocks // dominated by one of the successors. if (SuccToSinkTo) { // If a previous operand picked a block to sink to, then this operand // must be sinkable to the same block. - if (!AllUsesDominatedByBlock(Reg, SuccToSinkTo)) + if (!AllUsesDominatedByBlock(Reg, SuccToSinkTo)) return false; + continue; } - + // Otherwise, we should look at all the successors and decide which one // we should sink to. for (MachineBasicBlock::succ_iterator SI = ParentBlock->succ_begin(), @@ -252,13 +261,13 @@ bool MachineSinking::SinkInstruction(MachineInstr *MI, bool &SawStore) { break; } } - + // If we couldn't find a block to sink to, ignore this instruction. if (SuccToSinkTo == 0) return false; } } - + // If there are no outputs, it must have side-effects. if (SuccToSinkTo == 0) return false; @@ -267,15 +276,26 @@ bool MachineSinking::SinkInstruction(MachineInstr *MI, bool &SawStore) { // landing pad is implicitly defined. if (SuccToSinkTo->isLandingPad()) return false; - + // It is not possible to sink an instruction into its own block. This can // happen with loops. if (MI->getParent() == SuccToSinkTo) return false; - - DEBUG(dbgs() << "Sink instr " << *MI); - DEBUG(dbgs() << "to block " << *SuccToSinkTo); - + + // If the instruction to move defines a dead physical register which is live + // when leaving the basic block, don't move it because it could turn into a + // "zombie" define of that preg. E.g., EFLAGS. (<rdar://problem/8030636>) + for (unsigned I = 0, E = MI->getNumOperands(); I != E; ++I) { + const MachineOperand &MO = MI->getOperand(I); + if (!MO.isReg()) continue; + unsigned Reg = MO.getReg(); + if (Reg == 0 || !TargetRegisterInfo::isPhysicalRegister(Reg)) continue; + if (SuccToSinkTo->isLiveIn(Reg)) + return false; + } + + DEBUG(dbgs() << "Sink instr " << *MI << "\tinto block " << *SuccToSinkTo); + // If the block has multiple predecessors, this would introduce computation on // a path that it doesn't already exist. We could split the critical edge, // but for now we just punt. @@ -305,18 +325,18 @@ bool MachineSinking::SinkInstruction(MachineInstr *MI, bool &SawStore) { // Otherwise we are OK with sinking along a critical edge. DEBUG(dbgs() << "Sinking along critical edge.\n"); } - - // Determine where to insert into. Skip phi nodes. + + // Determine where to insert into. Skip phi nodes. MachineBasicBlock::iterator InsertPos = SuccToSinkTo->begin(); while (InsertPos != SuccToSinkTo->end() && InsertPos->isPHI()) ++InsertPos; - + // Move the instruction. SuccToSinkTo->splice(InsertPos, ParentBlock, MI, ++MachineBasicBlock::iterator(MI)); - // Conservatively, clear any kill flags, since it's possible that - // they are no longer correct. + // Conservatively, clear any kill flags, since it's possible that they are no + // longer correct. MI->clearKillInfo(); return true; |
