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::set<INode*> 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
