Line data    Source code

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