Frequent Path LICM

Beginners
1

Hi everyone. I am trying to implement a frequent path LICM pass for a school project and I’d like to hear your thoughts on my approach.

In the original LICM, an instruction is moved out of the loop if its operands do not change within the loop. In frequent path LICM, we move an instruction if it is invariant on the frequent path of a loop. We then insert fix-up code in the infrequent blocks to restore correctness. We can decide whether a block is on the frequent path or not from profiling data, and the exact threshold for “frequentness” can be tuned for performance. Below is an example.

image
image2268×1282 173 KB

I have the following approach in mind:

  1. Strip away infrequent BBs, resulting in a stripped-down loop consisting only of the frequent path and the backedge
  2. Run the original LICM on the stripped-down loop
  3. Glue back the infrequent BBs. For each hoisted/sunk instruction on the frequent path, insert fix-ups in the infrequent BBs

Does this look like a valid approach to you? I am asking because I am getting blocked left and right trying to implement it. In particular, I don’t know how to strip down a loop. I tried methods like L->removeBlockFromLoop(BB) and LI.removeBlock(BB), but I ended up failing the assert statements.

Thanks in advance for your help!

2

Removing/re-adding basic blocks correctly is going to be much harder than just stealing the bits of LICM you need.

For L->removeBlockFromLoop(BB), LoopInfo is just a reflection of the control flow graph; modifying it without modifying the actual control flow won’t work.

1 Like