Hi,
Good day,
I want to study and review Instruction Selection Algorithms in LLVM.
Do anyone knows good references to begin?
I believe LLVM’s SelectionDAG ISel are using a pretty straight forward greedy algorithm to select DAG from bottom up (from the perspective of lexical program ordering). An operation is selected before its operands, and it always select a pattern with local optimal (hence the greediness).
What’s more interesting, IMHO, is how the patterns are ordered since it dictates the decision on local optimal. Currently LLVM sorted them by a combination of source/replacement pattern size and a complexity parameter assigned by developers. You can checkout this class for more details.
If you’re really seeking some academia references, I think this is a more recent one: Instruction Selection: Principles, Methods, and Applications | SpringerLink
1 Like