I am a sophomore at the University of Electronic Science and Technology of China. In the first semester of my sophomore year, I was introduced to the course Principles of Compilation. Along with my peers, I am now working on implementing a compiler for a subset of the C language, following the LLVM model. This subset omits structures and pointer from the C language.
I am currently responsible for the optimization of the middle-end in our compiler project. While implementing Global Value Numbering with Global Code Motion (GVN-GCM), I’ve discovered that Global Value Numbering with Partial Redundancy Elimination (GVN-PRE) is more efficient. Additionally, GVN-PRE includes Loop-Invariant Code Motion (LICM), enhancing its optimization capabilities.After reading the paper:“Partial redundancy elimination in SSA form” written by ROBERT KENNEDY, I have a few questions:
1.In the phi_insertion step described in the paper, there’s a process “for each occurrence X of E(i) in the program” It seems we should use a Global Value Numbering (GVN) approach to determine if an IR instruction is an occurrence of an expression. However, regarding expressions, only binary instructions similar to a1+b1 are considered expressions. Are there other types of instructions that should be treated as expressions too?
2.Why hasn’t LLVM adopted this algorithm? Is it because there are more efficient methods available?
Is there any advice or methods can offer to me?
1 Like
cc: @alina
LLVM’s GVN does perform scalar PRE as a separate optimization, see:
It also performs load PRE as part of the main GVN analysis (includes for loops), see the two calls here:
1 Like
thanks for the reference!