Page MenuHomePhabricator

[PredicateInfo] Replace pointer comparisons with deterministic compares.
ClosedPublic

Authored by fhahn on Jul 17 2019, 6:31 AM.

Details

Summary

Currently there are a few pointer comparisons in ValueDFS_Compare, which
can cause non-deterministic ordering when materializing values. There
are 2 cases this patch fixes:

  1. Order defs before uses used to compare pointers, which guarantees defs before uses, but causes non-deterministic ordering between 2 uses or 2 defs, depending on the allocation order. By converting the pointers to booleans, we can circumvent that problem.
  1. comparePHIRelated was comparing the basic block pointers of edges, which also results in a non-deterministic order and is also not really meaningful for ordering. By ordering by their destination DFS numbers we guarantee a deterministic order.

For the example below, we can end up with 2 different uselist orderings,
when running opt -mem2reg -ipsccp hundreds of times. Because the
non-determinism is caused by allocation ordering, we cannot reproduce it
with ipsccp alone.

declare i32 @hoge() local_unnamed_addr #0

define dso_local i32 @ham(i8* %arg, i8* %arg1) #0 {
bb:
  %tmp = alloca i32
  %tmp2 = alloca i32, align 4
  br label %bb19

bb4:                                              ; preds = %bb20
  br label %bb6

bb6:                                              ; preds = %bb4
  %tmp7 = call i32 @hoge()
  store i32 %tmp7, i32* %tmp
  %tmp8 = load i32, i32* %tmp
  %tmp9 = icmp eq i32 %tmp8, 912730082
  %tmp10 = load i32, i32* %tmp
  br i1 %tmp9, label %bb11, label %bb16

bb11:                                             ; preds = %bb6
  unreachable

bb13:                                             ; preds = %bb20
  br label %bb14

bb14:                                             ; preds = %bb13
  %tmp15 = load i32, i32* %tmp
  br label %bb16

bb16:                                             ; preds = %bb14, %bb6
  %tmp17 = phi i32 [ %tmp10, %bb6 ], [ 0, %bb14 ]
  br label %bb19

bb18:                                             ; preds = %bb20
  unreachable

bb19:                                             ; preds = %bb16, %bb
  br label %bb20

bb20:                                             ; preds = %bb19
  indirectbr i8* null, [label %bb4, label %bb13, label %bb18]
}

Diff Detail

Repository
rL LLVM

Event Timeline

fhahn created this revision.Jul 17 2019, 6:31 AM
Herald added a project: Restricted Project. · View Herald TranscriptJul 17 2019, 6:31 AM
fhahn updated this revision to Diff 210317.Jul 17 2019, 6:42 AM

Fix wording in assert messages.

efriedma added inline comments.Jul 23 2019, 2:36 PM
llvm/lib/Transforms/Utils/PredicateInfo.cpp
151 ↗(On Diff #210317)

Isn't isAU always equal to !isADef?

198 ↗(On Diff #210317)

Do you really need to compare AOut? getDFSNumIn() should be unique for every domtree node.

fhahn updated this revision to Diff 211782.Jul 25 2019, 9:41 AM

Address Eli's comments.

fhahn updated this revision to Diff 211784.Jul 25 2019, 9:50 AM

Remove some unnecessary comparisons of DSF out numbers.

fhahn marked 3 inline comments as done.Jul 25 2019, 9:52 AM
fhahn added inline comments.
llvm/lib/Transforms/Utils/PredicateInfo.cpp
151 ↗(On Diff #210317)

For edge only entries, both are null, but we still only need one.

198 ↗(On Diff #210317)

Thanks, I was going with the existing code to start with, but only comparing in numbers should be fine here (and a few other places I also adjusted)

efriedma accepted this revision.Jul 25 2019, 1:14 PM

LGTM with one nit.

llvm/test/Transforms/SCCP/ipsccp-predinfo-uselists.ll
2 ↗(On Diff #211784)

Is there any reason to add "preserve-ll-uselistorder" if you aren't actually going to CHECK it?

This revision is now accepted and ready to land.Jul 25 2019, 1:14 PM
fhahn marked 2 inline comments as done.Jul 25 2019, 1:30 PM
fhahn added inline comments.
llvm/test/Transforms/SCCP/ipsccp-predinfo-uselists.ll
2 ↗(On Diff #211784)

Nope, when starting to look at this issue, I suspected uselists to cause the problem, but it's not related and I'll drop it before committing,

fhahn added a comment.Jul 25 2019, 1:47 PM

Thanks Eli!

This revision was automatically updated to reflect the committed changes.