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 #include "llvm/ADT/SetVector.h"
  11 #include "llvm/Analysis/AliasAnalysis.h"
  12 #include "llvm/CodeGen/MachineFunctionPass.h"
  13 #include "llvm/CodeGen/MachineInstr.h"
  14 #include "llvm/CodeGen/MachineRegisterInfo.h"
  15 #include "llvm/CodeGen/Passes.h"
  16 #include "llvm/Support/Debug.h"
  17 #include "llvm/Support/raw_ostream.h"
  18 #include "llvm/Target/TargetInstrInfo.h"
  19
  20 using namespace llvm;
  21
  22 #define DEBUG_TYPE "processimplicitdefs"
  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   void getAnalysisUsage(AnalysisUsage &au) const override;
  45
  46   bool runOnMachineFunction(MachineFunction &fn) override;
  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 (MachineOperand &MO : MRI->use_nodbg_operands(Reg)) {
  84       MO.setIsUndef();
  85       MachineInstr *UserMI = MO.getParent();
  86       if (!canTurnIntoImplicitDef(UserMI))
  87         continue;
  88       DEBUG(dbgs() << "Converting to IMPLICIT_DEF: " << *UserMI);
  89       UserMI->setDesc(TII->get(TargetOpcode::IMPLICIT_DEF));
  90       WorkList.insert(UserMI);
  91     }
  92     MI->eraseFromParent();
  93     return;
  94   }
  95
  96   // This is a physreg implicit-def.
  97   // Look for the first instruction to use or define an alias.
  98   MachineBasicBlock::instr_iterator UserMI = MI;
  99   MachineBasicBlock::instr_iterator UserE = MI->getParent()->instr_end();
 100   bool Found = false;
 101   for (++UserMI; UserMI != UserE; ++UserMI) {
 102     for (MIOperands MO(UserMI); MO.isValid(); ++MO) {
 103       if (!MO->isReg())
 104         continue;
 105       unsigned UserReg = MO->getReg();
 106       if (!TargetRegisterInfo::isPhysicalRegister(UserReg) ||
 107           !TRI->regsOverlap(Reg, UserReg))
 108         continue;
 109       // UserMI uses or redefines Reg. Set <undef> flags on all uses.
 110       Found = true;
 111       if (MO->isUse())
 112         MO->setIsUndef();
 113     }
 114     if (Found)
 115       break;
 116   }
 117
 118   // If we found the using MI, we can erase the IMPLICIT_DEF.
 119   if (Found) {
 120     DEBUG(dbgs() << "Physreg user: " << *UserMI);
 121     MI->eraseFromParent();
 122     return;
 123   }
 124
 125   // Using instr wasn't found, it could be in another block.
 126   // Leave the physreg IMPLICIT_DEF, but trim any extra operands.
 127   for (unsigned i = MI->getNumOperands() - 1; i; --i)
 128     MI->RemoveOperand(i);
 129   DEBUG(dbgs() << "Keeping physreg: " << *MI);
 130 }
 131
 132 /// processImplicitDefs - Process IMPLICIT_DEF instructions and turn them into
 133 /// <undef> operands.
 134 bool ProcessImplicitDefs::runOnMachineFunction(MachineFunction &MF) {
 135
 136   DEBUG(dbgs() << "********** PROCESS IMPLICIT DEFS **********\n"
 137                << "********** Function: " << MF.getName() << '\n');
 138
 139   bool Changed = false;
 140
 141   TII = MF.getTarget().getInstrInfo();
 142   TRI = MF.getTarget().getRegisterInfo();
 143   MRI = &MF.getRegInfo();
 144   assert(MRI->isSSA() && "ProcessImplicitDefs only works on SSA form.");
 145   assert(WorkList.empty() && "Inconsistent worklist state");
 146
 147   for (MachineFunction::iterator MFI = MF.begin(), MFE = MF.end();
 148        MFI != MFE; ++MFI) {
 149     // Scan the basic block for implicit defs.
 150     for (MachineBasicBlock::instr_iterator MBBI = MFI->instr_begin(),
 151          MBBE = MFI->instr_end(); MBBI != MBBE; ++MBBI)
 152       if (MBBI->isImplicitDef())
 153         WorkList.insert(MBBI);
 154
 155     if (WorkList.empty())
 156       continue;
 157
 158     DEBUG(dbgs() << "BB#" << MFI->getNumber() << " has " << WorkList.size()
 159                  << " implicit defs.\n");
 160     Changed = true;
 161
 162     // Drain the WorkList to recursively process any new implicit defs.
 163     do processImplicitDef(WorkList.pop_back_val());
 164     while (!WorkList.empty());
 165   }
 166   return Changed;
 167 }