Hi all,This is meant for a code review and NOT for submission (just yet). This is my implementation of Chow & Hennesey's Priority-Based Coloring Approach to Register Allocation. It's still in the experimental stages (though it compiles the tests). I'd like people to look at it and let me know what you think. The patch included is needed for compilation. You'd place the "RegAllocGraphColoring.cpp" file in the llvm/lib/ CodeGen directory. You can use the graph coloring with the commandline:
llc -regalloc=graphcoloring foo.bc
All comments are welcome!
-bw
RegAllocGraphColoring.cpp
Description: Binary data
Index: include/llvm/CodeGen/LinkAllCodegenComponents.h
===================================================================
RCS file: /var/cvs/llvm/llvm/include/llvm/CodeGen/LinkAllCodegenComponents.h,v
retrieving revision 1.3
diff -a -u -r1.3 LinkAllCodegenComponents.h
--- include/llvm/CodeGen/LinkAllCodegenComponents.h 1 Aug 2006 19:14:14
-0000 1.3
+++ include/llvm/CodeGen/LinkAllCodegenComponents.h 16 Nov 2006 00:54:23
-0000
@@ -31,6 +31,7 @@
(void) llvm::createSimpleRegisterAllocator();
(void) llvm::createLocalRegisterAllocator();
(void) llvm::createLinearScanRegisterAllocator();
+ (void) llvm::createGraphColoringRegisterAllocator();
(void) llvm::createBFS_DAGScheduler(NULL, NULL, NULL);
(void) llvm::createSimpleDAGScheduler(NULL, NULL, NULL);
Index: include/llvm/CodeGen/LiveInterval.h
===================================================================
RCS file: /var/cvs/llvm/llvm/include/llvm/CodeGen/LiveInterval.h,v
retrieving revision 1.25
diff -a -u -r1.25 LiveInterval.h
--- include/llvm/CodeGen/LiveInterval.h 2 Sep 2006 05:37:53 -0000 1.25
+++ include/llvm/CodeGen/LiveInterval.h 16 Nov 2006 00:54:23 -0000
@@ -244,6 +244,10 @@
/// the range must already be in this interval in its entirety.
void removeRange(unsigned Start, unsigned End);
+ void removeRange(LiveRange LR) {
+ removeRange(LR.start, LR.end);
+ }
+
bool operator<(const LiveInterval& other) const {
return beginNumber() < other.beginNumber();
}
Index: include/llvm/CodeGen/LiveIntervalAnalysis.h
===================================================================
RCS file: /var/cvs/llvm/llvm/include/llvm/CodeGen/LiveIntervalAnalysis.h,v
retrieving revision 1.64
diff -a -u -r1.64 LiveIntervalAnalysis.h
--- include/llvm/CodeGen/LiveIntervalAnalysis.h 15 Sep 2006 03:57:23 -0000
1.64
+++ include/llvm/CodeGen/LiveIntervalAnalysis.h 16 Nov 2006 00:54:23 -0000
@@ -148,6 +148,11 @@
VirtRegMap& vrm,
int slot);
+ /// CreateNewLiveInterval - Create a new live interval with the given live
+ /// ranges.
+ LiveInterval& CreateNewLiveInterval(const LiveInterval* LI,
+ std::vector<LiveRange>& LRs);
+
virtual void getAnalysisUsage(AnalysisUsage &AU) const;
virtual void releaseMemory();
Index: include/llvm/CodeGen/Passes.h
===================================================================
RCS file: /var/cvs/llvm/llvm/include/llvm/CodeGen/Passes.h,v
retrieving revision 1.22
diff -a -u -r1.22 Passes.h
--- include/llvm/CodeGen/Passes.h 7 Nov 2006 19:33:46 -0000 1.22
+++ include/llvm/CodeGen/Passes.h 16 Nov 2006 00:54:23 -0000
@@ -70,6 +70,12 @@
///
FunctionPass *createLinearScanRegisterAllocator();
+ /// GraphColoringRegisterAllocator Pass - This pass implements the
+ /// priority-based coloring approach to register allocation, a global
register
+ /// allocator.
+ ///
+ FunctionPass *createGraphColoringRegisterAllocator();
+
/// PrologEpilogCodeInserter Pass - This pass inserts prolog and epilog code,
/// and eliminates abstract frame references.
///
Index: lib/CodeGen/LiveIntervalAnalysis.cpp
===================================================================
RCS file: /var/cvs/llvm/llvm/lib/CodeGen/LiveIntervalAnalysis.cpp,v
retrieving revision 1.195
diff -a -u -r1.195 LiveIntervalAnalysis.cpp
--- lib/CodeGen/LiveIntervalAnalysis.cpp 15 Nov 2006 20:54:11 -0000
1.195
+++ lib/CodeGen/LiveIntervalAnalysis.cpp 16 Nov 2006 00:54:24 -0000
@@ -251,6 +251,67 @@
}
}
+/// CreateNewLiveInterval - Create a new live interval with the given live
+/// ranges.
+LiveInterval&
+LiveIntervals::CreateNewLiveInterval(const LiveInterval* LI,
+ std::vector<LiveRange>& LRs) {
+ lv_ = getAnalysisToUpdate<LiveVariables>();
+ const TargetRegisterClass* RC = mf_->getSSARegMap()->getRegClass(LI->reg);
+
+ // Create a new virtual register for the spill interval.
+ unsigned NewVReg = mf_->getSSARegMap()->createVirtualRegister(RC);
+
+ // Replace the old virtual registers in the machine operands with the shiny
+ // new one.
+ for (std::vector<LiveRange>::iterator
+ I = LRs.begin(), E = LRs.end(); I != E; ++I) {
+ unsigned Index = getBaseIndex(I->start);
+ unsigned End = getBaseIndex(I->end - 1) + InstrSlots::NUM;
+
+ for (; Index != End; Index += InstrSlots::NUM) {
+ // Skip deleted instructions
+ while (Index != End && !getInstructionFromIndex(Index))
+ Index += InstrSlots::NUM;
+
+ if (Index == End) break;
+
+ MachineInstr* MI = getInstructionFromIndex(Index);
+
+ for (unsigned J = 0; J != MI->getNumOperands(); ++J) {
+ MachineOperand& MOp = MI->getOperand(J);
+
+ if (MOp.isRegister() && MOp.getReg() == LI->reg) {
+ MOp.setReg(NewVReg);
+
+ for (unsigned K = J + 1; K != MI->getNumOperands(); ++K)
+ if (MI->getOperand(K).isReg() &&
+ MI->getOperand(K).getReg() == LI->reg)
+ MI->getOperand(K).setReg(NewVReg);
+ }
+ }
+
+ // Update live variables if it is available
+ if (lv_)
+ lv_->addVirtualRegisterKilled(NewVReg, MI);
+ }
+ }
+
+ LiveInterval& NewLI = getOrCreateInterval(NewVReg);
+
+ // The spill weight is now infinity as it cannot be spilled again
+ NewLI.weight = float(HUGE_VAL);
+
+ for (std::vector<LiveRange>::iterator
+ I = LRs.begin(), E = LRs.end(); I != E; ++I) {
+ DEBUG(std::cerr << " Adding live range " << *I << " to new interval\n");
+ NewLI.addRange(*I);
+ }
+
+ DEBUG(std::cerr << "Created new live interval " << NewLI << "\n");
+ return NewLI;
+}
+
std::vector<LiveInterval*> LiveIntervals::
addIntervalsForSpills(const LiveInterval &li, VirtRegMap &vrm, int slot) {
// since this is called after the analysis is done we don't know if
_______________________________________________ llvm-commits mailing list llvm-commits@cs.uiuc.edu http://lists.cs.uiuc.edu/mailman/listinfo/llvm-commits
