X-Git-Url: http://demsky.eecs.uci.edu/git/?a=blobdiff_plain;f=lib%2FCodeGen%2FRegisterCoalescer.cpp;h=1e1a42451485223c9ef68087ca05d31eab73d2f4;hb=021e3b6444e9179751002db7b20de96455e03171;hp=5ec0aece1e5db165cf99d7a79d8da89d70c308f1;hpb=2344abc939b29ab80bbd247995a0ceb2efa5938b;p=oota-llvm.git diff --git a/lib/CodeGen/RegisterCoalescer.cpp b/lib/CodeGen/RegisterCoalescer.cpp index 5ec0aece1e5..1e1a4245148 100644 --- a/lib/CodeGen/RegisterCoalescer.cpp +++ b/lib/CodeGen/RegisterCoalescer.cpp @@ -16,36 +16,31 @@ #define DEBUG_TYPE "regalloc" #include "RegisterCoalescer.h" #include "LiveDebugVariables.h" -#include "VirtRegMap.h" - -#include "llvm/Pass.h" -#include "llvm/Value.h" #include "llvm/ADT/OwningPtr.h" #include "llvm/ADT/STLExtras.h" #include "llvm/ADT/SmallSet.h" #include "llvm/ADT/Statistic.h" #include "llvm/Analysis/AliasAnalysis.h" #include "llvm/CodeGen/LiveIntervalAnalysis.h" -#include "llvm/CodeGen/LiveIntervalAnalysis.h" #include "llvm/CodeGen/LiveRangeEdit.h" #include "llvm/CodeGen/MachineFrameInfo.h" #include "llvm/CodeGen/MachineInstr.h" -#include "llvm/CodeGen/MachineInstr.h" #include "llvm/CodeGen/MachineLoopInfo.h" #include "llvm/CodeGen/MachineRegisterInfo.h" -#include "llvm/CodeGen/MachineRegisterInfo.h" #include "llvm/CodeGen/Passes.h" #include "llvm/CodeGen/RegisterClassInfo.h" +#include "llvm/CodeGen/VirtRegMap.h" +#include "llvm/Pass.h" #include "llvm/Support/CommandLine.h" #include "llvm/Support/Debug.h" #include "llvm/Support/ErrorHandling.h" #include "llvm/Support/raw_ostream.h" #include "llvm/Target/TargetInstrInfo.h" -#include "llvm/Target/TargetInstrInfo.h" #include "llvm/Target/TargetMachine.h" #include "llvm/Target/TargetOptions.h" #include "llvm/Target/TargetRegisterInfo.h" #include "llvm/Target/TargetSubtargetInfo.h" +#include "llvm/Value.h" #include #include using namespace llvm; @@ -65,10 +60,9 @@ EnableJoining("join-liveintervals", cl::init(true)); // Temporary flag to test critical edge unsplitting. -static cl::opt +static cl::opt EnableJoinSplits("join-splitedges", - cl::desc("Coalesce copies on split edges (default=subtarget)"), - cl::init(cl::BOU_UNSET), cl::Hidden); + cl::desc("Coalesce copies on split edges (default=subtarget)"), cl::Hidden); // Temporary flag to test global copy optimization. static cl::opt @@ -179,7 +173,7 @@ namespace { MachineInstr *CopyMI); /// canJoinPhys - Return true if a physreg copy should be joined. - bool canJoinPhys(CoalescerPair &CP); + bool canJoinPhys(const CoalescerPair &CP); /// updateRegDefsUses - Replace all defs and uses of SrcReg to DstReg and /// update the subregister number if it is not zero. If DstReg is a @@ -892,8 +886,17 @@ void RegisterCoalescer::updateRegDefsUses(unsigned SrcReg, // Update LiveDebugVariables. LDV->renameRegister(SrcReg, DstReg, SubIdx); + SmallPtrSet Visited; for (MachineRegisterInfo::reg_iterator I = MRI->reg_begin(SrcReg); MachineInstr *UseMI = I.skipInstruction();) { + // Each instruction can only be rewritten once because sub-register + // composition is not always idempotent. When SrcReg != DstReg, rewriting + // the UseMI operands removes them from the SrcReg use-def chain, but when + // SrcReg is DstReg we could encounter UseMI twice if it has multiple + // operands mentioning the virtual register. + if (SrcReg == DstReg && !Visited.insert(UseMI)) + continue; + SmallVector Ops; bool Reads, Writes; tie(Reads, Writes) = UseMI->readsWritesVirtualRegister(SrcReg, &Ops); @@ -929,7 +932,7 @@ void RegisterCoalescer::updateRegDefsUses(unsigned SrcReg, } /// canJoinPhys - Return true if a copy involving a physreg should be joined. -bool RegisterCoalescer::canJoinPhys(CoalescerPair &CP) { +bool RegisterCoalescer::canJoinPhys(const CoalescerPair &CP) { /// Always join simple intervals that are defined by a single copy from a /// reserved register. This doesn't increase register pressure, so it is /// always beneficial. @@ -1937,46 +1940,41 @@ bool RegisterCoalescer::joinIntervals(CoalescerPair &CP) { } namespace { - // Information concerning MBB coalescing priority. - struct MBBPriorityInfo { - MachineBasicBlock *MBB; - unsigned Depth; - bool IsSplit; - - MBBPriorityInfo(MachineBasicBlock *mbb, unsigned depth, bool issplit) - : MBB(mbb), Depth(depth), IsSplit(issplit) {} - }; - - // MBBPriorityCompare - Comparison predicate that sorts first based on the - // loop depth of the basic block (the unsigned), and then on the MBB number. - // - // EnableGlobalCopies assumes that the primary sort key is loop depth. - struct MBBPriorityCompare { - bool JoinSplitEdges; - - MBBPriorityCompare(bool joinsplits): JoinSplitEdges(joinsplits) {} - - bool operator()(const MBBPriorityInfo &LHS, - const MBBPriorityInfo &RHS) const { - // Deeper loops first - if (LHS.Depth != RHS.Depth) - return LHS.Depth > RHS.Depth; - - // Try to unsplit critical edges next. - if (JoinSplitEdges && LHS.IsSplit != RHS.IsSplit) - return LHS.IsSplit; - - // Prefer blocks that are more connected in the CFG. This takes care of - // the most difficult copies first while intervals are short. - unsigned cl = LHS.MBB->pred_size() + LHS.MBB->succ_size(); - unsigned cr = RHS.MBB->pred_size() + RHS.MBB->succ_size(); - if (cl != cr) - return cl > cr; +// Information concerning MBB coalescing priority. +struct MBBPriorityInfo { + MachineBasicBlock *MBB; + unsigned Depth; + bool IsSplit; + + MBBPriorityInfo(MachineBasicBlock *mbb, unsigned depth, bool issplit) + : MBB(mbb), Depth(depth), IsSplit(issplit) {} +}; +} - // As a last resort, sort by block number. - return LHS.MBB->getNumber() < RHS.MBB->getNumber(); - } - }; +// C-style comparator that sorts first based on the loop depth of the basic +// block (the unsigned), and then on the MBB number. +// +// EnableGlobalCopies assumes that the primary sort key is loop depth. +static int compareMBBPriority(const void *L, const void *R) { + const MBBPriorityInfo *LHS = static_cast(L); + const MBBPriorityInfo *RHS = static_cast(R); + // Deeper loops first + if (LHS->Depth != RHS->Depth) + return LHS->Depth > RHS->Depth ? -1 : 1; + + // Try to unsplit critical edges next. + if (LHS->IsSplit != RHS->IsSplit) + return LHS->IsSplit ? -1 : 1; + + // Prefer blocks that are more connected in the CFG. This takes care of + // the most difficult copies first while intervals are short. + unsigned cl = LHS->MBB->pred_size() + LHS->MBB->succ_size(); + unsigned cr = RHS->MBB->pred_size() + RHS->MBB->succ_size(); + if (cl != cr) + return cl > cr ? -1 : 1; + + // As a last resort, sort by block number. + return LHS->MBB->getNumber() < RHS->MBB->getNumber() ? -1 : 1; } /// \returns true if the given copy uses or defines a local live range. @@ -2069,19 +2067,22 @@ void RegisterCoalescer::joinAllIntervals() { assert(WorkList.empty() && LocalWorkList.empty() && "Old data still around."); std::vector MBBs; + MBBs.reserve(MF->size()); for (MachineFunction::iterator I = MF->begin(), E = MF->end();I != E;++I){ MachineBasicBlock *MBB = I; MBBs.push_back(MBBPriorityInfo(MBB, Loops->getLoopDepth(MBB), - isSplitEdge(MBB))); + JoinSplitEdges && isSplitEdge(MBB))); } - std::sort(MBBs.begin(), MBBs.end(), MBBPriorityCompare(JoinSplitEdges)); + array_pod_sort(MBBs.begin(), MBBs.end(), compareMBBPriority); // Coalesce intervals in MBB priority order. unsigned CurrDepth = UINT_MAX; for (unsigned i = 0, e = MBBs.size(); i != e; ++i) { // Try coalescing the collected local copies for deeper loops. - if (JoinGlobalCopies && MBBs[i].Depth < CurrDepth) + if (JoinGlobalCopies && MBBs[i].Depth < CurrDepth) { coalesceLocals(); + CurrDepth = MBBs[i].Depth; + } copyCoalesceInMBB(MBBs[i].MBB); } coalesceLocals(); @@ -2116,10 +2117,10 @@ bool RegisterCoalescer::runOnMachineFunction(MachineFunction &fn) { else JoinGlobalCopies = (EnableGlobalCopies == cl::BOU_TRUE); - if (EnableJoinSplits == cl::BOU_UNSET) - JoinSplitEdges = ST.enableMachineScheduler(); - else - JoinSplitEdges = (EnableJoinSplits == cl::BOU_TRUE); + // The MachineScheduler does not currently require JoinSplitEdges. This will + // either be enabled unconditionally or replaced by a more general live range + // splitting optimization. + JoinSplitEdges = EnableJoinSplits; DEBUG(dbgs() << "********** SIMPLE REGISTER COALESCING **********\n" << "********** Function: " << MF->getName() << '\n');