lib/CodeGen/BreakFalseDeps.cpp

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