Add LoopUtils class to gather some loop transformation support.
authorVictor Lomuller <victor@codeplay.com>
Fri, 26 Jan 2018 12:07:10 +0000 (12:07 +0000)
committerSteven Perron <stevenperron@google.com>
Thu, 1 Feb 2018 20:35:09 +0000 (15:35 -0500)
commit50e85c865ca9c4b53e2724f36a84fb2566c1ce97
tree28907f9d378f13af982e73ecdbe15ad529afa506
parent61d8c0384b8400e5a88febb457611d22e36a76c8
Add LoopUtils class to gather some loop transformation support.

This patch adds LoopUtils class to handle some loop related transformations. For now it has 2 transformations that simplifies other transformations such as loop unroll or unswitch:
 - Dedicate exit blocks: this ensure that all exit basic block
   (out-of-loop basic blocks that have a predecessor in the loop)
   have all their predecessors in the loop;
 - Loop Closed SSA (LCSSA): this ensure that all definitions in a loop are used inside the loop
   or in a phi instruction in an exit basic block.

It also adds the following capabilities:
 - Loop::IsLCSSA to test if the loop is in a LCSSA form
 - Loop::GetOrCreatePreHeaderBlock that can build a loop preheader if required;
 - New methods to allow on the fly updates of the loop descriptors.
 - New methods to allow on the fly updates of the CFG analysis.
 - Instruction::SetOperand to allow expression of the index relative to Instruction::NumOperands (to be compatible with the index returned by DefUseManager::ForEachUse)
16 files changed:
source/opt/CMakeLists.txt
source/opt/basic_block.cpp
source/opt/basic_block.h
source/opt/cfg.cpp
source/opt/cfg.h
source/opt/def_use_manager.cpp
source/opt/instruction.h
source/opt/ir_builder.h
source/opt/loop_descriptor.cpp
source/opt/loop_descriptor.h
source/opt/loop_utils.cpp [new file with mode: 0644]
source/opt/loop_utils.h [new file with mode: 0644]
test/opt/loop_optimizations/CMakeLists.txt
test/opt/loop_optimizations/lcssa.cpp [new file with mode: 0644]
test/opt/loop_optimizations/loop_descriptions.cpp
test/opt/loop_optimizations/nested_loops.cpp