This is an archive of the discontinued LLVM Phabricator instance.

[GVN] Fix undef incoming value for phi node when new loop exit block created.
Needs ReviewPublic

Authored by wwei on Sep 8 2020, 9:52 AM.

Details

Summary

In order to preserve LoopSimplify, SplitCriticalEdge will generate a new exit block,
which may become a new dominance frontier for dead blocks. After that, we need to
add this block to DF list, and update the undef incoming value for phi correctly.

Bugzilla:https://bugs.llvm.org/show_bug.cgi?id=47462

Diff Detail

Event Timeline

wwei created this revision.Sep 8 2020, 9:52 AM
wwei requested review of this revision.Sep 8 2020, 9:52 AM

The repository for this diff is specified as Zorg, which does not seem right.

asbirlea added inline comments.Sep 8 2020, 3:59 PM
llvm/lib/Transforms/Scalar/GVN.cpp
2822

Could you please explain in more details the mechanics here?
When added into Candidates, the llvm::any_of condition is true. What makes the condition become false below?
What's the purpose of the intersection of non-dead succs and preds?

2834

s/NewBolcks/NewBlocks

wwei updated this revision to Diff 290720.Sep 9 2020, 5:46 AM
wwei edited the summary of this revision. (Show Details)
wwei changed the repository for this revision from rZORG LLVM Github Zorg to rG LLVM Github Monorepo.
wwei added inline comments.Sep 9 2020, 5:56 AM
llvm/lib/Transforms/Scalar/GVN.cpp
2822

I have updated the code, and some comments to descibe the details for it.

    //     - - - - - - - -
    //    |    ... ...    |
    //    |[D1]           |   =>  A simplified loop<L>
    //    | |  \          |
    //    | |   [D2] [B1] |
    //     -|- - |- - |- -
    //      |    |    |
    //      \    |    /
    //       \   |   /
    //        [ DF1 ]        => exit block for loop<L>
    //
    // Consider the above scenario, there're two dead blocks [D1] + [D2], and
// a live block[B1]([D1][D2][B1] in one loop). [DF1] will a common dominance
    // frontier block for [D1] and [D2], so Candidates will contain two elements
    // [D1, D2]. [D1] has two succs: [D2] and [DF1], for [D1],first llvm::any_of
    // will return true, so splitCriticalEdges will be called.
    //
    //     - - - - - - - -
    //    |    ... ...    |
    //    |[D1]           |   =>  A simplified loop<L>
    //    | |  \          |
    //    | |   [D2] [B1] |
    //     -|- - |- - |- -
    //      |    |    |
    //      |    \    /
    //     [D3]   [DF2]      => New Exit block[DF2] for loop<L>
    //       \      |
    //        [ DF1 ]
    //
    // After splitCriticalEdges, a new crit_edge block[D3] will be created, and
    // it is added into dead blocks. Also, a new loop exit block[DF2] is created
    // to preserve LoopSimplify. After that, llvm::any_of will return false for
    // [D2], and we need to add [DF2] as a new dominance frontier block for [D2]
    // since it has a pred edge to non-dead block[B1], and then, we need to
    // update the undef incoming value for phi in [DF2].

About the purpose of the intersection of non-dead succs and preds, we should consider another case like below:

//     - - - - - - - -
//    |    ... ...    |
//    |    ... ...    |  =>  A simplified loop<L>
//    | [  D1 ]  [B1] |
//     -|- |- |- -|- - 
//      |  |  |   |
//      |  |  |   |
//      \  |  |   |
//       \ |  /  /
//        [ DF1 ]        => exit block for loop<L>
//
// After split edeges,
//     - - - - - - - -
//    |    ... ...    |
//    |    ... ...    |  =>  A simplified loop<L>
//    | [  D1  ]  [B1]|
//     -|-  |- |- -|-- 
//      |   |  |   |
//      |   |  \   /
//     [D2][D3][DF2]     => New Exit block[DF2] for loop<L>
//       \  |    /
//        [ DF1 ]
//
//    switch-case: [  D1  ] will have multi edges to  [ DF1 ], after split,  [D2][D3] are new created,
//    both will be dead blocks, so we need to use  the intersection of non-dead succs and preds to get [DF2]
wwei added inline comments.Sep 9 2020, 6:35 AM
llvm/lib/Transforms/Scalar/GVN.cpp
2834

changed.

wwei updated this revision to Diff 292540.Sep 17 2020, 9:24 AM

update test cases mentioned in PR47462

asbirlea added inline comments.Oct 5 2020, 11:31 PM
llvm/lib/Transforms/Scalar/GVN.cpp
2761–2762

It doesn't look like this condition is needed here anymore, since splitting critical edges is done below. So just checking isCriticalEdge should be enough to make it a candidate.

Simplify this to iterate over B's predecessors directly; the vector is not needed when predecessors don't change.

2822

Thank you for adding the example in code, that's very helpful!

I may be missing some details in the last example, but it seems like the non-dead predecessors for B (the IDF block) should cover the new blocks? ([D2]and [D3] should be in DeadBlocks following the split).

llvm/test/Transforms/GVN/pr47462.ll
2

Can you add a RUN line using the new pass manager? (-passes=...)

wwei updated this revision to Diff 296906.Oct 8 2020, 2:57 AM
wwei added inline comments.Oct 8 2020, 3:00 AM
llvm/lib/Transforms/Scalar/GVN.cpp
2761–2762

Thanks, fixed.

llvm/test/Transforms/GVN/pr47462.ll
2

done

wwei added inline comments.Oct 8 2020, 7:58 AM
llvm/lib/Transforms/Scalar/GVN.cpp
2822

yeah, the non-dead predecessors for B should cover the new blocks, there're some mistakes for the diagram after split edeges, the right one should be:

// After split edeges,
//     - - - - - - - -
//    |    ... ...    |
//    |    ... ...    |  =>  A simplified loop<L>
//    | [  D1  ]  [B1]|
//     -|-  |- |- -|-- 
//      |   |  |   |
//      |   \  |  /
//     [D2]  [DF2]       => New Exit block[DF2] for loop<L>
//       \     |
//        [ DF1 ]

[D2] and [DF2] are both new created blocks after split edeges,[D2] will be a dead block while [DF2] will be a new IDF block

asbirlea added inline comments.Nov 24 2020, 6:06 PM
llvm/lib/Transforms/Scalar/GVN.cpp
2758

for (BasicBlock *P : predecessors(B)) {

delete Preds.

2822

I didn't review further because I didn't see the change in code. Doesn't this mean just the predecessors is enough, vs intersection of succs and preds?