Project Ortega BCM5719 LLVM https://git.raptorcs.com/git/bcm5719-llvm/atom?h=meklort-10.0.1 2020-06-17T03:16:13+00:00 2020-06-17T03:16:13+00:00 Tom Stellard tstellar@redhat.com 2020-05-27T19:16:30+00:00 urn:sha1:4d0626a822be3cfe1809d9b3ba976e5bda0b02e4 Summary: Currently, `rewriteLoopExitValues()`'s logic is roughly as following: > Loop over each incoming value in each PHI node. > Query whether the SCEV for that incoming value is high-cost. > Expand the SCEV. > Perform sanity check (`isValidRewrite()`, D51582) > Record the info > Afterwards, see if we can drop the loop given replacements. > Maybe perform replacements. The problem is that we interleave SCEV cost checking and expansion. This is A Problem, because `isHighCostExpansion()` takes special care to not bill for the expansions that were already expanded, and we can reuse. While it makes sense in general - if we know that we will expand some SCEV, all the other SCEV's costs should account for that, which might cause some of them to become non-high-cost too, and cause chain reaction. But that isn't what we are doing here. We expand *all* SCEV's, unconditionally. So every next SCEV's cost will be affected by the already-performed expansions for previous SCEV's. Even if we are not planning on keeping some of the expansions we performed. Worse yet, this current "bonus" depends on the exact PHI node incoming value processing order. This is completely wrong. As an example of an issue, see @dmajor's `pr45835.ll` - if we happen to have a PHI node with two(!) identical high-cost incoming values for the same basic blocks, we would decide first time around that it is high-cost, expand it, and immediately decide that it is not high-cost because we have an expansion that we could reuse (because we expanded it right before, temporarily), and replace the second incoming value but not the first one; thus resulting in a broken PHI. What we instead should do for now, is not perform any expansions until after we've queried all the costs. Later, in particular after `isValidRewrite()` is an assertion (D51582) we could improve upon that, but in a more coherent fashion. See [[ https://bugs.llvm.org/show_bug.cgi?id=45835 | PR45835 ]] Reviewers: dmajor, reames, mkazantsev, fhahn, efriedma Reviewed By: dmajor, mkazantsev Subscribers: smeenai, nikic, hiraditya, javed.absar, llvm-commits, dmajor Tags: #llvm Differential Revision: https://reviews.llvm.org/D79787 (cherry picked from commit b2df96123198deadad74634c978e84912314da26) 2020-01-10T09:35:00+00:00 Sjoerd Meijer sjoerd.meijer@arm.com 2020-01-10T09:30:02+00:00 urn:sha1:67bf9a6154d4b82c6c01aad01141bf08c1bbd0f6 Teach SCEV about the @loop.decrement.reg intrinsic, which has exactly the same semantics as a sub expression. This allows us to query hardware-loops, which contain this @loop.decrement.reg intrinsic, so that we can calculate iteration counts, exit values, etc. of hardwareloops. This "int_loop_decrement_reg" intrinsic is defined as "IntrNoDuplicate". Thus, while hardware-loops and tripcounts now become analysable by SCEV, this prevents the usual loop transformations from applying transformations on hardware-loops, which is what we want at this point, for which I have added test cases for loopunrolling and IndVarSimplify and LFTR. Differential Revision: https://reviews.llvm.org/D71563 2019-12-24T23:57:33+00:00 Fangrui Song maskray@google.com 2019-12-24T23:52:21+00:00 urn:sha1:502a77f125f43ffde57af34d3fd1b900248a91cd 2019-11-06T23:41:57+00:00 Philip Reames listmail@philipreames.com 2019-11-06T23:30:47+00:00 urn:sha1:8748be7750920b7bd669a47be72a81ee7f1d305c The basic idea of the transform is to convert variant loop exit conditions into invariant exit conditions by changing the iteration on which the exit is taken when we know that the trip count is unobservable. See the original patch which introduced the code for a more complete explanation. The individual parts of this have been reviewed, the result has been fuzzed, and then further analyzed by hand, but despite all of that, I will not be suprised to see breakage here. If you see problems, please don't hesitate to revert - though please do provide a test case. The most likely class of issues are latent SCEV bugs and without a reduced test case, I'll be essentially stuck on reducing them. (Note: A bunch of tests were opted out of the new transform to preserve coverage. That landed in a previous commit to simplify revert cycles if they turn out to be needed.) 2019-11-06T23:41:57+00:00 Philip Reames listmail@philipreames.com 2019-11-06T23:16:43+00:00 urn:sha1:20cbb6cdf8b33dd3732b9ef8702e7946b6d8c739 I'm about to enable the new loop predication transform by default. It has the effect of completely destroying many read only loops - which happen to be a super common idiom in our test cases. So as to preserve test coverage of other transforms, disable the new transform where it would cause sharp test coverage regressions. (This is semantically part of the enabling commit. It's committed separate to ease revert if the actual flag flip gets reverted.) 2019-10-20T23:38:02+00:00 Philip Reames listmail@philipreames.com 2019-10-20T23:38:02+00:00 urn:sha1:8cbcd2f484a2bc6720d9fd66b71aeaf50a49bc70 We can end up with two loop exits whose exit counts are equivalent, but whose textual representation is different and non-obvious. For the sub-case where we have a series of exits which dominate one another (common), eliminate any exits which would iterate *after* a previous exit on the exiting iteration. As noted in the TODO being removed, I'd always thought this was a good idea, but I've now seen this in a real workload as well. Interestingly, in review, Nikita pointed out there's let another oppurtunity to leverage SCEV's reasoning. If we kept track of the min of dominanting exits so far, we could discharge exits with EC >= MDE. This is less powerful than the existing transform (since later exits aren't considered), but potentially more powerful for any case where SCEV can prove a >= b, but neither a == b or a > b. I don't have an example to illustrate that oppurtunity, but won't be suprised if we find one and return to handle that case as well. Differential Revision: https://reviews.llvm.org/D69009 llvm-svn: 375379 2019-10-16T20:27:10+00:00 Philip Reames listmail@philipreames.com 2019-10-16T20:27:10+00:00 urn:sha1:ac77947315c5cf9a79b1aa5b813baaa2d018cbe3 llvm-svn: 375040 2019-10-16T19:58:26+00:00 Philip Reames listmail@philipreames.com 2019-10-16T19:58:26+00:00 urn:sha1:d4346584fa35232af286ededf9f01353d905ed9f The problem is that we can have two loop exits, 'a' and 'b', where 'a' and 'b' would exit at the same iteration, 'a' precedes 'b' along some path, and 'b' is predicated while 'a' is not. In this case (see the previously submitted test case), we causing the loop to exit through 'b' whereas it should have exited through 'a'. This only applies to loop exits where the exit counts are not provably inequal, but that isn't as much of a restriction as it appears. If we could order the exit counts, we'd have already removed one of the two exits. In theory, we might be able to prove inequality w/o ordering, but I didn't really explore that piece. Instead, I went for the obvious restriction and ensured we didn't predicate exits following non-predicateable exits. Credit goes to Evgeny Brevnov for figuring out the problematic case. Fuzzing probably also found it (failures seen), but due to some silly infrastructure problems I hadn't gotten to the results before Evgeny hand reduced it from a benchmark (he manually enabled the transform). Once this is fixed, I'll try to filter through the fuzzer failures to see if there's anything additional lurking. Differential Revision https://reviews.llvm.org/D68956 llvm-svn: 375038 2019-10-14T19:49:40+00:00 Philip Reames listmail@philipreames.com 2019-10-14T19:49:40+00:00 urn:sha1:2b161cd0a4f7fcb5b0328e7c32e834fec821e898 Credit goes to Evgeny Brevnov for figuring out the problematic case. Fuzzing probably also found it (lots of failures), but due to some silly infrastructure problems I hadn't gotten to the results before Evgeny hand reduced it from a benchmark. llvm-svn: 374812 2019-10-14T19:10:39+00:00 Philip Reames listmail@philipreames.com 2019-10-14T19:10:39+00:00 urn:sha1:02945107f8d61e2f7d982344bfdd13eab9f65889 llvm-svn: 374807