[UnifyLoopExits] Reduce number of guard blocks
authorBrendon Cahoon <brendon.cahoon@amd.com>
Wed, 6 Apr 2022 01:53:46 +0000 (20:53 -0500)
committerBrendon Cahoon <brendon.cahoon@amd.com>
Wed, 22 Jun 2022 20:44:23 +0000 (15:44 -0500)
commite13248ab0e79b59d5e5ac73e2fe57d82ce485ce1
tree15ec3c5ff26b8b6a9d2242b0b3aa9b419d6917be
parent5011b4ca0e4bc7e4c72ac3511be53d23fd50c695
[UnifyLoopExits] Reduce number of guard blocks

UnifyLoopExits creates a single exit, a control flow hub, for
loops with multiple exits. There is an input to the block for
each loop exiting block and an output from the block for each
loop exit block. Multiple checks, or guard blocks, are needed
to branch to the correct exit block.

For large loops with lots of exit blocks, all the extra guard
blocks cause problems for StructurizeCFG and subsequent passes.
This patch reduces the number of guard blocks needed when the
exit blocks branch to a common block (e.g., an unreachable
block). The guard blocks are reduced by changing the inputs
and outputs of the control flow hub. The inputs are the exit
blocks and the outputs are the common block.

Reducing the guard blocks enables StructurizeCFG to reorder the
basic blocks in the CFG to reduce the values that exit a loop
with multiple exits. This reduces the compile-time of
StructurizeCFG and also reduces register pressure.

Differential Revision: https://reviews.llvm.org/D123230
llvm/lib/Transforms/Utils/UnifyLoopExits.cpp
llvm/test/Transforms/UnifyLoopExits/reduce_guards.ll [new file with mode: 0644]