4
$\begingroup$

There are well-known algorithms LICM, and they work well. Unfortunately, there are certain cases when these optimizations can cause runtime failures with code that was initially correct. Consider the following example:

read a
read_array bs
for (b in bs) {
    if (a != 0) {
        c = 5 / a
        print b * c
    }
}

applying loop-invariant code motion we find that c = 5 / a is loop-invariant and therefore can be moved out of loop. These may cause runtime error when a == 0, though original code works fine.

What to do then? I am not certain, but I have several ideas.

  1. We can refuse from optimizing potentially unsafe instructions
  2. We can apply loop unswitching before loop-invariant code motion. But I would not rely on this optimization, since it must be applied carefully to avoid code bloating.
  3. When moving unsafe instructions out of loop body we add range checks. However, it again causes code bloating (but not as great as in the previous case). Also this approach harder to implement, since we can't put these checks into single basic block, unless we have a special division instruction that does not cause runtime error.
  4. Perform range analysis before applying LICM. If divisor is never equal to zero, don't perform LICM.

Are there best practices to deal with such unsafe operations? Notice, that I am looking primarily for algorithms appropriate for SSA form.

$\endgroup$
4
$\begingroup$

This kind of optimization is more difficult than typical data-flow based transformations, because you need to actually change the branching structure of the control flow graph.

You need something more than SSA (or something more than the dataflow graph you get from reaching definitions.) That "something" is the control dependence graph (which relies on the same (post)dominator analysis that you use to construct the SSA graph. (Google for "program dependence graph" (which is the combination of the control-dependence graph and the SSA data-flow graph).) Loop invariants (including loop invariant conditionals) are "obvious" in the program dependence graph. A loop invariant is any node all of whose data and control dependences come from outside the loop.

Unfortunately, in the general case, rebuilding a control-flow graph from the program-dependence graph is somewhat involved. (Google for "percolation scheduling" and "gated SSA form" if you are interested. Also (self promotion) my dissertation gives a (terse) overview of a method for converting from PDG back to CFG.) You can, luckily, do something substantially simpler if you are willing to restrict your transformation to specific structured control flow (in your case, an if-else block inside a do-while block.) This is the same simplification that loop unswitching makes.

So working through the steps. First convert while and for loops to if-do-while

read a
read_array bs
b = bs.first
if (b is not bs.end):
  do:
    if (a != 0):
      c = 5 / a
      print b * c
    more stuff
    b = b.next
  while (b is not bs.end)

Then (as with loop unswitching) you see that a != 0 is loop invariant, so the if statement is loop invariant, so any statements inside the if block that are loop invariant (c = 5/a) can be moved out of the loop (along with the conditional that protects those statements.) Essentially what you are doing is breaking each invariant conditional block into the parts that are and are not loop invariant:

read a
read_array bs
b = bs.first
if (b is not bs.end):
  do:
    if (a != 0):
      c = 5 / a
    if (a != 0):
      print b * c
    more stuff
    b = b.next
  while (b is not bs.end)

Then you can move the entirety of the blocks that are completely loop-invariant out of the loop:

read a
read_array bs
b = bs.first
if (b is not bs.end):
  if (a != 0):
    c = 5 / a
  do:
    if (a != 0):
      print b * c
    more stuff
    b = b.next
  while (b is not bs.end)
$\endgroup$
0
$\begingroup$

The loop invariant that can be moved is

if (a != 0) {
    c = 5 / a
}

The loop variant that needs to be kept is

if (a != 0) {
    print b * c
}
$\endgroup$
  • $\begingroup$ How does the optimizer recognize this efficiently? $\endgroup$ – Alexey Andreev Jun 28 '14 at 12:41
  • $\begingroup$ Just as $a$ is not modified within the loop. $\endgroup$ – Yves Daoust Jun 28 '14 at 12:45
  • $\begingroup$ But how does the optimizer recognize which part of the CFG we need to transfer out of loop? $\endgroup$ – Alexey Andreev Jun 28 '14 at 12:53
  • $\begingroup$ By removing the variant part of the loop body and keeping what is left. $\endgroup$ – Yves Daoust Jun 28 '14 at 13:55
  • $\begingroup$ Actually,anything conditional only on a is not loop variant. In this case, assuming reading frombs does not have side effects (ordinary memory, not volatile), for (b in bs) {print b * c} would be inside the if (a != 0) conditional. (If read_array did not have side effects and bs was not used later, then it could be moved forward into the conditional since all uses would be guarded by the condition.) $\endgroup$ – Paul A. Clayton Jun 28 '14 at 14:25

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.