1198892Srdivacky//===---------------------- ProcessImplicitDefs.cpp -----------------------===// 2198892Srdivacky// 3198892Srdivacky// The LLVM Compiler Infrastructure 4198892Srdivacky// 5198892Srdivacky// This file is distributed under the University of Illinois Open Source 6198892Srdivacky// License. See LICENSE.TXT for details. 7198892Srdivacky// 8198892Srdivacky//===----------------------------------------------------------------------===// 9198892Srdivacky 10198892Srdivacky#define DEBUG_TYPE "processimplicitdefs" 11198892Srdivacky 12239462Sdim#include "llvm/ADT/SetVector.h" 13198892Srdivacky#include "llvm/Analysis/AliasAnalysis.h" 14239462Sdim#include "llvm/CodeGen/MachineFunctionPass.h" 15198892Srdivacky#include "llvm/CodeGen/MachineInstr.h" 16198892Srdivacky#include "llvm/CodeGen/MachineRegisterInfo.h" 17198892Srdivacky#include "llvm/CodeGen/Passes.h" 18198892Srdivacky#include "llvm/Support/Debug.h" 19239462Sdim#include "llvm/Support/raw_ostream.h" 20198892Srdivacky#include "llvm/Target/TargetInstrInfo.h" 21198892Srdivacky 22198892Srdivackyusing namespace llvm; 23198892Srdivacky 24239462Sdimnamespace { 25239462Sdim/// Process IMPLICIT_DEF instructions and make sure there is one implicit_def 26239462Sdim/// for each use. Add isUndef marker to implicit_def defs and their uses. 27239462Sdimclass ProcessImplicitDefs : public MachineFunctionPass { 28239462Sdim const TargetInstrInfo *TII; 29239462Sdim const TargetRegisterInfo *TRI; 30239462Sdim MachineRegisterInfo *MRI; 31239462Sdim 32239462Sdim SmallSetVector<MachineInstr*, 16> WorkList; 33239462Sdim 34239462Sdim void processImplicitDef(MachineInstr *MI); 35239462Sdim bool canTurnIntoImplicitDef(MachineInstr *MI); 36239462Sdim 37239462Sdimpublic: 38239462Sdim static char ID; 39239462Sdim 40239462Sdim ProcessImplicitDefs() : MachineFunctionPass(ID) { 41239462Sdim initializeProcessImplicitDefsPass(*PassRegistry::getPassRegistry()); 42239462Sdim } 43239462Sdim 44239462Sdim virtual void getAnalysisUsage(AnalysisUsage &au) const; 45239462Sdim 46239462Sdim virtual bool runOnMachineFunction(MachineFunction &fn); 47239462Sdim}; 48239462Sdim} // end anonymous namespace 49239462Sdim 50198892Srdivackychar ProcessImplicitDefs::ID = 0; 51234353Sdimchar &llvm::ProcessImplicitDefsID = ProcessImplicitDefs::ID; 52234353Sdim 53218893SdimINITIALIZE_PASS_BEGIN(ProcessImplicitDefs, "processimpdefs", 54218893Sdim "Process Implicit Definitions", false, false) 55218893SdimINITIALIZE_PASS_END(ProcessImplicitDefs, "processimpdefs", 56218893Sdim "Process Implicit Definitions", false, false) 57198892Srdivacky 58198892Srdivackyvoid ProcessImplicitDefs::getAnalysisUsage(AnalysisUsage &AU) const { 59198892Srdivacky AU.setPreservesCFG(); 60198892Srdivacky AU.addPreserved<AliasAnalysis>(); 61198892Srdivacky MachineFunctionPass::getAnalysisUsage(AU); 62198892Srdivacky} 63198892Srdivacky 64239462Sdimbool ProcessImplicitDefs::canTurnIntoImplicitDef(MachineInstr *MI) { 65239462Sdim if (!MI->isCopyLike() && 66239462Sdim !MI->isInsertSubreg() && 67239462Sdim !MI->isRegSequence() && 68239462Sdim !MI->isPHI()) 69239462Sdim return false; 70239462Sdim for (MIOperands MO(MI); MO.isValid(); ++MO) 71239462Sdim if (MO->isReg() && MO->isUse() && MO->readsReg()) 72210299Sed return false; 73239462Sdim return true; 74198892Srdivacky} 75198892Srdivacky 76239462Sdimvoid ProcessImplicitDefs::processImplicitDef(MachineInstr *MI) { 77239462Sdim DEBUG(dbgs() << "Processing " << *MI); 78239462Sdim unsigned Reg = MI->getOperand(0).getReg(); 79198892Srdivacky 80239462Sdim if (TargetRegisterInfo::isVirtualRegister(Reg)) { 81263508Sdim // For virtual registers, mark all uses as <undef>, and convert users to 82239462Sdim // implicit-def when possible. 83239462Sdim for (MachineRegisterInfo::use_nodbg_iterator UI = 84239462Sdim MRI->use_nodbg_begin(Reg), 85239462Sdim UE = MRI->use_nodbg_end(); UI != UE; ++UI) { 86239462Sdim MachineOperand &MO = UI.getOperand(); 87239462Sdim MO.setIsUndef(); 88239462Sdim MachineInstr *UserMI = MO.getParent(); 89239462Sdim if (!canTurnIntoImplicitDef(UserMI)) 90239462Sdim continue; 91239462Sdim DEBUG(dbgs() << "Converting to IMPLICIT_DEF: " << *UserMI); 92239462Sdim UserMI->setDesc(TII->get(TargetOpcode::IMPLICIT_DEF)); 93239462Sdim WorkList.insert(UserMI); 94239462Sdim } 95239462Sdim MI->eraseFromParent(); 96239462Sdim return; 97239462Sdim } 98198892Srdivacky 99239462Sdim // This is a physreg implicit-def. 100239462Sdim // Look for the first instruction to use or define an alias. 101239462Sdim MachineBasicBlock::instr_iterator UserMI = MI; 102239462Sdim MachineBasicBlock::instr_iterator UserE = MI->getParent()->instr_end(); 103239462Sdim bool Found = false; 104239462Sdim for (++UserMI; UserMI != UserE; ++UserMI) { 105239462Sdim for (MIOperands MO(UserMI); MO.isValid(); ++MO) { 106239462Sdim if (!MO->isReg()) 107198892Srdivacky continue; 108239462Sdim unsigned UserReg = MO->getReg(); 109239462Sdim if (!TargetRegisterInfo::isPhysicalRegister(UserReg) || 110239462Sdim !TRI->regsOverlap(Reg, UserReg)) 111239462Sdim continue; 112239462Sdim // UserMI uses or redefines Reg. Set <undef> flags on all uses. 113239462Sdim Found = true; 114239462Sdim if (MO->isUse()) 115239462Sdim MO->setIsUndef(); 116239462Sdim } 117239462Sdim if (Found) 118239462Sdim break; 119239462Sdim } 120198892Srdivacky 121239462Sdim // If we found the using MI, we can erase the IMPLICIT_DEF. 122239462Sdim if (Found) { 123239462Sdim DEBUG(dbgs() << "Physreg user: " << *UserMI); 124239462Sdim MI->eraseFromParent(); 125239462Sdim return; 126239462Sdim } 127226633Sdim 128239462Sdim // Using instr wasn't found, it could be in another block. 129239462Sdim // Leave the physreg IMPLICIT_DEF, but trim any extra operands. 130239462Sdim for (unsigned i = MI->getNumOperands() - 1; i; --i) 131239462Sdim MI->RemoveOperand(i); 132239462Sdim DEBUG(dbgs() << "Keeping physreg: " << *MI); 133239462Sdim} 134198892Srdivacky 135239462Sdim/// processImplicitDefs - Process IMPLICIT_DEF instructions and turn them into 136239462Sdim/// <undef> operands. 137239462Sdimbool ProcessImplicitDefs::runOnMachineFunction(MachineFunction &MF) { 138198892Srdivacky 139239462Sdim DEBUG(dbgs() << "********** PROCESS IMPLICIT DEFS **********\n" 140243830Sdim << "********** Function: " << MF.getName() << '\n'); 141198892Srdivacky 142239462Sdim bool Changed = false; 143198892Srdivacky 144239462Sdim TII = MF.getTarget().getInstrInfo(); 145239462Sdim TRI = MF.getTarget().getRegisterInfo(); 146239462Sdim MRI = &MF.getRegInfo(); 147239462Sdim assert(MRI->isSSA() && "ProcessImplicitDefs only works on SSA form."); 148239462Sdim assert(WorkList.empty() && "Inconsistent worklist state"); 149198892Srdivacky 150239462Sdim for (MachineFunction::iterator MFI = MF.begin(), MFE = MF.end(); 151239462Sdim MFI != MFE; ++MFI) { 152239462Sdim // Scan the basic block for implicit defs. 153239462Sdim for (MachineBasicBlock::instr_iterator MBBI = MFI->instr_begin(), 154239462Sdim MBBE = MFI->instr_end(); MBBI != MBBE; ++MBBI) 155239462Sdim if (MBBI->isImplicitDef()) 156239462Sdim WorkList.insert(MBBI); 157198892Srdivacky 158239462Sdim if (WorkList.empty()) 159239462Sdim continue; 160198892Srdivacky 161239462Sdim DEBUG(dbgs() << "BB#" << MFI->getNumber() << " has " << WorkList.size() 162239462Sdim << " implicit defs.\n"); 163239462Sdim Changed = true; 164198892Srdivacky 165239462Sdim // Drain the WorkList to recursively process any new implicit defs. 166239462Sdim do processImplicitDef(WorkList.pop_back_val()); 167239462Sdim while (!WorkList.empty()); 168198892Srdivacky } 169198892Srdivacky return Changed; 170198892Srdivacky} 171