X-Git-Url: http://plrg.eecs.uci.edu/git/?a=blobdiff_plain;f=lib%2FCodeGen%2FOptimizePHIs.cpp;h=a1042e720c37585c1299abe47c14d751a25091cd;hb=027a9f45617c2a9ecb809e6b28aac12bdc2d08ec;hp=5b3fa6a68ab71a7b3ba150663bf1997dfa210c45;hpb=fe61fb1e1082c81653ed78efd6d471592a2e57ad;p=oota-llvm.git diff --git a/lib/CodeGen/OptimizePHIs.cpp b/lib/CodeGen/OptimizePHIs.cpp index 5b3fa6a68ab..a1042e720c3 100644 --- a/lib/CodeGen/OptimizePHIs.cpp +++ b/lib/CodeGen/OptimizePHIs.cpp @@ -12,18 +12,21 @@ // //===----------------------------------------------------------------------===// -#define DEBUG_TYPE "phi-opt" #include "llvm/CodeGen/Passes.h" +#include "llvm/ADT/SmallPtrSet.h" +#include "llvm/ADT/Statistic.h" #include "llvm/CodeGen/MachineFunctionPass.h" #include "llvm/CodeGen/MachineInstr.h" #include "llvm/CodeGen/MachineRegisterInfo.h" +#include "llvm/IR/Function.h" #include "llvm/Target/TargetInstrInfo.h" -#include "llvm/Function.h" -#include "llvm/ADT/SmallSet.h" -#include "llvm/ADT/Statistic.h" +#include "llvm/Target/TargetSubtargetInfo.h" using namespace llvm; +#define DEBUG_TYPE "phi-opt" + STATISTIC(NumPHICycles, "Number of PHI cycles replaced"); +STATISTIC(NumDeadPHICycles, "Number of dead PHI cycles"); namespace { class OptimizePHIs : public MachineFunctionPass { @@ -32,38 +35,47 @@ namespace { public: static char ID; // Pass identification - OptimizePHIs() : MachineFunctionPass(&ID) {} + OptimizePHIs() : MachineFunctionPass(ID) { + initializeOptimizePHIsPass(*PassRegistry::getPassRegistry()); + } - virtual bool runOnMachineFunction(MachineFunction &MF); + bool runOnMachineFunction(MachineFunction &MF) override; - virtual void getAnalysisUsage(AnalysisUsage &AU) const { + void getAnalysisUsage(AnalysisUsage &AU) const override { AU.setPreservesCFG(); MachineFunctionPass::getAnalysisUsage(AU); } private: - bool IsSingleValuePHICycle(const MachineInstr *MI, unsigned &SingleValReg, - SmallSet &RegsInCycle); - bool ReplacePHICycles(MachineBasicBlock &MBB); + typedef SmallPtrSet InstrSet; + typedef SmallPtrSetIterator InstrSetIterator; + + bool IsSingleValuePHICycle(MachineInstr *MI, unsigned &SingleValReg, + InstrSet &PHIsInCycle); + bool IsDeadPHICycle(MachineInstr *MI, InstrSet &PHIsInCycle); + bool OptimizeBB(MachineBasicBlock &MBB); }; } char OptimizePHIs::ID = 0; -static RegisterPass -X("opt-phis", "Optimize machine instruction PHIs"); - -FunctionPass *llvm::createOptimizePHIsPass() { return new OptimizePHIs(); } +char &llvm::OptimizePHIsID = OptimizePHIs::ID; +INITIALIZE_PASS(OptimizePHIs, "opt-phis", + "Optimize machine instruction PHIs", false, false) bool OptimizePHIs::runOnMachineFunction(MachineFunction &Fn) { + if (skipOptnoneFunction(*Fn.getFunction())) + return false; + MRI = &Fn.getRegInfo(); - TII = Fn.getTarget().getInstrInfo(); + TII = Fn.getSubtarget().getInstrInfo(); - // Find PHI cycles that can be replaced by a single value. InstCombine - // does this, but DAG legalization may introduce new opportunities, e.g., - // when i64 values are split up for 32-bit targets. + // Find dead PHI cycles and PHI cycles that can be replaced by a single + // value. InstCombine does these optimizations, but DAG legalization may + // introduce new opportunities, e.g., when i64 values are split up for + // 32-bit targets. bool Changed = false; for (MachineFunction::iterator I = Fn.begin(), E = Fn.end(); I != E; ++I) - Changed |= ReplacePHICycles(*I); + Changed |= OptimizeBB(*I); return Changed; } @@ -71,20 +83,20 @@ bool OptimizePHIs::runOnMachineFunction(MachineFunction &Fn) { /// IsSingleValuePHICycle - Check if MI is a PHI where all the source operands /// are copies of SingleValReg, possibly via copies through other PHIs. If /// SingleValReg is zero on entry, it is set to the register with the single -/// non-copy value. RegsInCycle is a set used to keep track of the PHIs that +/// non-copy value. PHIsInCycle is a set used to keep track of the PHIs that /// have been scanned. -bool OptimizePHIs::IsSingleValuePHICycle(const MachineInstr *MI, +bool OptimizePHIs::IsSingleValuePHICycle(MachineInstr *MI, unsigned &SingleValReg, - SmallSet &RegsInCycle) { + InstrSet &PHIsInCycle) { assert(MI->isPHI() && "IsSingleValuePHICycle expects a PHI instruction"); unsigned DstReg = MI->getOperand(0).getReg(); // See if we already saw this register. - if (!RegsInCycle.insert(DstReg)) + if (!PHIsInCycle.insert(MI).second) return true; // Don't scan crazily complex things. - if (RegsInCycle.size() == 16) + if (PHIsInCycle.size() == 16) return false; // Scan the PHI operands. @@ -92,20 +104,19 @@ bool OptimizePHIs::IsSingleValuePHICycle(const MachineInstr *MI, unsigned SrcReg = MI->getOperand(i).getReg(); if (SrcReg == DstReg) continue; - const MachineInstr *SrcMI = MRI->getVRegDef(SrcReg); + MachineInstr *SrcMI = MRI->getVRegDef(SrcReg); // Skip over register-to-register moves. - unsigned MvSrcReg, MvDstReg, SrcSubIdx, DstSubIdx; - if (SrcMI && - TII->isMoveInstr(*SrcMI, MvSrcReg, MvDstReg, SrcSubIdx, DstSubIdx) && - SrcSubIdx == 0 && DstSubIdx == 0 && - TargetRegisterInfo::isVirtualRegister(MvSrcReg)) - SrcMI = MRI->getVRegDef(MvSrcReg); + if (SrcMI && SrcMI->isCopy() && + !SrcMI->getOperand(0).getSubReg() && + !SrcMI->getOperand(1).getSubReg() && + TargetRegisterInfo::isVirtualRegister(SrcMI->getOperand(1).getReg())) + SrcMI = MRI->getVRegDef(SrcMI->getOperand(1).getReg()); if (!SrcMI) return false; if (SrcMI->isPHI()) { - if (!IsSingleValuePHICycle(SrcMI, SingleValReg, RegsInCycle)) + if (!IsSingleValuePHICycle(SrcMI, SingleValReg, PHIsInCycle)) return false; } else { // Fail if there is more than one non-phi/non-move register. @@ -117,9 +128,33 @@ bool OptimizePHIs::IsSingleValuePHICycle(const MachineInstr *MI, return true; } -/// ReplacePHICycles - Find PHI cycles that can be replaced by a single -/// value and remove them. -bool OptimizePHIs::ReplacePHICycles(MachineBasicBlock &MBB) { +/// IsDeadPHICycle - Check if the register defined by a PHI is only used by +/// other PHIs in a cycle. +bool OptimizePHIs::IsDeadPHICycle(MachineInstr *MI, InstrSet &PHIsInCycle) { + assert(MI->isPHI() && "IsDeadPHICycle expects a PHI instruction"); + unsigned DstReg = MI->getOperand(0).getReg(); + assert(TargetRegisterInfo::isVirtualRegister(DstReg) && + "PHI destination is not a virtual register"); + + // See if we already saw this register. + if (!PHIsInCycle.insert(MI).second) + return true; + + // Don't scan crazily complex things. + if (PHIsInCycle.size() == 16) + return false; + + for (MachineInstr &UseMI : MRI->use_instructions(DstReg)) { + if (!UseMI.isPHI() || !IsDeadPHICycle(&UseMI, PHIsInCycle)) + return false; + } + + return true; +} + +/// OptimizeBB - Remove dead PHI cycles and PHI cycles that can be replaced by +/// a single value. +bool OptimizePHIs::OptimizeBB(MachineBasicBlock &MBB) { bool Changed = false; for (MachineBasicBlock::iterator MII = MBB.begin(), E = MBB.end(); MII != E; ) { @@ -127,14 +162,34 @@ bool OptimizePHIs::ReplacePHICycles(MachineBasicBlock &MBB) { if (!MI->isPHI()) break; + // Check for single-value PHI cycles. unsigned SingleValReg = 0; - SmallSet RegsInCycle; - if (IsSingleValuePHICycle(MI, SingleValReg, RegsInCycle) && + InstrSet PHIsInCycle; + if (IsSingleValuePHICycle(MI, SingleValReg, PHIsInCycle) && SingleValReg != 0) { - MRI->replaceRegWith(MI->getOperand(0).getReg(), SingleValReg); + unsigned OldReg = MI->getOperand(0).getReg(); + if (!MRI->constrainRegClass(SingleValReg, MRI->getRegClass(OldReg))) + continue; + + MRI->replaceRegWith(OldReg, SingleValReg); MI->eraseFromParent(); ++NumPHICycles; Changed = true; + continue; + } + + // Check for dead PHI cycles. + PHIsInCycle.clear(); + if (IsDeadPHICycle(MI, PHIsInCycle)) { + for (InstrSetIterator PI = PHIsInCycle.begin(), PE = PHIsInCycle.end(); + PI != PE; ++PI) { + MachineInstr *PhiMI = *PI; + if (&*MII == PhiMI) + ++MII; + PhiMI->eraseFromParent(); + } + ++NumDeadPHICycles; + Changed = true; } } return Changed;