This is an archive of the discontinued LLVM Phabricator instance.

[CGP] Avoid segmentation fault when doing PHI node simplifications
ClosedPublic

Authored by bjope on Mar 16 2018, 9:30 AM.

Details

Summary

Made PHI node simplifiations more robust in several ways:

  • Minor refactoring to let the SimplificationTracker own the

sets with new PHI/Select nodes that are introduced. This is
maybe not mapping to the original intention with the
SimplificationTracker, but IMHO it encapsulates the logic behind
those sets a little bit better.

  • MatchPhiNode can sometimes populate the Matched set with

several entries, where it maps one PHI node to different candidates
for replacement. The Matched set is changed into a SmallSetVector
to make sure we get a deterministic iteration when doing
the replacements.

  • As described above we may get several different replacements

for a single PHI node. The loop in MatchPhiSet that is doing
the replacements could end up calling eraseFromParent several
times for the same PHI node, resulting in segmentation faults.
This problem was supposed to be fixed in rL327250, but due to
the non-determinism(?) it only appeared to be fixed (I still
got crashes sometime when turning on/off -print-after-all etc
to get different iteration order in the DenseSets).
With this patch we follow the deterministic ordering in the
Matched set when replacing the PHI nodes. If we find a new
replacement for an already replaced PHI node we replace the
new replacement by the old replacement instead. This is quite
similar to what happened in the rl327250 patch, but here we
also recursively verify that the old replacement hasn't been
replaced already.

  • It was really hard to track down the fault described above

(segementation fault due to doing eraseFromParent multiple
times for the same instruction). The fault was intermittent and
small changes in the code, or simply turning on -print-after-all
etc could make the problem go away. This was basically due to
the iteration over PhiNodesToMatch in MatchPhiSet no being
deterministic. Therefore I've changed the data structure for
the SimplificationTracker::AllPhiNodes into an SmallSetVector.
This gives a deterministic behavior.

Diff Detail

Event Timeline

bjope created this revision.Mar 16 2018, 9:30 AM
bjope added a comment.Mar 16 2018, 9:37 AM

I had not seen https://reviews.llvm.org/D43758 so this is my attempt at solving the same problem. Although, this patch also takes care of some problems with non-deterministic behavior.

I'm also a little bit afraid that the solution in D43758 has some other limitations. See the XXX at line 2983.
The new loop that was added in D43758 (to avoid multiple eraseFromParent() in the second loop) is doing eraseFromParent() itself. Without removing the erased PHI-nodes from the PhiNodesToMatch, and without making sure that the erased PHI nodes aren't already in the MatchedPHINodeMapping.

skatkov added inline comments.Mar 18 2018, 11:12 PM
lib/CodeGen/CodeGenPrepare.cpp
2642

It can be an assert now (taking into account two loops in the place of invocation.

2976–2977

you do not need {} now.

2979

Make sense however I guess that in general MV.second will never be in the PhiNodesToMatch.

The idea here that PhiNodesToMatch contains a Phi nodes created on previous steps. And they are matched against already existed Phi nodes before this algorithm started to work. So in general PhiNodesToMatch should not intersect with MV.second.

I guess assert will be ok in this case.

bjope updated this revision to Diff 139018.Mar 19 2018, 4:00 PM

Basically moved the solution from rL327250 into SimplificationTracker::ReplacePhi. This avoids the need for the DenseSet (with non-deterministic iteration) that was added in rL327250.

I also made sure that we recursively check if the new replacement already have been replaced when doing the simplifications for "already matched" nodes.

bjope edited the summary of this revision. (Show Details)Mar 19 2018, 4:02 PM
skatkov accepted this revision.Mar 20 2018, 12:23 AM
This revision is now accepted and ready to land.Mar 20 2018, 12:23 AM
This revision was automatically updated to reflect the committed changes.