Introduce fix-irreducible pass
authorSameer Sahasrabuddhe <sameer.sahasrabuddhe@amd.com>
Wed, 15 Apr 2020 05:59:19 +0000 (11:29 +0530)
committerSameer Sahasrabuddhe <sameer.sahasrabuddhe@amd.com>
Wed, 15 Apr 2020 05:59:19 +0000 (11:29 +0530)
commit2ada8e2525dd2653f30c8696a27162a3b1647d66
tree150f1361a967dfc22a30786b5597028a27f9e603
parentd83541d1b8f75ff44083c8ba1dba1ca7bac330cf
Introduce fix-irreducible pass

An irreducible SCC is one which has multiple "header" blocks, i.e., blocks
with control-flow edges incident from outside the SCC. This pass converts an
irreducible SCC into a natural loop by introducing a single new header
block and redirecting all the edges on the original headers to this
new block.

This is a useful workaround for a limitation in the structurizer
which, which produces incorrect control flow in the presence of
irreducible regions. The AMDGPU backend provides an option to
enable this pass before the structurizer, which may eventually be
enabled by default.

Reviewed By: nhaehnle

Differential Revision: https://reviews.llvm.org/D77198
14 files changed:
llvm/include/llvm/Analysis/LoopInfo.h
llvm/include/llvm/InitializePasses.h
llvm/include/llvm/LinkAllPasses.h
llvm/include/llvm/Transforms/Utils.h
llvm/lib/Target/AMDGPU/AMDGPUTargetMachine.cpp
llvm/lib/Transforms/Utils/BasicBlockUtils.cpp
llvm/lib/Transforms/Utils/CMakeLists.txt
llvm/lib/Transforms/Utils/FixIrreducible.cpp [new file with mode: 0644]
llvm/lib/Transforms/Utils/Utils.cpp
llvm/test/Transforms/FixIrreducible/basic.ll [new file with mode: 0644]
llvm/test/Transforms/FixIrreducible/nested.ll [new file with mode: 0644]
llvm/test/Transforms/FixIrreducible/switch.ll [new file with mode: 0644]
llvm/test/Transforms/StructurizeCFG/workarounds/needs-fix-reducible.ll [new file with mode: 0644]
llvm/test/Transforms/StructurizeCFG/workarounds/needs-fr-ule.ll [new file with mode: 0644]