Page MenuHomePhabricator

[LoopDeletion] Exploit undef Phi inputs when symbolically executing 1st iteration
ClosedPublic

Authored by mkazantsev on Jun 20 2021, 11:43 PM.

Details

Summary

Follow-up on Roman's idea expressed in D103959.

  • If a Phi has undefined inputs from live blocks:
    • and no other inputs, assume it is undef itself;
    • and exactly one non-undef input, we can assume that all undefs are equal to this input.

Diff Detail

Event Timeline

mkazantsev created this revision.Jun 20 2021, 11:43 PM
mkazantsev requested review of this revision.Jun 20 2021, 11:43 PM
Herald added a project: Restricted Project. · View Herald TranscriptJun 20 2021, 11:43 PM
mkazantsev planned changes to this revision.Jun 20 2021, 11:49 PM

Actually the 2nd part isn't true. Need rework.

mkazantsev edited the summary of this revision. (Show Details)

Fixed 2nd item

mkazantsev edited the summary of this revision. (Show Details)Jun 21 2021, 12:01 AM

Urgh, I double-checked with lang ref and my initial version was fine:

Branching on an undefined value is undefined behavior.

Rolling back to initial version.

mkazantsev edited the summary of this revision. (Show Details)

Looks good to me, thank you.

Urgh, I double-checked with lang ref and my initial version was fine:

Branching on an undefined value is undefined behavior.

Rolling back to initial version.

It is correct as per langref, but i'm not confident we currently
don't restrain ourselves about it in other places.

Hi,
I'm afraid that fixes on br i1 undef are still ongoing. I have one GSoC student who will work on fixing them.
Currently the list of buggy transformations are tracked at https://llvm.org/pr46144 .
Would it be a good idea to mark only one of edges live (line 344) and leave comment at pr46144 about this?

I would suggest splitting this into two patches. The "ignore undef input in phi" is safe, and commonly done across the optimizer. The "branch on undef" is tricky. Just from a risk management perspective, I think it makes sense to split them into separate changes.

If you want to split, you can consider this an LGTM for the "ignore undef input in phi" part, and then continue this review for the "branch on undef" part.

I'm fine with splitting this in two parts, especially if br i1 undef is broken.

mkazantsev edited the summary of this revision. (Show Details)

Split out 1st part only.

mkazantsev retitled this revision from [LoopDeletion] Exploit undef when symbolically executing 1st iteration to [LoopDeletion] Exploit undef Phi inputs when symbolically executing 1st iteration.
nikic accepted this revision.Jun 22 2021, 12:44 AM

LGTM

llvm/lib/Transforms/Scalar/LoopDeletion.cpp
263

nit: they are equal

llvm/test/Transforms/LoopDeletion/eval_first_iteration.ll
744

It would be good to replace these br i1 undef by br i1 %c1 where %c1 is an arg, to avoid making the code UB.

This revision is now accepted and ready to land.Jun 22 2021, 12:44 AM

As yesterday, wings-down to give some time to underlying patch to fail. :)

llvm/lib/Transforms/Scalar/LoopDeletion.cpp
263

Will fix

llvm/test/Transforms/LoopDeletion/eval_first_iteration.ll
744

Good point!

lebedev.ri accepted this revision.Jun 22 2021, 2:18 AM

LGTM, thank you.