LCOV - code coverage report
Current view: top level - lib/CodeGen - OptimizePHIs.cpp (source / functions) Hit Total Coverage
Test: llvm-toolchain.info Lines: 58 59 98.3 %
Date: 2018-07-13 00:08:38 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/CodeGen/TargetRegisterInfo.h"
      24             : #include "llvm/CodeGen/TargetSubtargetInfo.h"
      25             : #include "llvm/Pass.h"
      26             : #include <cassert>
      27             : 
      28             : using namespace llvm;
      29             : 
      30             : #define DEBUG_TYPE "opt-phis"
      31             : 
      32             : STATISTIC(NumPHICycles, "Number of PHI cycles replaced");
      33             : STATISTIC(NumDeadPHICycles, "Number of dead PHI cycles");
      34             : 
      35             : namespace {
      36             : 
      37       19151 :   class OptimizePHIs : public MachineFunctionPass {
      38             :     MachineRegisterInfo *MRI;
      39             :     const TargetInstrInfo *TII;
      40             : 
      41             :   public:
      42             :     static char ID; // Pass identification
      43             : 
      44       19255 :     OptimizePHIs() : MachineFunctionPass(ID) {
      45       19255 :       initializeOptimizePHIsPass(*PassRegistry::getPassRegistry());
      46       19255 :     }
      47             : 
      48             :     bool runOnMachineFunction(MachineFunction &MF) override;
      49             : 
      50       19111 :     void getAnalysisUsage(AnalysisUsage &AU) const override {
      51       19111 :       AU.setPreservesCFG();
      52       19111 :       MachineFunctionPass::getAnalysisUsage(AU);
      53       19111 :     }
      54             : 
      55             :   private:
      56             :     using InstrSet = SmallPtrSet<MachineInstr *, 16>;
      57             :     using InstrSetIterator = SmallPtrSetIterator<MachineInstr *>;
      58             : 
      59             :     bool IsSingleValuePHICycle(MachineInstr *MI, unsigned &SingleValReg,
      60             :                                InstrSet &PHIsInCycle);
      61             :     bool IsDeadPHICycle(MachineInstr *MI, InstrSet &PHIsInCycle);
      62             :     bool OptimizeBB(MachineBasicBlock &MBB);
      63             :   };
      64             : 
      65             : } // end anonymous namespace
      66             : 
      67             : char OptimizePHIs::ID = 0;
      68             : 
      69             : char &llvm::OptimizePHIsID = OptimizePHIs::ID;
      70             : 
      71      185120 : INITIALIZE_PASS(OptimizePHIs, DEBUG_TYPE,
      72             :                 "Optimize machine instruction PHIs", false, false)
      73             : 
      74      184096 : bool OptimizePHIs::runOnMachineFunction(MachineFunction &Fn) {
      75      184096 :   if (skipFunction(Fn.getFunction()))
      76             :     return false;
      77             : 
      78      183940 :   MRI = &Fn.getRegInfo();
      79      183940 :   TII = Fn.getSubtarget().getInstrInfo();
      80             : 
      81             :   // Find dead PHI cycles and PHI cycles that can be replaced by a single
      82             :   // value.  InstCombine does these optimizations, but DAG legalization may
      83             :   // introduce new opportunities, e.g., when i64 values are split up for
      84             :   // 32-bit targets.
      85             :   bool Changed = false;
      86      523418 :   for (MachineFunction::iterator I = Fn.begin(), E = Fn.end(); I != E; ++I)
      87      339478 :     Changed |= OptimizeBB(*I);
      88             : 
      89             :   return Changed;
      90             : }
      91             : 
      92             : /// IsSingleValuePHICycle - Check if MI is a PHI where all the source operands
      93             : /// are copies of SingleValReg, possibly via copies through other PHIs.  If
      94             : /// SingleValReg is zero on entry, it is set to the register with the single
      95             : /// non-copy value.  PHIsInCycle is a set used to keep track of the PHIs that
      96             : /// have been scanned.
      97       57518 : bool OptimizePHIs::IsSingleValuePHICycle(MachineInstr *MI,
      98             :                                          unsigned &SingleValReg,
      99             :                                          InstrSet &PHIsInCycle) {
     100             :   assert(MI->isPHI() && "IsSingleValuePHICycle expects a PHI instruction");
     101       57518 :   unsigned DstReg = MI->getOperand(0).getReg();
     102             : 
     103             :   // See if we already saw this register.
     104       57518 :   if (!PHIsInCycle.insert(MI).second)
     105             :     return true;
     106             : 
     107             :   // Don't scan crazily complex things.
     108      112426 :   if (PHIsInCycle.size() == 16)
     109             :     return false;
     110             : 
     111             :   // Scan the PHI operands.
     112      141833 :   for (unsigned i = 1; i != MI->getNumOperands(); i += 2) {
     113      196848 :     unsigned SrcReg = MI->getOperand(i).getReg();
     114       98424 :     if (SrcReg == DstReg)
     115          11 :       continue;
     116       98413 :     MachineInstr *SrcMI = MRI->getVRegDef(SrcReg);
     117             : 
     118             :     // Skip over register-to-register moves.
     119      139339 :     if (SrcMI && SrcMI->isCopy() &&
     120       81852 :         !SrcMI->getOperand(0).getSubReg() &&
     121      133905 :         !SrcMI->getOperand(1).getSubReg() &&
     122       35492 :         TargetRegisterInfo::isVirtualRegister(SrcMI->getOperand(1).getReg()))
     123       32118 :       SrcMI = MRI->getVRegDef(SrcMI->getOperand(1).getReg());
     124       98413 :     if (!SrcMI)
     125             :       return false;
     126             : 
     127             :     if (SrcMI->isPHI()) {
     128       16535 :       if (!IsSingleValuePHICycle(SrcMI, SingleValReg, PHIsInCycle))
     129             :         return false;
     130             :     } else {
     131             :       // Fail if there is more than one non-phi/non-move register.
     132       81878 :       if (SingleValReg != 0)
     133             :         return false;
     134       40976 :       SingleValReg = SrcReg;
     135             :     }
     136             :   }
     137             :   return true;
     138             : }
     139             : 
     140             : /// IsDeadPHICycle - Check if the register defined by a PHI is only used by
     141             : /// other PHIs in a cycle.
     142       83017 : bool OptimizePHIs::IsDeadPHICycle(MachineInstr *MI, InstrSet &PHIsInCycle) {
     143             :   assert(MI->isPHI() && "IsDeadPHICycle expects a PHI instruction");
     144       83017 :   unsigned DstReg = MI->getOperand(0).getReg();
     145             :   assert(TargetRegisterInfo::isVirtualRegister(DstReg) &&
     146             :          "PHI destination is not a virtual register");
     147             : 
     148             :   // See if we already saw this register.
     149       83017 :   if (!PHIsInCycle.insert(MI).second)
     150             :     return true;
     151             : 
     152             :   // Don't scan crazily complex things.
     153      164332 :   if (PHIsInCycle.size() == 16)
     154             :     return false;
     155             : 
     156      260392 :   for (MachineInstr &UseMI : MRI->use_nodbg_instructions(DstReg)) {
     157       42078 :     if (!UseMI.isPHI() || !IsDeadPHICycle(&UseMI, PHIsInCycle))
     158       72231 :       return false;
     159             :   }
     160             : 
     161        9901 :   return true;
     162             : }
     163             : 
     164             : /// OptimizeBB - Remove dead PHI cycles and PHI cycles that can be replaced by
     165             : /// a single value.
     166      339478 : bool OptimizePHIs::OptimizeBB(MachineBasicBlock &MBB) {
     167             :   bool Changed = false;
     168             :   for (MachineBasicBlock::iterator
     169      719939 :          MII = MBB.begin(), E = MBB.end(); MII != E; ) {
     170             :     MachineInstr *MI = &*MII++;
     171             :     if (!MI->isPHI())
     172             :       break;
     173             : 
     174             :     // Check for single-value PHI cycles.
     175       40983 :     unsigned SingleValReg = 0;
     176             :     InstrSet PHIsInCycle;
     177       41028 :     if (IsSingleValuePHICycle(MI, SingleValReg, PHIsInCycle) &&
     178          45 :         SingleValReg != 0) {
     179          44 :       unsigned OldReg = MI->getOperand(0).getReg();
     180          88 :       if (!MRI->constrainRegClass(SingleValReg, MRI->getRegClass(OldReg)))
     181           0 :         continue;
     182             : 
     183          44 :       MRI->replaceRegWith(OldReg, SingleValReg);
     184          44 :       MI->eraseFromParent();
     185             :       ++NumPHICycles;
     186             :       Changed = true;
     187          44 :       continue;
     188             :     }
     189             : 
     190             :     // Check for dead PHI cycles.
     191       40939 :     PHIsInCycle.clear();
     192       40939 :     if (IsDeadPHICycle(MI, PHIsInCycle)) {
     193        3754 :       for (InstrSetIterator PI = PHIsInCycle.begin(), PE = PHIsInCycle.end();
     194       13117 :            PI != PE; ++PI) {
     195             :         MachineInstr *PhiMI = *PI;
     196        9363 :         if (MII == PhiMI)
     197             :           ++MII;
     198        9363 :         PhiMI->eraseFromParent();
     199             :       }
     200             :       ++NumDeadPHICycles;
     201             :       Changed = true;
     202             :     }
     203             :   }
     204      339478 :   return Changed;
     205             : }

Generated by: LCOV version 1.13