304 lines · 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-exception6//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 implicitly13/// need to read the other parts of the register. This may cause unwanted14/// stalls preventing otherwise unrelated instructions from executing in15/// parallel in an out-of-order CPU.16/// This pass is aimed at identifying and avoiding these dependencies.17//18//===----------------------------------------------------------------------===//19 20#include "llvm/ADT/DepthFirstIterator.h"21#include "llvm/CodeGen/LivePhysRegs.h"22#include "llvm/CodeGen/MachineFunctionPass.h"23#include "llvm/CodeGen/ReachingDefAnalysis.h"24#include "llvm/CodeGen/RegisterClassInfo.h"25#include "llvm/CodeGen/TargetInstrInfo.h"26#include "llvm/InitializePasses.h"27#include "llvm/MC/MCInstrDesc.h"28#include "llvm/MC/MCRegister.h"29#include "llvm/MC/MCRegisterInfo.h"30#include "llvm/Support/Debug.h"31 32using namespace llvm;33 34namespace {35 36class BreakFalseDeps : public MachineFunctionPass {37private:38 MachineFunction *MF = nullptr;39 const TargetInstrInfo *TII = nullptr;40 const TargetRegisterInfo *TRI = nullptr;41 RegisterClassInfo RegClassInfo;42 43 /// List of undefined register reads in this block in forward order.44 std::vector<std::pair<MachineInstr *, unsigned>> UndefReads;45 46 /// Storage for register unit liveness.47 LivePhysRegs LiveRegSet;48 49 ReachingDefInfo *RDI = nullptr;50 51public:52 static char ID; // Pass identification, replacement for typeid53 54 BreakFalseDeps() : MachineFunctionPass(ID) {55 initializeBreakFalseDepsPass(*PassRegistry::getPassRegistry());56 }57 58 void getAnalysisUsage(AnalysisUsage &AU) const override {59 AU.setPreservesAll();60 AU.addRequired<ReachingDefInfoWrapperPass>();61 MachineFunctionPass::getAnalysisUsage(AU);62 }63 64 bool runOnMachineFunction(MachineFunction &MF) override;65 66 MachineFunctionProperties getRequiredProperties() const override {67 return MachineFunctionProperties().setNoVRegs();68 }69 70private:71 /// Process he given basic block.72 void processBasicBlock(MachineBasicBlock *MBB);73 74 /// Update def-ages for registers defined by MI.75 /// Also break dependencies on partial defs and undef uses.76 void processDefs(MachineInstr *MI);77 78 /// Helps avoid false dependencies on undef registers by updating the79 /// machine instructions' undef operand to use a register that the instruction80 /// is truly dependent on, or use a register with clearance higher than Pref.81 /// Returns true if it was able to find a true dependency, thus not requiring82 /// a dependency breaking instruction regardless of clearance.83 bool pickBestRegisterForUndef(MachineInstr *MI, unsigned OpIdx,84 unsigned Pref);85 86 /// Return true to if it makes sense to break dependence on a partial87 /// def or undef use.88 bool shouldBreakDependence(MachineInstr *, unsigned OpIdx, unsigned Pref);89 90 /// Break false dependencies on undefined register reads.91 /// Walk the block backward computing precise liveness. This is expensive, so92 /// we only do it on demand. Note that the occurrence of undefined register93 /// reads that should be broken is very rare, but when they occur we may have94 /// many in a single block.95 void processUndefReads(MachineBasicBlock *);96};97 98} // namespace99 100#define DEBUG_TYPE "break-false-deps"101 102char BreakFalseDeps::ID = 0;103INITIALIZE_PASS_BEGIN(BreakFalseDeps, DEBUG_TYPE, "BreakFalseDeps", false, false)104INITIALIZE_PASS_DEPENDENCY(ReachingDefInfoWrapperPass)105INITIALIZE_PASS_END(BreakFalseDeps, DEBUG_TYPE, "BreakFalseDeps", false, false)106 107FunctionPass *llvm::createBreakFalseDeps() { return new BreakFalseDeps(); }108 109bool BreakFalseDeps::pickBestRegisterForUndef(MachineInstr *MI, unsigned OpIdx,110 unsigned Pref) {111 112 // We can't change tied operands.113 if (MI->isRegTiedToDefOperand(OpIdx))114 return false;115 116 MachineOperand &MO = MI->getOperand(OpIdx);117 assert(MO.isUndef() && "Expected undef machine operand");118 119 // We can't change registers that aren't renamable.120 if (!MO.isRenamable())121 return false;122 123 MCRegister OriginalReg = MO.getReg().asMCReg();124 125 // Update only undef operands that have reg units that are mapped to one root.126 for (MCRegUnit Unit : TRI->regunits(OriginalReg)) {127 unsigned NumRoots = 0;128 for (MCRegUnitRootIterator Root(Unit, TRI); Root.isValid(); ++Root) {129 NumRoots++;130 if (NumRoots > 1)131 return false;132 }133 }134 135 // Get the undef operand's register class136 const TargetRegisterClass *OpRC = TII->getRegClass(MI->getDesc(), OpIdx);137 assert(OpRC && "Not a valid register class");138 139 // If the instruction has a true dependency, we can hide the false depdency140 // behind it.141 for (MachineOperand &CurrMO : MI->all_uses()) {142 if (CurrMO.isUndef() || !OpRC->contains(CurrMO.getReg()))143 continue;144 // We found a true dependency - replace the undef register with the true145 // dependency.146 MO.setReg(CurrMO.getReg());147 return true;148 }149 150 // Go over all registers in the register class and find the register with151 // max clearance or clearance higher than Pref.152 unsigned MaxClearance = 0;153 unsigned MaxClearanceReg = OriginalReg;154 ArrayRef<MCPhysReg> Order = RegClassInfo.getOrder(OpRC);155 for (MCPhysReg Reg : Order) {156 unsigned Clearance = RDI->getClearance(MI, Reg);157 if (Clearance <= MaxClearance)158 continue;159 MaxClearance = Clearance;160 MaxClearanceReg = Reg;161 162 if (MaxClearance > Pref)163 break;164 }165 166 // Update the operand if we found a register with better clearance.167 if (MaxClearanceReg != OriginalReg)168 MO.setReg(MaxClearanceReg);169 170 return false;171}172 173bool BreakFalseDeps::shouldBreakDependence(MachineInstr *MI, unsigned OpIdx,174 unsigned Pref) {175 MCRegister Reg = MI->getOperand(OpIdx).getReg().asMCReg();176 unsigned Clearance = RDI->getClearance(MI, Reg);177 LLVM_DEBUG(dbgs() << "Clearance: " << Clearance << ", want " << Pref);178 179 if (Pref > Clearance) {180 LLVM_DEBUG(dbgs() << ": Break dependency.\n");181 return true;182 }183 LLVM_DEBUG(dbgs() << ": OK .\n");184 return false;185}186 187void BreakFalseDeps::processDefs(MachineInstr *MI) {188 assert(!MI->isDebugInstr() && "Won't process debug values");189 190 const MCInstrDesc &MCID = MI->getDesc();191 192 // Break dependence on undef uses. Do this before updating LiveRegs below.193 // This can remove a false dependence with no additional instructions.194 for (unsigned i = MCID.getNumDefs(), e = MCID.getNumOperands(); i != e; ++i) {195 MachineOperand &MO = MI->getOperand(i);196 if (!MO.isReg() || !MO.getReg() || !MO.isUse() || !MO.isUndef())197 continue;198 199 unsigned Pref = TII->getUndefRegClearance(*MI, i, TRI);200 if (Pref) {201 bool HadTrueDependency = pickBestRegisterForUndef(MI, i, Pref);202 // We don't need to bother trying to break a dependency if this203 // instruction has a true dependency on that register through another204 // operand - we'll have to wait for it to be available regardless.205 if (!HadTrueDependency && shouldBreakDependence(MI, i, Pref))206 UndefReads.push_back(std::make_pair(MI, i));207 }208 }209 210 // The code below allows the target to create a new instruction to break the211 // dependence. That opposes the goal of minimizing size, so bail out now.212 if (MF->getFunction().hasMinSize())213 return;214 215 for (unsigned i = 0,216 e = MI->isVariadic() ? MI->getNumOperands() : MCID.getNumDefs();217 i != e; ++i) {218 MachineOperand &MO = MI->getOperand(i);219 if (!MO.isReg() || !MO.getReg())220 continue;221 if (MO.isUse())222 continue;223 // Check clearance before partial register updates.224 unsigned Pref = TII->getPartialRegUpdateClearance(*MI, i, TRI);225 if (Pref && shouldBreakDependence(MI, i, Pref))226 TII->breakPartialRegDependency(*MI, i, TRI);227 }228}229 230void BreakFalseDeps::processUndefReads(MachineBasicBlock *MBB) {231 if (UndefReads.empty())232 return;233 234 // The code below allows the target to create a new instruction to break the235 // dependence. That opposes the goal of minimizing size, so bail out now.236 if (MF->getFunction().hasMinSize())237 return;238 239 // Collect this block's live out register units.240 LiveRegSet.init(*TRI);241 // We do not need to care about pristine registers as they are just preserved242 // but not actually used in the function.243 LiveRegSet.addLiveOutsNoPristines(*MBB);244 245 MachineInstr *UndefMI = UndefReads.back().first;246 unsigned OpIdx = UndefReads.back().second;247 248 for (MachineInstr &I : llvm::reverse(*MBB)) {249 // Update liveness, including the current instruction's defs.250 LiveRegSet.stepBackward(I);251 252 if (UndefMI == &I) {253 if (!LiveRegSet.contains(UndefMI->getOperand(OpIdx).getReg()))254 TII->breakPartialRegDependency(*UndefMI, OpIdx, TRI);255 256 UndefReads.pop_back();257 if (UndefReads.empty())258 return;259 260 UndefMI = UndefReads.back().first;261 OpIdx = UndefReads.back().second;262 }263 }264}265 266void BreakFalseDeps::processBasicBlock(MachineBasicBlock *MBB) {267 UndefReads.clear();268 // If this block is not done, it makes little sense to make any decisions269 // based on clearance information. We need to make a second pass anyway,270 // and by then we'll have better information, so we can avoid doing the work271 // to try and break dependencies now.272 for (MachineInstr &MI : *MBB) {273 if (!MI.isDebugInstr())274 processDefs(&MI);275 }276 processUndefReads(MBB);277}278 279bool BreakFalseDeps::runOnMachineFunction(MachineFunction &mf) {280 if (skipFunction(mf.getFunction()))281 return false;282 MF = &mf;283 TII = MF->getSubtarget().getInstrInfo();284 TRI = MF->getSubtarget().getRegisterInfo();285 RDI = &getAnalysis<ReachingDefInfoWrapperPass>().getRDI();286 287 RegClassInfo.runOnMachineFunction(mf, /*Rev=*/true);288 289 LLVM_DEBUG(dbgs() << "********** BREAK FALSE DEPENDENCIES **********\n");290 291 // Skip Dead blocks due to ReachingDefAnalysis has no idea about instructions292 // in them.293 df_iterator_default_set<MachineBasicBlock *> Reachable;294 for (MachineBasicBlock *MBB : depth_first_ext(&mf, Reachable))295 (void)MBB /* Mark all reachable blocks */;296 297 // Traverse the basic blocks.298 for (MachineBasicBlock &MBB : mf)299 if (Reachable.count(&MBB))300 processBasicBlock(&MBB);301 302 return false;303}304