4
$\begingroup$

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:

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

  2. Is there a way to generalise this analysis so it gives interesting results for instances of unstructured control flow which are not loops?

$\endgroup$
4
  • $\begingroup$ (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.) $\endgroup$
    – Moonchild
    Aug 22, 2023 at 21:36
  • $\begingroup$ 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 $\endgroup$
    – blueberry
    Aug 22, 2023 at 23:16
  • $\begingroup$ 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. $\endgroup$
    – SK-logic
    Aug 23, 2023 at 8:56
  • $\begingroup$ 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. $\endgroup$
    – SK-logic
    Aug 23, 2023 at 8:57

1 Answer 1

2
$\begingroup$

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. (User 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 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 on control flow graphs is kind of a nice first resource.

$\endgroup$
4
  • $\begingroup$ "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. $\endgroup$
    – kaya3
    Sep 5, 2023 at 18:12
  • $\begingroup$ Perhaps a better example: Java's notion of definite assignment 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. $\endgroup$
    – kaya3
    Sep 5, 2023 at 18:20
  • $\begingroup$ @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. $\endgroup$
    – cody
    Sep 6, 2023 at 15:34
  • $\begingroup$ @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. $\endgroup$
    – supercat
    Sep 26, 2023 at 18:35

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .