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