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
Re: [llvm-commits] Priority-Based
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: Cool. I'll review the patch. Evan, can you take a first look at the new file? The patch looks good, but please: 1. Change CreateNewLiveInterval to take LRs by const reference. This will require changing the iterators to be const_iterator instead of just iterator's. 2. Please change int* X to int *X to fit with the rest of the code. 3. Why do this? + lv_ = getAnalysisToUpdateLiveVariables(); Isn't lv_ already valid when the method is called? 4. I don't think this is sufficient: +MachineOperand MOp = MI-getOperand(J); +if (MOp.isRegister() MOp.getReg() == LI-reg) { In particular, consider if you have two vregs (R1025 and R1027) that get coallesced before RA. When this happens I believe that live intervals just marks the two vregs as having the same interval, and that interval only has one reg (say R1027). When this happens, the actual machine instrs are not updated. This means that you can have a reference to R1025, even though the interval says it is R1027. To fix this, try using: +MachineOperand MOp = MI-getOperand(J); +if (MOp.isRegister() rep(MOp.getReg()) == LI-reg) { which should handle this case. 5. It is unclear to me why you have this loop: + 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); If not needed, just remove it. 6. I don't think this is right: + // Update live variables if it is available + if (lv_) +lv_-addVirtualRegisterKilled(NewVReg, MI); With Evan's recent change, kill/dead markers are now stored on the instruction. If MOp.setReg doesn't modify these markers, you probably don't need to do anything to update live vars. 7. The comment: +/// CreateNewLiveInterval - Create a new live interval with the given live +/// ranges. Should mention that the created interval has an infinite spill weight. If you make these changes, go ahead and commit the LiveIntervalAnalysis.cpp, LiveIntervalAnalysis.h, and LiveInterval.h changes, even before the rest is reviewed. Thanks Bill! -Chris ___ llvm-commits mailing list llvm-commits@cs.uiuc.edu http://lists.cs.uiuc.edu/mailman/listinfo/llvm-commits
Re: [llvm-commits] Priority-Based
On Nov 15, 2006, at 6:04 PM, Chris Lattner wrote: The patch looks good, but please: 1. Change CreateNewLiveInterval to take LRs by const reference. This will require changing the iterators to be const_iterator instead of just iterator's. Will do. 2. Please change int* X to int *X to fit with the rest of the code. ARRRGH!! ;-) But okay. Consistency is a good thing :-) 3. Why do this? + lv_ = getAnalysisToUpdateLiveVariables(); Isn't lv_ already valid when the method is called? I was kind of copying the code from addIntervalsForSpills. It has this comment: // since this is called after the analysis is done we don't know if // LiveVariables is available I'm not sure if this is also valid for this method...I'll try it without this in it. 4. I don't think this is sufficient: +MachineOperand MOp = MI-getOperand(J); +if (MOp.isRegister() MOp.getReg() == LI-reg) { In particular, consider if you have two vregs (R1025 and R1027) that get coallesced before RA. When this happens I believe that live intervals just marks the two vregs as having the same interval, and that interval only has one reg (say R1027). When this happens, the actual machine instrs are not updated. This means that you can have a reference to R1025, even though the interval says it is R1027. To fix this, try using: +MachineOperand MOp = MI-getOperand(J); +if (MOp.isRegister() rep(MOp.getReg()) == LI-reg) { which should handle this case. Ah! Okay. That's a good point. If this isn't documented, it might be a good idea to throw it in a webpage somewhere. 5. It is unclear to me why you have this loop: + 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); If not needed, just remove it. Hmm...you're right. It looks superfluous. I probably wrote it at 2AM or something. 6. I don't think this is right: + // Update live variables if it is available + if (lv_) +lv_-addVirtualRegisterKilled(NewVReg, MI); With Evan's recent change, kill/dead markers are now stored on the instruction. If MOp.setReg doesn't modify these markers, you probably don't need to do anything to update live vars. Alrighty. 7. The comment: +/// CreateNewLiveInterval - Create a new live interval with the given live +/// ranges. Should mention that the created interval has an infinite spill weight. Okay. If you make these changes, go ahead and commit the LiveIntervalAnalysis.cpp, LiveIntervalAnalysis.h, and LiveInterval.h changes, even before the rest is reviewed. Cool. Thanks! -bw ___ llvm-commits mailing list llvm-commits@cs.uiuc.edu http://lists.cs.uiuc.edu/mailman/listinfo/llvm-commits