Index: llvm/trunk/include/llvm/CodeGen/ExecutionDomainFix.h =================================================================== --- llvm/trunk/include/llvm/CodeGen/ExecutionDomainFix.h +++ llvm/trunk/include/llvm/CodeGen/ExecutionDomainFix.h @@ -1,4 +1,4 @@ -//==--- llvm/CodeGen/ExecutionDepsFix.h - Execution Domain Fix -*- C++ -*---==// +//==-- llvm/CodeGen/ExecutionDomainFix.h - Execution Domain Fix -*- C++ -*--==// // // The LLVM Compiler Infrastructure // @@ -20,15 +20,14 @@ // //===----------------------------------------------------------------------===// -#ifndef LLVM_CODEGEN_EXECUTIONDEPSFIX_H -#define LLVM_CODEGEN_EXECUTIONDEPSFIX_H +#ifndef LLVM_CODEGEN_EXECUTIONDOMAINFIX_H +#define LLVM_CODEGEN_EXECUTIONDOMAINFIX_H -#include "llvm/ADT/DenseMap.h" #include "llvm/ADT/SmallVector.h" -#include "llvm/ADT/iterator_range.h" -#include "llvm/CodeGen/LivePhysRegs.h" +#include "llvm/CodeGen/LoopTraversal.h" #include "llvm/CodeGen/MachineFunctionPass.h" -#include "llvm/CodeGen/RegisterClassInfo.h" +#include "llvm/CodeGen/ReachingDefAnalysis.h" +#include "llvm/CodeGen/TargetRegisterInfo.h" namespace llvm { @@ -106,173 +105,6 @@ } }; -/// This class provides the basic blocks traversal order used by passes like -/// ReachingDefAnalysis and ExecutionDomainFix. -/// It identifies basic blocks that are part of loops and should to be visited -/// twice and returns efficient traversal order for all the blocks. -/// -/// We want to visit every instruction in every basic block in order to update -/// it's execution domain or collect clearance information. However, for the -/// clearance calculation, we need to know clearances from all predecessors -/// (including any backedges), therfore we need to visit some blocks twice. -/// As an example, consider the following loop. -/// -/// -/// PH -> A -> B (xmm -> xmm) -> C -> D -> EXIT -/// ^ | -/// +----------------------------------+ -/// -/// The iteration order this pass will return is as follows: -/// Optimized: PH A B C A' B' C' D -/// -/// The basic block order is constructed as follows: -/// Once we finish processing some block, we update the counters in MBBInfos -/// and re-process any successors that are now 'done'. -/// We call a block that is ready for its final round of processing `done` -/// (isBlockDone), e.g. when all predecessor information is known. -/// -/// Note that a naive traversal order would be to do two complete passes over -/// all basic blocks/instructions, the first for recording clearances, the -/// second for updating clearance based on backedges. -/// However, for functions without backedges, or functions with a lot of -/// straight-line code, and a small loop, that would be a lot of unnecessary -/// work (since only the BBs that are part of the loop require two passes). -/// -/// E.g., the naive iteration order for the above exmple is as follows: -/// Naive: PH A B C D A' B' C' D' -/// -/// In the optimized approach we avoid processing D twice, because we -/// can entirely process the predecessors before getting to D. -class LoopTraversal { -private: - struct MBBInfo { - /// Whether we have gotten to this block in primary processing yet. - bool PrimaryCompleted = false; - - /// The number of predecessors for which primary processing has completed - unsigned IncomingProcessed = 0; - - /// The value of `IncomingProcessed` at the start of primary processing - unsigned PrimaryIncoming = 0; - - /// The number of predecessors for which all processing steps are done. - unsigned IncomingCompleted = 0; - - MBBInfo() = default; - }; - using MBBInfoMap = SmallVector; - /// Helps keep track if we proccessed this block and all its predecessors. - MBBInfoMap MBBInfos; - -public: - struct TraversedMBBInfo { - /// The basic block. - MachineBasicBlock *MBB = nullptr; - - /// True if this is the first time we process the basic block. - bool PrimaryPass = true; - - /// True if the block that is ready for its final round of processing. - bool IsDone = true; - - TraversedMBBInfo(MachineBasicBlock *BB = nullptr, bool Primary = true, - bool Done = true) - : MBB(BB), PrimaryPass(Primary), IsDone(Done) {} - }; - LoopTraversal() {} - - /// \brief Identifies basic blocks that are part of loops and should to be - /// visited twise and returns efficient traversal order for all the blocks. - typedef SmallVector TraversalOrder; - TraversalOrder traverse(MachineFunction &MF); - -private: - /// Returens true if the block is ready for its final round of processing. - bool isBlockDone(MachineBasicBlock *MBB); -}; - -/// This class provides the reaching def analysis. -class ReachingDefAnalysis : public MachineFunctionPass { -private: - MachineFunction *MF; - const TargetInstrInfo *TII; - const TargetRegisterInfo *TRI; - unsigned NumRegUnits; - /// Instruction that defined each register, relative to the beginning of the - /// current basic block. When a LiveRegsDefInfo is used to represent a - /// live-out register, this value is relative to the end of the basic block, - /// so it will be a negative number. - using LiveRegsDefInfo = std::vector; - LiveRegsDefInfo LiveRegs; - - /// Keeps clearance information for all registers. Note that this - /// is different from the usual definition notion of liveness. The CPU - /// doesn't care whether or not we consider a register killed. - using OutRegsInfoMap = SmallVector; - OutRegsInfoMap MBBOutRegsInfos; - - /// Current instruction number. - /// The first instruction in each basic block is 0. - int CurInstr; - - /// Maps instructions to their instruction Ids, relative to the begining of - /// their basic blocks. - DenseMap InstIds; - - /// All reaching defs of a given RegUnit for a given MBB. - using MBBRegUnitDefs = SmallVector; - /// All reaching defs of all reg units for a given MBB - using MBBDefsInfo = std::vector; - /// All reaching defs of all reg units for a all MBBs - using MBBReachingDefsInfo = SmallVector; - MBBReachingDefsInfo MBBReachingDefs; - - /// Default values are 'nothing happened a long time ago'. - const int ReachingDedDefaultVal = -(1 << 20); - -public: - static char ID; // Pass identification, replacement for typeid - - ReachingDefAnalysis() : MachineFunctionPass(ID) { - initializeReachingDefAnalysisPass(*PassRegistry::getPassRegistry()); - } - void releaseMemory() override; - - void getAnalysisUsage(AnalysisUsage &AU) const override { - AU.setPreservesAll(); - MachineFunctionPass::getAnalysisUsage(AU); - } - - bool runOnMachineFunction(MachineFunction &MF) override; - - MachineFunctionProperties getRequiredProperties() const override { - return MachineFunctionProperties().set( - MachineFunctionProperties::Property::NoVRegs); - } - - /// Provides the instruction id of the closest reaching def instruction of - /// PhysReg that reaches MI, relative to the begining of MI's basic block. - int getReachingDef(MachineInstr *MI, int PhysReg); - - /// Provides the clearance - the number of instructions since the closest - /// reaching def instuction of PhysReg that reaches MI. - int getClearance(MachineInstr *MI, MCPhysReg PhysReg); - -private: - /// Set up LiveRegs by merging predecessor live-out values. - void enterBasicBlock(const LoopTraversal::TraversedMBBInfo &TraversedMBB); - - /// Update live-out values. - void leaveBasicBlock(const LoopTraversal::TraversedMBBInfo &TraversedMBB); - - /// Process he given basic block. - void processBasicBlock(const LoopTraversal::TraversedMBBInfo &TraversedMBB); - - /// Update def-ages for registers defined by MI. - /// Also break dependencies on partial defs and undef uses. - void processDefs(MachineInstr *); -}; - class ExecutionDomainFix : public MachineFunctionPass { SpecificBumpPtrAllocator Allocator; SmallVector Avail; @@ -376,69 +208,6 @@ void visitHardInstr(MachineInstr *, unsigned domain); }; -class BreakFalseDeps : public MachineFunctionPass { -private: - MachineFunction *MF; - const TargetInstrInfo *TII; - const TargetRegisterInfo *TRI; - RegisterClassInfo RegClassInfo; - - /// List of undefined register reads in this block in forward order. - std::vector> UndefReads; - - /// Storage for register unit liveness. - LivePhysRegs LiveRegSet; - - ReachingDefAnalysis *RDA; - -public: - static char ID; // Pass identification, replacement for typeid - - BreakFalseDeps() : MachineFunctionPass(ID) { - initializeBreakFalseDepsPass(*PassRegistry::getPassRegistry()); - } - - void getAnalysisUsage(AnalysisUsage &AU) const override { - AU.setPreservesAll(); - AU.addRequired(); - MachineFunctionPass::getAnalysisUsage(AU); - } - - bool runOnMachineFunction(MachineFunction &MF) override; - - MachineFunctionProperties getRequiredProperties() const override { - return MachineFunctionProperties().set( - MachineFunctionProperties::Property::NoVRegs); - } - -private: - /// Process he given basic block. - void processBasicBlock(MachineBasicBlock *MBB); - - /// Update def-ages for registers defined by MI. - /// Also break dependencies on partial defs and undef uses. - void processDefs(MachineInstr *MI); - - /// \brief Helps avoid false dependencies on undef registers by updating the - /// machine instructions' undef operand to use a register that the instruction - /// is truly dependent on, or use a register with clearance higher than Pref. - /// Returns true if it was able to find a true dependency, thus not requiring - /// a dependency breaking instruction regardless of clearance. - bool pickBestRegisterForUndef(MachineInstr *MI, unsigned OpIdx, - unsigned Pref); - - /// \brief Return true to if it makes sense to break dependence on a partial - /// def or undef use. - bool shouldBreakDependence(MachineInstr *, unsigned OpIdx, unsigned Pref); - - /// \brief Break false dependencies on undefined register reads. - /// Walk the block backward computing precise liveness. This is expensive, so - /// we only do it on demand. Note that the occurrence of undefined register - /// reads that should be broken is very rare, but when they occur we may have - /// many in a single block. - void processUndefReads(MachineBasicBlock *); -}; - } // namespace llvm -#endif // LLVM_CODEGEN_EXECUTIONDEPSFIX_H +#endif // LLVM_CODEGEN_EXECUTIONDOMAINFIX_H Index: llvm/trunk/include/llvm/CodeGen/LoopTraversal.h =================================================================== --- llvm/trunk/include/llvm/CodeGen/LoopTraversal.h +++ llvm/trunk/include/llvm/CodeGen/LoopTraversal.h @@ -0,0 +1,116 @@ +//==------ llvm/CodeGen/LoopTraversal.h - Loop Traversal -*- C++ -*---------==// +// +// The LLVM Compiler Infrastructure +// +// This file is distributed under the University of Illinois Open Source +// License. See LICENSE.TXT for details. +// +//===----------------------------------------------------------------------===// +// +/// \file Loop Traversal logic. +/// +/// This class provides the basic blocks traversal order used by passes like +/// ReachingDefAnalysis and ExecutionDomainFix. +/// It identifies basic blocks that are part of loops and should to be visited +/// twice and returns efficient traversal order for all the blocks. +// +//===----------------------------------------------------------------------===// + +#ifndef LLVM_CODEGEN_LOOPTRAVERSAL_H +#define LLVM_CODEGEN_LOOPTRAVERSAL_H + +#include "llvm/ADT/SmallVector.h" + +namespace llvm { + +class MachineBasicBlock; +class MachineFunction; + +/// This class provides the basic blocks traversal order used by passes like +/// ReachingDefAnalysis and ExecutionDomainFix. +/// It identifies basic blocks that are part of loops and should to be visited +/// twice and returns efficient traversal order for all the blocks. +/// +/// We want to visit every instruction in every basic block in order to update +/// it's execution domain or collect clearance information. However, for the +/// clearance calculation, we need to know clearances from all predecessors +/// (including any backedges), therfore we need to visit some blocks twice. +/// As an example, consider the following loop. +/// +/// +/// PH -> A -> B (xmm -> xmm) -> C -> D -> EXIT +/// ^ | +/// +----------------------------------+ +/// +/// The iteration order this pass will return is as follows: +/// Optimized: PH A B C A' B' C' D +/// +/// The basic block order is constructed as follows: +/// Once we finish processing some block, we update the counters in MBBInfos +/// and re-process any successors that are now 'done'. +/// We call a block that is ready for its final round of processing `done` +/// (isBlockDone), e.g. when all predecessor information is known. +/// +/// Note that a naive traversal order would be to do two complete passes over +/// all basic blocks/instructions, the first for recording clearances, the +/// second for updating clearance based on backedges. +/// However, for functions without backedges, or functions with a lot of +/// straight-line code, and a small loop, that would be a lot of unnecessary +/// work (since only the BBs that are part of the loop require two passes). +/// +/// E.g., the naive iteration order for the above exmple is as follows: +/// Naive: PH A B C D A' B' C' D' +/// +/// In the optimized approach we avoid processing D twice, because we +/// can entirely process the predecessors before getting to D. +class LoopTraversal { +private: + struct MBBInfo { + /// Whether we have gotten to this block in primary processing yet. + bool PrimaryCompleted = false; + + /// The number of predecessors for which primary processing has completed + unsigned IncomingProcessed = 0; + + /// The value of `IncomingProcessed` at the start of primary processing + unsigned PrimaryIncoming = 0; + + /// The number of predecessors for which all processing steps are done. + unsigned IncomingCompleted = 0; + + MBBInfo() = default; + }; + using MBBInfoMap = SmallVector; + /// Helps keep track if we proccessed this block and all its predecessors. + MBBInfoMap MBBInfos; + +public: + struct TraversedMBBInfo { + /// The basic block. + MachineBasicBlock *MBB = nullptr; + + /// True if this is the first time we process the basic block. + bool PrimaryPass = true; + + /// True if the block that is ready for its final round of processing. + bool IsDone = true; + + TraversedMBBInfo(MachineBasicBlock *BB = nullptr, bool Primary = true, + bool Done = true) + : MBB(BB), PrimaryPass(Primary), IsDone(Done) {} + }; + LoopTraversal() {} + + /// \brief Identifies basic blocks that are part of loops and should to be + /// visited twice and returns efficient traversal order for all the blocks. + typedef SmallVector TraversalOrder; + TraversalOrder traverse(MachineFunction &MF); + +private: + /// Returens true if the block is ready for its final round of processing. + bool isBlockDone(MachineBasicBlock *MBB); +}; + +} // namespace llvm + +#endif // LLVM_CODEGEN_LOOPTRAVERSAL_H Index: llvm/trunk/include/llvm/CodeGen/Passes.h =================================================================== --- llvm/trunk/include/llvm/CodeGen/Passes.h +++ llvm/trunk/include/llvm/CodeGen/Passes.h @@ -425,6 +425,9 @@ // This pass expands memcmp() to load/stores. FunctionPass *createExpandMemCmpPass(); + /// Creates Break False Dependencies pass. \see BreakFalseDeps.cpp + FunctionPass *createBreakFalseDeps(); + } // End llvm namespace #endif Index: llvm/trunk/include/llvm/CodeGen/ReachingDefAnalysis.h =================================================================== --- llvm/trunk/include/llvm/CodeGen/ReachingDefAnalysis.h +++ llvm/trunk/include/llvm/CodeGen/ReachingDefAnalysis.h @@ -0,0 +1,118 @@ +//==--- llvm/CodeGen/ReachingDefAnalysis.h - Reaching Def Analysis -*- C++ -*---==// +// +// The LLVM Compiler Infrastructure +// +// This file is distributed under the University of Illinois Open Source +// License. See LICENSE.TXT for details. +// +//===----------------------------------------------------------------------===// +// +/// \file Reaching Defs Analysis pass. +/// +/// This pass tracks for each instruction what is the “closest” reaching def of +/// a given register. It is used by BreakFalseDeps (for clearance calculation) +/// and ExecutionDomainFix (for arbitrating conflicting domains). +/// +/// Note that this is different from the usual definition notion of liveness. +/// The CPU doesn't care whether or not we consider a register killed. +/// +// +//===----------------------------------------------------------------------===// + +#ifndef LLVM_CODEGEN_REACHINGDEFSANALYSIS_H +#define LLVM_CODEGEN_REACHINGDEFSANALYSIS_H + +#include "llvm/ADT/DenseMap.h" +#include "llvm/ADT/SmallVector.h" +#include "llvm/CodeGen/LoopTraversal.h" +#include "llvm/CodeGen/MachineFunctionPass.h" + +namespace llvm { + +class MachineBasicBlock; +class MachineInstr; + +/// This class provides the reaching def analysis. +class ReachingDefAnalysis : public MachineFunctionPass { +private: + MachineFunction *MF; + const TargetRegisterInfo *TRI; + unsigned NumRegUnits; + /// Instruction that defined each register, relative to the beginning of the + /// current basic block. When a LiveRegsDefInfo is used to represent a + /// live-out register, this value is relative to the end of the basic block, + /// so it will be a negative number. + using LiveRegsDefInfo = std::vector; + LiveRegsDefInfo LiveRegs; + + /// Keeps clearance information for all registers. Note that this + /// is different from the usual definition notion of liveness. The CPU + /// doesn't care whether or not we consider a register killed. + using OutRegsInfoMap = SmallVector; + OutRegsInfoMap MBBOutRegsInfos; + + /// Current instruction number. + /// The first instruction in each basic block is 0. + int CurInstr; + + /// Maps instructions to their instruction Ids, relative to the begining of + /// their basic blocks. + DenseMap InstIds; + + /// All reaching defs of a given RegUnit for a given MBB. + using MBBRegUnitDefs = SmallVector; + /// All reaching defs of all reg units for a given MBB + using MBBDefsInfo = std::vector; + /// All reaching defs of all reg units for a all MBBs + using MBBReachingDefsInfo = SmallVector; + MBBReachingDefsInfo MBBReachingDefs; + + /// Default values are 'nothing happened a long time ago'. + const int ReachingDedDefaultVal = -(1 << 20); + +public: + static char ID; // Pass identification, replacement for typeid + + ReachingDefAnalysis() : MachineFunctionPass(ID) { + initializeReachingDefAnalysisPass(*PassRegistry::getPassRegistry()); + } + void releaseMemory() override; + + void getAnalysisUsage(AnalysisUsage &AU) const override { + AU.setPreservesAll(); + MachineFunctionPass::getAnalysisUsage(AU); + } + + bool runOnMachineFunction(MachineFunction &MF) override; + + MachineFunctionProperties getRequiredProperties() const override { + return MachineFunctionProperties().set( + MachineFunctionProperties::Property::NoVRegs); + } + + /// Provides the instruction id of the closest reaching def instruction of + /// PhysReg that reaches MI, relative to the begining of MI's basic block. + int getReachingDef(MachineInstr *MI, int PhysReg); + + /// Provides the clearance - the number of instructions since the closest + /// reaching def instuction of PhysReg that reaches MI. + int getClearance(MachineInstr *MI, MCPhysReg PhysReg); + +private: + /// Set up LiveRegs by merging predecessor live-out values. + void enterBasicBlock(const LoopTraversal::TraversedMBBInfo &TraversedMBB); + + /// Update live-out values. + void leaveBasicBlock(const LoopTraversal::TraversedMBBInfo &TraversedMBB); + + /// Process he given basic block. + void processBasicBlock(const LoopTraversal::TraversedMBBInfo &TraversedMBB); + + /// Update def-ages for registers defined by MI. + /// Also break dependencies on partial defs and undef uses. + void processDefs(MachineInstr *); +}; + +} // namespace llvm + +#endif // LLVM_CODEGEN_REACHINGDEFSANALYSIS_H Index: llvm/trunk/lib/CodeGen/BreakFalseDeps.cpp =================================================================== --- llvm/trunk/lib/CodeGen/BreakFalseDeps.cpp +++ llvm/trunk/lib/CodeGen/BreakFalseDeps.cpp @@ -0,0 +1,271 @@ +//==- llvm/CodeGen/BreakFalseDeps.cpp - Break False Dependency Fix -*- C++ -*==// +// +// The LLVM Compiler Infrastructure +// +// This file is distributed under the University of Illinois Open Source +// License. See LICENSE.TXT for details. +// +//===----------------------------------------------------------------------===// +// +/// \file Break False Dependency pass. +/// +/// Some instructions have false dependencies which cause unnecessary stalls. +/// For exmaple, instructions that only write part of a register, and implicitly +/// need to read the other parts of the register. This may cause unwanted +/// stalls preventing otherwise unrelated instructions from executing in +/// parallel in an out-of-order CPU. +/// This pass is aimed at identifying and avoiding these depepndencies when +/// possible. +// +//===----------------------------------------------------------------------===// + +#include "llvm/CodeGen/LivePhysRegs.h" +#include "llvm/CodeGen/MachineFunctionPass.h" +#include "llvm/CodeGen/ReachingDefAnalysis.h" +#include "llvm/CodeGen/RegisterClassInfo.h" +#include "llvm/CodeGen/MachineRegisterInfo.h" +#include "llvm/CodeGen/TargetInstrInfo.h" + + +using namespace llvm; + +namespace llvm { + +class BreakFalseDeps : public MachineFunctionPass { +private: + MachineFunction *MF; + const TargetInstrInfo *TII; + const TargetRegisterInfo *TRI; + RegisterClassInfo RegClassInfo; + + /// List of undefined register reads in this block in forward order. + std::vector> UndefReads; + + /// Storage for register unit liveness. + LivePhysRegs LiveRegSet; + + ReachingDefAnalysis *RDA; + +public: + static char ID; // Pass identification, replacement for typeid + + BreakFalseDeps() : MachineFunctionPass(ID) { + initializeBreakFalseDepsPass(*PassRegistry::getPassRegistry()); + } + + void getAnalysisUsage(AnalysisUsage &AU) const override { + AU.setPreservesAll(); + AU.addRequired(); + MachineFunctionPass::getAnalysisUsage(AU); + } + + bool runOnMachineFunction(MachineFunction &MF) override; + + MachineFunctionProperties getRequiredProperties() const override { + return MachineFunctionProperties().set( + MachineFunctionProperties::Property::NoVRegs); + } + +private: + /// Process he given basic block. + void processBasicBlock(MachineBasicBlock *MBB); + + /// Update def-ages for registers defined by MI. + /// Also break dependencies on partial defs and undef uses. + void processDefs(MachineInstr *MI); + + /// \brief Helps avoid false dependencies on undef registers by updating the + /// machine instructions' undef operand to use a register that the instruction + /// is truly dependent on, or use a register with clearance higher than Pref. + /// Returns true if it was able to find a true dependency, thus not requiring + /// a dependency breaking instruction regardless of clearance. + bool pickBestRegisterForUndef(MachineInstr *MI, unsigned OpIdx, + unsigned Pref); + + /// \brief Return true to if it makes sense to break dependence on a partial + /// def or undef use. + bool shouldBreakDependence(MachineInstr *, unsigned OpIdx, unsigned Pref); + + /// \brief Break false dependencies on undefined register reads. + /// Walk the block backward computing precise liveness. This is expensive, so + /// we only do it on demand. Note that the occurrence of undefined register + /// reads that should be broken is very rare, but when they occur we may have + /// many in a single block. + void processUndefReads(MachineBasicBlock *); +}; + +} // namespace llvm + +#define DEBUG_TYPE "break-false-deps" + +char BreakFalseDeps::ID = 0; +INITIALIZE_PASS_BEGIN(BreakFalseDeps, DEBUG_TYPE, "BreakFalseDeps", false, false) +INITIALIZE_PASS_DEPENDENCY(ReachingDefAnalysis) +INITIALIZE_PASS_END(BreakFalseDeps, DEBUG_TYPE, "BreakFalseDeps", false, false) + +FunctionPass *llvm::createBreakFalseDeps() { return new BreakFalseDeps(); } + +bool BreakFalseDeps::pickBestRegisterForUndef(MachineInstr *MI, unsigned OpIdx, + unsigned Pref) { + MachineOperand &MO = MI->getOperand(OpIdx); + assert(MO.isUndef() && "Expected undef machine operand"); + + unsigned OriginalReg = MO.getReg(); + + // Update only undef operands that have reg units that are mapped to one root. + for (MCRegUnitIterator Unit(OriginalReg, TRI); Unit.isValid(); ++Unit) { + unsigned NumRoots = 0; + for (MCRegUnitRootIterator Root(*Unit, TRI); Root.isValid(); ++Root) { + NumRoots++; + if (NumRoots > 1) + return false; + } + } + + // Get the undef operand's register class + const TargetRegisterClass *OpRC = + TII->getRegClass(MI->getDesc(), OpIdx, TRI, *MF); + + // If the instruction has a true dependency, we can hide the false depdency + // behind it. + for (MachineOperand &CurrMO : MI->operands()) { + if (!CurrMO.isReg() || CurrMO.isDef() || CurrMO.isUndef() || + !OpRC->contains(CurrMO.getReg())) + continue; + // We found a true dependency - replace the undef register with the true + // dependency. + MO.setReg(CurrMO.getReg()); + return true; + } + + // Go over all registers in the register class and find the register with + // max clearance or clearance higher than Pref. + unsigned MaxClearance = 0; + unsigned MaxClearanceReg = OriginalReg; + ArrayRef Order = RegClassInfo.getOrder(OpRC); + for (MCPhysReg Reg : Order) { + unsigned Clearance = RDA->getClearance(MI, Reg); + if (Clearance <= MaxClearance) + continue; + MaxClearance = Clearance; + MaxClearanceReg = Reg; + + if (MaxClearance > Pref) + break; + } + + // Update the operand if we found a register with better clearance. + if (MaxClearanceReg != OriginalReg) + MO.setReg(MaxClearanceReg); + + return false; +} + +bool BreakFalseDeps::shouldBreakDependence(MachineInstr *MI, unsigned OpIdx, + unsigned Pref) { + unsigned reg = MI->getOperand(OpIdx).getReg(); + unsigned Clearance = RDA->getClearance(MI, reg); + DEBUG(dbgs() << "Clearance: " << Clearance << ", want " << Pref); + + if (Pref > Clearance) { + DEBUG(dbgs() << ": Break dependency.\n"); + return true; + } + DEBUG(dbgs() << ": OK .\n"); + return false; +} + +void BreakFalseDeps::processDefs(MachineInstr *MI) { + assert(!MI->isDebugValue() && "Won't process debug values"); + + // Break dependence on undef uses. Do this before updating LiveRegs below. + unsigned OpNum; + unsigned Pref = TII->getUndefRegClearance(*MI, OpNum, TRI); + if (Pref) { + bool HadTrueDependency = pickBestRegisterForUndef(MI, OpNum, Pref); + // We don't need to bother trying to break a dependency if this + // instruction has a true dependency on that register through another + // operand - we'll have to wait for it to be available regardless. + if (!HadTrueDependency && shouldBreakDependence(MI, OpNum, Pref)) + UndefReads.push_back(std::make_pair(MI, OpNum)); + } + + const MCInstrDesc &MCID = MI->getDesc(); + for (unsigned i = 0, + e = MI->isVariadic() ? MI->getNumOperands() : MCID.getNumDefs(); + i != e; ++i) { + MachineOperand &MO = MI->getOperand(i); + if (!MO.isReg() || !MO.getReg()) + continue; + if (MO.isUse()) + continue; + // Check clearance before partial register updates. + unsigned Pref = TII->getPartialRegUpdateClearance(*MI, i, TRI); + if (Pref && shouldBreakDependence(MI, i, Pref)) + TII->breakPartialRegDependency(*MI, i, TRI); + } +} + +void BreakFalseDeps::processUndefReads(MachineBasicBlock *MBB) { + if (UndefReads.empty()) + return; + + // Collect this block's live out register units. + LiveRegSet.init(*TRI); + // We do not need to care about pristine registers as they are just preserved + // but not actually used in the function. + LiveRegSet.addLiveOutsNoPristines(*MBB); + + MachineInstr *UndefMI = UndefReads.back().first; + unsigned OpIdx = UndefReads.back().second; + + for (MachineInstr &I : make_range(MBB->rbegin(), MBB->rend())) { + // Update liveness, including the current instruction's defs. + LiveRegSet.stepBackward(I); + + if (UndefMI == &I) { + if (!LiveRegSet.contains(UndefMI->getOperand(OpIdx).getReg())) + TII->breakPartialRegDependency(*UndefMI, OpIdx, TRI); + + UndefReads.pop_back(); + if (UndefReads.empty()) + return; + + UndefMI = UndefReads.back().first; + OpIdx = UndefReads.back().second; + } + } +} + +void BreakFalseDeps::processBasicBlock(MachineBasicBlock *MBB) { + UndefReads.clear(); + // If this block is not done, it makes little sense to make any decisions + // based on clearance information. We need to make a second pass anyway, + // and by then we'll have better information, so we can avoid doing the work + // to try and break dependencies now. + for (MachineInstr &MI : *MBB) { + if (!MI.isDebugValue()) + processDefs(&MI); + } + processUndefReads(MBB); +} + +bool BreakFalseDeps::runOnMachineFunction(MachineFunction &mf) { + if (skipFunction(mf.getFunction())) + return false; + MF = &mf; + TII = MF->getSubtarget().getInstrInfo(); + TRI = MF->getSubtarget().getRegisterInfo(); + RDA = &getAnalysis(); + + RegClassInfo.runOnMachineFunction(mf); + + DEBUG(dbgs() << "********** BREAK FALSE DEPENDENCIES **********\n"); + + // Traverse the basic blocks. + for (MachineBasicBlock &MBB : mf) { + processBasicBlock(&MBB); + } + + return false; +} Index: llvm/trunk/lib/CodeGen/CMakeLists.txt =================================================================== --- llvm/trunk/lib/CodeGen/CMakeLists.txt +++ llvm/trunk/lib/CodeGen/CMakeLists.txt @@ -6,6 +6,7 @@ BasicTargetTransformInfo.cpp BranchFolding.cpp BranchRelaxation.cpp + BreakFalseDeps.cpp BuiltinGCs.cpp CalcSpillWeights.cpp CallingConvLower.cpp @@ -55,6 +56,7 @@ LiveVariables.cpp LLVMTargetMachine.cpp LocalStackSlotAllocation.cpp + LoopTraversal.cpp LowLevelType.cpp LowerEmuTLS.cpp MachineBasicBlock.cpp @@ -104,6 +106,7 @@ ProcessImplicitDefs.cpp PrologEpilogInserter.cpp PseudoSourceValue.cpp + ReachingDefAnalysis.cpp RegAllocBase.cpp RegAllocBasic.cpp RegAllocFast.cpp Index: llvm/trunk/lib/CodeGen/ExecutionDomainFix.cpp =================================================================== --- llvm/trunk/lib/CodeGen/ExecutionDomainFix.cpp +++ llvm/trunk/lib/CodeGen/ExecutionDomainFix.cpp @@ -1,4 +1,4 @@ -//===- ExecutionDepsFix.cpp - Fix execution domain issues ----*- C++ -*-===// +//===- ExecutionDomainFix.cpp - Fix execution domain issues ----*- C++ -*--===// // // The LLVM Compiler Infrastructure // @@ -8,7 +8,6 @@ //===----------------------------------------------------------------------===// #include "llvm/CodeGen/ExecutionDomainFix.h" -#include "llvm/ADT/PostOrderIterator.h" #include "llvm/CodeGen/MachineRegisterInfo.h" #include "llvm/CodeGen/TargetInstrInfo.h" @@ -16,17 +15,6 @@ #define DEBUG_TYPE "execution-deps-fix" -char ReachingDefAnalysis::ID = 0; -INITIALIZE_PASS(ReachingDefAnalysis, "reaching-deps-analysis", - "ReachingDefAnalysis", false, true) - -char BreakFalseDeps::ID = 0; -INITIALIZE_PASS_BEGIN(BreakFalseDeps, "break-false-deps", "BreakFalseDeps", - false, false) -INITIALIZE_PASS_DEPENDENCY(ReachingDefAnalysis) -INITIALIZE_PASS_END(BreakFalseDeps, "break-false-deps", "BreakFalseDeps", false, - false) - iterator_range::const_iterator> ExecutionDomainFix::regIndices(unsigned Reg) const { assert(Reg < AliasMap.size() && "Invalid register"); @@ -161,61 +149,6 @@ return true; } -void ReachingDefAnalysis::enterBasicBlock( - const LoopTraversal::TraversedMBBInfo &TraversedMBB) { - - MachineBasicBlock *MBB = TraversedMBB.MBB; - int MBBNumber = MBB->getNumber(); - assert(MBBNumber < MBBReachingDefs.size() && - "Unexpected basic block number."); - MBBReachingDefs[MBBNumber].resize(NumRegUnits); - - // Reset instruction counter in each basic block. - CurInstr = 0; - - // Set up LiveRegs to represent registers entering MBB. - // Default values are 'nothing happened a long time ago'. - if (LiveRegs.empty()) - LiveRegs.assign(NumRegUnits, ReachingDedDefaultVal); - - // This is the entry block. - if (MBB->pred_empty()) { - for (const auto &LI : MBB->liveins()) { - for (MCRegUnitIterator Unit(LI.PhysReg, TRI); Unit.isValid(); ++Unit) { - // Treat function live-ins as if they were defined just before the first - // instruction. Usually, function arguments are set up immediately - // before the call. - LiveRegs[*Unit] = -1; - MBBReachingDefs[MBBNumber][*Unit].push_back(LiveRegs[*Unit]); - } - } - DEBUG(dbgs() << printMBBReference(*MBB) << ": entry\n"); - return; - } - - // Try to coalesce live-out registers from predecessors. - for (MachineBasicBlock *pred : MBB->predecessors()) { - assert(pred->getNumber() < MBBOutRegsInfos.size() && - "Should have pre-allocated MBBInfos for all MBBs"); - const LiveRegsDefInfo &Incoming = MBBOutRegsInfos[pred->getNumber()]; - // Incoming is null if this is a backedge from a BB - // we haven't processed yet - if (Incoming.empty()) - continue; - - for (unsigned Unit = 0; Unit != NumRegUnits; ++Unit) { - // Use the most recent predecessor def for each register. - LiveRegs[Unit] = std::max(LiveRegs[Unit], Incoming[Unit]); - if ((LiveRegs[Unit] != ReachingDedDefaultVal)) - MBBReachingDefs[MBBNumber][Unit].push_back(LiveRegs[Unit]); - } - } - - DEBUG(dbgs() << printMBBReference(*MBB) - << (!TraversedMBB.IsDone ? ": incomplete\n" - : ": all preds known\n")); -} - void ExecutionDomainFix::enterBasicBlock( const LoopTraversal::TraversedMBBInfo &TraversedMBB) { @@ -272,24 +205,6 @@ : ": all preds known\n")); } -void ReachingDefAnalysis::leaveBasicBlock( - const LoopTraversal::TraversedMBBInfo &TraversedMBB) { - assert(!LiveRegs.empty() && "Must enter basic block first."); - int MBBNumber = TraversedMBB.MBB->getNumber(); - assert(MBBNumber < MBBOutRegsInfos.size() && - "Unexpected basic block number."); - // Save register clearances at end of MBB - used by enterBasicBlock(). - MBBOutRegsInfos[MBBNumber] = LiveRegs; - - // While processing the basic block, we kept `Def` relative to the start - // of the basic block for convenience. However, future use of this information - // only cares about the clearance from the end of the block, so adjust - // everything to be relative to the end of the basic block. - for (int &OutLiveReg : MBBOutRegsInfos[MBBNumber]) - OutLiveReg -= CurInstr; - LiveRegs.clear(); -} - void ExecutionDomainFix::leaveBasicBlock( const LoopTraversal::TraversedMBBInfo &TraversedMBB) { assert(!LiveRegs.empty() && "Must enter basic block first."); @@ -317,76 +232,6 @@ return !DomP.first; } -bool BreakFalseDeps::pickBestRegisterForUndef(MachineInstr *MI, unsigned OpIdx, - unsigned Pref) { - MachineOperand &MO = MI->getOperand(OpIdx); - assert(MO.isUndef() && "Expected undef machine operand"); - - unsigned OriginalReg = MO.getReg(); - - // Update only undef operands that have reg units that are mapped to one root. - for (MCRegUnitIterator Unit(OriginalReg, TRI); Unit.isValid(); ++Unit) { - unsigned NumRoots = 0; - for (MCRegUnitRootIterator Root(*Unit, TRI); Root.isValid(); ++Root) { - NumRoots++; - if (NumRoots > 1) - return false; - } - } - - // Get the undef operand's register class - const TargetRegisterClass *OpRC = - TII->getRegClass(MI->getDesc(), OpIdx, TRI, *MF); - - // If the instruction has a true dependency, we can hide the false depdency - // behind it. - for (MachineOperand &CurrMO : MI->operands()) { - if (!CurrMO.isReg() || CurrMO.isDef() || CurrMO.isUndef() || - !OpRC->contains(CurrMO.getReg())) - continue; - // We found a true dependency - replace the undef register with the true - // dependency. - MO.setReg(CurrMO.getReg()); - return true; - } - - // Go over all registers in the register class and find the register with - // max clearance or clearance higher than Pref. - unsigned MaxClearance = 0; - unsigned MaxClearanceReg = OriginalReg; - ArrayRef Order = RegClassInfo.getOrder(OpRC); - for (MCPhysReg Reg : Order) { - unsigned Clearance = RDA->getClearance(MI, Reg); - if (Clearance <= MaxClearance) - continue; - MaxClearance = Clearance; - MaxClearanceReg = Reg; - - if (MaxClearance > Pref) - break; - } - - // Update the operand if we found a register with better clearance. - if (MaxClearanceReg != OriginalReg) - MO.setReg(MaxClearanceReg); - - return false; -} - -bool BreakFalseDeps::shouldBreakDependence(MachineInstr *MI, unsigned OpIdx, - unsigned Pref) { - unsigned reg = MI->getOperand(OpIdx).getReg(); - unsigned Clearance = RDA->getClearance(MI, reg); - DEBUG(dbgs() << "Clearance: " << Clearance << ", want " << Pref); - - if (Pref > Clearance) { - DEBUG(dbgs() << ": Break dependency.\n"); - return true; - } - DEBUG(dbgs() << ": OK .\n"); - return false; -} - void ExecutionDomainFix::processDefs(MachineInstr *MI, bool Kill) { assert(!MI->isDebugValue() && "Won't process debug values"); const MCInstrDesc &MCID = MI->getDesc(); @@ -409,97 +254,6 @@ } } -void ReachingDefAnalysis::processDefs(MachineInstr *MI) { - assert(!MI->isDebugValue() && "Won't process debug values"); - - int MBBNumber = MI->getParent()->getNumber(); - assert(MBBNumber < MBBReachingDefs.size() && - "Unexpected basic block number."); - const MCInstrDesc &MCID = MI->getDesc(); - for (unsigned i = 0, - e = MI->isVariadic() ? MI->getNumOperands() : MCID.getNumDefs(); - i != e; ++i) { - MachineOperand &MO = MI->getOperand(i); - if (!MO.isReg() || !MO.getReg()) - continue; - if (MO.isUse()) - continue; - for (MCRegUnitIterator Unit(MO.getReg(), TRI); Unit.isValid(); ++Unit) { - // This instruction explicitly defines the current reg unit. - DEBUG(dbgs() << printReg(MO.getReg(), TRI) << ":\t" << CurInstr << '\t' - << *MI); - - // How many instructions since this reg unit was last written? - LiveRegs[*Unit] = CurInstr; - MBBReachingDefs[MBBNumber][*Unit].push_back(CurInstr); - } - } - InstIds[MI] = CurInstr; - ++CurInstr; -} - -void BreakFalseDeps::processDefs(MachineInstr *MI) { - assert(!MI->isDebugValue() && "Won't process debug values"); - - // Break dependence on undef uses. Do this before updating LiveRegs below. - unsigned OpNum; - unsigned Pref = TII->getUndefRegClearance(*MI, OpNum, TRI); - if (Pref) { - bool HadTrueDependency = pickBestRegisterForUndef(MI, OpNum, Pref); - // We don't need to bother trying to break a dependency if this - // instruction has a true dependency on that register through another - // operand - we'll have to wait for it to be available regardless. - if (!HadTrueDependency && shouldBreakDependence(MI, OpNum, Pref)) - UndefReads.push_back(std::make_pair(MI, OpNum)); - } - - const MCInstrDesc &MCID = MI->getDesc(); - for (unsigned i = 0, - e = MI->isVariadic() ? MI->getNumOperands() : MCID.getNumDefs(); - i != e; ++i) { - MachineOperand &MO = MI->getOperand(i); - if (!MO.isReg() || !MO.getReg()) - continue; - if (MO.isUse()) - continue; - // Check clearance before partial register updates. - unsigned Pref = TII->getPartialRegUpdateClearance(*MI, i, TRI); - if (Pref && shouldBreakDependence(MI, i, Pref)) - TII->breakPartialRegDependency(*MI, i, TRI); - } -} - -void BreakFalseDeps::processUndefReads(MachineBasicBlock *MBB) { - if (UndefReads.empty()) - return; - - // Collect this block's live out register units. - LiveRegSet.init(*TRI); - // We do not need to care about pristine registers as they are just preserved - // but not actually used in the function. - LiveRegSet.addLiveOutsNoPristines(*MBB); - - MachineInstr *UndefMI = UndefReads.back().first; - unsigned OpIdx = UndefReads.back().second; - - for (MachineInstr &I : make_range(MBB->rbegin(), MBB->rend())) { - // Update liveness, including the current instruction's defs. - LiveRegSet.stepBackward(I); - - if (UndefMI == &I) { - if (!LiveRegSet.contains(UndefMI->getOperand(OpIdx).getReg())) - TII->breakPartialRegDependency(*UndefMI, OpIdx, TRI); - - UndefReads.pop_back(); - if (UndefReads.empty()) - return; - - UndefMI = UndefReads.back().first; - OpIdx = UndefReads.back().second; - } - } -} - void ExecutionDomainFix::visitHardInstr(MachineInstr *mi, unsigned domain) { // Collapse all uses. for (unsigned i = mi->getDesc().getNumDefs(), @@ -657,92 +411,6 @@ leaveBasicBlock(TraversedMBB); } -void ReachingDefAnalysis::processBasicBlock( - const LoopTraversal::TraversedMBBInfo &TraversedMBB) { - enterBasicBlock(TraversedMBB); - for (MachineInstr &MI : *TraversedMBB.MBB) { - if (!MI.isDebugValue()) - processDefs(&MI); - } - leaveBasicBlock(TraversedMBB); -} - -void BreakFalseDeps::processBasicBlock(MachineBasicBlock *MBB) { - UndefReads.clear(); - // If this block is not done, it makes little sense to make any decisions - // based on clearance information. We need to make a second pass anyway, - // and by then we'll have better information, so we can avoid doing the work - // to try and break dependencies now. - for (MachineInstr &MI : *MBB) { - if (!MI.isDebugValue()) - processDefs(&MI); - } - processUndefReads(MBB); -} - -bool LoopTraversal::isBlockDone(MachineBasicBlock *MBB) { - int MBBNumber = MBB->getNumber(); - assert(MBBNumber < MBBInfos.size() && "Unexpected basic block number."); - return MBBInfos[MBBNumber].PrimaryCompleted && - MBBInfos[MBBNumber].IncomingCompleted == - MBBInfos[MBBNumber].PrimaryIncoming && - MBBInfos[MBBNumber].IncomingProcessed == MBB->pred_size(); -} - -LoopTraversal::TraversalOrder LoopTraversal::traverse(MachineFunction &MF) { - // Initialize the MMBInfos - MBBInfos.assign(MF.getNumBlockIDs(), MBBInfo()); - - MachineBasicBlock *Entry = &*MF.begin(); - ReversePostOrderTraversal RPOT(Entry); - SmallVector Workqueue; - SmallVector MBBTraversalOrder; - for (MachineBasicBlock *MBB : RPOT) { - // N.B: IncomingProcessed and IncomingCompleted were already updated while - // processing this block's predecessors. - int MBBNumber = MBB->getNumber(); - assert(MBBNumber < MBBInfos.size() && "Unexpected basic block number."); - MBBInfos[MBBNumber].PrimaryCompleted = true; - MBBInfos[MBBNumber].PrimaryIncoming = MBBInfos[MBBNumber].IncomingProcessed; - bool Primary = true; - Workqueue.push_back(MBB); - while (!Workqueue.empty()) { - MachineBasicBlock *ActiveMBB = &*Workqueue.back(); - Workqueue.pop_back(); - bool Done = isBlockDone(ActiveMBB); - MBBTraversalOrder.push_back(TraversedMBBInfo(ActiveMBB, Primary, Done)); - for (MachineBasicBlock *Succ : ActiveMBB->successors()) { - int SuccNumber = Succ->getNumber(); - assert(SuccNumber < MBBInfos.size() && - "Unexpected basic block number."); - if (!isBlockDone(Succ)) { - if (Primary) - MBBInfos[SuccNumber].IncomingProcessed++; - if (Done) - MBBInfos[SuccNumber].IncomingCompleted++; - if (isBlockDone(Succ)) - Workqueue.push_back(Succ); - } - } - Primary = false; - } - } - - // We need to go through again and finalize any blocks that are not done yet. - // This is possible if blocks have dead predecessors, so we didn't visit them - // above. - for (MachineBasicBlock *MBB : RPOT) { - if (!isBlockDone(MBB)) - MBBTraversalOrder.push_back(TraversedMBBInfo(MBB, false, true)); - // Don't update successors here. We'll get to them anyway through this - // loop. - } - - MBBInfos.clear(); - - return MBBTraversalOrder; -} - bool ExecutionDomainFix::runOnMachineFunction(MachineFunction &mf) { if (skipFunction(mf.getFunction())) return false; @@ -803,87 +471,3 @@ return false; } - -bool ReachingDefAnalysis::runOnMachineFunction(MachineFunction &mf) { - if (skipFunction(mf.getFunction())) - return false; - MF = &mf; - TII = MF->getSubtarget().getInstrInfo(); - TRI = MF->getSubtarget().getRegisterInfo(); - - LiveRegs.clear(); - NumRegUnits = TRI->getNumRegUnits(); - - MBBReachingDefs.resize(mf.getNumBlockIDs()); - - DEBUG(dbgs() << "********** REACHING DEFINITION ANALYSIS **********\n"); - - // Initialize the MBBOutRegsInfos - MBBOutRegsInfos.resize(mf.getNumBlockIDs()); - - // Traverse the basic blocks. - LoopTraversal Traversal; - LoopTraversal::TraversalOrder TraversedMBBOrder = Traversal.traverse(mf); - for (LoopTraversal::TraversedMBBInfo TraversedMBB : TraversedMBBOrder) { - processBasicBlock(TraversedMBB); - } - - // Sorting all reaching defs found for a ceartin reg unit in a given BB. - for (MBBDefsInfo &MBBDefs : MBBReachingDefs) { - for (MBBRegUnitDefs &RegUnitDefs : MBBDefs) - std::sort(RegUnitDefs.begin(), RegUnitDefs.end()); - } - - return false; -} - -void ReachingDefAnalysis::releaseMemory() { - // Clear the internal vectors. - MBBOutRegsInfos.clear(); - MBBReachingDefs.clear(); - InstIds.clear(); -} - -bool BreakFalseDeps::runOnMachineFunction(MachineFunction &mf) { - if (skipFunction(mf.getFunction())) - return false; - MF = &mf; - TII = MF->getSubtarget().getInstrInfo(); - TRI = MF->getSubtarget().getRegisterInfo(); - RDA = &getAnalysis(); - - RegClassInfo.runOnMachineFunction(mf); - - DEBUG(dbgs() << "********** BREAK FALSE DEPENDENCIES **********\n"); - - // Traverse the basic blocks. - for (MachineBasicBlock &MBB : mf) { - processBasicBlock(&MBB); - } - - return false; -} - -int ReachingDefAnalysis::getReachingDef(MachineInstr *MI, int PhysReg) { - assert(InstIds.count(MI) && "Unexpected machine instuction."); - int InstId = InstIds[MI]; - int DefRes = ReachingDedDefaultVal; - int MBBNumber = MI->getParent()->getNumber(); - assert(MBBNumber < MBBReachingDefs.size() && - "Unexpected basic block number."); - int LatestDef = ReachingDedDefaultVal; - for (MCRegUnitIterator Unit(PhysReg, TRI); Unit.isValid(); ++Unit) { - for (int Def : MBBReachingDefs[MBBNumber][*Unit]) { - if (Def >= InstId) - break; - DefRes = Def; - } - LatestDef = std::max(LatestDef, DefRes); - } - return LatestDef; -} - -int ReachingDefAnalysis::getClearance(MachineInstr *MI, MCPhysReg PhysReg) { - assert(InstIds.count(MI) && "Unexpected machine instuction."); - return InstIds[MI] - getReachingDef(MI, PhysReg); -} Index: llvm/trunk/lib/CodeGen/LoopTraversal.cpp =================================================================== --- llvm/trunk/lib/CodeGen/LoopTraversal.cpp +++ llvm/trunk/lib/CodeGen/LoopTraversal.cpp @@ -0,0 +1,77 @@ +//===- LoopTraversal.cpp - Optimal basic block traversal order --*- C++ -*-===// +// +// The LLVM Compiler Infrastructure +// +// This file is distributed under the University of Illinois Open Source +// License. See LICENSE.TXT for details. +// +//===----------------------------------------------------------------------===// + +#include "llvm/CodeGen/LoopTraversal.h" +#include "llvm/ADT/PostOrderIterator.h" +#include "llvm/CodeGen/MachineFunction.h" + +using namespace llvm; + +bool LoopTraversal::isBlockDone(MachineBasicBlock *MBB) { + int MBBNumber = MBB->getNumber(); + assert(MBBNumber < MBBInfos.size() && "Unexpected basic block number."); + return MBBInfos[MBBNumber].PrimaryCompleted && + MBBInfos[MBBNumber].IncomingCompleted == + MBBInfos[MBBNumber].PrimaryIncoming && + MBBInfos[MBBNumber].IncomingProcessed == MBB->pred_size(); +} + +LoopTraversal::TraversalOrder LoopTraversal::traverse(MachineFunction &MF) { + // Initialize the MMBInfos + MBBInfos.assign(MF.getNumBlockIDs(), MBBInfo()); + + MachineBasicBlock *Entry = &*MF.begin(); + ReversePostOrderTraversal RPOT(Entry); + SmallVector Workqueue; + SmallVector MBBTraversalOrder; + for (MachineBasicBlock *MBB : RPOT) { + // N.B: IncomingProcessed and IncomingCompleted were already updated while + // processing this block's predecessors. + int MBBNumber = MBB->getNumber(); + assert(MBBNumber < MBBInfos.size() && "Unexpected basic block number."); + MBBInfos[MBBNumber].PrimaryCompleted = true; + MBBInfos[MBBNumber].PrimaryIncoming = MBBInfos[MBBNumber].IncomingProcessed; + bool Primary = true; + Workqueue.push_back(MBB); + while (!Workqueue.empty()) { + MachineBasicBlock *ActiveMBB = &*Workqueue.back(); + Workqueue.pop_back(); + bool Done = isBlockDone(ActiveMBB); + MBBTraversalOrder.push_back(TraversedMBBInfo(ActiveMBB, Primary, Done)); + for (MachineBasicBlock *Succ : ActiveMBB->successors()) { + int SuccNumber = Succ->getNumber(); + assert(SuccNumber < MBBInfos.size() && + "Unexpected basic block number."); + if (!isBlockDone(Succ)) { + if (Primary) + MBBInfos[SuccNumber].IncomingProcessed++; + if (Done) + MBBInfos[SuccNumber].IncomingCompleted++; + if (isBlockDone(Succ)) + Workqueue.push_back(Succ); + } + } + Primary = false; + } + } + + // We need to go through again and finalize any blocks that are not done yet. + // This is possible if blocks have dead predecessors, so we didn't visit them + // above. + for (MachineBasicBlock *MBB : RPOT) { + if (!isBlockDone(MBB)) + MBBTraversalOrder.push_back(TraversedMBBInfo(MBB, false, true)); + // Don't update successors here. We'll get to them anyway through this + // loop. + } + + MBBInfos.clear(); + + return MBBTraversalOrder; +} Index: llvm/trunk/lib/CodeGen/ReachingDefAnalysis.cpp =================================================================== --- llvm/trunk/lib/CodeGen/ReachingDefAnalysis.cpp +++ llvm/trunk/lib/CodeGen/ReachingDefAnalysis.cpp @@ -0,0 +1,195 @@ +//===---- ReachingDefAnalysis.cpp - Reaching Def Analysis ---*- C++ -*-----===// +// +// The LLVM Compiler Infrastructure +// +// This file is distributed under the University of Illinois Open Source +// License. See LICENSE.TXT for details. +// +//===----------------------------------------------------------------------===// + +#include "llvm/CodeGen/ReachingDefAnalysis.h" +#include "llvm/CodeGen/TargetRegisterInfo.h" +#include "llvm/CodeGen/TargetSubtargetInfo.h" + +using namespace llvm; + +#define DEBUG_TYPE "reaching-deps-analysis" + +char ReachingDefAnalysis::ID = 0; +INITIALIZE_PASS(ReachingDefAnalysis, DEBUG_TYPE, "ReachingDefAnalysis", false, + true) + +void ReachingDefAnalysis::enterBasicBlock( + const LoopTraversal::TraversedMBBInfo &TraversedMBB) { + + MachineBasicBlock *MBB = TraversedMBB.MBB; + int MBBNumber = MBB->getNumber(); + assert(MBBNumber < MBBReachingDefs.size() && + "Unexpected basic block number."); + MBBReachingDefs[MBBNumber].resize(NumRegUnits); + + // Reset instruction counter in each basic block. + CurInstr = 0; + + // Set up LiveRegs to represent registers entering MBB. + // Default values are 'nothing happened a long time ago'. + if (LiveRegs.empty()) + LiveRegs.assign(NumRegUnits, ReachingDedDefaultVal); + + // This is the entry block. + if (MBB->pred_empty()) { + for (const auto &LI : MBB->liveins()) { + for (MCRegUnitIterator Unit(LI.PhysReg, TRI); Unit.isValid(); ++Unit) { + // Treat function live-ins as if they were defined just before the first + // instruction. Usually, function arguments are set up immediately + // before the call. + LiveRegs[*Unit] = -1; + MBBReachingDefs[MBBNumber][*Unit].push_back(LiveRegs[*Unit]); + } + } + DEBUG(dbgs() << printMBBReference(*MBB) << ": entry\n"); + return; + } + + // Try to coalesce live-out registers from predecessors. + for (MachineBasicBlock *pred : MBB->predecessors()) { + assert(pred->getNumber() < MBBOutRegsInfos.size() && + "Should have pre-allocated MBBInfos for all MBBs"); + const LiveRegsDefInfo &Incoming = MBBOutRegsInfos[pred->getNumber()]; + // Incoming is null if this is a backedge from a BB + // we haven't processed yet + if (Incoming.empty()) + continue; + + for (unsigned Unit = 0; Unit != NumRegUnits; ++Unit) { + // Use the most recent predecessor def for each register. + LiveRegs[Unit] = std::max(LiveRegs[Unit], Incoming[Unit]); + if ((LiveRegs[Unit] != ReachingDedDefaultVal)) + MBBReachingDefs[MBBNumber][Unit].push_back(LiveRegs[Unit]); + } + } + + DEBUG(dbgs() << printMBBReference(*MBB) + << (!TraversedMBB.IsDone ? ": incomplete\n" + : ": all preds known\n")); +} + +void ReachingDefAnalysis::leaveBasicBlock( + const LoopTraversal::TraversedMBBInfo &TraversedMBB) { + assert(!LiveRegs.empty() && "Must enter basic block first."); + int MBBNumber = TraversedMBB.MBB->getNumber(); + assert(MBBNumber < MBBOutRegsInfos.size() && + "Unexpected basic block number."); + // Save register clearances at end of MBB - used by enterBasicBlock(). + MBBOutRegsInfos[MBBNumber] = LiveRegs; + + // While processing the basic block, we kept `Def` relative to the start + // of the basic block for convenience. However, future use of this information + // only cares about the clearance from the end of the block, so adjust + // everything to be relative to the end of the basic block. + for (int &OutLiveReg : MBBOutRegsInfos[MBBNumber]) + OutLiveReg -= CurInstr; + LiveRegs.clear(); +} + +void ReachingDefAnalysis::processDefs(MachineInstr *MI) { + assert(!MI->isDebugValue() && "Won't process debug values"); + + int MBBNumber = MI->getParent()->getNumber(); + assert(MBBNumber < MBBReachingDefs.size() && + "Unexpected basic block number."); + const MCInstrDesc &MCID = MI->getDesc(); + for (unsigned i = 0, + e = MI->isVariadic() ? MI->getNumOperands() : MCID.getNumDefs(); + i != e; ++i) { + MachineOperand &MO = MI->getOperand(i); + if (!MO.isReg() || !MO.getReg()) + continue; + if (MO.isUse()) + continue; + for (MCRegUnitIterator Unit(MO.getReg(), TRI); Unit.isValid(); ++Unit) { + // This instruction explicitly defines the current reg unit. + DEBUG(dbgs() << printReg(MO.getReg(), TRI) << ":\t" << CurInstr << '\t' + << *MI); + + // How many instructions since this reg unit was last written? + LiveRegs[*Unit] = CurInstr; + MBBReachingDefs[MBBNumber][*Unit].push_back(CurInstr); + } + } + InstIds[MI] = CurInstr; + ++CurInstr; +} + +void ReachingDefAnalysis::processBasicBlock( + const LoopTraversal::TraversedMBBInfo &TraversedMBB) { + enterBasicBlock(TraversedMBB); + for (MachineInstr &MI : *TraversedMBB.MBB) { + if (!MI.isDebugValue()) + processDefs(&MI); + } + leaveBasicBlock(TraversedMBB); +} + +bool ReachingDefAnalysis::runOnMachineFunction(MachineFunction &mf) { + if (skipFunction(mf.getFunction())) + return false; + MF = &mf; + TRI = MF->getSubtarget().getRegisterInfo(); + + LiveRegs.clear(); + NumRegUnits = TRI->getNumRegUnits(); + + MBBReachingDefs.resize(mf.getNumBlockIDs()); + + DEBUG(dbgs() << "********** REACHING DEFINITION ANALYSIS **********\n"); + + // Initialize the MBBOutRegsInfos + MBBOutRegsInfos.resize(mf.getNumBlockIDs()); + + // Traverse the basic blocks. + LoopTraversal Traversal; + LoopTraversal::TraversalOrder TraversedMBBOrder = Traversal.traverse(mf); + for (LoopTraversal::TraversedMBBInfo TraversedMBB : TraversedMBBOrder) { + processBasicBlock(TraversedMBB); + } + + // Sorting all reaching defs found for a ceartin reg unit in a given BB. + for (MBBDefsInfo &MBBDefs : MBBReachingDefs) { + for (MBBRegUnitDefs &RegUnitDefs : MBBDefs) + std::sort(RegUnitDefs.begin(), RegUnitDefs.end()); + } + + return false; +} + +void ReachingDefAnalysis::releaseMemory() { + // Clear the internal vectors. + MBBOutRegsInfos.clear(); + MBBReachingDefs.clear(); + InstIds.clear(); +} + +int ReachingDefAnalysis::getReachingDef(MachineInstr *MI, int PhysReg) { + assert(InstIds.count(MI) && "Unexpected machine instuction."); + int InstId = InstIds[MI]; + int DefRes = ReachingDedDefaultVal; + int MBBNumber = MI->getParent()->getNumber(); + assert(MBBNumber < MBBReachingDefs.size() && + "Unexpected basic block number."); + int LatestDef = ReachingDedDefaultVal; + for (MCRegUnitIterator Unit(PhysReg, TRI); Unit.isValid(); ++Unit) { + for (int Def : MBBReachingDefs[MBBNumber][*Unit]) { + if (Def >= InstId) + break; + DefRes = Def; + } + LatestDef = std::max(LatestDef, DefRes); + } + return LatestDef; +} + +int ReachingDefAnalysis::getClearance(MachineInstr *MI, MCPhysReg PhysReg) { + assert(InstIds.count(MI) && "Unexpected machine instuction."); + return InstIds[MI] - getReachingDef(MI, PhysReg); +} Index: llvm/trunk/lib/Target/ARM/ARMTargetMachine.cpp =================================================================== --- llvm/trunk/lib/Target/ARM/ARMTargetMachine.cpp +++ llvm/trunk/lib/Target/ARM/ARMTargetMachine.cpp @@ -466,7 +466,7 @@ addPass(createARMLoadStoreOptimizationPass()); addPass(new ARMExecutionDomainFix()); - addPass(new BreakFalseDeps()); + addPass(createBreakFalseDeps()); } // Expand some pseudo instructions into multiple instructions to allow Index: llvm/trunk/lib/Target/X86/X86TargetMachine.cpp =================================================================== --- llvm/trunk/lib/Target/X86/X86TargetMachine.cpp +++ llvm/trunk/lib/Target/X86/X86TargetMachine.cpp @@ -446,7 +446,7 @@ void X86PassConfig::addPreEmitPass() { if (getOptLevel() != CodeGenOpt::None) { addPass(new X86ExecutionDomainFix()); - addPass(new BreakFalseDeps()); + addPass(createBreakFalseDeps()); } addPass(createX86IndirectBranchTrackingPass());