Page MenuHomePhabricator

[DFAJumpThreading] Determinator BB should precede switch-defining BB

Authored by alexey.zhikhar on Dec 15 2021, 2:40 PM.



Otherwise, it is possible that the state defined in the determinator
block defines the state for the next iteration of the loop, rather than
for the current one.

Fixes llvm-test-suite's
on X86.

Diff Detail

Event Timeline

alexey.zhikhar created this revision.Dec 15 2021, 2:40 PM
alexey.zhikhar requested review of this revision.Dec 15 2021, 2:40 PM
Herald added a project: Restricted Project. · View Herald TranscriptDec 15 2021, 2:40 PM

I attach a picture of the CFG illustrating the problem in one of the llvm-test-suite tests that was failing on X86.

The DFA jump threader attempted to jump-thread the switch inside the if.else basic block. One of the threading paths is

< if.else sw.default.i if.end while.body sw.bb1 sw.epilog >

where basic block sw.epilog is marked as the determinator.

Determinator BB is the BB that that contains the phi-node that "determines" the value of the switch condition. Does sw.epilog determine the next state in the switch statement inside if.else? Not immediately: %next.state first is propagated through %state.1 and %state and only then this new state is used.

To catch and discard this case, this patch verifies the sequence of types of basic blocks: determinator BB should be followed by the basic block that defines the switch condition, followed by the basic block that uses the switch condition (the BB with the candidate switch).

amehsan accepted this revision.EditedDec 17 2021, 7:52 AM

Alex and I have discussed this in detail. This testcase can also be investigated for potentially extending the algorithm. While we are confident that with the existing information (the paths that we gather during analysis phase) it is not possible to jump thread the switch statement, it may be possible to jump thread it if we gather more information (gathering a set of longer paths in the analysis phase). But at this point it does not seem worthwhile to explore this path, and the most reasonable solution is to add this new condition to make the case illegal. Alex have also compared with gcc, and they do not jump thread this switch statement.

This revision is now accepted and ready to land.Dec 17 2021, 7:52 AM
This revision was landed with ongoing or failed builds.Dec 24 2021, 7:28 AM
This revision was automatically updated to reflect the committed changes.