This is an archive of the discontinued LLVM Phabricator instance.

Add some shortcuts in Value Propagation for alloca
ClosedPublic

Authored by wmi on Mar 10 2016, 3:00 PM.

Details

Summary

The is the part1 to solve https://llvm.org/bugs/show_bug.cgi?id=10584

Inlining functions called inside of a large loop can introduce many long stretched variables because the alloca instructions inside callee will be promoted to the entry of the caller. Such long stretched variables could increase the compile time of correlated value propagation (CVP) and register allocation significantly (More significantly for value propagation).

The fact that a lot of alloca instructions are promoted can be used to reduce the compile time of CVP. CVP checks non-null for pointer params of each callsite. If we know the def of param is an alloca instruction, we know it is non-null without querying LVI. Similarly, CVP checks constant pointer for each mem access. If the def of the pointer is an alloca instruction, we know it is not a constant pointer without querying LVI. These shortcuts can reduce the cost of CVP significantly.

Diff Detail

Repository
rL LLVM

Event Timeline

wmi updated this revision to Diff 50361.Mar 10 2016, 3:00 PM
wmi retitled this revision from to Add some shortcuts in Value Propagation for alloca.
wmi updated this object.
wmi added reviewers: atrick, reames, hfinkel.
wmi set the repository for this revision to rL LLVM.
wmi added subscribers: llvm-commits, davidxl.
davidxl added inline comments.Mar 11 2016, 4:09 PM
lib/Transforms/Scalar/CorrelatedValuePropagation.cpp
322 ↗(On Diff #50361)

Maybe add a helper function to make this more readable:

if (mayHaveNullValue(...) && ...

324 ↗(On Diff #50361)

Have a helper function like:

bool isValueNonNull(V) -- which does simple checks.

So the combined check becomes:

if (mayHaveNullValue(...) && (isValueNonNull(V) || LVI ....)) {
}

Note that isValueNonNull can also handle simple cases with gep:

foo() {

 int a[10];
  ...
  bar(&a[5]);
...

}
we know &a[5] can not be null.

test/Transforms/CorrelatedValuePropagation/alloca.ll
5

not constant --> not null.

reames edited edge metadata.Mar 11 2016, 4:29 PM

Really interesting observations and great idea, but the patch is not structured well. In both cases, we're really talking about generic properties of LVI and we should structure it that way. That should help all callers of LVI, not just these two.

lib/Transforms/Scalar/CorrelatedValuePropagation.cpp
180 ↗(On Diff #50361)

This should be sunk inside LVI. Specifically, at the top of LazyValueInfo::getConstant.

I'm also not entirely sure this is accurate. I could construct a branch of the form:
if (%alloca == %some_constant_pointer) {
} else { }

Inside the if clause, I could find a constant value for the alloca. It's just that we happen to know that the branch can't be true and thus that we'd only be able to simplify in dead code.

At minimum, we should have a better description here. This is effectively a profitability heuristic more than anything else.

324 ↗(On Diff #50361)

This is the wrong place. Rather than special casing this particular caller, we should really sink this down into LVI. We could do this in one of two ways:

  1. Use the non-context sensative form of isKnownNonNull in getPreciateAt when answering a non-null query.
  2. Recognize the fact that the only fact we can infer about a pointer typed value is a constant or non-constant result. The only non-constant we can get - I think - is not-null. We can probably short circuit the search in this case.
davidxl added inline comments.Mar 11 2016, 5:14 PM
lib/Transforms/Scalar/CorrelatedValuePropagation.cpp
324 ↗(On Diff #50361)

I agree with you wrt to the final picture -- but should this be done in stages (to avoid over fixing the problem at hand)? Basically have a local fix now, get it stablized/tested and then move on to a general fix? (I am fine either way)

wmi updated this revision to Diff 50540.Mar 12 2016, 9:53 PM
wmi edited edge metadata.

Addressed David and Philip's comments. Fixed tests under clang/test.

reames requested changes to this revision.Apr 18 2016, 5:42 PM
reames edited edge metadata.
reames added inline comments.
lib/Analysis/LazyValueInfo.cpp
1381

Use stripPointerCasts

1390

This bail is reasonable. Needs commented and code cleanup, but otherwise ready to go in. (I am purposely *not* saying LGTM yet.)

1512

if (V->getType()->isPointerTy() &&
C->isNullValue() && isKnownNonNull(V))

Use isKnownNonNull from ValueTracking.

Comment why this is here. In particular, this is only a fastpath, falling through would be correct.

1513

This check is wrong. Just use ValueTracking

This revision now requires changes to proceed.Apr 18 2016, 5:42 PM
wmi updated this revision to Diff 54440.Apr 20 2016, 5:04 PM
wmi edited edge metadata.

reames, thanks for the helpful comments. Patch updated as suggested.

I just checked in a change which may greatly accelerate LVI for the comparison against null case. Can you check to see if after "267642: [LVI] Reduce compile time by lazily scanning blocks if needed." you're still seeing compile time problems?

The not-constant bypass might still be needed. I'm not entirely sure.

wmi added a comment.Apr 27 2016, 11:05 AM

Hi Philip,

I tried r267642 using testcases - Groonga and scribus from PR10584.
The result showed r267642 didn't reduce the compile time much. I
looked at r267642 and found a possible reason was that the first
shortcut of nonnull check took effect only when current BB was the
entry BB so we still needed to iterate CFG, right?

scribus13format.cc (scribus):
r266775: 57.89s
r266775 + r267642: 56.05s
r266775 + patch here: 31.17s

expr.c (Groonga):
r266775: 226.03s
r266775 + r267642: 225.32s
r266775 + patch here: 44.10s

Thanks,
Wei.

wmi added a comment.Aug 9 2016, 2:24 PM

Sorry for not visiting the patch for a long time. I just evaluated the original testcase on trunk. The compile time issue was still there, and the patch would still help. Philip, maybe it is still worth to consider the patch since the simple shortcut patch will not bring any harm?

reames accepted this revision.Sep 12 2016, 4:08 PM
reames edited edge metadata.

Sorry for being unresponsive for so long. This has reached the top of my queue again.

I'm still not entirely happy with this patch, mostly because I don't feel I understand *why* it makes such a huge difference, but I've also held this up for much too long. This is a reasonable approach to a real problem and we can iterate in tree if needed.

LGTM.

lib/Analysis/LazyValueInfo.cpp
1380

Add
/// Returns true if we can statically tell that this value will never be a "useful" constant. In practice, this means we've got something like an alloca or a malloc call for which a comparison against a constant can only be guarding dead code. Note that we are potentially giving up some precision here (a constant result) in favour of avoiding a expensive search for a easily answered common query.

This revision is now accepted and ready to land.Sep 12 2016, 4:08 PM
This revision was automatically updated to reflect the committed changes.