LCOV - code coverage report
Current view: top level - lib/CodeGen - OptimizePHIs.cpp (source / functions) Hit Total Coverage
Test: llvm-toolchain.info Lines: 68 68 100.0 %
Date: 2017-09-14 15:23:50 Functions: 9 10 90.0 %
Legend: Lines: hit not hit

          Line data    Source code
       1             : //===- OptimizePHIs.cpp - Optimize machine instruction PHIs ---------------===//
       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             : // This pass optimizes machine instruction PHIs to take advantage of
      11             : // opportunities created during DAG legalization.
      12             : //
      13             : //===----------------------------------------------------------------------===//
      14             : 
      15             : #include "llvm/ADT/SmallPtrSet.h"
      16             : #include "llvm/ADT/Statistic.h"
      17             : #include "llvm/CodeGen/MachineBasicBlock.h"
      18             : #include "llvm/CodeGen/MachineFunction.h"
      19             : #include "llvm/CodeGen/MachineFunctionPass.h"
      20             : #include "llvm/CodeGen/MachineInstr.h"
      21             : #include "llvm/CodeGen/MachineOperand.h"
      22             : #include "llvm/CodeGen/MachineRegisterInfo.h"
      23             : #include "llvm/Pass.h"
      24             : #include "llvm/Target/TargetInstrInfo.h"
      25             : #include "llvm/Target/TargetRegisterInfo.h"
      26             : #include "llvm/Target/TargetSubtargetInfo.h"
      27             : #include <cassert>
      28             : 
      29             : using namespace llvm;
      30             : 
      31             : #define DEBUG_TYPE "opt-phis"
      32             : 
      33             : STATISTIC(NumPHICycles, "Number of PHI cycles replaced");
      34             : STATISTIC(NumDeadPHICycles, "Number of dead PHI cycles");
      35             : 
      36             : namespace {
      37             : 
      38       15514 :   class OptimizePHIs : public MachineFunctionPass {
      39             :     MachineRegisterInfo *MRI;
      40             :     const TargetInstrInfo *TII;
      41             : 
      42             :   public:
      43             :     static char ID; // Pass identification
      44             : 
      45       15613 :     OptimizePHIs() : MachineFunctionPass(ID) {
      46       15613 :       initializeOptimizePHIsPass(*PassRegistry::getPassRegistry());
      47       15613 :     }
      48             : 
      49             :     bool runOnMachineFunction(MachineFunction &MF) override;
      50             : 
      51       15567 :     void getAnalysisUsage(AnalysisUsage &AU) const override {
      52       15567 :       AU.setPreservesCFG();
      53       15567 :       MachineFunctionPass::getAnalysisUsage(AU);
      54       15567 :     }
      55             : 
      56             :   private:
      57             :     using InstrSet = SmallPtrSet<MachineInstr *, 16>;
      58             :     using InstrSetIterator = SmallPtrSetIterator<MachineInstr *>;
      59             : 
      60             :     bool IsSingleValuePHICycle(MachineInstr *MI, unsigned &SingleValReg,
      61             :                                InstrSet &PHIsInCycle);
      62             :     bool IsDeadPHICycle(MachineInstr *MI, InstrSet &PHIsInCycle);
      63             :     bool OptimizeBB(MachineBasicBlock &MBB);
      64             :   };
      65             : 
      66             : } // end anonymous namespace
      67             : 
      68             : char OptimizePHIs::ID = 0;
      69             : 
      70             : char &llvm::OptimizePHIsID = OptimizePHIs::ID;
      71             : 
      72      198038 : INITIALIZE_PASS(OptimizePHIs, DEBUG_TYPE,
      73             :                 "Optimize machine instruction PHIs", false, false)
      74             : 
      75      135760 : bool OptimizePHIs::runOnMachineFunction(MachineFunction &Fn) {
      76      135760 :   if (skipFunction(*Fn.getFunction()))
      77             :     return false;
      78             : 
      79      135703 :   MRI = &Fn.getRegInfo();
      80      135703 :   TII = Fn.getSubtarget().getInstrInfo();
      81             : 
      82             :   // Find dead PHI cycles and PHI cycles that can be replaced by a single
      83             :   // value.  InstCombine does these optimizations, but DAG legalization may
      84             :   // introduce new opportunities, e.g., when i64 values are split up for
      85             :   // 32-bit targets.
      86      135703 :   bool Changed = false;
      87      271406 :   for (MachineFunction::iterator I = Fn.begin(), E = Fn.end(); I != E; ++I)
      88      279025 :     Changed |= OptimizeBB(*I);
      89             : 
      90             :   return Changed;
      91             : }
      92             : 
      93             : /// IsSingleValuePHICycle - Check if MI is a PHI where all the source operands
      94             : /// are copies of SingleValReg, possibly via copies through other PHIs.  If
      95             : /// SingleValReg is zero on entry, it is set to the register with the single
      96             : /// non-copy value.  PHIsInCycle is a set used to keep track of the PHIs that
      97             : /// have been scanned.
      98       53274 : bool OptimizePHIs::IsSingleValuePHICycle(MachineInstr *MI,
      99             :                                          unsigned &SingleValReg,
     100             :                                          InstrSet &PHIsInCycle) {
     101             :   assert(MI->isPHI() && "IsSingleValuePHICycle expects a PHI instruction");
     102       53274 :   unsigned DstReg = MI->getOperand(0).getReg();
     103             : 
     104             :   // See if we already saw this register.
     105       53274 :   if (!PHIsInCycle.insert(MI).second)
     106             :     return true;
     107             : 
     108             :   // Don't scan crazily complex things.
     109      104488 :   if (PHIsInCycle.size() == 16)
     110             :     return false;
     111             : 
     112             :   // Scan the PHI operands.
     113      129924 :   for (unsigned i = 1; i != MI->getNumOperands(); i += 2) {
     114      181178 :     unsigned SrcReg = MI->getOperand(i).getReg();
     115       90589 :     if (SrcReg == DstReg)
     116          11 :       continue;
     117       90578 :     MachineInstr *SrcMI = MRI->getVRegDef(SrcReg);
     118             : 
     119             :     // Skip over register-to-register moves.
     120      130083 :     if (SrcMI && SrcMI->isCopy() &&
     121      118515 :         !SrcMI->getOperand(0).getSubReg() &&
     122      203801 :         !SrcMI->getOperand(1).getSubReg() &&
     123       68426 :         TargetRegisterInfo::isVirtualRegister(SrcMI->getOperand(1).getReg()))
     124       31152 :       SrcMI = MRI->getVRegDef(SrcMI->getOperand(1).getReg());
     125       90578 :     if (!SrcMI)
     126             :       return false;
     127             : 
     128       74680 :     if (SrcMI->isPHI()) {
     129       15898 :       if (!IsSingleValuePHICycle(SrcMI, SingleValReg, PHIsInCycle))
     130             :         return false;
     131             :     } else {
     132             :       // Fail if there is more than one non-phi/non-move register.
     133       74680 :       if (SingleValReg != 0)
     134             :         return false;
     135       37370 :       SingleValReg = SrcReg;
     136             :     }
     137             :   }
     138             :   return true;
     139             : }
     140             : 
     141             : /// IsDeadPHICycle - Check if the register defined by a PHI is only used by
     142             : /// other PHIs in a cycle.
     143       81424 : bool OptimizePHIs::IsDeadPHICycle(MachineInstr *MI, InstrSet &PHIsInCycle) {
     144             :   assert(MI->isPHI() && "IsDeadPHICycle expects a PHI instruction");
     145       81424 :   unsigned DstReg = MI->getOperand(0).getReg();
     146             :   assert(TargetRegisterInfo::isVirtualRegister(DstReg) &&
     147             :          "PHI destination is not a virtual register");
     148             : 
     149             :   // See if we already saw this register.
     150       81424 :   if (!PHIsInCycle.insert(MI).second)
     151             :     return true;
     152             : 
     153             :   // Don't scan crazily complex things.
     154      161282 :   if (PHIsInCycle.size() == 16)
     155             :     return false;
     156             : 
     157      326652 :   for (MachineInstr &UseMI : MRI->use_instructions(DstReg)) {
     158       44078 :     if (!UseMI.isPHI() || !IsDeadPHICycle(&UseMI, PHIsInCycle))
     159             :       return false;
     160             :   }
     161             : 
     162             :   return true;
     163             : }
     164             : 
     165             : /// OptimizeBB - Remove dead PHI cycles and PHI cycles that can be replaced by
     166             : /// a single value.
     167      279025 : bool OptimizePHIs::OptimizeBB(MachineBasicBlock &MBB) {
     168      279025 :   bool Changed = false;
     169             :   for (MachineBasicBlock::iterator
     170      874451 :          MII = MBB.begin(), E = MBB.end(); MII != E; ) {
     171      937824 :     MachineInstr *MI = &*MII++;
     172      275232 :     if (!MI->isPHI())
     173             :       break;
     174             : 
     175             :     // Check for single-value PHI cycles.
     176       37376 :     unsigned SingleValReg = 0;
     177       74722 :     InstrSet PHIsInCycle;
     178       37406 :     if (IsSingleValuePHICycle(MI, SingleValReg, PHIsInCycle) &&
     179          30 :         SingleValReg != 0) {
     180          30 :       unsigned OldReg = MI->getOperand(0).getReg();
     181          60 :       if (!MRI->constrainRegClass(SingleValReg, MRI->getRegClass(OldReg)))
     182          30 :         continue;
     183             : 
     184          30 :       MRI->replaceRegWith(OldReg, SingleValReg);
     185          30 :       MI->eraseFromParent();
     186          30 :       ++NumPHICycles;
     187          30 :       Changed = true;
     188          30 :       continue;
     189             :     }
     190             : 
     191             :     // Check for dead PHI cycles.
     192       37346 :     PHIsInCycle.clear();
     193       37346 :     if (IsDeadPHICycle(MI, PHIsInCycle)) {
     194        3709 :       for (InstrSetIterator PI = PHIsInCycle.begin(), PE = PHIsInCycle.end();
     195       13247 :            PI != PE; ++PI) {
     196       19076 :         MachineInstr *PhiMI = *PI;
     197        9538 :         if (MII == PhiMI)
     198             :           ++MII;
     199        9538 :         PhiMI->eraseFromParent();
     200             :       }
     201        3709 :       ++NumDeadPHICycles;
     202        3709 :       Changed = true;
     203             :     }
     204             :   }
     205      279025 :   return Changed;
     206             : }

Generated by: LCOV version 1.13