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.
- We can refuse from optimizing potentially unsafe instructions
- 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.
- 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.
- 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.