X-Git-Url: http://demsky.eecs.uci.edu/git/?a=blobdiff_plain;f=lib%2FCodeGen%2FMachineSink.cpp;h=c177e3c7bae833084474546fd1e1f2dcb339dc13;hb=0fd90fd8d1c2143a763dee509c66a5b3c74088b1;hp=87114396f9e5fcb8c8f12fa6327ee6a3fe7a685f;hpb=d68a07650cdb2e18f18f362ba533459aa10e01b6;p=oota-llvm.git diff --git a/lib/CodeGen/MachineSink.cpp b/lib/CodeGen/MachineSink.cpp index 87114396f9e..c177e3c7bae 100644 --- a/lib/CodeGen/MachineSink.cpp +++ b/lib/CodeGen/MachineSink.cpp @@ -7,7 +7,12 @@ // //===----------------------------------------------------------------------===// // -// This pass +// 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 +// for an LLVM-IR-level sinking pass. It is only designed to sink simple +// constructs that are not exposed before lowering and instruction selection. // //===----------------------------------------------------------------------===// @@ -15,23 +20,25 @@ #include "llvm/CodeGen/Passes.h" #include "llvm/CodeGen/MachineRegisterInfo.h" #include "llvm/CodeGen/MachineDominators.h" +#include "llvm/Analysis/AliasAnalysis.h" #include "llvm/Target/TargetRegisterInfo.h" #include "llvm/Target/TargetInstrInfo.h" #include "llvm/Target/TargetMachine.h" #include "llvm/ADT/Statistic.h" -#include "llvm/Support/Compiler.h" #include "llvm/Support/Debug.h" +#include "llvm/Support/raw_ostream.h" using namespace llvm; STATISTIC(NumSunk, "Number of machine instructions sunk"); namespace { - class VISIBILITY_HIDDEN MachineSinking : public MachineFunctionPass { - const TargetMachine *TM; + class MachineSinking : public MachineFunctionPass { const TargetInstrInfo *TII; - MachineFunction *CurMF; // Current MachineFunction + const TargetRegisterInfo *TRI; MachineRegisterInfo *RegInfo; // Machine register information - MachineDominatorTree *DT; // Machine dominator tree for the current Loop + MachineDominatorTree *DT; // Machine dominator tree + AliasAnalysis *AA; + BitVector AllocatableSet; // Which physregs are allocatable? public: static char ID; // Pass identification @@ -40,7 +47,9 @@ namespace { virtual bool runOnMachineFunction(MachineFunction &MF); virtual void getAnalysisUsage(AnalysisUsage &AU) const { + AU.setPreservesCFG(); MachineFunctionPass::getAnalysisUsage(AU); + AU.addRequired(); AU.addRequired(); AU.addPreserved(); } @@ -63,10 +72,8 @@ bool MachineSinking::AllUsesDominatedByBlock(unsigned Reg, MachineBasicBlock *MBB) const { assert(TargetRegisterInfo::isVirtualRegister(Reg) && "Only makes sense for vregs"); - for (MachineRegisterInfo::reg_iterator I = RegInfo->reg_begin(Reg), - E = RegInfo->reg_end(); I != E; ++I) { - if (I.getOperand().isDef()) continue; // ignore def. - + for (MachineRegisterInfo::use_iterator I = RegInfo->use_begin(Reg), + E = RegInfo->use_end(); I != E; ++I) { // Determine the block of the use. MachineInstr *UseInst = &*I; MachineBasicBlock *UseBlock = UseInst->getParent(); @@ -82,16 +89,16 @@ bool MachineSinking::AllUsesDominatedByBlock(unsigned Reg, return true; } - - bool MachineSinking::runOnMachineFunction(MachineFunction &MF) { - DOUT << "******** Machine Sinking ********\n"; + DEBUG(dbgs() << "******** Machine Sinking ********\n"); - CurMF = &MF; - TM = &CurMF->getTarget(); - TII = TM->getInstrInfo(); - RegInfo = &CurMF->getRegInfo(); + const TargetMachine &TM = MF.getTarget(); + TII = TM.getInstrInfo(); + TRI = TM.getRegisterInfo(); + RegInfo = &MF.getRegInfo(); DT = &getAnalysis(); + AA = &getAnalysis(); + AllocatableSet = TRI->getAllocatableSet(MF); bool EverMadeChange = false; @@ -99,7 +106,7 @@ bool MachineSinking::runOnMachineFunction(MachineFunction &MF) { bool MadeChange = false; // Process all basic blocks. - for (MachineFunction::iterator I = CurMF->begin(), E = CurMF->end(); + for (MachineFunction::iterator I = MF.begin(), E = MF.end(); I != E; ++I) MadeChange |= ProcessBlock(*I); @@ -111,20 +118,29 @@ bool MachineSinking::runOnMachineFunction(MachineFunction &MF) { } bool MachineSinking::ProcessBlock(MachineBasicBlock &MBB) { - bool MadeChange = false; - // Can't sink anything out of a block that has less than two successors. - if (MBB.succ_size() <= 1) return false; - + if (MBB.succ_size() <= 1 || MBB.empty()) return false; + + bool MadeChange = false; + // Walk the basic block bottom-up. Remember if we saw a store. - bool SawStore = false; - for (MachineBasicBlock::iterator I = MBB.end(); I != MBB.begin(); ){ - MachineBasicBlock::iterator LastIt = I; - if (SinkInstruction(--I, SawStore)) { - I = LastIt; - ++NumSunk; - } - } + MachineBasicBlock::iterator I = MBB.end(); + --I; + 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(); + if (!ProcessedBegin) + --I; + + if (SinkInstruction(MI, SawStore)) + ++NumSunk, MadeChange = true; + + // If we just processed the first instruction in the block, we're done. + } while (!ProcessedBegin); return MadeChange; } @@ -133,7 +149,7 @@ bool MachineSinking::ProcessBlock(MachineBasicBlock &MBB) { /// instruction out of its current block into a successor. bool MachineSinking::SinkInstruction(MachineInstr *MI, bool &SawStore) { // Check if it's safe to move the instruction. - if (!MI->isSafeToMove(TII, SawStore)) + if (!MI->isSafeToMove(TII, SawStore, AA)) return false; // FIXME: This should include support for sinking instructions within the @@ -142,7 +158,7 @@ bool MachineSinking::SinkInstruction(MachineInstr *MI, bool &SawStore) { // also sink them down before their first use in the block. This xform has to // 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 only the shrink the live range of x. + // 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. @@ -160,13 +176,33 @@ bool MachineSinking::SinkInstruction(MachineInstr *MI, bool &SawStore) { if (Reg == 0) continue; if (TargetRegisterInfo::isPhysicalRegister(Reg)) { - // If this is a physical register use, we can't move it. If it is a def, - // we can move it, but only if the def is dead. - if (MO.isUse() || !MO.isDead()) + if (MO.isUse()) { + // If the physreg has no defs anywhere, it's just an ambient register + // and we can freely move its uses. Alternatively, if it's allocatable, + // 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; + } + } else if (!MO.isDead()) { + // A def that isn't dead. We can't move it. return false; + } } else { // Virtual register uses are always safe to sink. if (MO.isUse()) continue; + + // 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 @@ -208,16 +244,26 @@ bool MachineSinking::SinkInstruction(MachineInstr *MI, bool &SawStore) { // If there are no outputs, it must have side-effects. if (SuccToSinkTo == 0) return false; + + // It's not safe to sink instructions to EH landing pad. Control flow into + // 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(cerr << "Sink instr " << *MI); - DEBUG(cerr << "to block " << *SuccToSinkTo); + DEBUG(dbgs() << "Sink instr " << *MI); + DEBUG(dbgs() << "to 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. // FIXME: Split critical edges if not backedges. if (SuccToSinkTo->pred_size() > 1) { - DEBUG(cerr << " *** PUNTING: Critical edge found\n"); + DEBUG(dbgs() << " *** PUNTING: Critical edge found\n"); return false; }