//
//===----------------------------------------------------------------------===//
-#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;
-static RegisterPass<ProcessImplicitDefs> X("processimpdefs",
- "Process Implicit Definitions.");
-
-void ProcessImplicitDefs::getAnalysisUsage(AnalysisUsage &AU) const {
- AU.setPreservesCFG();
- AU.addPreserved<AliasAnalysis>();
- AU.addPreserved<LiveVariables>();
- AU.addRequired<LiveVariables>();
- 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_) {
- unsigned SrcReg, DstReg, SrcSubReg, DstSubReg;
- if (tii_->isMoveInstr(*MI, SrcReg, DstReg, SrcSubReg, DstSubReg) &&
- Reg == SrcReg && DstSubReg == 0)
- return true;
+#define DEBUG_TYPE "processimplicitdefs"
- switch(OpIdx) {
- case 1: return (MI->isExtractSubreg() || MI->isCopy()) &&
- MI->getOperand(0).getSubReg() == 0;
- case 2: return MI->isSubregToReg() && MI->getOperand(0).getSubReg() == 0;
- default: 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<MachineInstr*, 16> 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<LiveVariables>();
+ void getAnalysisUsage(AnalysisUsage &au) const override;
- SmallSet<unsigned, 8> ImpDefRegs;
- SmallVector<MachineInstr*, 8> ImpDefMIs;
- SmallVector<MachineInstr*, 4> RUses;
- SmallPtrSet<MachineBasicBlock*,16> Visited;
- SmallPtrSet<MachineInstr*, 8> ModInsts;
+ bool runOnMachineFunction(MachineFunction &fn) override;
+};
+} // end anonymous namespace
- MachineBasicBlock *Entry = fn.begin();
- for (df_ext_iterator<MachineBasicBlock*, SmallPtrSet<MachineBasicBlock*,16> >
- 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<def> = COPY undef.
- if (MI->isCopy() && MI->getOperand(0).getSubReg()) {
- MachineOperand &MO = MI->getOperand(1);
- if (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_)) {
- 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<AliasAnalysis>();
+ 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 <undef>, 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<MachineInstr*, 4> 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 <undef> 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.
- unsigned SrcReg, DstReg, SrcSubReg, DstSubReg;
- if ((RMI->isCopy() && RMI->getOperand(1).getReg() == Reg &&
- RMI->getOperand(0).getSubReg() == 0) ||
- (tii_->isMoveInstr(*RMI, SrcReg, DstReg, SrcSubReg, DstSubReg) &&
- Reg == SrcReg && DstSubReg == 0)) {
- RMI->setDesc(tii_->get(TargetOpcode::IMPLICIT_DEF));
+/// processImplicitDefs - Process IMPLICIT_DEF instructions and turn them into
+/// <undef> operands.
+bool ProcessImplicitDefs::runOnMachineFunction(MachineFunction &MF) {
- bool isKill = false;
- SmallVector<unsigned, 4> 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;
}
-
projects / oota-llvm.git / blobdiff