Remove the limitation in LoopUnrollPass that exiting block must be either header or latch.
Details
Details
- Reviewers
dmgreen jdoerfert Meinersbur kbarton bmahjour etiotto fhahn efriedma - Commits
- rG0fee91a187d9: [LoopUnroll] Add a test case for rG7873376bb36b.
rG1bc73b02d693: [LoopUnroll] Support loops with exiting block that is neither header nor latch.
rG281058226587: [LoopUnroll] Support loops with exiting block that is neither header nor latch.
Diff Detail
Diff Detail
- Repository
- rG LLVM Github Monorepo
Event Timeline
| llvm/lib/Transforms/Utils/LoopUnroll.cpp | ||
|---|---|---|
| 326 ↗ | (On Diff #265876) | Please add a comment to explain why an exiting block conditional branch may be chosen with 'higher priority' and the rationale. |
| 639 ↗ | (On Diff #265876) | [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 | ||
| 47 | 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. | |
Comment Actions
The patch doesn't apply cleanly to trunk. Could you update?
Could you summarize which restrictions remain?
| llvm/lib/Transforms/Utils/LoopUnroll.cpp | ||
|---|---|---|
| 307–310 ↗ | (On Diff #266097) | Doesn't this need to be updated? |
| 339–340 ↗ | (On Diff #266097) | If this supports any number of exits, why the need to find a special one? |
| llvm/lib/Transforms/Utils/LoopUnroll.cpp | ||
|---|---|---|
| 322 ↗ | (On Diff #266097) | 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. |
Comment Actions
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.
Comment Actions
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 | ||
|---|---|---|
| 322 ↗ | (On Diff #266097) |
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. |
Comment Actions
Updated the patch so it can be apply cleanly to trunk.
And addressed some of the comments.
| llvm/lib/Transforms/Utils/LoopUnroll.cpp | ||
|---|---|---|
| 322 ↗ | (On Diff #266097) |
That's true, removed the check.
The code below expects one exiting block to optimize. We still give highest priority to the latch branch.
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. |
| 339–340 ↗ | (On Diff #266097) | The code expects one exiting block to be used to optimize away the conditional branch to the exit block. |
| llvm/lib/Transforms/Utils/LoopUnroll.cpp | ||
|---|---|---|
| 339–340 ↗ | (On Diff #266097) | 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. |
Comment Actions
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.
Comment Actions
As suggested, modified this patch to only remove one limitation: exiting block must be either header or latch.
Comment Actions
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!
| llvm/lib/Transforms/Utils/LoopUnroll.cpp | ||
|---|---|---|
| 315 ↗ | (On Diff #266335) | 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 ↗ | (On Diff #266335) | Maybe bool LatchIsExiting = L->isLoopExiting(LatchBlock); |
| 321 ↗ | (On Diff #266335) | 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. |
Comment Actions
Addressed Eli's review comments.
| llvm/lib/Transforms/Utils/LoopUnroll.cpp | ||
|---|---|---|
| 315 ↗ | (On Diff #266335) |
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. |
Comment Actions
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 | ||
|---|---|---|
| 314 ↗ | (On Diff #266391) | Just dyn_cast<>: the latch always has a terminator |
| 324 ↗ | (On Diff #266391) | Also dyn_cast<> here. You only need dyn_cast_or_null if the argument can be null. |
| llvm/lib/Transforms/Utils/LoopUnroll.cpp | ||
|---|---|---|
| 309 ↗ | (On Diff #266492) | 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. |
| 319 ↗ | (On Diff #266492) | 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. |
| 326 ↗ | (On Diff #266492) | 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 |
| 806 ↗ | (On Diff #266492) | The comment seems a bit out-of-date now. It would be good to re-phrase it in terms of exiting blocks. |
Comment Actions
Addressed or replied all latest comments from Florian.
| llvm/lib/Transforms/Utils/LoopUnroll.cpp | ||
|---|---|---|
| 309 ↗ | (On Diff #266492) | When the single loop latch is an exiting block, the loop is allowed to have multiple exiting blocks. This is the original behaviour. |
| 319 ↗ | (On Diff #266492) | But getExitingBlock may be nullptr when L->isLoopExiting(LatchBlock) |
| 326 ↗ | (On Diff #266492) | since multiple exiting block is allowed when loop latch is one of them, I current wording seems more relevant. |
Comment Actions
LGTM, thanks!
| llvm/lib/Transforms/Utils/LoopUnroll.cpp | ||
|---|---|---|
| 309 ↗ | (On Diff #266492) | oh right, I thought we where restricting it to single exiting block earlier on, but it is indeed not the case. |
Comment Actions
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.
This comment was removed by Whitney.
Comment Actions
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.
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.