Re: [llvm-commits] Priority-Based Coloring Approach to Register Allocation
Hi Bill,
It's great to have a graph coloring regalloc to compare the current
implement against. Thanks!
Comments:
1. INode NeighborList is a std::setINode* which is very slow.
Please use a more efficient data structure. You may have to wrap
LiveIntervals in something else and give each one a unique id.
2. Here is something I do have the answer for. But it's wonder
considering. Graph coloring can be slow. Does it make sense to
separate nodes by regclasses which cannot conflict. e.g. Do graph
coloring for all integer nodes and then do another round for all
floating point ones. This reduces the size of the graph.
3. Is LINodeMap a std::map? Again, you can probably use a more
efficient data structure if you assign each interval unique id. You
already have INode, why not use it?
4. CalculateInterference(). Why pass LINeighbors.begin() and .end().
LINodeMap is a RegAlloc ivar.
5.
/// Test if this live range interferes with the current live
range and that
/// they're both in the same register class.
if (CurNode-interferes(NeighborNode)
RelatedRegClasses.getLeaderValue(RegRC) == RCLeader)
CurNode-addNeighbor(NeighborNode);
else
CurNode-removeNeighbor(NeighborNode);
Why is removeNeighbor() needed? If it is not a neighbor, just don't
add it to the list?
6. Making ForbiddenRegs a map seems unnecessary. Why not add a ivar
to each INode that keeps track which registers are forbbiden?
7. SepareUnconstrainedLiveIntervals(): is it possible to create
separate lists in BuildGraph() rather than separate them later?
8. CalculatePriority(): The formula in paper is based on spill cost.
But it doesn't look like you are using this? For future please
consider LI's which can be rematerialized. Should we give LI's which
are more restricted (e.g. greater # of ForbiddenRegs, register pairs)
higher priorities?
9. PriorityBasedColoring():
/// FIXME: This algorithm is pretty gross and will probably
result in
/// massive performance issues!
if (IsUncolorable(CLI)) {
RemoveNodeFromGraph(LINodeMap[CLI]);
UncolorableLIs.insert(CLI);
DEBUG(std::cerr Removing uncolorable LiveInterval:
*CLI \n);
}
Instead of inserting into the UncolorableLIs set and remove them
outside the loop, perhaps a worklist based approach can be used?
10. GetFreeReg(): That goto inside the nested for loop is evil. :-)
How about something like this:
while (I != E) {
bool TryAgain = false;
for () {
if () {
TryAgain = true;
break;
}
}
if (!TryAgain)
break;
++I;
}
I am not sure how to fix it. But GetFreeReg() seems to be pretty
expensive? After a register is picked, you update ForbbidenRegs set
of the neighbors. Is it more desirable to keep track a list of
candidates? Perhaps we can use a bitmap representation of a register
class and calculate a unique mask for each physical register before
coloring?
11. Please give INode::begin() end() more descriptive names.
12. Loop c in PriorityBasedColoring() seems very expensive. There
should be a cheaper way to detect whether a LI has to be split. Can
we cache the result of GetNumMappableRegs()?
I haven't read SplitLiveInterval in details, so no comment about it yet.
Cheers,
Evan
On Nov 15, 2006, at 5:03 PM, Bill Wendling wrote:
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
ra-patch.txt
___
llvm-commits mailing list
llvm-commits@cs.uiuc.edu
http://lists.cs.uiuc.edu/mailman/listinfo/llvm-commits
___
llvm-commits mailing list
llvm-commits@cs.uiuc.edu
http://lists.cs.uiuc.edu/mailman/listinfo/llvm-commits
[llvm-commits] Priority-Based Coloring Approach to Register Allocation
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::vectorLiveRange 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::vectorLiveRange LRs) {
+ lv_ = getAnalysisToUpdateLiveVariables();
+ 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::vectorLiveRange::iterator
+ I = LRs.begin(), E =
