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
- 1.3
+++ include/llvm/CodeGen/LinkAllCodegenComponents.h 16 Nov 2006 00:54:23
-
@@ -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 - 1.25
+++ include/llvm/CodeGen/LiveInterval.h 16 Nov 2006 00:54:23 -
@@ -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 -
1.64
+++ include/llvm/CodeGen/LiveIntervalAnalysis.h 16 Nov 2006 00:54:23 -
@@ -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& 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 - 1.22
+++ include/llvm/CodeGen/Passes.h 16 Nov 2006 00:54:23 -
@@ -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.cpp15 Nov 2006 20:54:11 -
1.195
+++ lib/CodeGen/LiveIntervalAnalysis.cpp16 Nov 2006 00:54:24 -
@@ -251,6 +251,67 @@
}
}
+/// CreateNewLiveInterval - Create a new live interval with the given live
+/// ranges.
+LiveInterval&
+LiveIntervals::CreateNewLiveInterval(const LiveInterval* LI,
+ std::vector& LRs) {
+ lv_ = getAnalysisToUpdate();
+ 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::iterator
+ I = LRs.begin(), E = LRs.end(); I != E; ++I) {
+