Introduce unify-loop-exits pass.
authorSameer Sahasrabuddhe <sameer.sahasrabuddhe@amd.com>
Sat, 28 Mar 2020 11:13:35 +0000 (07:13 -0400)
committerSameer Sahasrabuddhe <sameer.sahasrabuddhe@amd.com>
Mon, 30 Mar 2020 17:23:56 +0000 (13:23 -0400)
commit3cbbded68c260ea5574798ca444b3feecfbbcd70
tree0ec622ce7cdd399a33a7fd6209224830425722ae
parentdcc410b5cf202e354105df431fad62d2f5f7eac7
Introduce unify-loop-exits pass.

For each natural loop with multiple exit blocks, this pass creates a
new block N such that all exiting blocks now branch to N, and then
control flow is redistributed to all the original exit blocks.

The bulk of the tranformation is a new function introduced in
BasicBlockUtils that an redirect control flow from a set of incoming
blocks to a set of outgoing blocks via a common "hub".

This is a useful workaround for a limitation in the structurizer which
incorrectly orders blocks when processing a nest of loops. This pass
bypasses that issue by ensuring that each natural loop is recognized
as a separate region. Since the structurizer is a region pass, it no
longer sees a nest of loops in a single region, and instead processes
each "level" in the nesting as a separate region.

The AMDGPU backend provides a new option to enable this pass before
the structurizer, which may eventually be enabled by default.

Reviewers: madhur13490, arsenm, nhaehnle

Reviewed By: nhaehnle

Differential Revision: https://reviews.llvm.org/D75865
19 files changed:
llvm/include/llvm/InitializePasses.h
llvm/include/llvm/LinkAllPasses.h
llvm/include/llvm/Transforms/Utils.h
llvm/include/llvm/Transforms/Utils/BasicBlockUtils.h
llvm/include/llvm/Transforms/Utils/Local.h
llvm/lib/Target/AMDGPU/AMDGPUTargetMachine.cpp
llvm/lib/Transforms/Scalar/StructurizeCFG.cpp
llvm/lib/Transforms/Utils/BasicBlockUtils.cpp
llvm/lib/Transforms/Utils/CMakeLists.txt
llvm/lib/Transforms/Utils/Local.cpp
llvm/lib/Transforms/Utils/UnifyLoopExits.cpp [new file with mode: 0644]
llvm/lib/Transforms/Utils/Utils.cpp
llvm/test/CodeGen/AMDGPU/loop_break.ll
llvm/test/Transforms/StructurizeCFG/workarounds/needs-unified-loop-exits.ll [new file with mode: 0644]
llvm/test/Transforms/UnifyLoopExits/basic.ll [new file with mode: 0644]
llvm/test/Transforms/UnifyLoopExits/nested.ll [new file with mode: 0644]
llvm/test/Transforms/UnifyLoopExits/restore-ssa.ll [new file with mode: 0644]
llvm/test/Transforms/UnifyLoopExits/switch.ll [new file with mode: 0644]
llvm/tools/llc/llc.cpp