Home | History | Annotate | Download | only in CodeGen 
      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 }
    169