lib/CodeGen/ProcessImplicitDefs.cpp

   1 //===---------------------- ProcessImplicitDefs.cpp -----------------------===//
   2 //
   3 //                     The LLVM Compiler Infrastructure
   4 //
   5 // This file is distributed under the University of Illinois Open Source
   6 // License. See LICENSE.TXT for details.
   7 //
   8 //===----------------------------------------------------------------------===//
   9
  10 #define DEBUG_TYPE "processimplicitdefs"
  11
  12 #include "llvm/ADT/SetVector.h"
  13 #include "llvm/Analysis/AliasAnalysis.h"
  14 #include "llvm/CodeGen/MachineFunctionPass.h"
  15 #include "llvm/CodeGen/MachineInstr.h"
  16 #include "llvm/CodeGen/MachineRegisterInfo.h"
  17 #include "llvm/CodeGen/Passes.h"
  18 #include "llvm/Support/Debug.h"
  19 #include "llvm/Support/raw_ostream.h"
  20 #include "llvm/Target/TargetInstrInfo.h"
  21
  22 using namespace llvm;
  23
  24 namespace {
  25 /// Process IMPLICIT_DEF instructions and make sure there is one implicit_def
  26 /// for each use. Add isUndef marker to implicit_def defs and their uses.
  27 class ProcessImplicitDefs : public MachineFunctionPass {
  28   const TargetInstrInfo *TII;
  29   const TargetRegisterInfo *TRI;
  30   MachineRegisterInfo *MRI;
  31
  32   SmallSetVector<MachineInstr*, 16> WorkList;
  33
  34   void processImplicitDef(MachineInstr *MI);
  35   bool canTurnIntoImplicitDef(MachineInstr *MI);
  36
  37 public:
  38   static char ID;
  39
  40   ProcessImplicitDefs() : MachineFunctionPass(ID) {
  41     initializeProcessImplicitDefsPass(*PassRegistry::getPassRegistry());
  42   }
  43
  44   virtual void getAnalysisUsage(AnalysisUsage &au) const;
  45
  46   virtual bool runOnMachineFunction(MachineFunction &fn);
  47 };
  48 } // end anonymous namespace
  49
  50 char ProcessImplicitDefs::ID = 0;
  51 char &llvm::ProcessImplicitDefsID = ProcessImplicitDefs::ID;
  52
  53 INITIALIZE_PASS_BEGIN(ProcessImplicitDefs, "processimpdefs",
  54                 "Process Implicit Definitions", false, false)
  55 INITIALIZE_PASS_END(ProcessImplicitDefs, "processimpdefs",
  56                 "Process Implicit Definitions", false, false)
  57
  58 void ProcessImplicitDefs::getAnalysisUsage(AnalysisUsage &AU) const {
  59   AU.setPreservesCFG();
  60   AU.addPreserved<AliasAnalysis>();
  61   MachineFunctionPass::getAnalysisUsage(AU);
  62 }
  63
  64 bool ProcessImplicitDefs::canTurnIntoImplicitDef(MachineInstr *MI) {
  65   if (!MI->isCopyLike() &&
  66       !MI->isInsertSubreg() &&
  67       !MI->isRegSequence() &&
  68       !MI->isPHI())
  69     return false;
  70   for (MIOperands MO(MI); MO.isValid(); ++MO)
  71     if (MO->isReg() && MO->isUse() && MO->readsReg())
  72       return false;
  73   return true;
  74 }
  75
  76 void ProcessImplicitDefs::processImplicitDef(MachineInstr *MI) {
  77   DEBUG(dbgs() << "Processing " << *MI);
  78   unsigned Reg = MI->getOperand(0).getReg();
  79
  80   if (TargetRegisterInfo::isVirtualRegister(Reg)) {
  81     // For virtual registers, mark all uses as <undef>, and convert users to
  82     // implicit-def when possible.
  83     for (MachineRegisterInfo::use_nodbg_iterator UI =
  84          MRI->use_nodbg_begin(Reg),
  85          UE = MRI->use_nodbg_end(); UI != UE; ++UI) {
  86       MachineOperand &MO = UI.getOperand();
  87       MO.setIsUndef();
  88       MachineInstr *UserMI = MO.getParent();
  89       if (!canTurnIntoImplicitDef(UserMI))
  90         continue;
  91       DEBUG(dbgs() << "Converting to IMPLICIT_DEF: " << *UserMI);
  92       UserMI->setDesc(TII->get(TargetOpcode::IMPLICIT_DEF));
  93       WorkList.insert(UserMI);
  94     }
  95     MI->eraseFromParent();
  96     return;
  97   }
  98
  99   // This is a physreg implicit-def.
 100   // Look for the first instruction to use or define an alias.
 101   MachineBasicBlock::instr_iterator UserMI = MI;
 102   MachineBasicBlock::instr_iterator UserE = MI->getParent()->instr_end();
 103   bool Found = false;
 104   for (++UserMI; UserMI != UserE; ++UserMI) {
 105     for (MIOperands MO(UserMI); MO.isValid(); ++MO) {
 106       if (!MO->isReg())
 107         continue;
 108       unsigned UserReg = MO->getReg();
 109       if (!TargetRegisterInfo::isPhysicalRegister(UserReg) ||
 110           !TRI->regsOverlap(Reg, UserReg))
 111         continue;
 112       // UserMI uses or redefines Reg. Set <undef> flags on all uses.
 113       Found = true;
 114       if (MO->isUse())
 115         MO->setIsUndef();
 116     }
 117     if (Found)
 118       break;
 119   }
 120
 121   // If we found the using MI, we can erase the IMPLICIT_DEF.
 122   if (Found) {
 123     DEBUG(dbgs() << "Physreg user: " << *UserMI);
 124     MI->eraseFromParent();
 125     return;
 126   }
 127
 128   // Using instr wasn't found, it could be in another block.
 129   // Leave the physreg IMPLICIT_DEF, but trim any extra operands.
 130   for (unsigned i = MI->getNumOperands() - 1; i; --i)
 131     MI->RemoveOperand(i);
 132   DEBUG(dbgs() << "Keeping physreg: " << *MI);
 133 }
 134
 135 /// processImplicitDefs - Process IMPLICIT_DEF instructions and turn them into
 136 /// <undef> operands.
 137 bool ProcessImplicitDefs::runOnMachineFunction(MachineFunction &MF) {
 138
 139   DEBUG(dbgs() << "********** PROCESS IMPLICIT DEFS **********\n"
 140                << "********** Function: " << MF.getName() << '\n');
 141
 142   bool Changed = false;
 143
 144   TII = MF.getTarget().getInstrInfo();
 145   TRI = MF.getTarget().getRegisterInfo();
 146   MRI = &MF.getRegInfo();
 147   assert(MRI->isSSA() && "ProcessImplicitDefs only works on SSA form.");
 148   assert(WorkList.empty() && "Inconsistent worklist state");
 149
 150   for (MachineFunction::iterator MFI = MF.begin(), MFE = MF.end();
 151        MFI != MFE; ++MFI) {
 152     // Scan the basic block for implicit defs.
 153     for (MachineBasicBlock::instr_iterator MBBI = MFI->instr_begin(),
 154          MBBE = MFI->instr_end(); MBBI != MBBE; ++MBBI)
 155       if (MBBI->isImplicitDef())
 156         WorkList.insert(MBBI);
 157
 158     if (WorkList.empty())
 159       continue;
 160
 161     DEBUG(dbgs() << "BB#" << MFI->getNumber() << " has " << WorkList.size()
 162                  << " implicit defs.\n");
 163     Changed = true;
 164
 165     // Drain the WorkList to recursively process any new implicit defs.
 166     do processImplicitDef(WorkList.pop_back_val());
 167     while (!WorkList.empty());
 168   }
 169   return Changed;
 170 }