This is an archive of the discontinued LLVM Phabricator instance.

[LVI] Constant-propagate a zero extension of the switch condition value through case edges
ClosedPublic

Authored by hjyamauchi on Aug 2 2017, 3:52 PM.

Details

Summary

(This is a second attempt as https://reviews.llvm.org/D34822 was reverted.)

LazyValueInfo currently computes the constant value of the switch condition through case edges, which allows the constant value to be propagated through the case edges.

But we have seen a case where a zero-extended value of the switch condition is used past case edges for which the constant propagation doesn't occur.

This patch adds a small logic to handle such a case in getEdgeValueLocal().

This is motivated by the Python 2.7 eval loop in PyEval_EvalFrameEx() where the lack of the constant propagation causes longer live ranges and more spill code than necessary.

With this patch, we see that the code size of PyEval_EvalFrameEx() decreases by ~5.4% and a performance test improves by ~4.6%.

Event Timeline

hjyamauchi created this revision.Aug 2 2017, 3:52 PM

The first diff is the same as the reverted https://reviews.llvm.org/D34822.

hjyamauchi updated this revision to Diff 109449.Aug 2 2017, 4:00 PM

This second diff is the new one that fixes the bug (see test20).

The issue with D34822 was that it is not correct to propagate the constant range of the value that's derived from the switch condition to the *default* edge.

For example,

%12 = and i64 %11, 1
switch i64 %11, label %default [

i64 0, label %86
i64 3, label %87

]

...

%default:

%92 = icmp eq i64 %12, 0, !dbg !1921
br i1 %92, label %94, label %93, !dbg !1921

It's correct to propagate that %11 != 0 and %11 != 3 to the %default edge.

But it's not correct to propagate the corresponding value of %12, that is %12 != 0 (0 & 1) and %12 != 1 (3 & 1), on the %default edge (which isn't even logically possible.)

The fix is to restrict the default-case propagation to the "Val == Condition" case only.

This is ready for review.

Note the newly added @test20 demonstrates the bug in D34822.

sanjoy edited edge metadata.Aug 2 2017, 5:40 PM

Code wise this looks correct to me, but I'd prefer to phrase the solution a bit differently in the commit message and in the comments: IIUC the bug we had was that we were assuming Condition != T (in the default block) implied f(Condition) != f(T). However this isn't true for a non injective f (like f(i32 x) = and i32 x, 2).

For instance we could still do this transformation for

  x = cond + 2
  switch cond, label %left, [ i32 20, label %right]

left:
  ...
right:
 ...

In left we know that cond is not 20 and thus x is not 22, since f(x) = x + 2 is injective.

(I'm not suggesting we actually do the above btw, I think the case this patch is handling (f(x) = x) is enough for now.)

lib/Analysis/LazyValueInfo.cpp
158

Can you return None; here?

test/Transforms/CorrelatedValuePropagation/range.ll
587

Can we demonstrate the issue with just one switch?

hjyamauchi marked 2 inline comments as done.

Agreed on the phrasing and that there are cases where we could do the propagation/transformation.

I fixed the code comment there.

Addressed the inline comments.

sanjoy accepted this revision.Aug 3 2017, 12:40 PM

lgtm

lib/Analysis/LazyValueInfo.cpp
1508–1513

I would be somewhat more explicit here:

We know Condition != EdgeVal in BBTo.  In some cases we can use this to infer Val == f(Condition) is != f(EdgeVal).  For now, we only do this when f is identity (i.e. Val == Condition), but we should be able to do this for any injective f.

The "There is no need to perform difference for those cases." comment is also somewhat misleading -- it is not just that there is no need, we cannot perform the difference in these cases. Can you please update that comment since you're touching nearby code anyway?

This revision is now accepted and ready to land.Aug 3 2017, 12:40 PM
hjyamauchi updated this revision to Diff 109625.Aug 3 2017, 1:49 PM

Addressed the comment.

hjyamauchi added inline comments.Aug 3 2017, 1:49 PM
lib/Analysis/LazyValueInfo.cpp
1508–1513

Done. I assumed by EdgeVal you meant CaseValue where EdgeVal = f(CaseValue).

sanjoy added inline comments.Aug 3 2017, 1:53 PM
lib/Analysis/LazyValueInfo.cpp
1508–1513

Yes, thanks!

hjyamauchi closed this revision.Aug 3 2017, 2:12 PM