<p>The basic form of a loop is as follows:</p>
<pre><code>loopvars := init

body:
loopvars := f(loopvars)
done := term(loopvars)
br done, end, body

end:
</code></pre>
<p>Suppose we've recognised this as a loop; we can imagine performing a basic analysis of it as follows: derive abstractions init# and f#, and then iterate f# to a fixed point.  That is:</p>
<pre><code>fix (\x -&gt; x ∪ (f# x)) init#
</code></pre>
<p>The result will be a sound type for loopvars (or, under the SSA regime, its loop-borne definition, since the initial definition is just init#).  This differs from the traditional approach (as in e.g. 'combining analyses, combining optimisations', chapters 2 and 3), but I believe it will produce the same result.</p>
<p>However, it has the advantage that it can produce more information about the loop.  Suppose we instead consider the sequence init#, f#(init#), f#(f#(init#)), ...; we might find a finite prefix (possibly of length zero) followed by a finite-length cycle.  If the length of the cycle is short, then we might be able to profit by unrolling the loop by length of the cycle, obtaining a more precise type for each instance.  For instance, suppose one of the loop variables is a boolean which is alternately true and false, and the loop body branches on the value of that variable.  There is a cycle of length 2; if we unroll the loop 2x, then in the first half, the boolean is always true, and in the second, it is always false, so we can eliminate the branch.</p>
<p>Obviously, the sequence could fail to converge, and we need heuristics to decide when unrolling is worth it, but those issues can be wrangled.  The main problem I have with this that it only works when we recognise that something is a loop.  I have two questions:</p>
<ol>
<li><p>Can this analysis be applied to an ir representing only unstructured control flow, without specifically recognising loops?</p>
</li>
<li><p>Is there a way to generalise this analysis so it gives interesting results for instances of unstructured control flow which are not loops?</p>
</li>
</ol>

<optimization><data-flow-analysis>
Can analysis of periodic loop behaviour be generalised to unstructured control flow?
CC BY-SA 4.0
2023-08-22T21:36:35.633Z
(To clarify the point about cycle-searching slightly: suppose our loop has two variables: a boolean which is alternately true and false, and an integer which counts up to 2 and then restarts at 0.  There is a precise 6-cycle ((true,0)(false,1)(true,2)(false,0)(true,1)(false,2)), an imprecise 3-cycle ((boolean,0)(boolean,1)(boolean,2)), and an imprecise 2-cycle ((true,int)(false,int)); all are sound, and which, if any, the analysis actually finds is just down to heuristics and resource limits.  The key observation being that we can soundly replace any element of the sequence with a supertype.)
Moonchild
CC BY-SA 4.0
2023-08-22T23:16:49.443Z
slightly off topic for the question asked, but this feels suspiciously close to the halting problem - more specifically, the section on detecting "cycles" within the loop in order to unroll it more effectively
blueberry
CC BY-SA 4.0
2023-08-23T08:56:22.957Z
You can do quite a bit of useful analysis on back-edges, ignoring the rest of the "loop" (if there is any). It can be done on even irreducible CFG. E.g., for unrolling, back-edge is all you're interested in, you can just clone all the basic blocks that follow back-edge to unroll once. In some cases you can even narrow loop variable types (ranges), etc. Not sure if strength reduction and alike would be possible, never tried for irreducible loops.
SK-logic
CC BY-SA 4.0
2023-08-23T08:57:36.137Z
P.S., this unrolling is pretty much the same thing as an algorithm for removing irreducibility, so once done, you'll just have a pile of structured CFGs you can apply the traditional analysis methods to.
SK-logic
<p>Generally, any hope of doing any analysis at all on a program requires some form of <a href="https://en.wikipedia.org/wiki/Control_flow_analysis" rel="nofollow noreferrer">control-flow analysis</a>; that is, building a big graph of possible sequences of instructions executed. (User <a href="https://langdev.stackexchange.com/users/89/kaya3">kaya3</a> points out that I'm being hyperbolic, indeed, typing is a kind of static analysis that does not &quot;really&quot; use control-flow analysis, and is thus &quot;flow-insensitive&quot;).</p>
<p>Every compiler and code analyzer builds a big such graph, usually <em>intra-procedurally</em> (there is roughly one graph <em>per</em> function definition).</p>
<p>This graph is an <strong>over approximation</strong> of the actual instruction execution: you may get some edge <code>i1 --&gt; i2</code> even though there is no way to actually execute <code>i2</code> right after <code>i1</code>, say in <code>i1; if false then i2;</code>. But it serves as a useful map of how execution is most likely going to happen.</p>
<p>We call this the <strong>control flow graph</strong> (CFG).</p>
<p>A <a href="https://en.wikipedia.org/wiki/Strongly_connected_component" rel="nofollow noreferrer">strongly connected component</a> or <strong>SCC</strong> is a subgraph of the CFG such that each node in the SCC can reach every other node: this basically means you have possible loops where each point reaches each other point arbitrarily often. This is what loops look like in a CFG. Each node is either not in a loop at all, or within a <strong>single</strong> SCC.</p>
<p>Note that nested for-loops will result in one &quot;big&quot; SCC. There are efficient (but non-trivial!) algorithms for finding such SCCs.</p>
<p>Generally, if your language is &quot;nice&quot; (basically not assembly), each SCC has a single <strong>entry node</strong>, which is the &quot;start&quot; of the loop. Usually there may be many &quot;exit&quot; nodes, corresponding to normal termination, early <code>return</code>, exceptions, etc.</p>
<p>In <em>theory</em> you can turn every such SCC into a nice basic loop such as that which you gave! In practice, you usually want to keep early exit nodes, and just generalize your analysis on &quot;easy&quot; loops to every loop with arbitrary numbers of exits.</p>
<p>In fact, you can do some analysis on the CFG itself to <strong>rebuild</strong> a little structured language in the form of nested loops and structured <code>if ... then ... else ...</code> constructs! This occasionally happens even in compilers which start from structured code, ironically.</p>
<p>Honestly the Wikipedia <a href="https://en.wikipedia.org/wiki/Control-flow_graph" rel="nofollow noreferrer">page</a> on control flow graphs is kind of a nice first resource.</p>

CC BY-SA 4.0
2023-09-05T15:32:09.977Z
2023-09-06T15:36:17.360Z
2023-09-06T15:36:17.360Z
cody
CC BY-SA 4.0
2023-09-05T18:12:56.753Z
*"Generally, any hope of doing any analysis at all on a program requires some form of control-flow analysis; that is, building a big graph of possible sequences of instructions executed."* ─ I think this is a big overstatement; most type-checkers work directly on the AST without needing to build a control-flow graph, for instance.
kaya3
CC BY-SA 4.0
2023-09-05T18:20:32.120Z
Perhaps a better example: Java's notion of [definite assignment](https://docs.oracle.com/javase/specs/jls/se7/html/jls-16.html) and definite unassignment is clearly analysing something about control-flow, but it's specified by structural recursion on the AST, without reference to a CFG.
kaya3
CC BY-SA 4.0
2023-09-06T15:34:32.080Z
@kaya3 You're right, I'm being hyperbolic, though AFAIK there's no production-level compiler worth it's salt that does not build a CFG. I'll slightly amend the answer. The definite assignment rule is definitely a kludge IMHO.
cody
CC BY-SA 4.0
2023-09-26T18:35:55.837Z
@cody: Java's definite assignment rule follows a principle that language designers should use when writing rules: ensure that there's an easy way of writing programs that are easily recognizable as valid, rather than write rules with corner cases that are extremely hard to resolve precisely.  That doesn't seem like a kludge to me.
supercat
# Can analysis of periodic loop behaviour be generalised to unstructured control flow?
Posted by: username_0 on 2023-08-22
The basic form of a loop is as follows:
loopvars := init

body:
loopvars := f(loopvars)
done := term(loopvars)
br done, end, body

end:

Suppose we've recognised this as a loop; we can imagine performing a basic analysis of it as follows: derive abstractions init# and f#, and then iterate f# to a fixed point.  That is:
fix (\x -> x ∪ (f# x)) init#

The result will be a sound type for loopvars (or, under the SSA regime, its loop-borne definition, since the initial definition is just init#).  This differs from the traditional approach (as in e.g. 'combining analyses, combining optimisations', chapters 2 and 3), but I believe it will produce the same result.
However, it has the advantage that it can produce more information about the loop.  Suppose we instead consider the sequence init#, f#(init#), f#(f#(init#)), ...; we might find a finite prefix (possibly of length zero) followed by a finite-length cycle.  If the length of the cycle is short, then we might be able to profit by unrolling the loop by length of the cycle, obtaining a more precise type for each instance.  For instance, suppose one of the loop variables is a boolean which is alternately true and false, and the loop body branches on the value of that variable.  There is a cycle of length 2; if we unroll the loop 2x, then in the first half, the boolean is always true, and in the second, it is always false, so we can eliminate the branch.
Obviously, the sequence could fail to converge, and we need heuristics to decide when unrolling is worth it, but those issues can be wrangled.  The main problem I have with this that it only works when we recognise that something is a loop.  I have two questions:

Can this analysis be applied to an ir representing only unstructured control flow, without specifically recognising loops?

Is there a way to generalise this analysis so it gives interesting results for instances of unstructured control flow which are not loops?
**Tags:** optimization data-flow-analysis
> **Comments:**
> **username_0**: (To clarify the point about cycle-searching slightly: suppose our loop has two variables: a boolean which is alternately true and false, and an integer which counts up to 2 and then restarts at 0.  There is a precise 6-cycle ((true,0)(false,1)(true,2)(false,0)(true,1)(false,2)), an imprecise 3-cycle ((boolean,0)(boolean,1)(boolean,2)), and an imprecise 2-cycle ((true,int)(false,int)); all are sound, and which, if any, the analysis actually finds is just down to heuristics and resource limits.  The key observation being that we can soundly replace any element of the sequence with a supertype.)  
> **username_1**: slightly off topic for the question asked, but this feels suspiciously close to the halting problem - more specifically, the section on detecting "cycles" within the loop in order to unroll it more effectively  
> **username_2**: You can do quite a bit of useful analysis on back-edges, ignoring the rest of the "loop" (if there is any). It can be done on even irreducible CFG. E.g., for unrolling, back-edge is all you're interested in, you can just clone all the basic blocks that follow back-edge to unroll once. In some cases you can even narrow loop variable types (ranges), etc. Not sure if strength reduction and alike would be possible, never tried for irreducible loops.  
> **username_2**: P.S., this unrolling is pretty much the same thing as an algorithm for removing irreducibility, so once done, you'll just have a pile of structured CFGs you can apply the traditional analysis methods to.  
---
## 1 answers
### Answer by username_3 on 2023-09-05. Score: 2
Generally, any hope of doing any analysis at all on a program requires some form of [control-flow analysis](https://en.wikipedia.org/wiki/Control_flow_analysis); that is, building a big graph of possible sequences of instructions executed. (User [kaya3](https://langdev.stackexchange.com/users/89/kaya3) points out that I'm being hyperbolic, indeed, typing is a kind of static analysis that does not "really" use control-flow analysis, and is thus "flow-insensitive").

Every compiler and code analyzer builds a big such graph, usually *intra-procedurally* (there is roughly one graph *per* function definition).

This graph is an **over approximation** of the actual instruction execution: you may get some edge `i1 --> i2` even though there is no way to actually execute `i2` right after `i1`, say in `i1; if false then i2;`. But it serves as a useful map of how execution is most likely going to happen.

We call this the **control flow graph** (CFG).

A [strongly connected component](https://en.wikipedia.org/wiki/Strongly_connected_component) or **SCC** is a subgraph of the CFG such that each node in the SCC can reach every other node: this basically means you have possible loops where each point reaches each other point arbitrarily often. This is what loops look like in a CFG. Each node is either not in a loop at all, or within a **single** SCC.

Note that nested for-loops will result in one "big" SCC. There are efficient (but non-trivial!) algorithms for finding such SCCs.

Generally, if your language is "nice" (basically not assembly), each SCC has a single **entry node**, which is the "start" of the loop. Usually there may be many "exit" nodes, corresponding to normal termination, early `return`, exceptions, etc.

In *theory* you can turn every such SCC into a nice basic loop such as that which you gave! In practice, you usually want to keep early exit nodes, and just generalize your analysis on "easy" loops to every loop with arbitrary numbers of exits.

In fact, you can do some analysis on the CFG itself to **rebuild** a little structured language in the form of nested loops and structured `if ... then ... else ...` constructs! This occasionally happens even in compilers which start from structured code, ironically.

Honestly the Wikipedia [page](https://en.wikipedia.org/wiki/Control-flow_graph) on control flow graphs is kind of a nice first resource.
> **Comments:**
> **username_4** (2023-09-05): *"Generally, any hope of doing any analysis at all on a program requires some form of control-flow analysis; that is, building a big graph of possible sequences of instructions executed."* ─ I think this is a big overstatement; most type-checkers work directly on the AST without needing to build a control-flow graph, for instance.  
> **username_4** (2023-09-05): Perhaps a better example: Java's notion of [definite assignment](https://docs.oracle.com/javase/specs/jls/se7/html/jls-16.html) and definite unassignment is clearly analysing something about control-flow, but it's specified by structural recursion on the AST, without reference to a CFG.  
> **username_3** (2023-09-06): @kaya3 You're right, I'm being hyperbolic, though AFAIK there's no production-level compiler worth it's salt that does not build a CFG. I'll slightly amend the answer. The definite assignment rule is definitely a kludge IMHO.  
> **username_5** (2023-09-26): @cody: Java's definite assignment rule follows a principle that language designers should use when writing rules: ensure that there's an easy way of writing programs that are easily recognizable as valid, rather than write rules with corner cases that are extremely hard to resolve precisely.  That doesn't seem like a kludge to me.  
---
