Page MenuHomePhabricator

Add PredicateInfo utility and printing pass
ClosedPublic

Authored by dberlin on Feb 3 2017, 3:06 PM.

Details

Summary

This patch adds a utility to build extended SSA (see "ABCD: eliminating
array bounds checks on demand"), and an intrinsic to support it. This
is then used to get functionality equivalent to propagateEquality in
GVN, in NewGVN (without having to replace instructions as we go). It
would work similarly in SCCP or other passes. This has been talked
about a few times, so i built a real implementation and tried to
productionize it.

Copies are inserted for operands used in assumes and conditional
branches that are based on comparisons (see below for more)

Every use affected by the predicate is renamed to the appropriate
intrinsic result.

E.g.
%cmp = icmp eq i32 %x, 50
br i1 %cmp, label %true, label %false
true:
ret i32 %x
false:
ret i32 1

will become

%cmp = icmp eq i32, %x, 50
br i1 %cmp, label %true, label %false
true:
; Has predicate info
; branch predicate info { TrueEdge: 1 Comparison: %cmp = icmp eq i32 %x, 50 }
%x.0 = call @llvm.predicateinfo.i32(i32 %x)
ret i32 %x.0
false:
ret i23 1

(you can use -print-predicateinfo to get an annotated-with-predicateinfo dump)

This enables us to easily determine what operations are affected by a
given predicate, and how operations affected by a chain of
predicates.

Diff Detail

Repository
rL LLVM

Event Timeline

dberlin created this revision.Feb 3 2017, 3:06 PM
Prazek added inline comments.Feb 3 2017, 4:45 PM
lib/Transforms/Utils/PredicateInfo.cpp
433 ↗(On Diff #87042)

This looks like a single usage of the OBBMap inside PredicateInfo.
Shouldn't it be just created inside ValueDFS_Compare?

dberlin added inline comments.Feb 3 2017, 4:49 PM
lib/Transforms/Utils/PredicateInfo.cpp
433 ↗(On Diff #87042)

No.

  1. This way it is shared between all the use renaming regardless of whether we share the comparator or not (we happen to now). It's unlikely someone will notice that moving this inside the loop will cause it to create orderedbasicblocks all the time.
  1. We are going to use it in a followup.
nlopes added a subscriber: nlopes.Feb 5 2017, 8:06 AM
nlopes added inline comments.
include/llvm/Transforms/Utils/PredicateInfo.h
36 ↗(On Diff #87042)

typo: should be %x.0

  • Update for review comments
dberlin updated this revision to Diff 87166.Feb 5 2017, 1:37 PM
  • Fix a bug Nuno noticed where we are giving information about and/or on edges where the info is not useful and easy to use wrong
dberlin updated this revision to Diff 87167.Feb 5 2017, 1:38 PM

(Fixing update since it doesn't track that i last diffed against a
branch, so everytime i forget, it screws up the diff)

davide edited edge metadata.Feb 6 2017, 7:11 PM

Some comments inline. I want to take another look, but this is coming along very nicely.

include/llvm/Transforms/Utils/PredicateInfo.h
103–105 ↗(On Diff #87167)

I guess this comment should go before OriginalOp? Or am I reading it wrong?

109 ↗(On Diff #87167)

I guess this classof() is unneded, but please double-check.

125 ↗(On Diff #87167)

I guess this classof() is unneded, but please double-check.

146 ↗(On Diff #87167)

I guess this is unneeded, isn't it? (please double check).

lib/Transforms/Utils/PredicateInfo.cpp
65–73 ↗(On Diff #87167)

We have this similar pattern in many places now: NewGVN, SSAUpdater, MemSSA and now here. Too bad we can't actually share more.

141–145 ↗(On Diff #87167)

Remove braces.

156 ↗(On Diff #87167)

commented code, remove.

223–224 ↗(On Diff #87167)

Ugh, can you open a bug for this once the patch goes in?

585 ↗(On Diff #87160)

The new PM port doesn't do verification of PredicateInfo. Any reason why? (I think it's very useful as an increasing number of people is now playing with the new pass manager).

585 ↗(On Diff #87160)

Oh, I see you split in two different passes in the new PM. Sounds good.

dberlin marked 7 inline comments as done.Feb 6 2017, 8:15 PM
dberlin added inline comments.
include/llvm/Transforms/Utils/PredicateInfo.h
103–105 ↗(On Diff #87167)

no, not sure how that got to that point.

109 ↗(On Diff #87167)

We do the same thing in MemorySSA.h, but it looks like you are correct, we always allow upcasts, only requiring it for downcasts.

lib/Transforms/Utils/PredicateInfo.cpp
65–73 ↗(On Diff #87167)

As mentioned, i'm working on it :)

223–224 ↗(On Diff #87167)

Will do. I have to reduce it, but it's an assert here:
lib/IR/Function.cpp:537: assert(!STyp->isLiteral() && "TODO: implement literal types");

585 ↗(On Diff #87160)

Right.
It's not really worth it for the old PM i think, but in the new PM we would want to be able to verify that either it's all valid, or all gone :)

dberlin updated this revision to Diff 87360.Feb 6 2017, 8:18 PM
dberlin marked 2 inline comments as done.
  • Update for review comments
davide accepted this revision.Feb 7 2017, 11:20 AM

I took another closer look and I convinced myself this is correct. Just one comment inline.

lib/Transforms/Utils/PredicateInfo.cpp
111–124 ↗(On Diff #87360)

This is pretty much the same code. I would appreciate if you could consider the usage a lambda or an helper, if possible.

This revision is now accepted and ready to land.Feb 7 2017, 11:20 AM

This and D29606 (I actually reviewed them together after applying the patches), so feel free to land both if you're done with your testing. I'll review the NewGVN bits once you upload them (I assume you already have them split away as it was the only remaining part of the original review). Also, thank you very much for e-SSA. I think it's gonna be very useful in the future.

dberlin added inline comments.Feb 7 2017, 11:35 AM
lib/Transforms/Utils/PredicateInfo.cpp
111–124 ↗(On Diff #87360)

I will factor this out (and there is some in the follow-on patch for critical edges) into helpers

This revision was automatically updated to reflect the committed changes.