X-Git-Url: http://plrg.eecs.uci.edu/git/?a=blobdiff_plain;f=lib%2FCodeGen%2FProcessImplicitDefs.cpp;h=b1538006e72492a9ecbb38fa619af4de28fcf19a;hb=076fd5dfc1f0600183bbc7db974dc7b39086136d;hp=b1637293b29d13bf5dec1ec669e993c8fe11bece;hpb=ce665bd2e2b581ab0858d1afe359192bac96b868;p=oota-llvm.git diff --git a/lib/CodeGen/ProcessImplicitDefs.cpp b/lib/CodeGen/ProcessImplicitDefs.cpp index b1637293b29..b1538006e72 100644 --- a/lib/CodeGen/ProcessImplicitDefs.cpp +++ b/lib/CodeGen/ProcessImplicitDefs.cpp @@ -7,289 +7,162 @@ // //===----------------------------------------------------------------------===// -#define DEBUG_TYPE "processimplicitdefs" - -#include "llvm/CodeGen/ProcessImplicitDefs.h" - -#include "llvm/ADT/DepthFirstIterator.h" -#include "llvm/ADT/SmallSet.h" +#include "llvm/ADT/SetVector.h" #include "llvm/Analysis/AliasAnalysis.h" -#include "llvm/CodeGen/LiveVariables.h" +#include "llvm/CodeGen/MachineFunctionPass.h" #include "llvm/CodeGen/MachineInstr.h" #include "llvm/CodeGen/MachineRegisterInfo.h" #include "llvm/CodeGen/Passes.h" #include "llvm/Support/Debug.h" +#include "llvm/Support/raw_ostream.h" #include "llvm/Target/TargetInstrInfo.h" -#include "llvm/Target/TargetRegisterInfo.h" - +#include "llvm/Target/TargetSubtargetInfo.h" using namespace llvm; -char ProcessImplicitDefs::ID = 0; -INITIALIZE_PASS(ProcessImplicitDefs, "processimpdefs", - "Process Implicit Definitions.", false, false) - -void ProcessImplicitDefs::getAnalysisUsage(AnalysisUsage &AU) const { - AU.setPreservesCFG(); - AU.addPreserved(); - AU.addPreserved(); - AU.addRequired(); - AU.addPreservedID(MachineLoopInfoID); - AU.addPreservedID(MachineDominatorsID); - AU.addPreservedID(TwoAddressInstructionPassID); - AU.addPreservedID(PHIEliminationID); - MachineFunctionPass::getAnalysisUsage(AU); -} - -bool -ProcessImplicitDefs::CanTurnIntoImplicitDef(MachineInstr *MI, - unsigned Reg, unsigned OpIdx, - const TargetInstrInfo *tii_, - SmallSet &ImpDefRegs) { - switch(OpIdx) { - case 1: - return MI->isCopy() && (MI->getOperand(0).getSubReg() == 0 || - ImpDefRegs.count(MI->getOperand(0).getReg())); - case 2: - return MI->isSubregToReg() && (MI->getOperand(0).getSubReg() == 0 || - ImpDefRegs.count(MI->getOperand(0).getReg())); - default: return false; - } -} +#define DEBUG_TYPE "processimplicitdefs" -static bool isUndefCopy(MachineInstr *MI, unsigned Reg, - const TargetInstrInfo *tii_, - SmallSet &ImpDefRegs) { - if (MI->isCopy()) { - MachineOperand &MO0 = MI->getOperand(0); - MachineOperand &MO1 = MI->getOperand(1); - if (MO1.getReg() != Reg) - return false; - if (!MO0.getSubReg() || ImpDefRegs.count(MO0.getReg())) - return true; - return false; - } - return false; -} +namespace { +/// Process IMPLICIT_DEF instructions and make sure there is one implicit_def +/// for each use. Add isUndef marker to implicit_def defs and their uses. +class ProcessImplicitDefs : public MachineFunctionPass { + const TargetInstrInfo *TII; + const TargetRegisterInfo *TRI; + MachineRegisterInfo *MRI; -/// processImplicitDefs - Process IMPLICIT_DEF instructions and make sure -/// there is one implicit_def for each use. Add isUndef marker to -/// implicit_def defs and their uses. -bool ProcessImplicitDefs::runOnMachineFunction(MachineFunction &fn) { + SmallSetVector WorkList; - DEBUG(dbgs() << "********** PROCESS IMPLICIT DEFS **********\n" - << "********** Function: " - << ((Value*)fn.getFunction())->getName() << '\n'); + void processImplicitDef(MachineInstr *MI); + bool canTurnIntoImplicitDef(MachineInstr *MI); - bool Changed = false; +public: + static char ID; - const TargetInstrInfo *tii_ = fn.getTarget().getInstrInfo(); - const TargetRegisterInfo *tri_ = fn.getTarget().getRegisterInfo(); - MachineRegisterInfo *mri_ = &fn.getRegInfo(); + ProcessImplicitDefs() : MachineFunctionPass(ID) { + initializeProcessImplicitDefsPass(*PassRegistry::getPassRegistry()); + } - LiveVariables *lv_ = &getAnalysis(); + void getAnalysisUsage(AnalysisUsage &au) const override; - SmallSet ImpDefRegs; - SmallVector ImpDefMIs; - SmallVector RUses; - SmallPtrSet Visited; - SmallPtrSet ModInsts; + bool runOnMachineFunction(MachineFunction &fn) override; +}; +} // end anonymous namespace - MachineBasicBlock *Entry = fn.begin(); - for (df_ext_iterator > - DFI = df_ext_begin(Entry, Visited), E = df_ext_end(Entry, Visited); - DFI != E; ++DFI) { - MachineBasicBlock *MBB = *DFI; - for (MachineBasicBlock::iterator I = MBB->begin(), E = MBB->end(); - I != E; ) { - MachineInstr *MI = &*I; - ++I; - if (MI->isImplicitDef()) { - if (MI->getOperand(0).getSubReg()) - continue; - unsigned Reg = MI->getOperand(0).getReg(); - ImpDefRegs.insert(Reg); - if (TargetRegisterInfo::isPhysicalRegister(Reg)) { - for (const unsigned *SS = tri_->getSubRegisters(Reg); *SS; ++SS) - ImpDefRegs.insert(*SS); - } - ImpDefMIs.push_back(MI); - continue; - } +char ProcessImplicitDefs::ID = 0; +char &llvm::ProcessImplicitDefsID = ProcessImplicitDefs::ID; - // Eliminate %reg1032:sub = COPY undef. - if (MI->isCopy() && MI->getOperand(0).getSubReg()) { - MachineOperand &MO = MI->getOperand(1); - if (MO.isUndef() || ImpDefRegs.count(MO.getReg())) { - if (MO.isKill()) { - LiveVariables::VarInfo& vi = lv_->getVarInfo(MO.getReg()); - vi.removeKill(MI); - } - MI->eraseFromParent(); - Changed = true; - continue; - } - } +INITIALIZE_PASS_BEGIN(ProcessImplicitDefs, "processimpdefs", + "Process Implicit Definitions", false, false) +INITIALIZE_PASS_END(ProcessImplicitDefs, "processimpdefs", + "Process Implicit Definitions", false, false) - bool ChangedToImpDef = false; - for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) { - MachineOperand& MO = MI->getOperand(i); - if (!MO.isReg() || (MO.isDef() && !MO.getSubReg()) || MO.isUndef()) - continue; - unsigned Reg = MO.getReg(); - if (!Reg) - continue; - if (!ImpDefRegs.count(Reg)) - continue; - // Use is a copy, just turn it into an implicit_def. - if (CanTurnIntoImplicitDef(MI, Reg, i, tii_, ImpDefRegs)) { - bool isKill = MO.isKill(); - MI->setDesc(tii_->get(TargetOpcode::IMPLICIT_DEF)); - for (int j = MI->getNumOperands() - 1, ee = 0; j > ee; --j) - MI->RemoveOperand(j); - if (isKill) { - ImpDefRegs.erase(Reg); - LiveVariables::VarInfo& vi = lv_->getVarInfo(Reg); - vi.removeKill(MI); - } - ChangedToImpDef = true; - Changed = true; - break; - } +void ProcessImplicitDefs::getAnalysisUsage(AnalysisUsage &AU) const { + AU.setPreservesCFG(); + AU.addPreserved(); + MachineFunctionPass::getAnalysisUsage(AU); +} - Changed = true; - MO.setIsUndef(); - // This is a partial register redef of an implicit def. - // Make sure the whole register is defined by the instruction. - if (MO.isDef()) { - MI->addRegisterDefined(Reg); - continue; - } - if (MO.isKill() || MI->isRegTiedToDefOperand(i)) { - // Make sure other uses of - for (unsigned j = i+1; j != e; ++j) { - MachineOperand &MOJ = MI->getOperand(j); - if (MOJ.isReg() && MOJ.isUse() && MOJ.getReg() == Reg) - MOJ.setIsUndef(); - } - ImpDefRegs.erase(Reg); - } - } +bool ProcessImplicitDefs::canTurnIntoImplicitDef(MachineInstr *MI) { + if (!MI->isCopyLike() && + !MI->isInsertSubreg() && + !MI->isRegSequence() && + !MI->isPHI()) + return false; + for (MIOperands MO(MI); MO.isValid(); ++MO) + if (MO->isReg() && MO->isUse() && MO->readsReg()) + return false; + return true; +} - if (ChangedToImpDef) { - // Backtrack to process this new implicit_def. - --I; - } else { - for (unsigned i = 0; i != MI->getNumOperands(); ++i) { - MachineOperand& MO = MI->getOperand(i); - if (!MO.isReg() || !MO.isDef()) - continue; - ImpDefRegs.erase(MO.getReg()); - } - } +void ProcessImplicitDefs::processImplicitDef(MachineInstr *MI) { + DEBUG(dbgs() << "Processing " << *MI); + unsigned Reg = MI->getOperand(0).getReg(); + + if (TargetRegisterInfo::isVirtualRegister(Reg)) { + // For virtual registers, mark all uses as , and convert users to + // implicit-def when possible. + for (MachineOperand &MO : MRI->use_nodbg_operands(Reg)) { + MO.setIsUndef(); + MachineInstr *UserMI = MO.getParent(); + if (!canTurnIntoImplicitDef(UserMI)) + continue; + DEBUG(dbgs() << "Converting to IMPLICIT_DEF: " << *UserMI); + UserMI->setDesc(TII->get(TargetOpcode::IMPLICIT_DEF)); + WorkList.insert(UserMI); } + MI->eraseFromParent(); + return; + } - // Any outstanding liveout implicit_def's? - for (unsigned i = 0, e = ImpDefMIs.size(); i != e; ++i) { - MachineInstr *MI = ImpDefMIs[i]; - unsigned Reg = MI->getOperand(0).getReg(); - if (TargetRegisterInfo::isPhysicalRegister(Reg) || - !ImpDefRegs.count(Reg)) { - // Delete all "local" implicit_def's. That include those which define - // physical registers since they cannot be liveout. - MI->eraseFromParent(); - Changed = true; + // This is a physreg implicit-def. + // Look for the first instruction to use or define an alias. + MachineBasicBlock::instr_iterator UserMI = MI; + MachineBasicBlock::instr_iterator UserE = MI->getParent()->instr_end(); + bool Found = false; + for (++UserMI; UserMI != UserE; ++UserMI) { + for (MIOperands MO(UserMI); MO.isValid(); ++MO) { + if (!MO->isReg()) continue; - } - - // If there are multiple defs of the same register and at least one - // is not an implicit_def, do not insert implicit_def's before the - // uses. - bool Skip = false; - SmallVector DeadImpDefs; - for (MachineRegisterInfo::def_iterator DI = mri_->def_begin(Reg), - DE = mri_->def_end(); DI != DE; ++DI) { - MachineInstr *DeadImpDef = &*DI; - if (!DeadImpDef->isImplicitDef()) { - Skip = true; - break; - } - DeadImpDefs.push_back(DeadImpDef); - } - if (Skip) + unsigned UserReg = MO->getReg(); + if (!TargetRegisterInfo::isPhysicalRegister(UserReg) || + !TRI->regsOverlap(Reg, UserReg)) continue; + // UserMI uses or redefines Reg. Set flags on all uses. + Found = true; + if (MO->isUse()) + MO->setIsUndef(); + } + if (Found) + break; + } - // The only implicit_def which we want to keep are those that are live - // out of its block. - for (unsigned j = 0, ee = DeadImpDefs.size(); j != ee; ++j) - DeadImpDefs[j]->eraseFromParent(); - Changed = true; - - // Process each use instruction once. - for (MachineRegisterInfo::use_iterator UI = mri_->use_begin(Reg), - UE = mri_->use_end(); UI != UE; ++UI) { - if (UI.getOperand().isUndef()) - continue; - MachineInstr *RMI = &*UI; - if (ModInsts.insert(RMI)) - RUses.push_back(RMI); - } + // If we found the using MI, we can erase the IMPLICIT_DEF. + if (Found) { + DEBUG(dbgs() << "Physreg user: " << *UserMI); + MI->eraseFromParent(); + return; + } - for (unsigned i = 0, e = RUses.size(); i != e; ++i) { - MachineInstr *RMI = RUses[i]; + // Using instr wasn't found, it could be in another block. + // Leave the physreg IMPLICIT_DEF, but trim any extra operands. + for (unsigned i = MI->getNumOperands() - 1; i; --i) + MI->RemoveOperand(i); + DEBUG(dbgs() << "Keeping physreg: " << *MI); +} - // Turn a copy use into an implicit_def. - if (isUndefCopy(RMI, Reg, tii_, ImpDefRegs)) { - RMI->setDesc(tii_->get(TargetOpcode::IMPLICIT_DEF)); +/// processImplicitDefs - Process IMPLICIT_DEF instructions and turn them into +/// operands. +bool ProcessImplicitDefs::runOnMachineFunction(MachineFunction &MF) { - bool isKill = false; - SmallVector Ops; - for (unsigned j = 0, ee = RMI->getNumOperands(); j != ee; ++j) { - MachineOperand &RRMO = RMI->getOperand(j); - if (RRMO.isReg() && RRMO.getReg() == Reg) { - Ops.push_back(j); - if (RRMO.isKill()) - isKill = true; - } - } - // Leave the other operands along. - for (unsigned j = 0, ee = Ops.size(); j != ee; ++j) { - unsigned OpIdx = Ops[j]; - RMI->RemoveOperand(OpIdx-j); - } + DEBUG(dbgs() << "********** PROCESS IMPLICIT DEFS **********\n" + << "********** Function: " << MF.getName() << '\n'); - // Update LiveVariables varinfo if the instruction is a kill. - if (isKill) { - LiveVariables::VarInfo& vi = lv_->getVarInfo(Reg); - vi.removeKill(RMI); - } - continue; - } + bool Changed = false; - // Replace Reg with a new vreg that's marked implicit. - const TargetRegisterClass* RC = mri_->getRegClass(Reg); - unsigned NewVReg = mri_->createVirtualRegister(RC); - bool isKill = true; - for (unsigned j = 0, ee = RMI->getNumOperands(); j != ee; ++j) { - MachineOperand &RRMO = RMI->getOperand(j); - if (RRMO.isReg() && RRMO.getReg() == Reg) { - RRMO.setReg(NewVReg); - RRMO.setIsUndef(); - if (isKill) { - // Only the first operand of NewVReg is marked kill. - RRMO.setIsKill(); - isKill = false; - } - } - } - } - RUses.clear(); - ModInsts.clear(); - } - ImpDefRegs.clear(); - ImpDefMIs.clear(); + TII = MF.getSubtarget().getInstrInfo(); + TRI = MF.getSubtarget().getRegisterInfo(); + MRI = &MF.getRegInfo(); + assert(MRI->isSSA() && "ProcessImplicitDefs only works on SSA form."); + assert(WorkList.empty() && "Inconsistent worklist state"); + + for (MachineFunction::iterator MFI = MF.begin(), MFE = MF.end(); + MFI != MFE; ++MFI) { + // Scan the basic block for implicit defs. + for (MachineBasicBlock::instr_iterator MBBI = MFI->instr_begin(), + MBBE = MFI->instr_end(); MBBI != MBBE; ++MBBI) + if (MBBI->isImplicitDef()) + WorkList.insert(MBBI); + + if (WorkList.empty()) + continue; + + DEBUG(dbgs() << "BB#" << MFI->getNumber() << " has " << WorkList.size() + << " implicit defs.\n"); + Changed = true; + + // Drain the WorkList to recursively process any new implicit defs. + do processImplicitDef(WorkList.pop_back_val()); + while (!WorkList.empty()); } - return Changed; } -