Page MenuHomePhabricator

[LICM] Teach LICM to hoist conditional loads
AbandonedPublic

Authored by aemerson on Jul 11 2017, 9:15 AM.

Details

Reviewers
mkuper
Summary

If the pointer operand of a load has been accessed by a load/store in a dominating block of the loop then it's safe to hoist.

Diff Detail

Repository
rL LLVM

Event Timeline

aemerson created this revision.Jul 11 2017, 9:15 AM
aemerson updated this revision to Diff 106049.Jul 11 2017, 9:19 AM

Whitespace fixes.

mkuper requested changes to this revision.Jul 11 2017, 11:23 AM

This looks wrong.
In particular, it would break for something like:

a = *p;
free(p)
while (k) { // k is always false
 ... = *p;
}

We have llvm::isSafeToLoadUnconditionally() that does the domination check safely, but just checking that it's safe to load unconditionally in the pre-header may not be enough.

Consider something like:

a = *p;
while (k) {
  if (m) {
    free(p);
  }
  ... = *p;

}

Now, in those cases we shouldn't be hoisting regardless, because if p escapes, the value may not be loop-invariant.
But we need to make sure the patch doesn't break that, so additional tests may be needed.

This revision now requires changes to proceed.Jul 11 2017, 11:23 AM
dberlin added inline comments.
lib/Transforms/Scalar/LICM.cpp
921

The DT queries are O(1), so i'm not sure what this buys you?

949

Domination does not guarantee execution.
It only guarantees that all paths that execute go through a given block before getting to another:

A
| \
B |
| /  
C

A dominates B and C, but only one of them will execute.

You want control dependence, and in particular, CDEQ sets, which divides blocks into equivalence classes where everything in the same equivalence class executes under the same set of conditions.

But you will find this is never going to be true for normal loops.

aemerson abandoned this revision.Jul 12 2017, 1:25 AM

This looks wrong.
In particular, it would break for something like:

a = *p;
free(p)
while (k) { // k is always false
 ... = *p;
}

We have llvm::isSafeToLoadUnconditionally() that does the domination check safely, but just checking that it's safe to load unconditionally in the pre-header may not be enough.

Consider something like:

a = *p;
while (k) {
  if (m) {
    free(p);
  }
  ... = *p;

}

Now, in those cases we shouldn't be hoisting regardless, because if p escapes, the value may not be loop-invariant.
But we need to make sure the patch doesn't break that, so additional tests may be needed.

Good points. The original intent of this patch was to hoist loads from more complicated loop nests, extending it to fully general conditional loads is too ambitious for the time I have so I'm going to drop this for now.

lib/Transforms/Scalar/LICM.cpp
921

According to GenericDomTree.h the dominates() routines have comments stating they're not constant time operations. Unless I'm looking in the wrong place?

949

In the context of this function checking for safety of complete unconditional execution I agree dominance isn't enough. The actual way this code seems to be used for loads is that it allows hoisting to the preheader of the loop, so not completely unconditional.