CycleInfo: Introduce cycles as a generalization of loops
authorSameer Sahasrabuddhe <sameer.sahasrabuddhe@amd.com>
Tue, 7 Dec 2021 06:31:22 +0000 (12:01 +0530)
committerSameer Sahasrabuddhe <sameer.sahasrabuddhe@amd.com>
Tue, 7 Dec 2021 06:32:34 +0000 (12:02 +0530)
commit0fe61ecc2cef333250a152cd90d80d0b802b27db
tree49e63b1eed4303bf731a092ca3c32f60926e8ddc
parent061f22dda9fddbcdaa1fd10b9cfb0cf2e1fb937a
CycleInfo: Introduce cycles as a generalization of loops

LLVM loops cannot represent irreducible structures in the CFG. This
change introduce the concept of cycles as a generalization of loops,
along with a CycleInfo analysis that discovers a nested
hierarchy of such cycles. This is based on Havlak (1997), Nesting of
Reducible and Irreducible Loops.

The cycle analysis is implemented as a generic template and then
instatiated for LLVM IR and Machine IR. The template relies on a new
GenericSSAContext template which must be specialized when used for
each IR.

This review is a restart of an older review request:
https://reviews.llvm.org/D83094

Original implementation by Nicolai Hähnle <nicolai.haehnle@amd.com>,
with recent refactoring by Sameer Sahasrabuddhe <sameer.sahasrabuddhe@amd.com>

Differential Revision: https://reviews.llvm.org/D112696
27 files changed:
llvm/docs/CycleTerminology.rst [new file with mode: 0644]
llvm/docs/UserGuides.rst
llvm/docs/cycle-1.png [new file with mode: 0644]
llvm/docs/cycle-2.png [new file with mode: 0644]
llvm/docs/cycle-3.png [new file with mode: 0644]
llvm/include/llvm/ADT/GenericCycleImpl.h [new file with mode: 0644]
llvm/include/llvm/ADT/GenericCycleInfo.h [new file with mode: 0644]
llvm/include/llvm/ADT/GenericSSAContext.h [new file with mode: 0644]
llvm/include/llvm/Analysis/CycleAnalysis.h [new file with mode: 0644]
llvm/include/llvm/CodeGen/MachineCycleAnalysis.h [new file with mode: 0644]
llvm/include/llvm/CodeGen/MachinePassRegistry.def
llvm/include/llvm/CodeGen/MachineSSAContext.h [new file with mode: 0644]
llvm/include/llvm/IR/SSAContext.h [new file with mode: 0644]
llvm/include/llvm/InitializePasses.h
llvm/lib/Analysis/Analysis.cpp
llvm/lib/Analysis/CMakeLists.txt
llvm/lib/Analysis/CycleAnalysis.cpp [new file with mode: 0644]
llvm/lib/CodeGen/CMakeLists.txt
llvm/lib/CodeGen/CodeGen.cpp
llvm/lib/CodeGen/MachineCycleAnalysis.cpp [new file with mode: 0644]
llvm/lib/CodeGen/MachineSSAContext.cpp [new file with mode: 0644]
llvm/lib/IR/CMakeLists.txt
llvm/lib/IR/SSAContext.cpp [new file with mode: 0644]
llvm/lib/Passes/PassBuilder.cpp
llvm/lib/Passes/PassRegistry.def
llvm/test/Analysis/CycleInfo/basic.ll [new file with mode: 0644]
llvm/test/CodeGen/X86/cycle-info.mir [new file with mode: 0644]