diff options
| -rw-r--r-- | include/llvm/InitializePasses.h | 1 | ||||
| -rw-r--r-- | lib/CodeGen/CMakeLists.txt | 1 | ||||
| -rw-r--r-- | lib/CodeGen/LiveRegMatrix.cpp | 152 | ||||
| -rw-r--r-- | lib/CodeGen/LiveRegMatrix.h | 143 |
4 files changed, 297 insertions, 0 deletions
diff --git a/include/llvm/InitializePasses.h b/include/llvm/InitializePasses.h index 67f2fa496d..1b8bd79eca 100644 --- a/include/llvm/InitializePasses.h +++ b/include/llvm/InitializePasses.h @@ -136,6 +136,7 @@ void initializeLibCallAliasAnalysisPass(PassRegistry&); void initializeLintPass(PassRegistry&); void initializeLiveDebugVariablesPass(PassRegistry&); void initializeLiveIntervalsPass(PassRegistry&); +void initializeLiveRegMatrixPass(PassRegistry&); void initializeLiveStacksPass(PassRegistry&); void initializeLiveVariablesPass(PassRegistry&); void initializeLoaderPassPass(PassRegistry&); diff --git a/lib/CodeGen/CMakeLists.txt b/lib/CodeGen/CMakeLists.txt index 855fa0cbfd..34947cee32 100644 --- a/lib/CodeGen/CMakeLists.txt +++ b/lib/CodeGen/CMakeLists.txt @@ -30,6 +30,7 @@ add_llvm_library(LLVMCodeGen LiveInterval.cpp LiveIntervalAnalysis.cpp LiveIntervalUnion.cpp + LiveRegMatrix.cpp LiveStackAnalysis.cpp LiveVariables.cpp LiveRangeCalc.cpp diff --git a/lib/CodeGen/LiveRegMatrix.cpp b/lib/CodeGen/LiveRegMatrix.cpp new file mode 100644 index 0000000000..61e1432b0e --- /dev/null +++ b/lib/CodeGen/LiveRegMatrix.cpp @@ -0,0 +1,152 @@ +//===-- LiveRegMatrix.cpp - Track register interference -------------------===// +// +// The LLVM Compiler Infrastructure +// +// This file is distributed under the University of Illinois Open Source +// License. See LICENSE.TXT for details. +// +//===----------------------------------------------------------------------===// +// +// This file defines the LiveRegMatrix analysis pass. +// +//===----------------------------------------------------------------------===// + +#define DEBUG_TYPE "regalloc" +#include "LiveRegMatrix.h" +#include "VirtRegMap.h" +#include "llvm/ADT/Statistic.h" +#include "llvm/CodeGen/MachineRegisterInfo.h" +#include "llvm/CodeGen/LiveIntervalAnalysis.h" +#include "llvm/Target/TargetMachine.h" +#include "llvm/Target/TargetRegisterInfo.h" +#include "llvm/Support/Debug.h" +#include "llvm/Support/raw_ostream.h" + +using namespace llvm; + +STATISTIC(NumAssigned , "Number of registers assigned"); +STATISTIC(NumUnassigned , "Number of registers unassigned"); + +char LiveRegMatrix::ID = 0; +INITIALIZE_PASS_BEGIN(LiveRegMatrix, "liveregmatrix", + "Live Register Matrix", false, false) +INITIALIZE_PASS_DEPENDENCY(LiveIntervals) +INITIALIZE_PASS_DEPENDENCY(VirtRegMap) +INITIALIZE_PASS_END(LiveRegMatrix, "liveregmatrix", + "Live Register Matrix", false, false) + +LiveRegMatrix::LiveRegMatrix() : MachineFunctionPass(ID), + UserTag(0), RegMaskTag(0), RegMaskVirtReg(0) {} + +void LiveRegMatrix::getAnalysisUsage(AnalysisUsage &AU) const { + AU.setPreservesAll(); + AU.addRequiredTransitive<LiveIntervals>(); + AU.addRequiredTransitive<VirtRegMap>(); + MachineFunctionPass::getAnalysisUsage(AU); +} + +bool LiveRegMatrix::runOnMachineFunction(MachineFunction &MF) { + TRI = MF.getTarget().getRegisterInfo(); + MRI = &MF.getRegInfo(); + LIS = &getAnalysis<LiveIntervals>(); + VRM = &getAnalysis<VirtRegMap>(); + + unsigned NumRegUnits = TRI->getNumRegUnits(); + if (NumRegUnits != Matrix.size()) + Queries.reset(new LiveIntervalUnion::Query[NumRegUnits]); + Matrix.init(LIUAlloc, NumRegUnits); + + // Make sure no stale queries get reused. + invalidateVirtRegs(); + return false; +} + +void LiveRegMatrix::releaseMemory() { + for (unsigned i = 0, e = Matrix.size(); i != e; ++i) { + Matrix[i].clear(); + Queries[i].clear(); + } +} + +void LiveRegMatrix::assign(LiveInterval &VirtReg, unsigned PhysReg) { + DEBUG(dbgs() << "assigning " << PrintReg(VirtReg.reg, TRI) + << " to " << PrintReg(PhysReg, TRI) << ':'); + assert(!VRM->hasPhys(VirtReg.reg) && "Duplicate VirtReg assignment"); + VRM->assignVirt2Phys(VirtReg.reg, PhysReg); + MRI->setPhysRegUsed(PhysReg); + for (MCRegUnitIterator Units(PhysReg, TRI); Units.isValid(); ++Units) { + DEBUG(dbgs() << ' ' << PrintRegUnit(*Units, TRI)); + Matrix[*Units].unify(VirtReg); + } + ++NumAssigned; + DEBUG(dbgs() << '\n'); +} + +void LiveRegMatrix::unassign(LiveInterval &VirtReg) { + unsigned PhysReg = VRM->getPhys(VirtReg.reg); + DEBUG(dbgs() << "unassigning " << PrintReg(VirtReg.reg, TRI) + << " from " << PrintReg(PhysReg, TRI) << ':'); + VRM->clearVirt(VirtReg.reg); + for (MCRegUnitIterator Units(PhysReg, TRI); Units.isValid(); ++Units) { + DEBUG(dbgs() << ' ' << PrintRegUnit(*Units, TRI)); + Matrix[*Units].extract(VirtReg); + } + ++NumUnassigned; + DEBUG(dbgs() << '\n'); +} + +bool LiveRegMatrix::checkRegMaskInterference(LiveInterval &VirtReg, + unsigned PhysReg) { + // Check if the cached information is valid. + // The same BitVector can be reused for all PhysRegs. + // We could cache multiple VirtRegs if it becomes necessary. + if (RegMaskVirtReg != VirtReg.reg || RegMaskTag != UserTag) { + RegMaskVirtReg = VirtReg.reg; + RegMaskTag = UserTag; + RegMaskUsable.clear(); + LIS->checkRegMaskInterference(VirtReg, RegMaskUsable); + } + + // The BitVector is indexed by PhysReg, not register unit. + // Regmask interference is more fine grained than regunits. + // For example, a Win64 call can clobber %ymm8 yet preserve %xmm8. + return !RegMaskUsable.empty() && !RegMaskUsable.test(PhysReg); +} + +bool LiveRegMatrix::checkRegUnitInterference(LiveInterval &VirtReg, + unsigned PhysReg) { + if (VirtReg.empty()) + return false; + for (MCRegUnitIterator Units(PhysReg, TRI); Units.isValid(); ++Units) + if (VirtReg.overlaps(LIS->getRegUnit(*Units))) + return true; + return false; +} + +LiveIntervalUnion::Query &LiveRegMatrix::query(LiveInterval &VirtReg, + unsigned RegUnit) { + LiveIntervalUnion::Query &Q = Queries[RegUnit]; + Q.init(UserTag, &VirtReg, &Matrix[RegUnit]); + return Q; +} + +LiveRegMatrix::InterferenceKind +LiveRegMatrix::checkInterference(LiveInterval &VirtReg, unsigned PhysReg) { + if (VirtReg.empty()) + return IK_Free; + + // Regmask interference is the fastest check. + if (checkRegMaskInterference(VirtReg, PhysReg)) + return IK_RegMask; + + // Check for fixed interference. + if (checkRegUnitInterference(VirtReg, PhysReg)) + return IK_RegUnit; + + // Check the matrix for virtual register interference. + for (MCRegUnitIterator Units(PhysReg, TRI); Units.isValid(); ++Units) + if (query(VirtReg, *Units).checkInterference()) + return IK_VirtReg; + + return IK_Free; +} diff --git a/lib/CodeGen/LiveRegMatrix.h b/lib/CodeGen/LiveRegMatrix.h new file mode 100644 index 0000000000..4c3e7d4782 --- /dev/null +++ b/lib/CodeGen/LiveRegMatrix.h @@ -0,0 +1,143 @@ +//===-- LiveRegMatrix.h - Track register interference ---------*- C++ -*---===// +// +// The LLVM Compiler Infrastructure +// +// This file is distributed under the University of Illinois Open Source +// License. See LICENSE.TXT for details. +// +//===----------------------------------------------------------------------===// +// +// The LiveRegMatrix analysis pass keeps track of virtual register interference +// along two dimensions: Slot indexes and register units. The matrix is used by +// register allocators to ensure that no interfering virtual registers get +// assigned to overlapping physical registers. +// +// Register units are defined in MCRegisterInfo.h, they represent the smallest +// unit of interference when dealing with overlapping physical registers. The +// LiveRegMatrix is represented as a LiveIntervalUnion per register unit. When +// a virtual register is assigned to a physicval register, the live range for +// the virtual register is inserted into the LiveIntervalUnion for each regunit +// in the physreg. +// +//===----------------------------------------------------------------------===// + +#ifndef LLVM_CODEGEN_LIVEREGMATRIX_H +#define LLVM_CODEGEN_LIVEREGMATRIX_H + +#include "LiveIntervalUnion.h" +#include "llvm/ADT/BitVector.h" +#include "llvm/ADT/OwningPtr.h" +#include "llvm/CodeGen/MachineFunctionPass.h" + +namespace llvm { + +class LiveInterval; +class LiveIntervalAnalysis; +class MachineRegisterInfo; +class TargetRegisterInfo; +class VirtRegMap; + +class LiveRegMatrix : public MachineFunctionPass { + const TargetRegisterInfo *TRI; + MachineRegisterInfo *MRI; + LiveIntervals *LIS; + VirtRegMap *VRM; + + // UserTag changes whenever virtual registers have been modified. + unsigned UserTag; + + // The matrix is represented as a LiveIntervalUnion per register unit. + LiveIntervalUnion::Allocator LIUAlloc; + LiveIntervalUnion::Array Matrix; + + // Cached queries per register unit. + OwningArrayPtr<LiveIntervalUnion::Query> Queries; + + // Cached register mask interference info. + unsigned RegMaskTag; + unsigned RegMaskVirtReg; + BitVector RegMaskUsable; + + // MachineFunctionPass boilerplate. + virtual void getAnalysisUsage(AnalysisUsage&) const; + virtual bool runOnMachineFunction(MachineFunction&); + virtual void releaseMemory(); +public: + static char ID; + LiveRegMatrix(); + + //===--------------------------------------------------------------------===// + // High-level interface. + //===--------------------------------------------------------------------===// + // + // Check for interference before assigning virtual registers to physical + // registers. + // + + /// Invalidate cached interference queries after modifying virtual register + /// live ranges. Interference checks may return stale information unless + /// caches are invalidated. + void invalidateVirtRegs() { ++UserTag; } + + enum InterferenceKind { + /// No interference, go ahead and assign. + IK_Free = 0, + + /// Virtual register interference. There are interfering virtual registers + /// assigned to PhysReg or its aliases. This interference could be resolved + /// by unassigning those other virtual registers. + IK_VirtReg, + + /// Register unit interference. A fixed live range is in the way, typically + /// argument registers for a call. This can't be resolved by unassigning + /// other virtual registers. + IK_RegUnit, + + /// RegMask interference. The live range is crossing an instruction with a + /// regmask operand that doesn't preserve PhysReg. This typically means + /// VirtReg is live across a call, and PhysReg isn't call-preserved. + IK_RegMask + }; + + /// Check for interference before assigning VirtReg to PhysReg. + /// If this function returns IK_Free, it is legal to assign(VirtReg, PhysReg). + /// When there is more than one kind of interference, the InterferenceKind + /// with the highest enum value is returned. + InterferenceKind checkInterference(LiveInterval &VirtReg, unsigned PhysReg); + + /// Assign VirtReg to PhysReg. + /// This will mark VirtReg's live range as occupied in the LiveRegMatrix and + /// update VirtRegMap. The live range is expected to be available in PhysReg. + void assign(LiveInterval &VirtReg, unsigned PhysReg); + + /// Unassign VirtReg from its PhysReg. + /// Assuming that VirtReg was previously assigned to a PhysReg, this undoes + /// the assignment and updates VirtRegMap accordingly. + void unassign(LiveInterval &VirtReg); + + //===--------------------------------------------------------------------===// + // Low-level interface. + //===--------------------------------------------------------------------===// + // + // Provide access to the underlying LiveIntervalUnions. + // + + /// Check for regmask interference only. + /// Return true if VirtReg crosses a regmask operand that clobbers PhysReg. + bool checkRegMaskInterference(LiveInterval &VirtReg, unsigned PhysReg); + + /// Check for regunit interference only. + /// Return true if VirtReg overlaps a fixed assignment of one of PhysRegs's + /// register units. + bool checkRegUnitInterference(LiveInterval &VirtReg, unsigned PhysReg); + + /// Query a line of the assigned virtual register matrix directly. + /// Use MCRegUnitIterator to enumerate all regunits in the desired PhysReg. + /// This returns a reference to an internal Query data structure that is only + /// valid until the next query() call. + LiveIntervalUnion::Query &query(LiveInterval &VirtReg, unsigned RegUnit); +}; + +} // end namespace llvm + +#endif // LLVM_CODEGEN_LIVEREGMATRIX_H |