To determine whether it is safe to duplicate the instruction by duplicating the
loop body. Will be used in loop versioning for array and loop unrolling.
This analysis provides the following functionality:
1. An abstraction over all loops and basic blocks called a 'region'. For
a given loop this abstraction is used to represent all immediate child
basic blocks (1) and immediate subloops (2) called child regions.
2. Detection of back edges that were not found by SILLoopInfo. The
heads/tails of such back edges are marked as being areas where unhandled
control flow occurs. This enables irreducible control flow to be handled
by users as appropriate.
3. For each loop in the loop tree an RPO/PO ordering of the loop's
subregions. This enables one to run dataflow on the loop tree using loop
abstractions in a structured, clean manner by processing regions and
depending on whether or not the region was a loop/BB handle it
appropriately.
Some notes:
1. Functions are represented as a top level loop.
2. The analysis is setup to conservatively handle loops with the
following properties:
a. Irreducible Control Flow.
b. Multiple Backedges
In these cases, we use the unknown control flow facility to allow for
users of the analysis to handle the behavior appropriately.
We assume 2.b. since I am going to implement canonicalization of
multiple backedge loops into nested loops.
Also two passes are provided for working with this analysis:
1. LoopRegionViewText - Dump loop regions in a textual format. This is
intended for usage with FileCheck tests.
2. LoopRegionViewCFG - Dump loop regions into a CFG pdf. The dumped CFG
includes the loops, functions, and BBs. It represents
successors/predecessors in the loop region by black arrows and
hierarchical relations in between regions/subregions by red dashed
arrows. It also prints out the contents of BBs and whether or not
unknown control flow occurs.
(1) BBs for which this loop is the inner most parent loop.
(2) Loops for which this loop is the inner most parent loop.
Thanks to Arnold review!
rdar://22238531
Swift SVN r32104
This follows the model of dominance info and allows me to create reachability
methods on SILBasicBlock without creating dependencies from swiftSIL to
swiftSILAnalysis.
Swift SVN r21866
