Project Ortega BCM5719 LLVM https://git.raptorcs.com/git/bcm5719-llvm/atom?h=meklort-10.0.1 2019-11-21T23:44:36+00:00 2019-11-21T23:44:36+00:00 Philip Reames listmail@philipreames.com 2019-11-21T23:26:58+00:00 urn:sha1:dfb7a9091affce6e5a8fdb017b4e2d58675bb9b0 We may end up with a case where we have a widenable branch above the loop, but not all widenable branches within the loop have been removed. Since a widenable branch inhibit SCEVs ability to reason about exit counts (by design), we have a tradeoff between effectiveness of this optimization and allowing future widening of the branches within the loop. LoopPred is thought to be one of the most important optimizations for range check elimination, so let's pay the cost. 2019-11-21T18:46:16+00:00 Philip Reames listmail@philipreames.com 2019-11-21T18:44:13+00:00 urn:sha1:aaea24802bf5de0420f1ef5f3660a9765e23dea8 As a reminder, a "widenable branch" is the pattern "br i1 (and i1 X, WC()), label %taken, label %untaken" where "WC" is the widenable condition intrinsics. The semantics of such a branch (derived from the semantics of WC) is that a new condition can be added into the condition arbitrarily without violating legality. Broaden the definition in two ways: Allow swapped operands to the br (and X, WC()) form Allow widenable branch w/trivial condition (i.e. true) which takes form of br i1 WC() The former is just general robustness (e.g. for X = non-instruction this is what instcombine produces). The later is specifically important as partial unswitching of a widenable range check produces exactly this form above the loop. Differential Revision: https://reviews.llvm.org/D70502 2019-11-19T22:06:36+00:00 Philip Reames listmail@philipreames.com 2019-11-19T22:06:36+00:00 urn:sha1:f3eb5dee5756876be0524c59c21478659eba8c4d Unswitch (and other loop transforms) like to generate loop exit blocks with unconditional successors, and phi nodes (LCSSA, or simple multiple exiting blocks sharing an exit). Generalize the "likely very rare exit" check slightly to handle this form. 2019-11-18T19:23:29+00:00 Philip Reames listmail@philipreames.com 2019-11-18T19:21:53+00:00 urn:sha1:ad5a84c883354e8bb595ebfd9971fe4a14b770fd This implements a version of the predicateLoopExits transform from IndVarSimplify extended to exploit widenable conditions - and thus be much wider in scope of legality. The code structure ends up being almost entirely different, so I chose to duplicate this into the LoopPredication pass instead of trying to reuse the code in the IndVars. The core notions of the transform are as follows: If we have a widenable condition which controls entry into the loop, we're allowed to widen it arbitrarily. Given that, it's simply a *profitability* question as to what conditions to fold into the widenable branch. To avoid pass ordering issues, we want to avoid widening cases that would otherwise be dischargeable. Or... widen in a form which can still be discharged. Thus, we phrase the transform as selecting one analyzeable exit from the set of analyzeable exits to keep. This avoids creating pass ordering complexities. Since none of the above proves that we actually exit through our analyzeable exits - we might exit through something else entirely - we limit ourselves to cases where a) the latch is analyzeable and b) the latch is predicted taken, and c) the exit being removed is statically cold. Differential Revision: https://reviews.llvm.org/D69830 2019-07-09T01:27:45+00:00 Philip Reames listmail@philipreames.com 2019-07-09T01:27:45+00:00 urn:sha1:5a637cbdc7d8a59d5d56f329871cb3834c1f5095 A while back, I added support for NE latches formed by LFTR. I didn't think that quite through, as LFTR will also produce the inverse EQ form for some loops and I hadn't handled that. This change just adds handling for that case as well. llvm-svn: 365419 2019-07-07T22:12:01+00:00 Petr Hosek phosek@chromium.org 2019-07-07T22:12:01+00:00 urn:sha1:e28fca29fefef678656b80c1267d4721ed96293e This reverts commit r365260 which broke the following tests: Clang :: CodeGenCXX/cfi-mfcall.cpp Clang :: CodeGenObjC/ubsan-nullability.m LLVM :: Transforms/LoopVectorize/AArch64/pr36032.ll llvm-svn: 365284 2019-07-06T04:28:00+00:00 Philip Reames listmail@philipreames.com 2019-07-06T04:28:00+00:00 urn:sha1:9812668d77121498cade95dc89526dc78a210251 Without this, we have the unfortunate property that tests are dependent on the order of operads passed the CreateOr and CreateAnd functions. In actual usage, we'd promptly optimize them away, but it made tests slightly more verbose than they should have been. llvm-svn: 365260 2019-06-06T18:02:36+00:00 Philip Reames listmail@philipreames.com 2019-06-06T18:02:36+00:00 urn:sha1:101915cfdaba9284b5bb8dedbbca2b7788f68da4 This is a really silly bug that even a simple test w/an unconditional latch would have caught. I tried to guard against the case, but put it in the wrong if check. Oops. llvm-svn: 362727 2019-06-01T00:31:58+00:00 Philip Reames listmail@philipreames.com 2019-06-01T00:31:58+00:00 urn:sha1:099eca832e7ef22c7229bc707789bc680ea228bd At the moment, LoopPredication completely bails out if it sees a latch of the form: %cmp = icmp ne %iv, %N br i1 %cmp, label %loop, label %exit OR %cmp = icmp ne %iv.next, %NPlus1 br i1 %cmp, label %loop, label %exit This is unfortunate since this is exactly the form that LFTR likes to produce. So, go ahead and recognize simple cases where we can. For pre-increment loops, we leverage the fact that LFTR likes canonical counters (i.e. those starting at zero) and a (presumed) range fact on RHS to discharge the check trivially. For post-increment forms, the key insight is in remembering that LFTR had to insert a (N+1) for the RHS. CVP can hopefully prove that add nsw/nuw (if there's appropriate range on N to start with). This leaves us both with the post-inc IV and the RHS involving an nsw/nuw add, and SCEV can discharge that with no problem. This does still need to be extended to handle non-one steps, or other harder patterns of variable (but range restricted) starting values. That'll come later. Differential Revision: https://reviews.llvm.org/D62748 llvm-svn: 362282 2019-05-31T22:22:29+00:00 Philip Reames listmail@philipreames.com 2019-05-31T22:22:29+00:00 urn:sha1:fa6bcd0b966ee67696d40256971d5325117875d5 llvm-svn: 362270