History log of /llvm-project/llvm/lib/Transforms/Scalar/LoopPredication.cpp (Results 51 – 75 of 106)
Revision (<<< Hide revision tags) (Show revision tags >>>) Date Author Comments
# 70c68a6b 19-Nov-2019 Philip Reames <listmail@philipreames.com>

[NFC] Factor out utilities for manipulating widenable branches

With the widenable condition construct, we have the ability to reason about branches which can be 'widened' (i.e. made to fail more oft

[NFC] Factor out utilities for manipulating widenable branches

With the widenable condition construct, we have the ability to reason about branches which can be 'widened' (i.e. made to fail more often). We've got a couple o transforms which leverage this. This patch just cleans up the API a bit.

This is prep work for generalizing our definition of a widenable branch slightly. At the moment "br i1 (and A, wc()), ..." is considered widenable, but oddly, neither "br i1 (and wc(), B), ..." or "br i1 wc(), ..." is. That clearly needs addressed, so first, let's centralize the code in one place.

show more ...


# f3eb5dee 19-Nov-2019 Philip Reames <listmail@philipreames.com>

[LoopPred] Generalize profitability check to handle unswitch output

Unswitch (and other loop transforms) like to generate loop exit blocks with unconditional successors, and phi nodes (LCSSA, or sim

[LoopPred] Generalize profitability check to handle unswitch output

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.

show more ...


# ad5a84c8 18-Nov-2019 Philip Reames <listmail@philipreames.com>

[LoopPred/WC] Use a dominating widenable condition to remove analyze loop exits

This implements a version of the predicateLoopExits transform from IndVarSimplify extended to exploit widenable condit

[LoopPred/WC] Use a dominating widenable condition to remove analyze loop exits

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

show more ...


# 4c1a1d3c 14-Nov-2019 Reid Kleckner <rnk@google.com>

Add missing includes needed to prune LLVMContext.h include, NFC

These are a pre-requisite to removing #include "llvm/Support/Options.h"
from LLVMContext.h: https://reviews.llvm.org/D70280


# 05da2fe5 13-Nov-2019 Reid Kleckner <rnk@google.com>

Sink all InitializePasses.h includes

This file lists every pass in LLVM, and is included by Pass.h, which is
very popular. Every time we add, remove, or rename a pass in LLVM, it
caused lots of reco

Sink all InitializePasses.h includes

This file lists every pass in LLVM, and is included by Pass.h, which is
very popular. Every time we add, remove, or rename a pass in LLVM, it
caused lots of recompilation.

I found this fact by looking at this table, which is sorted by the
number of times a file was changed over the last 100,000 git commits
multiplied by the number of object files that depend on it in the
current checkout:
recompiles touches affected_files header
342380 95 3604 llvm/include/llvm/ADT/STLExtras.h
314730 234 1345 llvm/include/llvm/InitializePasses.h
307036 118 2602 llvm/include/llvm/ADT/APInt.h
213049 59 3611 llvm/include/llvm/Support/MathExtras.h
170422 47 3626 llvm/include/llvm/Support/Compiler.h
162225 45 3605 llvm/include/llvm/ADT/Optional.h
158319 63 2513 llvm/include/llvm/ADT/Triple.h
140322 39 3598 llvm/include/llvm/ADT/StringRef.h
137647 59 2333 llvm/include/llvm/Support/Error.h
131619 73 1803 llvm/include/llvm/Support/FileSystem.h

Before this change, touching InitializePasses.h would cause 1345 files
to recompile. After this change, touching it only causes 550 compiles in
an incremental rebuild.

Reviewers: bkramer, asbirlea, bollu, jdoerfert

Differential Revision: https://reviews.llvm.org/D70211

show more ...


# 686f449e 06-Nov-2019 Philip Reames <listmail@philipreames.com>

[WC] Fix a subtle bug in our definition of widenable branch

We had a subtle, but nasty bug in our definition of a widenable branch, and thus in the transforms which used that utility. Specifically,

[WC] Fix a subtle bug in our definition of widenable branch

We had a subtle, but nasty bug in our definition of a widenable branch, and thus in the transforms which used that utility. Specifically, we returned true for any branch which included a widenable condition within it's condition, regardless of whether that widenable condition also had other uses.

The problem is that the result of the WC() call is defined to be one particular value. As such, all users must agree as to what that value is. If we widen a branch without also updating *all other users* of the WC in the same way, we have broken the required semantics.

Most of the textual diff is updating existing transforms not to leave dead uses hanging around. They're largely NFC as the dead instructions would be immediately deleted by other passes. The reason to make these changes is so that the transforms preserve the widenable branch form.

In practice, we don't get bitten by this only because it isn't profitable to CSE WC() calls and the lowering pass from guards uses distinct WC calls per branch.

Differential Revision: https://reviews.llvm.org/D69916

show more ...


Revision tags: llvmorg-9.0.0, llvmorg-9.0.0-rc6, llvmorg-9.0.0-rc5, llvmorg-9.0.0-rc4
# 27820f99 04-Sep-2019 Philip Reames <listmail@philipreames.com>

[Instruction] Add hasMetadata(Kind) helper [NFC]

It's a common idiom, so let's add the obvious wrapper for metadata kinds which are basically booleans.

llvm-svn: 370933


Revision tags: llvmorg-9.0.0-rc3, llvmorg-9.0.0-rc2, llvmorg-9.0.0-rc1, llvmorg-10-init, llvmorg-8.0.1, llvmorg-8.0.1-rc4
# c6caddb7 09-Jul-2019 Serguei Katkov <serguei.katkov@azul.com>

[LoopInfo] Update getExitEdges to accept vector of pairs for non const BasicBlock

D63921 requires getExitEdges fills a vector of Edge pairs where
BasicBlocks are not constant.

The rest Loop API mos

[LoopInfo] Update getExitEdges to accept vector of pairs for non const BasicBlock

D63921 requires getExitEdges fills a vector of Edge pairs where
BasicBlocks are not constant.

The rest Loop API mostly returns non-const BasicBlocks, so to be more consistent with
other Loop API getExitEdges is modified to return non-const BasicBlocks as well.

This is an alternative solution to D64060.

Reviewers: reames, fhahn
Reviewed By: reames, fhahn
Subscribers: hiraditya, llvm-commits
Differential Revision: https://reviews.llvm.org/D64309

llvm-svn: 365437

show more ...


# 0e344e9d 09-Jul-2019 Philip Reames <listmail@philipreames.com>

[LoopPred] Stylistic improvement to recently added NE/EQ normalization [NFC]

llvm-svn: 365425


# 5a637cbd 09-Jul-2019 Philip Reames <listmail@philipreames.com>

[LoopPred] Extend LFTR normalization to the inverse EQ case

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

[LoopPred] Extend LFTR normalization to the inverse EQ case

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

show more ...


# 9e62c864 06-Jul-2019 Philip Reames <listmail@philipreames.com>

[IRBuilder] Introduce helpers for and/or of multiple values at once

We had versions of this code scattered around, so consolidate into one location.

Not strictly NFC since the order of intermediate

[IRBuilder] Introduce helpers for and/or of multiple values at once

We had versions of this code scattered around, so consolidate into one location.

Not strictly NFC since the order of intermediate results may change in some places, but since these operations are associatives, should not change results.

llvm-svn: 365259

show more ...


Revision tags: llvmorg-8.0.1-rc3, llvmorg-8.0.1-rc2
# 101915cf 06-Jun-2019 Philip Reames <listmail@philipreames.com>

[LoopPred] Fix a bug in unconditional latch bailout introduced in r362284

This is a really silly bug that even a simple test w/an unconditional latch would have caught. I tried to guard against the

[LoopPred] Fix a bug in unconditional latch bailout introduced in r362284

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

show more ...


# 9ed16737 03-Jun-2019 Philip Reames <listmail@philipreames.com>

[LoopPred] Convert a second member function to a static helper [NFC]

(And remember to actually mark the first one static.)

llvm-svn: 362415


# 0912b06f 03-Jun-2019 Philip Reames <listmail@philipreames.com>

[LoopPred] Convert member function to free helper function [NFC]

llvm-svn: 362411


# 4e875464 01-Jun-2019 Richard Trieu <rtrieu@google.com>

Inline variable into assert to fix unused variable warning.

llvm-svn: 362285


# 19afdf74 01-Jun-2019 Philip Reames <listmail@philipreames.com>

[LoopPred] Eliminate a redundant/confusing cover function [NFC]

llvm-svn: 362284


# 099eca83 01-Jun-2019 Philip Reames <listmail@philipreames.com>

[LoopPred] Handle a subset of NE comparison based latches

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 %e

[LoopPred] Handle a subset of NE comparison based latches

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

show more ...


Revision tags: llvmorg-8.0.1-rc1
# adf288c5 18-Apr-2019 Philip Reames <listmail@philipreames.com>

[LoopPred] Fix a blatantly obvious bug in r358684

The bug is that I didn't check whether the operand of the invariant_loads were themselves invariant. I don't know how this got missed in the patch

[LoopPred] Fix a blatantly obvious bug in r358684

The bug is that I didn't check whether the operand of the invariant_loads were themselves invariant. I don't know how this got missed in the patch and review. I even had an unreduced test case locally, and I remember handling this case, but I must have lost it in one of the rebases. Oops.

llvm-svn: 358688

show more ...


# 92a7177e 18-Apr-2019 Philip Reames <listmail@philipreames.com>

[LoopPredication] Allow predication of loop invariant computations (within the loop)

The purpose of this patch is to eliminate a pass ordering dependence between LoopPredication and LICM. To underst

[LoopPredication] Allow predication of loop invariant computations (within the loop)

The purpose of this patch is to eliminate a pass ordering dependence between LoopPredication and LICM. To understand the purpose, consider the following snippet of code inside some loop 'L' with IV 'i'
A = _a.length;
guard (i < A)
a = _a[i]
B = _b.length;
guard (i < B);
b = _b[i];
...
Z = _z.length;
guard (i < Z)
z = _z[i]
accum += a + b + ... + z;

Today, we need LICM to hoist the length loads, LoopPredication to make the guards loop invariant, and TrivialUnswitch to eliminate the loop invariant guard to establish must execute for the next length load. Today, if we can't prove speculation safety, we'd have to iterate these three passes 26 times to reduce this example down to the minimal form.

Using the fact that the array lengths are known to be invariant, we can short circuit this iteration. By forming the loop invariant form of all the guards at once, we remove the need for LoopPredication from the iterative cycle. At the moment, we'd still have to iterate LICM and TrivialUnswitch; we'll leave that part for later.

As a secondary benefit, this allows LoopPred to expose peeling oppurtunities in a much more obvious manner. See the udiv test changes as an example. If the udiv was not hoistable (i.e. we couldn't prove speculation safety) this would be an example where peeling becomes obviously profitable whereas it wasn't before.

A couple of subtleties in the implementation:
- SCEV's isSafeToExpand guarantees speculation safety (i.e. let's us expand at a new point). It is not a precondition for expansion if we know the SCEV corresponds to a Value which dominates the requested expansion point.
- SCEV's isLoopInvariant returns true for expressions which compute the same value across all iterations executed, regardless of where the original Value is located. (i.e. it can be in the loop) This implies we have a speculation burden to prove before expanding them outside loops.
- invariant_loads and AA->pointsToConstantMemory are two cases that SCEV currently does not handle, but meets the SCEV definition of invariance. I plan to sink this part into SCEV once this has baked for a bit.

Differential Revision: https://reviews.llvm.org/D60093

llvm-svn: 358684

show more ...


# e46d77d1 15-Apr-2019 Philip Reames <listmail@philipreames.com>

[LoopPred] Stop passing around builders [NFC]

This is a preparatory patch for D60093. This patch itself is NFC, but while preparing this I noticed and committed a small hoisting change in rL358419.

[LoopPred] Stop passing around builders [NFC]

This is a preparatory patch for D60093. This patch itself is NFC, but while preparing this I noticed and committed a small hoisting change in rL358419.

The basic structure of the new scheme is that we pass around the guard ("the using instruction"), and select an optimal insert point by examining operands at each construction point. This seems conceptually a bit cleaner to start with as it isolates the knowledge about insertion safety at the actual insertion point.

Note that the non-hoisting path is not actually used at the moment. That's not exercised until D60093 is rebased on this one.

Differential Revision: https://reviews.llvm.org/D60718

llvm-svn: 358434

show more ...


# fbe64a2c 15-Apr-2019 Philip Reames <listmail@philipreames.com>

[LoopPred] Hoist and of predicated checks where legal

If we have multiple range checks which can be predicated, hoist the and of the results outside the loop. This minorly cleans up the resulting I

[LoopPred] Hoist and of predicated checks where legal

If we have multiple range checks which can be predicated, hoist the and of the results outside the loop. This minorly cleans up the resulting IR, but the main motivation is as a building block for D60093.

llvm-svn: 358419

show more ...


# adb3ece2 02-Apr-2019 Philip Reames <listmail@philipreames.com>

[LoopPredication] Simplify widenable condition handling [NFC]

The code doesn't actually need any of the information about the widenable condition at this level. The only thing we need is to ensure

[LoopPredication] Simplify widenable condition handling [NFC]

The code doesn't actually need any of the information about the widenable condition at this level. The only thing we need is to ensure the WC call is the last thing anded in, and even that is a quirk we should really look to remove.

llvm-svn: 357448

show more ...


# f608678f 01-Apr-2019 Philip Reames <listmail@philipreames.com>

[LoopPred] Rename a variable to simply a future patch [NFC]

llvm-svn: 357433


# 05e3e554 01-Apr-2019 Philip Reames <listmail@philipreames.com>

[LoopPred] Be uniform about proving generated conditions

We'd been optimizing the case where the predicate was obviously true, do the same for the false case. Mostly just for completeness sake, but

[LoopPred] Be uniform about proving generated conditions

We'd been optimizing the case where the predicate was obviously true, do the same for the false case. Mostly just for completeness sake, but also may improve compile time in loops which will exit through the guard. Such loops are presumed rare in fastpath code, but may be present down untaken paths, so optimizing for them is still useful.

llvm-svn: 357408

show more ...


# d109e2a7 01-Apr-2019 Philip Reames <listmail@philipreames.com>

[LoopPred] Delete the old condition expressions if unused

LoopPredication was replacing the original condition, but leaving the instructions to compute the old conditions around. This would get cle

[LoopPred] Delete the old condition expressions if unused

LoopPredication was replacing the original condition, but leaving the instructions to compute the old conditions around. This would get cleaned up by other passes of course, but we might as well do it eagerly. That also makes the test output less confusing.

llvm-svn: 357406

show more ...


12345