LCOV - code coverage report
Current view: top level - lib/CodeGen - BreakFalseDeps.cpp (source / functions) Hit Total Coverage
Test: llvm-toolchain.info Lines: 82 84 97.6 %
Date: 2018-10-20 13:21:21 Functions: 12 12 100.0 %
Legend: Lines: hit not hit

          Line data    Source code
       1             : //==- llvm/CodeGen/BreakFalseDeps.cpp - Break False Dependency Fix -*- C++ -*==//
       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             : /// \file Break False Dependency pass.
      11             : ///
      12             : /// Some instructions have false dependencies which cause unnecessary stalls.
      13             : /// For exmaple, instructions that only write part of a register, and implicitly
      14             : /// need to read the other parts of the register.  This may cause unwanted
      15             : /// stalls preventing otherwise unrelated instructions from executing in
      16             : /// parallel in an out-of-order CPU.
      17             : /// This pass is aimed at identifying and avoiding these depepndencies when
      18             : /// possible.
      19             : //
      20             : //===----------------------------------------------------------------------===//
      21             : 
      22             : #include "llvm/CodeGen/LivePhysRegs.h"
      23             : #include "llvm/CodeGen/MachineFunctionPass.h"
      24             : #include "llvm/CodeGen/ReachingDefAnalysis.h"
      25             : #include "llvm/CodeGen/RegisterClassInfo.h"
      26             : #include "llvm/CodeGen/MachineRegisterInfo.h"
      27             : #include "llvm/CodeGen/TargetInstrInfo.h"
      28             : 
      29             : 
      30             : using namespace llvm;
      31             : 
      32             : namespace llvm {
      33             : 
      34             : class BreakFalseDeps : public MachineFunctionPass {
      35             : private:
      36             :   MachineFunction *MF;
      37             :   const TargetInstrInfo *TII;
      38             :   const TargetRegisterInfo *TRI;
      39             :   RegisterClassInfo RegClassInfo;
      40             : 
      41             :   /// List of undefined register reads in this block in forward order.
      42             :   std::vector<std::pair<MachineInstr *, unsigned>> UndefReads;
      43             : 
      44             :   /// Storage for register unit liveness.
      45             :   LivePhysRegs LiveRegSet;
      46             : 
      47             :   ReachingDefAnalysis *RDA;
      48             : 
      49             : public:
      50             :   static char ID; // Pass identification, replacement for typeid
      51             : 
      52       10958 :   BreakFalseDeps() : MachineFunctionPass(ID) {
      53       10958 :     initializeBreakFalseDepsPass(*PassRegistry::getPassRegistry());
      54       10958 :   }
      55             : 
      56       10905 :   void getAnalysisUsage(AnalysisUsage &AU) const override {
      57             :     AU.setPreservesAll();
      58             :     AU.addRequired<ReachingDefAnalysis>();
      59       10905 :     MachineFunctionPass::getAnalysisUsage(AU);
      60       10905 :   }
      61             : 
      62             :   bool runOnMachineFunction(MachineFunction &MF) override;
      63             : 
      64       10908 :   MachineFunctionProperties getRequiredProperties() const override {
      65       10908 :     return MachineFunctionProperties().set(
      66       10908 :       MachineFunctionProperties::Property::NoVRegs);
      67             :   }
      68             : 
      69             : private:
      70             :   /// Process he given basic block.
      71             :   void processBasicBlock(MachineBasicBlock *MBB);
      72             : 
      73             :   /// Update def-ages for registers defined by MI.
      74             :   /// Also break dependencies on partial defs and undef uses.
      75             :   void processDefs(MachineInstr *MI);
      76             : 
      77             :   /// Helps avoid false dependencies on undef registers by updating the
      78             :   /// machine instructions' undef operand to use a register that the instruction
      79             :   /// is truly dependent on, or use a register with clearance higher than Pref.
      80             :   /// Returns true if it was able to find a true dependency, thus not requiring
      81             :   /// a dependency breaking instruction regardless of clearance.
      82             :   bool pickBestRegisterForUndef(MachineInstr *MI, unsigned OpIdx,
      83             :     unsigned Pref);
      84             : 
      85             :   /// Return true to if it makes sense to break dependence on a partial
      86             :   /// def or undef use.
      87             :   bool shouldBreakDependence(MachineInstr *, unsigned OpIdx, unsigned Pref);
      88             : 
      89             :   /// Break false dependencies on undefined register reads.
      90             :   /// Walk the block backward computing precise liveness. This is expensive, so
      91             :   /// we only do it on demand. Note that the occurrence of undefined register
      92             :   /// reads that should be broken is very rare, but when they occur we may have
      93             :   /// many in a single block.
      94             :   void processUndefReads(MachineBasicBlock *);
      95             : };
      96             : 
      97             : } // namespace llvm
      98             : 
      99             : #define DEBUG_TYPE "break-false-deps"
     100             : 
     101             : char BreakFalseDeps::ID = 0;
     102       10680 : INITIALIZE_PASS_BEGIN(BreakFalseDeps, DEBUG_TYPE, "BreakFalseDeps", false, false)
     103       10680 : INITIALIZE_PASS_DEPENDENCY(ReachingDefAnalysis)
     104       21638 : INITIALIZE_PASS_END(BreakFalseDeps, DEBUG_TYPE, "BreakFalseDeps", false, false)
     105             : 
     106       10958 : FunctionPass *llvm::createBreakFalseDeps() { return new BreakFalseDeps(); }
     107             : 
     108        1761 : bool BreakFalseDeps::pickBestRegisterForUndef(MachineInstr *MI, unsigned OpIdx,
     109             :   unsigned Pref) {
     110        1761 :   MachineOperand &MO = MI->getOperand(OpIdx);
     111             :   assert(MO.isUndef() && "Expected undef machine operand");
     112             : 
     113        1761 :   unsigned OriginalReg = MO.getReg();
     114             : 
     115             :   // Update only undef operands that have reg units that are mapped to one root.
     116        5283 :   for (MCRegUnitIterator Unit(OriginalReg, TRI); Unit.isValid(); ++Unit) {
     117             :     unsigned NumRoots = 0;
     118        3522 :     for (MCRegUnitRootIterator Root(*Unit, TRI); Root.isValid(); ++Root) {
     119        1761 :       NumRoots++;
     120        1761 :       if (NumRoots > 1)
     121             :         return false;
     122             :     }
     123             :   }
     124             : 
     125             :   // Get the undef operand's register class
     126             :   const TargetRegisterClass *OpRC =
     127        1761 :     TII->getRegClass(MI->getDesc(), OpIdx, TRI, *MF);
     128             : 
     129             :   // If the instruction has a true dependency, we can hide the false depdency
     130             :   // behind it.
     131        7280 :   for (MachineOperand &CurrMO : MI->operands()) {
     132        8091 :     if (!CurrMO.isReg() || CurrMO.isDef() || CurrMO.isUndef() ||
     133        2095 :       !OpRC->contains(CurrMO.getReg()))
     134             :       continue;
     135             :     // We found a true dependency - replace the undef register with the true
     136             :     // dependency.
     137         477 :     MO.setReg(CurrMO.getReg());
     138         477 :     return true;
     139             :   }
     140             : 
     141             :   // Go over all registers in the register class and find the register with
     142             :   // max clearance or clearance higher than Pref.
     143             :   unsigned MaxClearance = 0;
     144             :   unsigned MaxClearanceReg = OriginalReg;
     145        1284 :   ArrayRef<MCPhysReg> Order = RegClassInfo.getOrder(OpRC);
     146        5002 :   for (MCPhysReg Reg : Order) {
     147        4988 :     unsigned Clearance = RDA->getClearance(MI, Reg);
     148        4988 :     if (Clearance <= MaxClearance)
     149             :       continue;
     150             :     MaxClearance = Clearance;
     151        2588 :     MaxClearanceReg = Reg;
     152             : 
     153        2588 :     if (MaxClearance > Pref)
     154             :       break;
     155             :   }
     156             : 
     157             :   // Update the operand if we found a register with better clearance.
     158        1284 :   if (MaxClearanceReg != OriginalReg)
     159        1034 :     MO.setReg(MaxClearanceReg);
     160             : 
     161             :   return false;
     162             : }
     163             : 
     164        2036 : bool BreakFalseDeps::shouldBreakDependence(MachineInstr *MI, unsigned OpIdx,
     165             :                                            unsigned Pref) {
     166        2036 :   unsigned reg = MI->getOperand(OpIdx).getReg();
     167        2036 :   unsigned Clearance = RDA->getClearance(MI, reg);
     168             :   LLVM_DEBUG(dbgs() << "Clearance: " << Clearance << ", want " << Pref);
     169             : 
     170        2036 :   if (Pref > Clearance) {
     171             :     LLVM_DEBUG(dbgs() << ": Break dependency.\n");
     172         274 :     return true;
     173             :   }
     174             :   LLVM_DEBUG(dbgs() << ": OK .\n");
     175             :   return false;
     176             : }
     177             : 
     178     2513499 : void BreakFalseDeps::processDefs(MachineInstr *MI) {
     179             :   assert(!MI->isDebugInstr() && "Won't process debug values");
     180             : 
     181             :   // Break dependence on undef uses. Do this before updating LiveRegs below.
     182             :   unsigned OpNum;
     183     2513499 :   unsigned Pref = TII->getUndefRegClearance(*MI, OpNum, TRI);
     184     2513500 :   if (Pref) {
     185        1761 :     bool HadTrueDependency = pickBestRegisterForUndef(MI, OpNum, Pref);
     186             :     // We don't need to bother trying to break a dependency if this
     187             :     // instruction has a true dependency on that register through another
     188             :     // operand - we'll have to wait for it to be available regardless.
     189        1761 :     if (!HadTrueDependency && shouldBreakDependence(MI, OpNum, Pref))
     190          14 :       UndefReads.push_back(std::make_pair(MI, OpNum));
     191             :   }
     192             : 
     193     2513500 :   const MCInstrDesc &MCID = MI->getDesc();
     194     1460415 :   for (unsigned i = 0,
     195     2513500 :     e = MI->isVariadic() ? MI->getNumOperands() : MCID.getNumDefs();
     196     3973915 :     i != e; ++i) {
     197     1460415 :     MachineOperand &MO = MI->getOperand(i);
     198     1460415 :     if (!MO.isReg() || !MO.getReg())
     199             :       continue;
     200     1362771 :     if (MO.isUse())
     201             :       continue;
     202             :     // Check clearance before partial register updates.
     203     1216971 :     unsigned Pref = TII->getPartialRegUpdateClearance(*MI, i, TRI);
     204     1216971 :     if (Pref && shouldBreakDependence(MI, i, Pref))
     205         260 :       TII->breakPartialRegDependency(*MI, i, TRI);
     206             :   }
     207     2513500 : }
     208             : 
     209      365425 : void BreakFalseDeps::processUndefReads(MachineBasicBlock *MBB) {
     210      365425 :   if (UndefReads.empty())
     211             :     return;
     212             : 
     213             :   // Collect this block's live out register units.
     214          14 :   LiveRegSet.init(*TRI);
     215             :   // We do not need to care about pristine registers as they are just preserved
     216             :   // but not actually used in the function.
     217          14 :   LiveRegSet.addLiveOutsNoPristines(*MBB);
     218             : 
     219          14 :   MachineInstr *UndefMI = UndefReads.back().first;
     220          14 :   unsigned OpIdx = UndefReads.back().second;
     221             : 
     222         128 :   for (MachineInstr &I : make_range(MBB->rbegin(), MBB->rend())) {
     223             :     // Update liveness, including the current instruction's defs.
     224         128 :     LiveRegSet.stepBackward(I);
     225             : 
     226         128 :     if (UndefMI == &I) {
     227          42 :       if (!LiveRegSet.contains(UndefMI->getOperand(OpIdx).getReg()))
     228          13 :         TII->breakPartialRegDependency(*UndefMI, OpIdx, TRI);
     229             : 
     230             :       UndefReads.pop_back();
     231          14 :       if (UndefReads.empty())
     232             :         return;
     233             : 
     234           0 :       UndefMI = UndefReads.back().first;
     235           0 :       OpIdx = UndefReads.back().second;
     236             :     }
     237             :   }
     238             : }
     239             : 
     240      365424 : void BreakFalseDeps::processBasicBlock(MachineBasicBlock *MBB) {
     241             :   UndefReads.clear();
     242             :   // If this block is not done, it makes little sense to make any decisions
     243             :   // based on clearance information. We need to make a second pass anyway,
     244             :   // and by then we'll have better information, so we can avoid doing the work
     245             :   // to try and break dependencies now.
     246     2998804 :   for (MachineInstr &MI : *MBB) {
     247             :     if (!MI.isDebugInstr())
     248     2513500 :       processDefs(&MI);
     249             :   }
     250      365425 :   processUndefReads(MBB);
     251      365425 : }
     252             : 
     253      125006 : bool BreakFalseDeps::runOnMachineFunction(MachineFunction &mf) {
     254      125006 :   if (skipFunction(mf.getFunction()))
     255             :     return false;
     256      124864 :   MF = &mf;
     257      124864 :   TII = MF->getSubtarget().getInstrInfo();
     258      124864 :   TRI = MF->getSubtarget().getRegisterInfo();
     259      124864 :   RDA = &getAnalysis<ReachingDefAnalysis>();
     260             : 
     261      124864 :   RegClassInfo.runOnMachineFunction(mf);
     262             : 
     263             :   LLVM_DEBUG(dbgs() << "********** BREAK FALSE DEPENDENCIES **********\n");
     264             : 
     265             :   // Traverse the basic blocks.
     266      490289 :   for (MachineBasicBlock &MBB : mf) {
     267      365425 :     processBasicBlock(&MBB);
     268             :   }
     269             : 
     270             :   return false;
     271             : }

Generated by: LCOV version 1.13