X-Git-Url: http://plrg.eecs.uci.edu/git/?a=blobdiff_plain;f=lib%2FCodeGen%2FProcessImplicitDefs.cpp;h=d27ea2f51867a60353328703ee901bd47dd338df;hb=fdec461fa2fb048febec7b394c84b4e8b20f49cc;hp=455964b5c5ad4f6c2c302d132e685e678f3edf30;hpb=285a7d57dc3c1210eda135fc137928e727175200;p=oota-llvm.git diff --git a/lib/CodeGen/ProcessImplicitDefs.cpp b/lib/CodeGen/ProcessImplicitDefs.cpp index 455964b5c5a..d27ea2f5186 100644 --- a/lib/CodeGen/ProcessImplicitDefs.cpp +++ b/lib/CodeGen/ProcessImplicitDefs.cpp @@ -7,234 +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; +#define DEBUG_TYPE "processimplicitdefs" + +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; + + SmallSetVector WorkList; + + void processImplicitDef(MachineInstr *MI); + bool canTurnIntoImplicitDef(MachineInstr *MI); + +public: + static char ID; + + ProcessImplicitDefs() : MachineFunctionPass(ID) { + initializeProcessImplicitDefsPass(*PassRegistry::getPassRegistry()); + } + + void getAnalysisUsage(AnalysisUsage &au) const override; + + bool runOnMachineFunction(MachineFunction &fn) override; +}; +} // end anonymous namespace + char ProcessImplicitDefs::ID = 0; -static RegisterPass X("processimpdefs", - "Process Implicit Definitions."); +char &llvm::ProcessImplicitDefsID = ProcessImplicitDefs::ID; + +INITIALIZE_PASS_BEGIN(ProcessImplicitDefs, "processimpdefs", + "Process Implicit Definitions", false, false) +INITIALIZE_PASS_END(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); + AU.addPreserved(); MachineFunctionPass::getAnalysisUsage(AU); } -bool ProcessImplicitDefs::CanTurnIntoImplicitDef(MachineInstr *MI, - unsigned Reg, unsigned OpIdx, - const TargetInstrInfo *tii_) { - unsigned SrcReg, DstReg, SrcSubReg, DstSubReg; - if (tii_->isMoveInstr(*MI, SrcReg, DstReg, SrcSubReg, DstSubReg) && - Reg == SrcReg) - return true; - - if (OpIdx == 2 && MI->getOpcode() == TargetInstrInfo::SUBREG_TO_REG) - return true; - if (OpIdx == 1 && MI->getOpcode() == TargetInstrInfo::EXTRACT_SUBREG) - return true; - return false; +bool ProcessImplicitDefs::canTurnIntoImplicitDef(MachineInstr *MI) { + if (!MI->isCopyLike() && + !MI->isInsertSubreg() && + !MI->isRegSequence() && + !MI->isPHI()) + return false; + for (const MachineOperand &MO : MI->operands()) + if (MO.isReg() && MO.isUse() && MO.readsReg()) + return false; + return true; } -/// 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) { - - DEBUG(errs() << "********** PROCESS IMPLICIT DEFS **********\n" - << "********** Function: " - << ((Value*)fn.getFunction())->getName() << '\n'); - - bool Changed = false; - - const TargetInstrInfo *tii_ = fn.getTarget().getInstrInfo(); - const TargetRegisterInfo *tri_ = fn.getTarget().getRegisterInfo(); - MachineRegisterInfo *mri_ = &fn.getRegInfo(); - - LiveVariables *lv_ = &getAnalysis(); - - SmallSet ImpDefRegs; - SmallVector ImpDefMIs; - MachineBasicBlock *Entry = fn.begin(); - SmallPtrSet Visited; - SmallPtrSet ModInsts; - - 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->getOpcode() == TargetInstrInfo::IMPLICIT_DEF) { - 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); +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; - } - - if (MI->getOpcode() == TargetInstrInfo::INSERT_SUBREG) { - MachineOperand &MO = MI->getOperand(2); - if (ImpDefRegs.count(MO.getReg())) { - // %reg1032 = INSERT_SUBREG %reg1032, undef, 2 - // This is an identity copy, eliminate it now. - if (MO.isKill()) { - LiveVariables::VarInfo& vi = lv_->getVarInfo(MO.getReg()); - vi.removeKill(MI); - } - MI->eraseFromParent(); - Changed = true; - continue; - } - } - - bool ChangedToImpDef = false; - for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) { - MachineOperand& MO = MI->getOperand(i); - if (!MO.isReg() || !MO.isUse() || 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_)) { - bool isKill = MO.isKill(); - MI->setDesc(tii_->get(TargetInstrInfo::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; - } - - Changed = true; - MO.setIsUndef(); - 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); - } - } - - 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()); - } - } + 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->getIterator(); + MachineBasicBlock::instr_iterator UserE = MI->getParent()->instr_end(); + bool Found = false; + for (++UserMI; UserMI != UserE; ++UserMI) { + for (MachineOperand &MO : UserMI->operands()) { + 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; - for (MachineRegisterInfo::def_iterator DI = mri_->def_begin(Reg), - DE = mri_->def_end(); DI != DE; ++DI) { - if (DI->getOpcode() != TargetInstrInfo::IMPLICIT_DEF) { - Skip = true; - break; - } - } - if (Skip) + unsigned UserReg = MO.getReg(); + if (!TargetRegisterInfo::isPhysicalRegister(UserReg) || + !TRI->regsOverlap(Reg, UserReg)) continue; - - // The only implicit_def which we want to keep are those that are live - // out of its block. - MI->eraseFromParent(); - Changed = true; - - for (MachineRegisterInfo::use_iterator UI = mri_->use_begin(Reg), - UE = mri_->use_end(); UI != UE; ) { - MachineOperand &RMO = UI.getOperand(); - MachineInstr *RMI = &*UI; - ++UI; - if (ModInsts.count(RMI)) - continue; - MachineBasicBlock *RMBB = RMI->getParent(); - if (RMBB == MBB) - continue; - - // Turn a copy use into an implicit_def. - unsigned SrcReg, DstReg, SrcSubReg, DstSubReg; - if (tii_->isMoveInstr(*RMI, SrcReg, DstReg, SrcSubReg, DstSubReg) && - Reg == SrcReg) { - if (RMO.isKill()) { - LiveVariables::VarInfo& vi = lv_->getVarInfo(Reg); - vi.removeKill(RMI); - } - RMI->setDesc(tii_->get(TargetInstrInfo::IMPLICIT_DEF)); - for (int j = RMI->getNumOperands() - 1, ee = 0; j > ee; --j) - RMI->RemoveOperand(j); - ModInsts.insert(RMI); - continue; - } - - const TargetRegisterClass* RC = mri_->getRegClass(Reg); - unsigned NewVReg = mri_->createVirtualRegister(RC); - RMO.setReg(NewVReg); - RMO.setIsUndef(); - RMO.setIsKill(); - } + // UserMI uses or redefines Reg. Set flags on all uses. + Found = true; + if (MO.isUse()) + MO.setIsUndef(); } - ModInsts.clear(); - ImpDefRegs.clear(); - ImpDefMIs.clear(); + if (Found) + break; } - return Changed; + // If we found the using MI, we can erase the IMPLICIT_DEF. + if (Found) { + DEBUG(dbgs() << "Physreg user: " << *UserMI); + MI->eraseFromParent(); + return; + } + + // 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); } +/// processImplicitDefs - Process IMPLICIT_DEF instructions and turn them into +/// operands. +bool ProcessImplicitDefs::runOnMachineFunction(MachineFunction &MF) { + + DEBUG(dbgs() << "********** PROCESS IMPLICIT DEFS **********\n" + << "********** Function: " << MF.getName() << '\n'); + + bool Changed = false; + + 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; +}