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