This is an archive of the discontinued LLVM Phabricator instance.

[LoopUnroll] Support loops with exiting block that is neither header nor latch.
ClosedPublic

Authored by Whitney on May 23 2020, 10:52 AM.

Diff Detail

Event Timeline

Whitney created this revision.May 23 2020, 10:52 AM
etiotto edited the summary of this revision. (Show Details)May 25 2020, 10:03 AM
etiotto added inline comments.May 25 2020, 10:28 AM
llvm/lib/Transforms/Utils/LoopUnroll.cpp
321–322

Please add a comment to explain why an exiting block conditional branch may be chosen with 'higher priority' and the rationale.

627–632

[Typo]: You mean: Keep track of the exiting block and its in successor block contained in the unrolled loop current iteration ?

llvm/test/Transforms/LoopUnroll/nonlatchcondbr.ll
48

In this case the exiting block is the loop header. This case would have been handled by the existing implementation. To test your new code path you should make the exiting block not be the loop header.

Whitney updated this revision to Diff 266097.May 25 2020, 7:04 PM
Whitney marked 3 inline comments as done.

Addressed @etiotto review comments.

lkail added a subscriber: lkail.May 25 2020, 7:22 PM

The patch doesn't apply cleanly to trunk. Could you update?

Could you summarize which restrictions remain?

llvm/lib/Transforms/Utils/LoopUnroll.cpp
306–312

Doesn't this need to be updated?

325–326

If this supports any number of exits, why the need to find a special one?

efriedma added inline comments.
llvm/lib/Transforms/Utils/LoopUnroll.cpp
330

An exiting block can't end in an unconditional branch.

In general, we don't know which exit the loop is actually going to use. Setting BI to refer to an arbitrary non-latch branch is suspicious; is it really necessary?

If you want to support loops with multiple exits, we need some appropriate testcases.

Could you clarify what "multi-exiting blocks" means?

The test case if for the exiting block being neither the header nor the latch. If any other restriction is lifted, please add a test case for it.

fhahn requested changes to this revision.May 26 2020, 3:25 AM

Could you clarify what "multi-exiting blocks" means?

I think it is supposed to refer to loops with "multiple exiting blocks". Might be good to update/clarify

The test case if for the exiting block being neither the header nor the latch. If any other restriction is lifted, please add a test case for it.

Yes I think this would need a range of tests with various scenarios with multiple exiting blocks (with/without constant exit take counts).

IIUC the patch currently aims to remove 2 restrictions: 1) single exiting block required and 2) exiting block must be either header or latch. It might be good to lift those 2 restrictions in separate patches.

llvm/lib/Transforms/Utils/LoopUnroll.cpp
330

In general, we don't know which exit the loop is actually going to use. Setting BI to refer to an arbitrary non-latch branch is suspicious; is it really necessary?

IIUC the exiting block (without this patch either latch or header) is only used to optimize away the conditional branch to the exit block, if possible. This should be an optimizations only, but we should apply it to all exiting block which conditions could be eliminated based on the unroll count. I've put up D80544 to hopefully make this more clearer in the code that actually handles connecting latches & headers.

This revision now requires changes to proceed.May 26 2020, 3:25 AM
Whitney updated this revision to Diff 266159.May 26 2020, 3:59 AM
Whitney marked 5 inline comments as done.

Updated the patch so it can be apply cleanly to trunk.
And addressed some of the comments.

Whitney retitled this revision from [LoopUnroll] Support loop with multi exiting blocks to [LoopUnroll] Support loop with multiple exiting blocks.May 26 2020, 3:59 AM
Whitney edited the summary of this revision. (Show Details)
Whitney added inline comments.
llvm/lib/Transforms/Utils/LoopUnroll.cpp
325–326

The code expects one exiting block to be used to optimize away the conditional branch to the exit block.
As mentioned by Florain, ideally we should apply it to all exiting block which conditions could be eliminated based on the unroll count.
However, before this patch, if the latch is not one of the exiting blocks and there exists more than one exiting blocks, then it won't unroll.
Now, these kind of loops can still be unrolled, and one of the exiting block conditional branch is optimized.

330

An exiting block can't end in an unconditional branch.

That's true, removed the check.

In general, we don't know which exit the loop is actually going to use. Setting BI to refer to an arbitrary non-latch branch is suspicious; is it really necessary?

The code below expects one exiting block to optimize. We still give highest priority to the latch branch.

If you want to support loops with multiple exits, we need some appropriate testcases.

Right, I agree more testcases are needed. I was hoping to get some suggestions during the review process, which I actually got some, I will add those.

Meinersbur added inline comments.May 26 2020, 4:22 AM
llvm/lib/Transforms/Utils/LoopUnroll.cpp
325–326

IIUC, the only branch that could be optimized away are the branches that enforces the max trip count as determined by SCEV (BackedgeTakenCount::getMax()). There is no choice in optimizing an arbitrary branch. I am not sure about SCEV's capabilities here, whether it gives e.g. a min(LimitByExit1,LimitByExit2). If so, then both of the exiting conditionals are necessary, as the trip count is computed in advance anyway.

If implemented more generally, we could partially unrolled even (potentially) infinite loops, but the exiting conditions has to be checked after every iteration.

In any case, arbitrarily choosing as single conditional is probably incorrect.

Could you clarify what "multi-exiting blocks" means?

I think it is supposed to refer to loops with "multiple exiting blocks". Might be good to update/clarify.

Yes, this is what I was looking to be clarified. Neither the test case, nor the code change (which is still looking for a single BranchInst) seemed to handle multiple loop exits.

Whitney updated this revision to Diff 266218.May 26 2020, 8:16 AM
Whitney retitled this revision from [LoopUnroll] Support loop with multiple exiting blocks to [LoopUnroll] Support loops with exiting block that is neither header nor latch..
Whitney edited the summary of this revision. (Show Details)

As suggested, modified this patch to only remove one limitation: exiting block must be either header or latch.

Whitney updated this revision to Diff 266335.May 26 2020, 2:48 PM

Update the patch after https://reviews.llvm.org/D80544 landed.

@fhahn @Meinersbur Hopefully I didn't miss addressing any comments for adding support for loops with exiting block that is neither header nor latch.
Please feel free let me know if I do. Thanks!

efriedma added inline comments.May 26 2020, 5:42 PM
llvm/lib/Transforms/Utils/LoopUnroll.cpp
315

Maybe call this ExitingBI? And put a comment something like the following:

// A conditional branch which exits the loop, which can be optimized to an
// unconditional branch in the unrolled loop in some cases.

We could probably allow unrolling even if ExitingBI is null, but we can leave that as a followup.

316

Maybe bool LatchIsExiting = L->isLoopExiting(LatchBlock);

321

The old code would reject any loop with a latch terminator that isn't a BranchInst. You probably want to keep that check; I'm not sure the rest of the code handles that case correctly.

Whitney updated this revision to Diff 266391.May 26 2020, 6:50 PM
Whitney marked 4 inline comments as done.
Whitney added a reviewer: efriedma.

Addressed Eli's review comments.

llvm/lib/Transforms/Utils/LoopUnroll.cpp
315

We could probably allow unrolling even if ExitingBI is null, but we can leave that as a followup.

That's one of the things I wanted to do in the original patch, but I probably described it very confusingly, by optimizing one exiting block instead of null.
I will do that after this patch landed with more test cases.

efriedma accepted this revision.May 26 2020, 9:25 PM

LGTM with a couple minor comments, but please give a little time for the other people who have looked at this to chime in.

llvm/lib/Transforms/Utils/LoopUnroll.cpp
315–320

Just dyn_cast<>: the latch always has a terminator

325

Also dyn_cast<> here. You only need dyn_cast_or_null if the argument can be null.

Whitney updated this revision to Diff 266492.May 27 2020, 5:08 AM

Addressed the latest two comments from Eli.

etiotto accepted this revision.May 28 2020, 7:14 AM

LGTM

fhahn added inline comments.May 28 2020, 8:41 AM
llvm/lib/Transforms/Utils/LoopUnroll.cpp
309

I think for 2) it should be sufficient to state that we require a single exiting block. Unless I am missing something, that also implies that the latch must either be unconditional or the exiting block.

320

We really only have to know about whether the latch is exiting when it comes to patching up the latches (around line 716). Might be good to move it down there and just use getExitingBlock unconditionally. It would also require moving incrementing the stats increment (NumUnrolledNotLatch++), but that makes sense further down below as well.

322

might be worth updating the wording to match the checks a bit closer, IIUC : loop does not have a single exiting block or latch or exiting block not terminated by a branch

803

The comment seems a bit out-of-date now. It would be good to re-phrase it in terms of exiting blocks.

Whitney updated this revision to Diff 266905.May 28 2020, 9:10 AM
Whitney marked 11 inline comments as done.

Addressed or replied all latest comments from Florian.

llvm/lib/Transforms/Utils/LoopUnroll.cpp
309

When the single loop latch is an exiting block, the loop is allowed to have multiple exiting blocks. This is the original behaviour.

320

But getExitingBlock may be nullptr when L->isLoopExiting(LatchBlock)

322

since multiple exiting block is allowed when loop latch is one of them, I current wording seems more relevant.

fhahn accepted this revision.May 28 2020, 10:03 AM

LGTM, thanks!

llvm/lib/Transforms/Utils/LoopUnroll.cpp
309

oh right, I thought we where restricting it to single exiting block earlier on, but it is indeed not the case.

This revision is now accepted and ready to land.May 28 2020, 10:03 AM
This revision was automatically updated to reflect the committed changes.

This patch causes a crash in the Linux kernel when building s390 allyesconfig:

$ git bisect log
# bad: [4e74541a928090b3604094e239884b0ea0a631bb] [LoopUnroll] Fix not-rotated.ll by adding back a limitation was unintentionally removed in https://reviews.llvm.org/D80477
# good: [49544499954912c5a0f02014de53e0bc0234c7af] [Driver][X86] Support branch align options with LTO
git bisect start '4e74541a928090b3604094e239884b0ea0a631bb' '49544499954912c5a0f02014de53e0bc0234c7af'
# good: [a7fa35a629e85a72b8cf07a8f95c7c09d9663808] [ThinLTO] Compute the basic block count across modules.
git bisect good a7fa35a629e85a72b8cf07a8f95c7c09d9663808
# good: [8b3155829a99fecc9e62f84d95668d0e85a0dd62] [MLIR] Fix build when NVPTX is not enabled
git bisect good 8b3155829a99fecc9e62f84d95668d0e85a0dd62
# good: [791c78f5e0ce84bcd4cfcccbbbbcc1259f4d7e0c] [NFC,StackSafety] Add test flag
git bisect good 791c78f5e0ce84bcd4cfcccbbbbcc1259f4d7e0c
# good: [8c050070fb96b4e6b8608a120d102bac0c8ada1c] [X86] Fix a nullptr dereference in X86Subtarget::classifyLocalReference when compiling with -mcmodel=medium -fpic and using a constant pool
git bisect good 8c050070fb96b4e6b8608a120d102bac0c8ada1c
# bad: [59ba12994c07d03ac3b628c05c45a834774f9b17] [llvm-xray][test] Fix unsupported-elf32.txt after D80185
git bisect bad 59ba12994c07d03ac3b628c05c45a834774f9b17
# good: [38727bab6f1337880861b7ffd5a02fcff581facc] [NFC][SLP] Add test case exposing SLP cost model bug. The bug is related to aggregate build cost model adjustment that adds a bias to cost triggering vectorization of actually unprofitable to vectorize tree.
git bisect good 38727bab6f1337880861b7ffd5a02fcff581facc
# bad: [1bc73b02d6934c8586ca5740da416b7094c3c471] [LoopUnroll] Support loops with exiting block that is neither header nor latch.
git bisect bad 1bc73b02d6934c8586ca5740da416b7094c3c471
# good: [b4668a268ddedea76bd406818fd0313b58e6f750] [AMDGPU] DWARF Proposal For Heterogeneous Debugging
git bisect good b4668a268ddedea76bd406818fd0313b58e6f750
# first bad commit: [1bc73b02d6934c8586ca5740da416b7094c3c471] [LoopUnroll] Support loops with exiting block that is neither header nor latch.

$ CROSS_COMPILE=s390x-linux-gnu-

$ make \
    -C "${HOME}"/src/linux \
    -s \
    ARCH=s390 \
    CROSS_COMPILE=${CROSS_COMPILE} \
    LLVM=1 \
    LD=${CROSS_COMPILE}ld \
    OBJCOPY=${CROSS_COMPILE}objcopy \
    OBJDUMP=${CROSS_COMPILE}objdump \
    O=out/s390 \
    distclean \
    allyesconfig \
    kernel/trace/trace_events_filter.o
DominatorTree is different than a freshly computed one!
	Current:
=============================--------------------------------
Inorder Dominator Tree: DFSNumbers invalid: 0 slow queries.
  [1] %entry {0,653} [0]
    [2] %if.end51.thread.i {1,2} [1]
    [2] %calc_stack.exit {3,586} [1]
      [3] %if.then {4,13} [2]
        [4] %sw.default {5,6} [3]
        [4] %sw.epilog {7,8} [3]
        [4] %sw.bb {9,10} [3]
        [4] %sw.bb2 {11,12} [3]
      [3] %cleanup {14,15} [2]
      [3] %if.end {16,585} [2]
        [4] %if.then3 {17,18} [3]
        [4] %if.end4 {19,584} [3]
          [5] %if.then.i {20,21} [4]
          [5] %predicate_parse.exit {22,27} [4]
            [6] %if.then7 {23,24} [5]
            [6] %do.body {25,26} [5]
          [5] %if.end.i48 {28,583} [4]
            [6] %if.end6.i {29,566} [5]
              [7] %if.then10.i {30,31} [6]
              [7] %if.end11.i {32,565} [6]
                [8] %if.end130.thread.i {33,34} [7]
                [8] %if.then132.i {35,36} [7]
                [8] %while.body.lr.ph.i {37,564} [7]
                  [9] %while.body.i {38,563} [8]
                    [10] %if.end17.i {39,500} [9]
                      [11] %sw.epilog.i54 {40,485} [10]
                        [12] %if.end37.i {41,482} [11]
                          [13] %while.end.i.i {42,469} [12]
                            [14] %while.cond5.i.i {43,468} [13]
                              [15] %lor.rhs.i.i {44,45} [14]
                              [15] %while.body20.i.i {46,465} [14]
                                [16] %while.body20.critedge.i.i.1 {47,48} [15]
                                [16] %lor.rhs.i.i.1 {49,462} [15]
                                  [17] %while.end22.i.i {50,461} [16]
                                    [18] %if.then.i.i {51,52} [17]
                                    [18] %parse_pred.exit.i {53,98} [17]
                                      [19] %if.then52.i {54,55} [18]
                                      [19] %if.end53.i {56,97} [18]
                                        [20] %while.cond54.outer.i {57,96} [19]
                                          [21] %while.cond54.i.peel.begin {4294967295,4294967295} [20]
                                            [22] %while.cond54.i.peel {4294967295,4294967295} [21]
                                              [23] %while.cond54.i.peel.next {4294967295,4294967295} [22]
                                                [24] %while.cond54.i.peel.next342 {4294967295,4294967295} [23]
                                                  [25] %while.cond54.outer.i.peel.newph {4294967295,4294967295} [24]
                                                    [26] %while.cond54.i {58,95} [25]
                                              [23] %if.end65.i {59,94} [22]
                                                [24] %sw.default.i {60,61} [23]
                                                [24] %sw.epilog82.i {62,89} [23]
                                                  [25] %if.end89.i {63,86} [24]
                                                    [26] %if.then93.i {64,65} [25]
                                                    [26] %while.end.i {66,67} [25]
                                                    [26] %if.end94.i {68,85} [25]
                                                      [27] %if.end103.i {69,82} [26]
                                                        [28] %if.then107.i {70,71} [27]
                                                        [28] %if.end109.i {72,81} [27]
                                                          [29] %cleanup.thread32.i {73,74} [28]
                                                          [29] %if.end112.i {75,80} [28]
                                                            [30] %if.then115.i {76,77} [29]
                                                            [30] %if.end120.i {78,79} [29]
                                                      [27] %if.then97.i {83,84} [26]
                                                  [25] %if.then86.i {87,88} [24]
                                                [24] %sw.bb68.i {90,93} [23]
                                                  [25] %if.then75.i57 {91,92} [24]
                                    [18] %if.end.i.i {99,460} [17]
                                      [19] %if.then26.i.i {100,101} [18]
                                      [19] %if.end27.i.i {102,459} [18]
                                        [20] %if.then30.i.i {103,104} [19]
                                        [20] %while.cond32.preheader.i.i {105,458} [19]
                                          [21] %while.end44.i.i {106,445} [20]
                                            [22] %for.body.i.i {107,444} [21]
                                              [23] %if.end66.i.i {108,437} [22]
                                                [24] %kzalloc.exit.i.i {109,424} [23]
                                                  [25] %if.then88.i.i {110,111} [24]
                                                  [25] %if.end89.i.i {112,423} [24]
                                                    [26] %if.then94.i.i {113,158} [25]
                                                      [27] %if.end100.i.i {114,155} [26]
                                                        [28] %if.then111.i.i {115,116} [27]
                                                        [28] %if.end114.i.i {117,150} [27]
                                                          [29] %for.end154.i.i {118,119} [28]
                                                          [29] %if.end158.i.i {120,125} [28]
                                                            [30] %if.then162.i.i {121,122} [29]
                                                            [30] %if.end164.i.i {123,124} [29]
                                                          [29] %if.end158.i.i.sink.split {126,127} [28]
                                                          [29] %for.body120.lr.ph.i.i {128,149} [28]
                                                            [30] %for.body120.i.i {129,148} [29]
                                                              [31] %land.lhs.true132.i.i {130,137} [30]
                                                                [32] %lor.lhs.false138.i.i {131,134} [31]
                                                                  [33] %lor.lhs.false144.i.i {132,133} [32]
                                                                [32] %if.end158.i.i.sink.split.loopexit {135,136} [31]
                                                              [31] %for.inc152.i.i {138,141} [30]
                                                                [32] %for.end154.i.i.loopexit {139,140} [31]
                                                              [31] %land.lhs.true.i.i {142,147} [30]
                                                                [32] %for.end154.thread593.i.i {143,144} [31]
                                                                [32] %if.end130.i.i {145,146} [31]
                                                        [28] %lor.lhs.false.i.i {151,154} [27]
                                                          [29] %if.else.i.i {152,153} [28]
                                                      [27] %if.then98.i.i {156,157} [26]
                                                    [26] %if.end355.i.i {159,160} [25]
                                                    [26] %if.else175.i.i {161,422} [25]
                                                      [27] %if.then187.i.i {162,297} [26]
                                                        [28] %sw.default.i.i {163,164} [27]
                                                        [28] %cleanup.thread.i.i {165,166} [27]
                                                        [28] %sw.bb.i.i {167,168} [27]
                                                        [28] %sw.epilog.i.i {169,296} [27]
                                                          [29] %is_string_field.exit591.thread.i.i {170,171} [28]
                                                          [29] %if.end196.i.i {172,287} [28]
                                                            [30] %for.end213.i.i {173,264} [29]
                                                              [31] %if.then217.i.i {174,175} [30]
                                                              [31] %if.end219.i.i {176,263} [30]
                                                                [32] %if.then224.i.i {177,178} [31]
                                                                [32] %if.end226.i.i {179,262} [31]
                                                                  [33] %if.then.i.i.i {180,239} [32]
                                                                    [34] %if.then.i.i.i.i {181,182} [33]
                                                                    [34] %if.end.i.i.i.i {183,236} [33]
                                                                      [35] %land.rhs.i.i.i.i.i {184,187} [34]
                                                                        [36] %if.then4.i.i.i.i {185,186} [35]
                                                                      [35] %if.end5.i.i.i.i {188,223} [34]
                                                                        [36] %for.body.preheader.i.i.i.i {189,216} [35]
                                                                          [37] %for.body.i.i.i.i {190,215} [36]
                                                                            [38] %if.then12.i.i.i.i {191,206} [37]
                                                                              [39] %if.then14.i.i.i.i {192,193} [38]
                                                                              [39] %if.else15.i.i.i.i {194,205} [38]
                                                                                [40] %if.then18.i.i.i.i {195,202} [39]
                                                                                  [41] %if.then21.i.i.i.i {196,197} [40]
                                                                                  [41] %if.end23.i.i.i.i {198,199} [40]
                                                                                  [41] %if.else22.i.i.i.i {200,201} [40]
                                                                                [40] %if.else26.i.i.i.i {203,204} [39]
                                                                            [38] %for.inc.i.i.i.i {207,210} [37]
                                                                              [39] %for.end.i.i.i.i.loopexit {208,209} [38]
                                                                            [38] %if.else28.i.i.i.i {211,214} [37]
                                                                              [39] %if.then34.i.i.i.i {212,213} [38]
                                                                        [36] %for.end.i.i.i.i {217,222} [35]
                                                                          [37] %if.then41.i.i.i.i {218,219} [36]
                                                                          [37] %if.end42.i.i.i.i {220,221} [36]
                                                                      [35] %if.end.i.i.i {224,233} [34]
                                                                        [36] %sw.bb8.i.i.i {225,226} [35]
                                                                        [36] %sw.bb10.i.i.i {227,228} [35]
                                                                        [36] %sw.bb12.i.i.i {229,230} [35]
                                                                        [36] %sw.bb14.i.i.i {231,232} [35]
                                                                      [35] %if.end5.critedge.i.i.i.i {234,235} [34]
                                                                    [34] %if.else.i.i.i.i {237,238} [33]
                                                                  [33] %filter_build_regex.exit.i.i {240,255} [32]
                                                                    [34] %if.then242.i.i {241,242} [33]
                                                                    [34] %cleanup.i.i {243,244} [33]
                                                                    [34] %if.else244.i.i {245,254} [33]
                                                                      [35] %if.then248.i.i {246,247} [34]
                                                                      [35] %if.else251.i.i {248,253} [34]
                                                                        [36] %if.then255.i.i {249,250} [35]
                                                                        [36] %if.else257.i.i {251,252} [35]
                                                                  [33] %sw.bb.i.i.i {256,257} [32]
                                                                  [33] %filter_build_regex.exit.i.i.sink.split {258,259} [32]
                                                                  [33] %if.end.thread.i.i.i {260,261} [32]
                                                            [30] %for.body202.i.preheader.i {265,286} [29]
                                                              [31] %for.inc211.i.i.preheader {266,285} [30]
                                                                [32] %for.inc211.i.i {267,284} [31]
                                                                  [33] %for.end213.i.i.loopexit {268,269} [32]
                                                                  [33] %for.body202.i.i {270,283} [32]
                                                                    [34] %for.inc211.i.i.1 {271,282} [33]
                                                                      [35] %for.body202.i.i.1 {272,281} [34]
                                                                        [36] %for.inc211.i.i.2 {273,280} [35]
                                                                          [37] %for.body202.i.i.2 {274,279} [36]
                                                                            [38] %for.inc211.i.i.3 {275,278} [37]
                                                                              [39] %for.body202.i.i.3 {276,277} [38]
                                                          [29] %lor.lhs.false.i586.i.i {288,295} [28]
                                                            [30] %lor.lhs.false3.i588.i.i {289,294} [29]
                                                              [31] %is_string_field.exit591.i.i {290,293} [30]
                                                                [32] %if.then194.i.i {291,292} [31]
                                                      [27] %lor.lhs.false181.i.i {298,421} [26]
                                                        [28] %if.else263.i.i {299,420} [27]
                                                          [29] %land.rhs.i.i.i {300,301} [28]
                                                          [29] %isdigit.exit.i.i {302,419} [28]
                                                            [30] %lor.lhs.false269.i.i {303,306} [29]
                                                              [31] %if.else351.i.i {304,305} [30]
                                                            [30] %if.then275.i.i {307,418} [29]
                                                              [31] %is_string_field.exit.thread.i.i {308,309} [30]
                                                              [31] %if.then277.i.i {310,311} [30]
                                                              [31] %lor.lhs.false.i.i.i {312,417} [30]
                                                                [32] %lor.lhs.false3.i.i.i {313,416} [31]
                                                                  [33] %is_string_field.exit.i.i {314,415} [32]
                                                                    [34] %if.end279.i.i {315,414} [33]
                                                                      [35] %if.then282.i.i {316,317} [34]
                                                                      [35] %if.end284.i.i {318,413} [34]
                                                                        [36] %if.then290.i.i {319,320} [35]
                                                                        [36] %if.end292.i.i {321,412} [35]
                                                                          [37] %while.end305.i.i {322,399} [36]
                                                                            [38] %if.then310.i.i {323,324} [37]
                                                                            [38] %if.end312.i.i {325,398} [37]
                                                                              [39] %if.else324.i.i {326,327} [38]
                                                                              [39] %if.end327.i.i {328,395} [38]
                                                                                [40] %if.end331.i.i {329,392} [39]
                                                                                  [41] %if.then336.i.i {330,331} [40]
                                                                                  [41] %if.else338.i.i {332,391} [40]
                                                                                    [42] %sw.epilog.i.i.i {333,376} [41]
                                                                                      [43] %sw.epilog107.i.i.i {334,335} [42]
                                                                                      [43] %sw.bb54.i.i.i {336,345} [42]
                                                                                        [44] %if.then57.i.i.i {337,338} [43]
                                                                                        [44] %if.else.i.i.i {339,344} [43]
                                                                                          [45] %if.else60.i.i.i {340,341} [44]
                                                                                          [45] %if.then59.i.i.i {342,343} [44]
                                                                                      [43] %sw.bb65.i.i.i {346,355} [42]
                                                                                        [44] %if.then68.i.i.i {347,348} [43]
                                                                                        [44] %if.else69.i.i.i {349,354} [43]
                                                                                          [45] %if.else74.i.i.i {350,351} [44]
                                                                                          [45] %if.then71.i.i.i {352,353} [44]
                                                                                      [43] %sw.bb79.i.i.i {356,365} [42]
                                                                                        [44] %if.then82.i.i.i {357,358} [43]
                                                                                        [44] %if.else83.i.i.i {359,364} [43]
                                                                                          [45] %if.else88.i.i.i {360,361} [44]
                                                                                          [45] %if.then85.i.i.i {362,363} [44]
                                                                                      [43] %sw.bb93.i.i.i {366,375} [42]
                                                                                        [44] %if.then96.i.i.i {367,368} [43]
                                                                                        [44] %if.else97.i.i.i {369,374} [43]
                                                                                          [45] %if.else102.i.i.i {370,371} [44]
                                                                                          [45] %if.then99.i.i.i {372,373} [44]
                                                                                    [42] %select_comparison_fn.exit.i.i {377,380} [41]
                                                                                      [43] %if.then347.i.i {378,379} [42]
                                                                                    [42] %sw.default.i.i.i {381,390} [41]
                                                                                      [43] %do.body7.i.i.i {382,383} [42]
                                                                                      [43] %if.end19.critedge.i.i.i {384,389} [42]
                                                                                        [44] %do.body37.i.i.i {385,386} [43]
                                                                                        [44] %sw.epilog.critedge.i.i.i {387,388} [43]
                                                                                [40] %if.then329.i.i {393,394} [39]
                                                                              [39] %if.then321.i.i {396,397} [38]
                                                                          [37] %while.body303.i.i.preheader {400,411} [36]
                                                                            [38] %while.body303.i.i {401,410} [37]
                                                                              [39] %while.end305.i.i.loopexit {402,403} [38]
                                                                              [39] %while.body303.i.i.1 {404,409} [38]
                                                                                [40] %while.body303.i.i.2 {405,408} [39]
                                                                                  [41] %while.body303.i.i.3 {406,407} [40]
                                                [24] %while.body83.i.i.preheader {425,436} [23]
                                                  [25] %while.body83.i.i {426,435} [24]
                                                    [26] %kzalloc.exit.i.i.loopexit {427,428} [25]
                                                    [26] %while.body83.i.i.1 {429,434} [25]
                                                      [27] %while.body83.i.i.2 {430,433} [26]
                                                        [28] %while.body83.i.i.3 {431,432} [27]
                                              [23] %err_free.i.i {438,439} [22]
                                              [23] %for.inc.i.i {440,443} [22]
                                                [24] %if.then64.i.i {441,442} [23]
                                          [21] %while.body42.i.i.preheader {446,457} [20]
                                            [22] %while.body42.i.i {447,456} [21]
                                              [23] %while.end44.i.i.loopexit {448,449} [22]
                                              [23] %while.body42.i.i.1 {450,455} [22]
                                                [24] %while.body42.i.i.2 {451,454} [23]
                                                  [25] %while.body42.i.i.3 {452,453} [24]
                                [16] %while.body20.i.i.1 {463,464} [15]
                              [15] %while.body20.critedge.i.i {466,467} [14]
                          [13] %while.body.i.i.preheader {470,481} [12]
                            [14] %while.body.i.i {471,480} [13]
                              [15] %while.end.i.i.loopexit {472,473} [14]
                              [15] %while.body.i.i.1 {474,479} [14]
                                [16] %while.body.i.i.2 {475,478} [15]
                                  [17] %while.body.i.i.3 {476,477} [16]
                        [12] %if.then32.i {483,484} [11]
                      [11] %cleanup.thread.i {486,487} [10]
                      [11] %sw.bb.i52 {488,493} [10]
                        [12] %if.then22.i {489,490} [11]
                        [12] %if.end23.i {491,492} [11]
                      [11] %sw.bb25.i {494,499} [10]
                        [12] %if.end28.i {495,496} [11]
                        [12] %is_not.exit.i {497,498} [11]
                    [10] %cleanup.i58 {501,504} [9]
                      [11] %out.i.loopexit {502,503} [10]
                    [10] %out.i {505,560} [9]
                      [11] %if.end130.i {506,557} [10]
                        [12] %if.end130.i.if.then132.i_crit_edge {507,508} [11]
                        [12] %if.end137.i {509,556} [11]
                          [13] %for.end.i61 {510,527} [12]
                            [14] %for.body184.preheader.i {511,524} [13]
                              [15] %for.body184.i {512,523} [14]
                                [16] %for.inc.critedge.i {513,520} [15]
                                  [17] %for.end237.i.loopexit {514,515} [16]
                                  [17] %for.body184.i.1 {516,519} [16]
                                    [18] %for.inc.critedge.i.1 {517,518} [17]
                                [16] %do.body219.i {521,522} [15]
                            [14] %for.end237.i {525,526} [13]
                          [13] %for.body.preheader.i {528,555} [12]
                            [14] %for.body.i59.prol.preheader {529,536} [13]
                              [15] %for.body.i59.prol {530,535} [14]
                                [16] %if.then173.i.prol {531,532} [15]
                                [16] %if.end180.i.prol {533,534} [15]
                            [14] %for.body.i59.prol.loopexit {537,554} [13]
                              [15] %for.body.preheader.i.new {538,551} [14]
                                [16] %for.body.i59 {539,550} [15]
                                  [17] %if.then173.i {540,541} [16]
                                  [17] %if.end180.i {542,549} [16]
                                    [18] %if.end180.i.1 {543,546} [17]
                                      [19] %for.end.i61.loopexit.unr-lcssa {544,545} [18]
                                    [18] %if.then173.i.1 {547,548} [17]
                              [15] %for.end.i61.loopexit {552,553} [14]
                      [11] %if.then125.i {558,559} [10]
                    [10] %if.then16.i {561,562} [9]
            [6] %out_free.i {567,580} [5]
              [7] %if.then239.i {568,577} [6]
                [8] %for.end251.i {569,570} [7]
                [8] %for.body245.i.preheader {571,576} [7]
                  [9] %for.body245.i {572,575} [8]
                    [10] %for.end251.i.loopexit {573,574} [9]
              [7] %if.end252.i {578,579} [6]
            [6] %if.then5.i {581,582} [5]
    [2] %for.body.i.preheader {587,652} [1]
      [3] %for.body.i {588,651} [2]
        [4] %if.end.i {589,616} [3]
          [5] %if.end16.i {590,611} [4]
            [6] %sw.epilog.i {591,594} [5]
              [7] %if.then45.i {592,593} [6]
            [6] %sw.bb.i {595,596} [5]
            [6] %sw.bb23.i {597,600} [5]
              [7] %if.end33.i {598,599} [6]
            [6] %sw.bb34.i {601,604} [5]
              [7] %if.then37.i {602,603} [6]
            [6] %sw.bb39.i {605,610} [5]
              [7] %if.end43.i {606,607} [6]
              [7] %calc_stack.exit.loopexit {608,609} [6]
          [5] %if.then8.i {612,615} [4]
            [6] %if.then14.i {613,614} [5]
        [4] %for.inc.i {617,650} [3]
          [5] %for.end.i {618,649} [4]
            [6] %if.end51.i {619,648} [5]
              [7] %if.then54.i {620,647} [6]
                [8] %for.end87.i {621,622} [7]
                [8] %for.body58.i.preheader {623,646} [7]
                  [9] %for.body58.i {624,645} [8]
                    [10] %if.end68.i {625,636} [9]
                      [11] %sw.bb72.i {626,631} [10]
                        [12] %if.then75.i {627,628} [11]
                        [12] %if.end76.i {629,630} [11]
                      [11] %sw.bb78.i {632,633} [10]
                      [11] %sw.bb80.i {634,635} [10]
                    [10] %for.inc85.i {637,640} [9]
                      [11] %for.end87.i.loopexit {638,639} [10]
                    [10] %if.then60.i {641,644} [9]
                      [11] %if.then66.i {642,643} [10]
Roots: %entry 

	Freshly computed tree:
=============================--------------------------------
Inorder Dominator Tree: DFSNumbers invalid: 0 slow queries.
  [1] %entry {4294967295,4294967295} [0]
    [2] %if.end51.thread.i {4294967295,4294967295} [1]
    [2] %calc_stack.exit {4294967295,4294967295} [1]
      [3] %if.then {4294967295,4294967295} [2]
        [4] %sw.default {4294967295,4294967295} [3]
        [4] %sw.epilog {4294967295,4294967295} [3]
        [4] %sw.bb {4294967295,4294967295} [3]
        [4] %sw.bb2 {4294967295,4294967295} [3]
      [3] %cleanup {4294967295,4294967295} [2]
      [3] %if.end {4294967295,4294967295} [2]
        [4] %if.then3 {4294967295,4294967295} [3]
        [4] %if.end4 {4294967295,4294967295} [3]
          [5] %if.then.i {4294967295,4294967295} [4]
          [5] %predicate_parse.exit {4294967295,4294967295} [4]
            [6] %if.then7 {4294967295,4294967295} [5]
            [6] %do.body {4294967295,4294967295} [5]
          [5] %if.end.i48 {4294967295,4294967295} [4]
            [6] %if.end6.i {4294967295,4294967295} [5]
              [7] %if.then10.i {4294967295,4294967295} [6]
              [7] %if.end11.i {4294967295,4294967295} [6]
                [8] %if.end130.thread.i {4294967295,4294967295} [7]
                [8] %if.then132.i {4294967295,4294967295} [7]
                [8] %while.body.lr.ph.i {4294967295,4294967295} [7]
                  [9] %while.body.i {4294967295,4294967295} [8]
                    [10] %if.end17.i {4294967295,4294967295} [9]
                      [11] %sw.epilog.i54 {4294967295,4294967295} [10]
                        [12] %if.end37.i {4294967295,4294967295} [11]
                          [13] %while.end.i.i {4294967295,4294967295} [12]
                            [14] %while.cond5.i.i {4294967295,4294967295} [13]
                              [15] %lor.rhs.i.i {4294967295,4294967295} [14]
                              [15] %while.body20.i.i {4294967295,4294967295} [14]
                                [16] %lor.rhs.i.i.1 {4294967295,4294967295} [15]
                                [16] %while.body20.i.i.1 {4294967295,4294967295} [15]
                                [16] %while.body20.critedge.i.i.1 {4294967295,4294967295} [15]
                              [15] %while.end22.i.i {4294967295,4294967295} [14]
                                [16] %if.then.i.i {4294967295,4294967295} [15]
                                [16] %parse_pred.exit.i {4294967295,4294967295} [15]
                                  [17] %if.then52.i {4294967295,4294967295} [16]
                                  [17] %if.end53.i {4294967295,4294967295} [16]
                                    [18] %while.cond54.outer.i {4294967295,4294967295} [17]
                                      [19] %while.cond54.i.peel.begin {4294967295,4294967295} [18]
                                        [20] %while.cond54.i.peel {4294967295,4294967295} [19]
                                          [21] %if.end65.i {4294967295,4294967295} [20]
                                            [22] %sw.default.i {4294967295,4294967295} [21]
                                            [22] %sw.epilog82.i {4294967295,4294967295} [21]
                                              [23] %if.end89.i {4294967295,4294967295} [22]
                                                [24] %if.then93.i {4294967295,4294967295} [23]
                                                [24] %while.end.i {4294967295,4294967295} [23]
                                                [24] %if.end94.i {4294967295,4294967295} [23]
                                                  [25] %if.end103.i {4294967295,4294967295} [24]
                                                    [26] %if.then107.i {4294967295,4294967295} [25]
                                                    [26] %if.end109.i {4294967295,4294967295} [25]
                                                      [27] %cleanup.thread32.i {4294967295,4294967295} [26]
                                                      [27] %if.end112.i {4294967295,4294967295} [26]
                                                        [28] %if.then115.i {4294967295,4294967295} [27]
                                                        [28] %if.end120.i {4294967295,4294967295} [27]
                                                  [25] %if.then97.i {4294967295,4294967295} [24]
                                              [23] %if.then86.i {4294967295,4294967295} [22]
                                            [22] %sw.bb68.i {4294967295,4294967295} [21]
                                              [23] %if.then75.i57 {4294967295,4294967295} [22]
                                          [21] %while.cond54.i.peel.next {4294967295,4294967295} [20]
                                            [22] %while.cond54.i.peel.next342 {4294967295,4294967295} [21]
                                              [23] %while.cond54.outer.i.peel.newph {4294967295,4294967295} [22]
                                                [24] %while.cond54.i {4294967295,4294967295} [23]
                                [16] %if.end.i.i {4294967295,4294967295} [15]
                                  [17] %if.then26.i.i {4294967295,4294967295} [16]
                                  [17] %if.end27.i.i {4294967295,4294967295} [16]
                                    [18] %if.then30.i.i {4294967295,4294967295} [17]
                                    [18] %while.cond32.preheader.i.i {4294967295,4294967295} [17]
                                      [19] %while.end44.i.i {4294967295,4294967295} [18]
                                        [20] %for.body.i.i {4294967295,4294967295} [19]
                                          [21] %if.end66.i.i {4294967295,4294967295} [20]
                                            [22] %kzalloc.exit.i.i {4294967295,4294967295} [21]
                                              [23] %if.then88.i.i {4294967295,4294967295} [22]
                                              [23] %if.end89.i.i {4294967295,4294967295} [22]
                                                [24] %if.then94.i.i {4294967295,4294967295} [23]
                                                  [25] %if.end100.i.i {4294967295,4294967295} [24]
                                                    [26] %if.then111.i.i {4294967295,4294967295} [25]
                                                    [26] %if.end114.i.i {4294967295,4294967295} [25]
                                                      [27] %for.end154.i.i {4294967295,4294967295} [26]
                                                      [27] %if.end158.i.i {4294967295,4294967295} [26]
                                                        [28] %if.then162.i.i {4294967295,4294967295} [27]
                                                        [28] %if.end164.i.i {4294967295,4294967295} [27]
                                                      [27] %if.end158.i.i.sink.split {4294967295,4294967295} [26]
                                                      [27] %for.body120.lr.ph.i.i {4294967295,4294967295} [26]
                                                        [28] %for.body120.i.i {4294967295,4294967295} [27]
                                                          [29] %land.lhs.true132.i.i {4294967295,4294967295} [28]
                                                            [30] %if.end158.i.i.sink.split.loopexit {4294967295,4294967295} [29]
                                                            [30] %lor.lhs.false138.i.i {4294967295,4294967295} [29]
                                                              [31] %lor.lhs.false144.i.i {4294967295,4294967295} [30]
                                                          [29] %for.inc152.i.i {4294967295,4294967295} [28]
                                                            [30] %for.end154.i.i.loopexit {4294967295,4294967295} [29]
                                                          [29] %land.lhs.true.i.i {4294967295,4294967295} [28]
                                                            [30] %for.end154.thread593.i.i {4294967295,4294967295} [29]
                                                            [30] %if.end130.i.i {4294967295,4294967295} [29]
                                                    [26] %lor.lhs.false.i.i {4294967295,4294967295} [25]
                                                      [27] %if.else.i.i {4294967295,4294967295} [26]
                                                  [25] %if.then98.i.i {4294967295,4294967295} [24]
                                                [24] %if.end355.i.i {4294967295,4294967295} [23]
                                                [24] %if.else175.i.i {4294967295,4294967295} [23]
                                                  [25] %if.then187.i.i {4294967295,4294967295} [24]
                                                    [26] %sw.default.i.i {4294967295,4294967295} [25]
                                                    [26] %cleanup.thread.i.i {4294967295,4294967295} [25]
                                                    [26] %sw.bb.i.i {4294967295,4294967295} [25]
                                                    [26] %sw.epilog.i.i {4294967295,4294967295} [25]
                                                      [27] %is_string_field.exit591.thread.i.i {4294967295,4294967295} [26]
                                                      [27] %if.end196.i.i {4294967295,4294967295} [26]
                                                        [28] %for.end213.i.i {4294967295,4294967295} [27]
                                                          [29] %if.then217.i.i {4294967295,4294967295} [28]
                                                          [29] %if.end219.i.i {4294967295,4294967295} [28]
                                                            [30] %if.then224.i.i {4294967295,4294967295} [29]
                                                            [30] %if.end226.i.i {4294967295,4294967295} [29]
                                                              [31] %if.then.i.i.i {4294967295,4294967295} [30]
                                                                [32] %if.then.i.i.i.i {4294967295,4294967295} [31]
                                                                [32] %if.end.i.i.i.i {4294967295,4294967295} [31]
                                                                  [33] %land.rhs.i.i.i.i.i {4294967295,4294967295} [32]
                                                                    [34] %if.then4.i.i.i.i {4294967295,4294967295} [33]
                                                                  [33] %if.end5.i.i.i.i {4294967295,4294967295} [32]
                                                                    [34] %for.body.preheader.i.i.i.i {4294967295,4294967295} [33]
                                                                      [35] %for.body.i.i.i.i {4294967295,4294967295} [34]
                                                                        [36] %if.then12.i.i.i.i {4294967295,4294967295} [35]
                                                                          [37] %if.then14.i.i.i.i {4294967295,4294967295} [36]
                                                                          [37] %if.else15.i.i.i.i {4294967295,4294967295} [36]
                                                                            [38] %if.then18.i.i.i.i {4294967295,4294967295} [37]
                                                                              [39] %if.then21.i.i.i.i {4294967295,4294967295} [38]
                                                                              [39] %if.end23.i.i.i.i {4294967295,4294967295} [38]
                                                                              [39] %if.else22.i.i.i.i {4294967295,4294967295} [38]
                                                                            [38] %if.else26.i.i.i.i {4294967295,4294967295} [37]
                                                                        [36] %for.inc.i.i.i.i {4294967295,4294967295} [35]
                                                                          [37] %for.end.i.i.i.i.loopexit {4294967295,4294967295} [36]
                                                                        [36] %if.else28.i.i.i.i {4294967295,4294967295} [35]
                                                                          [37] %if.then34.i.i.i.i {4294967295,4294967295} [36]
                                                                    [34] %for.end.i.i.i.i {4294967295,4294967295} [33]
                                                                      [35] %if.then41.i.i.i.i {4294967295,4294967295} [34]
                                                                      [35] %if.end42.i.i.i.i {4294967295,4294967295} [34]
                                                                  [33] %if.end.i.i.i {4294967295,4294967295} [32]
                                                                    [34] %sw.bb8.i.i.i {4294967295,4294967295} [33]
                                                                    [34] %sw.bb10.i.i.i {4294967295,4294967295} [33]
                                                                    [34] %sw.bb12.i.i.i {4294967295,4294967295} [33]
                                                                    [34] %sw.bb14.i.i.i {4294967295,4294967295} [33]
                                                                  [33] %if.end5.critedge.i.i.i.i {4294967295,4294967295} [32]
                                                                [32] %if.else.i.i.i.i {4294967295,4294967295} [31]
                                                              [31] %filter_build_regex.exit.i.i {4294967295,4294967295} [30]
                                                                [32] %if.then242.i.i {4294967295,4294967295} [31]
                                                                [32] %cleanup.i.i {4294967295,4294967295} [31]
                                                                [32] %if.else244.i.i {4294967295,4294967295} [31]
                                                                  [33] %if.then248.i.i {4294967295,4294967295} [32]
                                                                  [33] %if.else251.i.i {4294967295,4294967295} [32]
                                                                    [34] %if.then255.i.i {4294967295,4294967295} [33]
                                                                    [34] %if.else257.i.i {4294967295,4294967295} [33]
                                                              [31] %sw.bb.i.i.i {4294967295,4294967295} [30]
                                                              [31] %filter_build_regex.exit.i.i.sink.split {4294967295,4294967295} [30]
                                                              [31] %if.end.thread.i.i.i {4294967295,4294967295} [30]
                                                        [28] %for.body202.i.preheader.i {4294967295,4294967295} [27]
                                                          [29] %for.inc211.i.i.preheader {4294967295,4294967295} [28]
                                                            [30] %for.inc211.i.i {4294967295,4294967295} [29]
                                                              [31] %for.end213.i.i.loopexit {4294967295,4294967295} [30]
                                                              [31] %for.body202.i.i {4294967295,4294967295} [30]
                                                                [32] %for.inc211.i.i.1 {4294967295,4294967295} [31]
                                                                  [33] %for.body202.i.i.1 {4294967295,4294967295} [32]
                                                                    [34] %for.inc211.i.i.2 {4294967295,4294967295} [33]
                                                                      [35] %for.body202.i.i.2 {4294967295,4294967295} [34]
                                                                        [36] %for.inc211.i.i.3 {4294967295,4294967295} [35]
                                                                          [37] %for.body202.i.i.3 {4294967295,4294967295} [36]
                                                      [27] %lor.lhs.false.i586.i.i {4294967295,4294967295} [26]
                                                        [28] %lor.lhs.false3.i588.i.i {4294967295,4294967295} [27]
                                                          [29] %is_string_field.exit591.i.i {4294967295,4294967295} [28]
                                                            [30] %if.then194.i.i {4294967295,4294967295} [29]
                                                  [25] %lor.lhs.false181.i.i {4294967295,4294967295} [24]
                                                    [26] %if.else263.i.i {4294967295,4294967295} [25]
                                                      [27] %land.rhs.i.i.i {4294967295,4294967295} [26]
                                                      [27] %isdigit.exit.i.i {4294967295,4294967295} [26]
                                                        [28] %lor.lhs.false269.i.i {4294967295,4294967295} [27]
                                                          [29] %if.else351.i.i {4294967295,4294967295} [28]
                                                        [28] %if.then275.i.i {4294967295,4294967295} [27]
                                                          [29] %is_string_field.exit.thread.i.i {4294967295,4294967295} [28]
                                                          [29] %if.then277.i.i {4294967295,4294967295} [28]
                                                          [29] %lor.lhs.false.i.i.i {4294967295,4294967295} [28]
                                                            [30] %lor.lhs.false3.i.i.i {4294967295,4294967295} [29]
                                                              [31] %is_string_field.exit.i.i {4294967295,4294967295} [30]
                                                                [32] %if.end279.i.i {4294967295,4294967295} [31]
                                                                  [33] %if.then282.i.i {4294967295,4294967295} [32]
                                                                  [33] %if.end284.i.i {4294967295,4294967295} [32]
                                                                    [34] %if.then290.i.i {4294967295,4294967295} [33]
                                                                    [34] %if.end292.i.i {4294967295,4294967295} [33]
                                                                      [35] %while.end305.i.i {4294967295,4294967295} [34]
                                                                        [36] %if.then310.i.i {4294967295,4294967295} [35]
                                                                        [36] %if.end312.i.i {4294967295,4294967295} [35]
                                                                          [37] %if.else324.i.i {4294967295,4294967295} [36]
                                                                          [37] %if.end327.i.i {4294967295,4294967295} [36]
                                                                            [38] %if.end331.i.i {4294967295,4294967295} [37]
                                                                              [39] %if.then336.i.i {4294967295,4294967295} [38]
                                                                              [39] %if.else338.i.i {4294967295,4294967295} [38]
                                                                                [40] %sw.epilog.i.i.i {4294967295,4294967295} [39]
                                                                                  [41] %sw.epilog107.i.i.i {4294967295,4294967295} [40]
                                                                                  [41] %sw.bb54.i.i.i {4294967295,4294967295} [40]
                                                                                    [42] %if.then57.i.i.i {4294967295,4294967295} [41]
                                                                                    [42] %if.else.i.i.i {4294967295,4294967295} [41]
                                                                                      [43] %if.else60.i.i.i {4294967295,4294967295} [42]
                                                                                      [43] %if.then59.i.i.i {4294967295,4294967295} [42]
                                                                                  [41] %sw.bb65.i.i.i {4294967295,4294967295} [40]
                                                                                    [42] %if.then68.i.i.i {4294967295,4294967295} [41]
                                                                                    [42] %if.else69.i.i.i {4294967295,4294967295} [41]
                                                                                      [43] %if.else74.i.i.i {4294967295,4294967295} [42]
                                                                                      [43] %if.then71.i.i.i {4294967295,4294967295} [42]
                                                                                  [41] %sw.bb79.i.i.i {4294967295,4294967295} [40]
                                                                                    [42] %if.then82.i.i.i {4294967295,4294967295} [41]
                                                                                    [42] %if.else83.i.i.i {4294967295,4294967295} [41]
                                                                                      [43] %if.else88.i.i.i {4294967295,4294967295} [42]
                                                                                      [43] %if.then85.i.i.i {4294967295,4294967295} [42]
                                                                                  [41] %sw.bb93.i.i.i {4294967295,4294967295} [40]
                                                                                    [42] %if.then96.i.i.i {4294967295,4294967295} [41]
                                                                                    [42] %if.else97.i.i.i {4294967295,4294967295} [41]
                                                                                      [43] %if.else102.i.i.i {4294967295,4294967295} [42]
                                                                                      [43] %if.then99.i.i.i {4294967295,4294967295} [42]
                                                                                [40] %select_comparison_fn.exit.i.i {4294967295,4294967295} [39]
                                                                                  [41] %if.then347.i.i {4294967295,4294967295} [40]
                                                                                [40] %sw.default.i.i.i {4294967295,4294967295} [39]
                                                                                  [41] %do.body7.i.i.i {4294967295,4294967295} [40]
                                                                                  [41] %if.end19.critedge.i.i.i {4294967295,4294967295} [40]
                                                                                    [42] %do.body37.i.i.i {4294967295,4294967295} [41]
                                                                                    [42] %sw.epilog.critedge.i.i.i {4294967295,4294967295} [41]
                                                                            [38] %if.then329.i.i {4294967295,4294967295} [37]
                                                                          [37] %if.then321.i.i {4294967295,4294967295} [36]
                                                                      [35] %while.body303.i.i.preheader {4294967295,4294967295} [34]
                                                                        [36] %while.body303.i.i {4294967295,4294967295} [35]
                                                                          [37] %while.end305.i.i.loopexit {4294967295,4294967295} [36]
                                                                          [37] %while.body303.i.i.1 {4294967295,4294967295} [36]
                                                                            [38] %while.body303.i.i.2 {4294967295,4294967295} [37]
                                                                              [39] %while.body303.i.i.3 {4294967295,4294967295} [38]
                                            [22] %while.body83.i.i.preheader {4294967295,4294967295} [21]
                                              [23] %while.body83.i.i {4294967295,4294967295} [22]
                                                [24] %kzalloc.exit.i.i.loopexit {4294967295,4294967295} [23]
                                                [24] %while.body83.i.i.1 {4294967295,4294967295} [23]
                                                  [25] %while.body83.i.i.2 {4294967295,4294967295} [24]
                                                    [26] %while.body83.i.i.3 {4294967295,4294967295} [25]
                                          [21] %err_free.i.i {4294967295,4294967295} [20]
                                          [21] %for.inc.i.i {4294967295,4294967295} [20]
                                            [22] %if.then64.i.i {4294967295,4294967295} [21]
                                      [19] %while.body42.i.i.preheader {4294967295,4294967295} [18]
                                        [20] %while.body42.i.i {4294967295,4294967295} [19]
                                          [21] %while.end44.i.i.loopexit {4294967295,4294967295} [20]
                                          [21] %while.body42.i.i.1 {4294967295,4294967295} [20]
                                            [22] %while.body42.i.i.2 {4294967295,4294967295} [21]
                                              [23] %while.body42.i.i.3 {4294967295,4294967295} [22]
                              [15] %while.body20.critedge.i.i {4294967295,4294967295} [14]
                          [13] %while.body.i.i.preheader {4294967295,4294967295} [12]
                            [14] %while.body.i.i {4294967295,4294967295} [13]
                              [15] %while.end.i.i.loopexit {4294967295,4294967295} [14]
                              [15] %while.body.i.i.1 {4294967295,4294967295} [14]
                                [16] %while.body.i.i.2 {4294967295,4294967295} [15]
                                  [17] %while.body.i.i.3 {4294967295,4294967295} [16]
                        [12] %if.then32.i {4294967295,4294967295} [11]
                      [11] %cleanup.thread.i {4294967295,4294967295} [10]
                      [11] %sw.bb.i52 {4294967295,4294967295} [10]
                        [12] %if.then22.i {4294967295,4294967295} [11]
                        [12] %if.end23.i {4294967295,4294967295} [11]
                      [11] %sw.bb25.i {4294967295,4294967295} [10]
                        [12] %if.end28.i {4294967295,4294967295} [11]
                        [12] %is_not.exit.i {4294967295,4294967295} [11]
                    [10] %cleanup.i58 {4294967295,4294967295} [9]
                      [11] %out.i.loopexit {4294967295,4294967295} [10]
                    [10] %out.i {4294967295,4294967295} [9]
                      [11] %if.end130.i {4294967295,4294967295} [10]
                        [12] %if.end130.i.if.then132.i_crit_edge {4294967295,4294967295} [11]
                        [12] %if.end137.i {4294967295,4294967295} [11]
                          [13] %for.end.i61 {4294967295,4294967295} [12]
                            [14] %for.body184.preheader.i {4294967295,4294967295} [13]
                              [15] %for.body184.i {4294967295,4294967295} [14]
                                [16] %for.inc.critedge.i {4294967295,4294967295} [15]
                                  [17] %for.end237.i.loopexit {4294967295,4294967295} [16]
                                  [17] %for.body184.i.1 {4294967295,4294967295} [16]
                                    [18] %for.inc.critedge.i.1 {4294967295,4294967295} [17]
                                [16] %do.body219.i {4294967295,4294967295} [15]
                            [14] %for.end237.i {4294967295,4294967295} [13]
                          [13] %for.body.preheader.i {4294967295,4294967295} [12]
                            [14] %for.body.i59.prol.preheader {4294967295,4294967295} [13]
                              [15] %for.body.i59.prol {4294967295,4294967295} [14]
                                [16] %if.then173.i.prol {4294967295,4294967295} [15]
                                [16] %if.end180.i.prol {4294967295,4294967295} [15]
                            [14] %for.body.i59.prol.loopexit {4294967295,4294967295} [13]
                              [15] %for.end.i61.loopexit {4294967295,4294967295} [14]
                              [15] %for.body.preheader.i.new {4294967295,4294967295} [14]
                                [16] %for.body.i59 {4294967295,4294967295} [15]
                                  [17] %if.then173.i {4294967295,4294967295} [16]
                                  [17] %if.end180.i {4294967295,4294967295} [16]
                                    [18] %if.then173.i.1 {4294967295,4294967295} [17]
                                    [18] %if.end180.i.1 {4294967295,4294967295} [17]
                                      [19] %for.end.i61.loopexit.unr-lcssa {4294967295,4294967295} [18]
                      [11] %if.then125.i {4294967295,4294967295} [10]
                    [10] %if.then16.i {4294967295,4294967295} [9]
            [6] %out_free.i {4294967295,4294967295} [5]
              [7] %if.then239.i {4294967295,4294967295} [6]
                [8] %for.end251.i {4294967295,4294967295} [7]
                [8] %for.body245.i.preheader {4294967295,4294967295} [7]
                  [9] %for.body245.i {4294967295,4294967295} [8]
                    [10] %for.end251.i.loopexit {4294967295,4294967295} [9]
              [7] %if.end252.i {4294967295,4294967295} [6]
            [6] %if.then5.i {4294967295,4294967295} [5]
    [2] %for.body.i.preheader {4294967295,4294967295} [1]
      [3] %for.body.i {4294967295,4294967295} [2]
        [4] %if.end.i {4294967295,4294967295} [3]
          [5] %if.end16.i {4294967295,4294967295} [4]
            [6] %sw.epilog.i {4294967295,4294967295} [5]
              [7] %if.then45.i {4294967295,4294967295} [6]
            [6] %sw.bb.i {4294967295,4294967295} [5]
            [6] %sw.bb23.i {4294967295,4294967295} [5]
              [7] %if.end33.i {4294967295,4294967295} [6]
            [6] %sw.bb34.i {4294967295,4294967295} [5]
              [7] %if.then37.i {4294967295,4294967295} [6]
            [6] %sw.bb39.i {4294967295,4294967295} [5]
              [7] %calc_stack.exit.loopexit {4294967295,4294967295} [6]
              [7] %if.end43.i {4294967295,4294967295} [6]
          [5] %if.then8.i {4294967295,4294967295} [4]
            [6] %if.then14.i {4294967295,4294967295} [5]
        [4] %for.inc.i {4294967295,4294967295} [3]
          [5] %for.end.i {4294967295,4294967295} [4]
            [6] %if.end51.i {4294967295,4294967295} [5]
              [7] %if.then54.i {4294967295,4294967295} [6]
                [8] %for.end87.i {4294967295,4294967295} [7]
                [8] %for.body58.i.preheader {4294967295,4294967295} [7]
                  [9] %for.body58.i {4294967295,4294967295} [8]
                    [10] %if.end68.i {4294967295,4294967295} [9]
                      [11] %sw.bb72.i {4294967295,4294967295} [10]
                        [12] %if.then75.i {4294967295,4294967295} [11]
                        [12] %if.end76.i {4294967295,4294967295} [11]
                      [11] %sw.bb78.i {4294967295,4294967295} [10]
                      [11] %sw.bb80.i {4294967295,4294967295} [10]
                    [10] %for.inc85.i {4294967295,4294967295} [9]
                      [11] %for.end87.i.loopexit {4294967295,4294967295} [10]
                    [10] %if.then60.i {4294967295,4294967295} [9]
                      [11] %if.then66.i {4294967295,4294967295} [10]
Roots: %entry 
clang-11: /home/nathan/cbl/git/tc-build/llvm-project/llvm/lib/Transforms/Utils/LoopUnrollPeel.cpp:789: bool llvm::peelLoop(llvm::Loop *, unsigned int, llvm::LoopInfo *, llvm::ScalarEvolution *, llvm::DominatorTree *, llvm::AssumptionCache *, bool): Assertion `DT->verify(DominatorTree::VerificationLevel::Fast)' failed.
PLEASE submit a bug report to https://bugs.llvm.org/ and include the crash backtrace, preprocessed source, and associated run script.
Stack dump:
0.	Program arguments: /home/nathan/cbl/git/tc-build/build/llvm/stage1/bin/clang-11 -cc1 -triple s390x-unknown-linux-gnu -S -disable-free -main-file-name trace_events_filter.c -mrelocation-model pic -pic-level 2 -pic-is-pie -mthread-model posix -fno-delete-null-pointer-checks -mllvm -warn-stack-size=2048 -mframe-pointer=none -relaxed-aliasing -fmath-errno -fno-rounding-math -no-integrated-as -mconstructor-aliases -target-cpu z196 -target-feature +soft-float -mbackchain -mpacked-stack -msoft-float -mfloat-abi soft -dwarf-column-info -fno-split-dwarf-inlining -debugger-tuning=gdb -femit-coverage-notes -femit-coverage-data -coverage-notes-file /home/nathan/src/linux/out/s390/kernel/trace/trace_events_filter.gcno -coverage-data-file /home/nathan/src/linux/out/s390/kernel/trace/trace_events_filter.gcda -nostdsysteminc -nobuiltininc -resource-dir /home/nathan/cbl/git/tc-build/build/llvm/stage1/lib/clang/11.0.0 -dependency-file kernel/trace/.trace_events_filter.o.d -MT kernel/trace/trace_events_filter.o -sys-header-deps -isystem /home/nathan/cbl/git/tc-build/build/llvm/stage1/lib/clang/11.0.0/include -include /home/nathan/src/linux/include/linux/kconfig.h -include /home/nathan/src/linux/include/linux/compiler_types.h -I /home/nathan/src/linux/arch/s390/include -I ./arch/s390/include/generated -I /home/nathan/src/linux/include -I ./include -I /home/nathan/src/linux/arch/s390/include/uapi -I ./arch/s390/include/generated/uapi -I /home/nathan/src/linux/include/uapi -I ./include/generated/uapi -D __KERNEL__ -D __PACK_STACK -D CONFIG_AS_CFI_VAL_OFFSET=1 -D CC_USING_NOP_MCOUNT -D CC_USING_FENTRY -I kernel/trace -I /home/nathan/src/linux/kernel/trace -I ./kernel/trace -D KBUILD_MODFILE="kernel/trace/trace_events_filter" -D KBUILD_BASENAME="trace_events_filter" -D KBUILD_MODNAME="trace_events_filter" -fmacro-prefix-map=/home/nathan/src/linux/= -O2 -Wall -Wundef -Werror=strict-prototypes -Wno-trigraphs -Werror=implicit-function-declaration -Werror=implicit-int -Wno-format-security -Werror=unknown-warning-option -Wno-sign-compare -Wno-frame-address -Wno-address-of-packed-member -Wno-format-invalid-specifier -Wno-gnu -Wno-unused-const-variable -Wdeclaration-after-statement -Wvla -Wno-pointer-sign -Wno-array-bounds -Werror=date-time -Werror=incompatible-pointer-types -Wno-initializer-overrides -Wno-format -Wno-sign-compare -Wno-format-zero-length -Wno-pointer-to-enum-cast -Wno-tautological-constant-out-of-range-compare -std=gnu89 -fno-dwarf-directory-asm -fdebug-compilation-dir /home/nathan/src/linux/out/s390 -ferror-limit 19 -fsanitize-coverage-type=3 -fsanitize-coverage-trace-cmp -fsanitize-coverage-trace-pc -fsanitize=kernel-address -fsanitize-recover=kernel-address -fwrapv -ftrivial-auto-var-init=pattern -fno-signed-char -fwchar-type=short -fno-signed-wchar -fgnuc-version=4.2.1 -vectorize-loops -vectorize-slp -mllvm -asan-mapping-offset=0x18000000000000 -mllvm -asan-globals=1 -mllvm -asan-instrumentation-with-call-threshold=0 -mllvm -asan-stack=0 -o /tmp/trace_events_filter-5be1c3.s -x c /home/nathan/src/linux/kernel/trace/trace_events_filter.c 
1.	<eof> parser at end of file
2.	Per-module optimization passes
3.	Running pass 'Function Pass Manager' on module '/home/nathan/src/linux/kernel/trace/trace_events_filter.c'.
4.	Running pass 'Loop Pass Manager' on function '@process_preds'
5.	Running pass 'Unroll loops' on basic block '%while.cond54.i'
 #0 0x0000000003537614 PrintStackTraceSignalHandler(void*) (/home/nathan/cbl/git/tc-build/build/llvm/stage1/bin/clang-11+0x3537614)
 #1 0x000000000353532e llvm::sys::RunSignalHandlers() (/home/nathan/cbl/git/tc-build/build/llvm/stage1/bin/clang-11+0x353532e)
 #2 0x0000000003537925 SignalHandler(int) (/home/nathan/cbl/git/tc-build/build/llvm/stage1/bin/clang-11+0x3537925)
 #3 0x00007f1dfa9c43c0 __restore_rt (/lib/x86_64-linux-gnu/libpthread.so.0+0x153c0)
 #4 0x00007f1dfa48918b raise (/lib/x86_64-linux-gnu/libc.so.6+0x4618b)
 #5 0x00007f1dfa468859 abort (/lib/x86_64-linux-gnu/libc.so.6+0x25859)
 #6 0x00007f1dfa468729 (/lib/x86_64-linux-gnu/libc.so.6+0x25729)
 #7 0x00007f1dfa479f36 (/lib/x86_64-linux-gnu/libc.so.6+0x36f36)
 #8 0x00000000035cf09e llvm::peelLoop(llvm::Loop*, unsigned int, llvm::LoopInfo*, llvm::ScalarEvolution*, llvm::DominatorTree*, llvm::AssumptionCache*, bool) (/home/nathan/cbl/git/tc-build/build/llvm/stage1/bin/clang-11+0x35cf09e)
 #9 0x00000000035bb045 llvm::UnrollLoop(llvm::Loop*, llvm::UnrollLoopOptions, llvm::LoopInfo*, llvm::ScalarEvolution*, llvm::DominatorTree*, llvm::AssumptionCache*, llvm::TargetTransformInfo const*, llvm::OptimizationRemarkEmitter*, bool, llvm::Loop**) (/home/nathan/cbl/git/tc-build/build/llvm/stage1/bin/clang-11+0x35bb045)
#10 0x00000000033ba3ac tryToUnrollLoop(llvm::Loop*, llvm::DominatorTree&, llvm::LoopInfo*, llvm::ScalarEvolution&, llvm::TargetTransformInfo const&, llvm::AssumptionCache&, llvm::OptimizationRemarkEmitter&, llvm::BlockFrequencyInfo*, llvm::ProfileSummaryInfo*, bool, int, bool, bool, llvm::Optional<unsigned int>, llvm::Optional<unsigned int>, llvm::Optional<bool>, llvm::Optional<bool>, llvm::Optional<bool>, llvm::Optional<bool>, llvm::Optional<bool>, llvm::Optional<unsigned int>) (/home/nathan/cbl/git/tc-build/build/llvm/stage1/bin/clang-11+0x33ba3ac)
#11 0x00000000033bd4fd (anonymous namespace)::LoopUnroll::runOnLoop(llvm::Loop*, llvm::LPPassManager&) (/home/nathan/cbl/git/tc-build/build/llvm/stage1/bin/clang-11+0x33bd4fd)
#12 0x0000000002915cd0 llvm::LPPassManager::runOnFunction(llvm::Function&) (/home/nathan/cbl/git/tc-build/build/llvm/stage1/bin/clang-11+0x2915cd0)
#13 0x0000000002f037e4 llvm::FPPassManager::runOnFunction(llvm::Function&) (/home/nathan/cbl/git/tc-build/build/llvm/stage1/bin/clang-11+0x2f037e4)
#14 0x0000000002f03ae8 llvm::FPPassManager::runOnModule(llvm::Module&) (/home/nathan/cbl/git/tc-build/build/llvm/stage1/bin/clang-11+0x2f03ae8)
#15 0x0000000002f04214 llvm::legacy::PassManagerImpl::run(llvm::Module&) (/home/nathan/cbl/git/tc-build/build/llvm/stage1/bin/clang-11+0x2f04214)
#16 0x00000000037377fa clang::EmitBackendOutput(clang::DiagnosticsEngine&, clang::HeaderSearchOptions const&, clang::CodeGenOptions const&, clang::TargetOptions const&, clang::LangOptions const&, llvm::DataLayout const&, llvm::Module*, clang::BackendAction, std::unique_ptr<llvm::raw_pwrite_stream, std::default_delete<llvm::raw_pwrite_stream> >) (/home/nathan/cbl/git/tc-build/build/llvm/stage1/bin/clang-11+0x37377fa)
#17 0x0000000003f080ed clang::BackendConsumer::HandleTranslationUnit(clang::ASTContext&) (/home/nathan/cbl/git/tc-build/build/llvm/stage1/bin/clang-11+0x3f080ed)
#18 0x00000000047b4a73 clang::ParseAST(clang::Sema&, bool, bool) (/home/nathan/cbl/git/tc-build/build/llvm/stage1/bin/clang-11+0x47b4a73)
#19 0x0000000003e6e2d0 clang::FrontendAction::Execute() (/home/nathan/cbl/git/tc-build/build/llvm/stage1/bin/clang-11+0x3e6e2d0)
#20 0x0000000003dcce53 clang::CompilerInstance::ExecuteAction(clang::FrontendAction&) (/home/nathan/cbl/git/tc-build/build/llvm/stage1/bin/clang-11+0x3dcce53)
#21 0x0000000003f02924 clang::ExecuteCompilerInvocation(clang::CompilerInstance*) (/home/nathan/cbl/git/tc-build/build/llvm/stage1/bin/clang-11+0x3f02924)
#22 0x0000000001e97281 cc1_main(llvm::ArrayRef<char const*>, char const*, void*) (/home/nathan/cbl/git/tc-build/build/llvm/stage1/bin/clang-11+0x1e97281)
#23 0x0000000001e9537c ExecuteCC1Tool(llvm::SmallVectorImpl<char const*>&) (/home/nathan/cbl/git/tc-build/build/llvm/stage1/bin/clang-11+0x1e9537c)
#24 0x0000000001e950df main (/home/nathan/cbl/git/tc-build/build/llvm/stage1/bin/clang-11+0x1e950df)
#25 0x00007f1dfa46a0b3 __libc_start_main (/lib/x86_64-linux-gnu/libc.so.6+0x270b3)
#26 0x0000000001e9217e _start (/home/nathan/cbl/git/tc-build/build/llvm/stage1/bin/clang-11+0x1e9217e)
clang-11: error: unable to execute command: Aborted
clang-11: error: clang frontend command failed due to signal (use -v to see invocation)
ClangBuiltLinux clang version 11.0.0 (https://github.com/llvm/llvm-project c2bb26d8613338b93a1aab54631d01e6a690bc29)
Target: s390x-unknown-linux-gnu
Thread model: posix
InstalledDir: /home/nathan/cbl/git/tc-build/build/llvm/stage1/bin

Reduction spits out:

a, b, c;
d() {
  while (c)
    ;
  while (a || b)
    ;
}

Files are here: https://github.com/nathanchance/creduce-files/tree/3bfd987920d1d9128f6d17bce4d72250993a6887/1bc73b02d6934c8586ca5740da416b7094c3c471

Sorry, I've been rather swamped with other stuff so I wasn't able to bisect the compiler flags beyond just removing the warning ones. Happy to provide whatever information you need to look into this further.

Whitney reopened this revision.May 30 2020, 4:32 AM
This comment was removed by Whitney.
This revision is now accepted and ready to land.May 30 2020, 4:32 AM
Whitney updated this revision to Diff 267468.May 30 2020, 11:31 AM

Updated the patch to fix build failure for allyesconfig.

Will deliver right away to unblock others. Feel free to give after commit comments if you see problem with the code.

Whitney marked an inline comment as done.May 30 2020, 11:33 AM
This revision was automatically updated to reflect the committed changes.