Page MenuHomePhabricator

[SImplifyCFG] Preserve knowledge about guarding condition by adding assume
ClosedPublic

Authored by dbakunevich on Sep 1 2021, 4:35 AM.

Details

Summary

This improvement aims to add "assume" after removing "undefined behavior" from "phinode" to improve optimization.

This code that I changed initially just removed the edge from the parent block that came in phinode with undefined behavior. Since the code simply removed the edge, there was no information left in the parent block under what condition the transition from the previous block to the current one was made.

pred:
  x = ...
  cond = x > 10
  br cond, bb, other.succ

bb:
  phi [nullptr, pred], ... // other possible preds
  load(phi) // UB if we came from pred

other.succ:
  // here we know that x <= 10, but this knowledge is lost
  // after the branch is turned to unconditional unless we
  // preserve it with assume.

Diff Detail

Event Timeline

dbakunevich created this revision.Sep 1 2021, 4:35 AM
dbakunevich requested review of this revision.Sep 1 2021, 4:35 AM
Herald added a project: Restricted Project. · View Herald TranscriptSep 1 2021, 4:35 AM
dbakunevich edited the summary of this revision. (Show Details)Sep 1 2021, 5:06 AM
dbakunevich edited the summary of this revision. (Show Details)Sep 1 2021, 5:43 AM
mkazantsev added a comment.EditedSep 1 2021, 10:00 PM

Please make the description more informative.

For patch name, I'd suggest something like "[SImplifyCFG] Preserve knowledge about guarding condition by adding assume".

The description is also confusing. I think what you are aiming would be

pred:
  x = ...
  cond = x > 10
  br cond, bb, other.succ

bb:
  phi [nullptr, pred], ... // other possible preds
  load(phi) // UB if we came from pred

other.succ:
  // here we know that x <= 10, but this knowledge is lost
  // after the branch is turned to unconditional unless we
  // preserve it with assume.
mkazantsev requested changes to this revision.Sep 1 2021, 10:03 PM

I'm OK with the code change, but please add some informative description on what this patch is about.

llvm/lib/Transforms/Utils/SimplifyCFG.cpp
6602

You can also add a comment on why is that made.

This revision now requires changes to proceed.Sep 1 2021, 10:03 PM
dbakunevich retitled this revision from Small improvement in SimplifyCFG.cpp to [SImplifyCFG] Preserve knowledge about guarding condition by adding assume.Sep 2 2021, 5:53 AM
dbakunevich edited the summary of this revision. (Show Details)
mkazantsev added inline comments.Sep 3 2021, 4:54 AM
llvm/lib/Transforms/Utils/SimplifyCFG.cpp
6601–6608

Do you mean "guarding condition", "assume" instea of "protection state" and "guess"?

dbakunevich marked an inline comment as done.
mkazantsev accepted this revision.Sep 6 2021, 9:58 PM

LGTM with a nit. Let's hold it for couple more days in case if someone has comments on it.

llvm/lib/Transforms/Utils/SimplifyCFG.cpp
6604

Move the comment here; I'd simply say "Preserve knowledge about guarding condition by adding an assume because it might not be inferrable anymore".

This revision is now accepted and ready to land.Sep 6 2021, 9:58 PM
lebedev.ri accepted this revision.Sep 7 2021, 1:25 AM

In general, i wonder if we should always be doing such a thing in situations like this.
There's potential the increase in block sizes will result in some other optimizations starting to fail.

In general, i wonder if we should always be doing such a thing in situations like this.
There's potential the increase in block sizes will result in some other optimizations starting to fail.

They should ignore such assumes anyway.

mkazantsev added a comment.EditedSep 7 2021, 11:12 PM

In general, i wonder if we should always be doing such a thing in situations like this.
There's potential the increase in block sizes will result in some other optimizations starting to fail.

If the removed condition is implied by another dominating condition, then we should theoretically still have all facts even after removal. It does not mean every pass *will* be able to infer it, but they *could*. But in this case, the removed condition might not be inferrable, because it is deleted based on something which is not (directly) related to it. So it makes sense to leave the assume in place.

As for the size -- assumed conditions should hopefully be ignored by costs models. If not, it's a bug in those cost models.

This revision was landed with ongoing or failed builds.Sep 8 2021, 12:06 AM
This revision was automatically updated to reflect the committed changes.