This is an archive of the discontinued LLVM Phabricator instance.

Fix PR/33305. caused by trying to simplify expressions in phi of ops that should have no leaders.
ClosedPublic

Authored by dberlin on Aug 25 2017, 8:36 PM.

Details

Summary

After a discussion with Rekka, i believe this (or a small variant)
should fix the remaining phi-of-ops problems.

Rekka's algorithm for completeness relies on looking up expressions
that should have no leader, and expecting it to fail (IE looking up
expressions that can't exist in a predecessor, and expecting it to
find nothing).

Unfortunately, our simplifier outsmarts this by taking these "not
quite right" expressions, and simplifying them into other expressions
or walking through phis, etc. In the past, we've sometimes been able
to find leaders for them, incorrectly.

This change causes us to not use the simplifier on such
expressions. We determine safety by seeing if they depend on a phi
node dominated by our block.

This is not perfect, we can do better, but this should be a
"correctness start" that we can then improve. It also requires a
bunch of caching that i'll eventually like to eliminate.

The only thing i am not 100% positive on is whether it is safe to
apply constant folding. It looks like our constant folder will also
use computeknownbits to go walking through things, and i'm not
positive that is safe.

The right solution, longer term, is to make the query interface for
the instruction simplifier/constant folder have the flags we need, so
that we can keep most things going, but turn off the possibly-invalid
parts (threading through phis, etc).

My plan is to start with this patch, and see if anyone can find an
issue with constant folding. If so, we'll give up and scale it back
till we can change the query interface for the simplifier and use that.

Event Timeline

dberlin created this revision.Aug 25 2017, 8:36 PM

The 33461 change is an example where i believe what we were doing is safe, but i want to see if we still find correctness bugs first :)

(In particular, i believe it may be correct to only care about phi nodes in the same block as the one we are trying to translate through, which would fix 33461 back to the better codegen)

Unfortunately, i can prove we have to give up rather than try to constant fold in this case.

Given:

for.body.i:
   %tmp1 = phi i1 [ true, %entry ], [ false, %cond.end.i ]
   %f.08.i = phi i32 [ 0, %entry ], [ %inc.i, %cond.end.i ]
   %mul.i = select i1 %cmp1.i, i32 %f.08.i, i32 0
   br i1 %tmp1, label %cond.end.i, label %cond.true.i

 cond.true.i:
   ;; Ensure we don't replace this divide with a phi of ops that merges the wrong loop iteration value
   %div.i = udiv i32 %mul.i, %f.08.i
   br label %cond.end.i

And trying to perform phi of ops on the udiv, the expression that normally can't be found is udiv i32 %mul.i, 0, even though that expression is 0.

(%mul.i can't exist in the entry predecessor).

If we don't fail phi of ops in that case, we may get the wrong answer.

So i'm going to rework this slightly (I've also moved to recursive DFS, and not try to check operands we translated).

I'm going to also test the cost of doing recursive translation on all the operands to see which turn out constant or have leaders (which is safe, but O(N) in the depth of the expression tree)

We can cache the translations as they can't change until the related operands change, and see how expensive it is in practice.

That will actually catch *more* cases than we do now.

  • Update patch for correctness
  • Add test

This also fixes PR 33432, i forgot to add it to the log :)
With the latest update it should be correct now.

The only case we now miss is where we could use a phi-of-ops we created earlier to get the values.
I will handle this case in a followup

  • Update patch for correctness
  • Add test
  • NewGVN: Add debug message when we can't find a phi of ops operand but looked
  • NewGVN: Revert now-unnecessary changes

This has now passed all testing i can throw at it, so i'm going to commit it in a day or two, but please feel free to do post-commit review :)

  • NewGVN: Cleanup comments
davide accepted this revision.Sep 1 2017, 12:04 PM

I gave a round of light testing to this during the morning and it didn't expose any significant issue.
I agree with your plan, this looks like a good starting point. I'm not exactly looking forward to seeing fuzzer generated crazy miscompiles, so I hope this sticks together.

include/llvm/ADT/PackedVector.h
60 ↗(On Diff #113543)

This change slipped through the cracks.

lib/Transforms/Scalar/NewGVN.cpp
1800

I thought this part already went in

This revision is now accepted and ready to land.Sep 1 2017, 12:04 PM
This revision was automatically updated to reflect the committed changes.