[LFTR] Use recomputed BE count

This was discussed as part of D62880. The basic thought is that computing BE taken count after widening should produce (on average) an equally good backedge taken cou

[LFTR] Use recomputed BE count

This was discussed as part of D62880. The basic thought is that computing BE taken count after widening should produce (on average) an equally good backedge taken count as the one before widening. Since there's only one test in the suite which is impacted by this change, and it's essentially equivelent codegen, that seems to be a reasonable assertion. This change was separated from r362971 so that if this turns out to be problematic, the triggering piece is obvious and easily revertable.

For the nestedIV example from elim-extend.ll, we end up with the following BE counts:
BEFORE: (-2 + (-1 * %innercount) + %limit)
AFTER: (-1 + (sext i32 (-1 + %limit) to i64) + (-1 * (sext i32 %innercount to i64))<nsw>)

Note that before is an i32 type, and the after is an i64. Truncating the i64 produces the i32.

llvm-svn: 362975

show more ...

Prepare for multi-exit LFTR [NFC]

This change does the plumbing to wire an ExitingBB parameter through the LFTR implementation, and reorganizes the code to work in terms of a set of individual loop

Prepare for multi-exit LFTR [NFC]

This change does the plumbing to wire an ExitingBB parameter through the LFTR implementation, and reorganizes the code to work in terms of a set of individual loop exits. Most of it is fairly obvious, but there's one key complexity which makes it worthy of consideration. The actual multi-exit LFTR patch is in D62625 for context.

Specifically, it turns out the existing code uses the backedge taken count from before a IV is widened. Oddly, we can end up with a different (more expensive, but semantically equivelent) BE count for the loop when requerying after widening. For the nestedIV example from elim-extend, we end up with the following BE counts:
BEFORE: (-2 + (-1 * %innercount) + %limit)
AFTER: (-1 + (sext i32 (-1 + %limit) to i64) + (-1 * (sext i32 %innercount to i64))<nsw>)

This is the only test in tree which seems sensitive to this difference. The actual result of using the wider BETC on this example is that we actually produce slightly better code. :)

In review, we decided to accept that test change. This patch is structured to preserve the old behavior, but a separate change will immediate follow with the behavior change. (I wanted it separate for problem attribution purposes.)

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

llvm-svn: 362971

show more ...

[IndVarSimplify] Fixup nowrap flags during LFTR (PR31181)

Fix for https://bugs.llvm.org/show_bug.cgi?id=31181 and partial fix
for LFTR poison handling issues in general.

When LFTR moves a condition

[IndVarSimplify] Fixup nowrap flags during LFTR (PR31181)

Fix for https://bugs.llvm.org/show_bug.cgi?id=31181 and partial fix
for LFTR poison handling issues in general.

When LFTR moves a condition from pre-inc to post-inc, it may now
depend on value that is poison due to nowrap flags. To avoid this,
we clear any nowrap flag that SCEV cannot prove for the post-inc
addrec.

Additionally, LFTR may switch to a different IV that is dynamically
dead and as such may be arbitrarily poison. This patch will correct
nowrap flags in some but not all cases where this happens. This is
related to the adoption of IR nowrap flags for the pre-inc addrec.
(See some of the switch_to_different_iv tests, where flags are not
dropped or insufficiently dropped.)

Finally, there are likely similar issues with the handling of GEP
inbounds, but we don't have a test case for this yet.

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

llvm-svn: 362292

show more ...

[LFTR] Strengthen assertions in genLoopLimit [NFCI]

llvm-svn: 360978

[IndVars] Don't reimplement Loop::isLoopInvariant [NFC]

Using dominance vs a set membership check is indistinguishable from a compile time perspective, and the two queries return equivelent results.

[IndVars] Don't reimplement Loop::isLoopInvariant [NFC]

Using dominance vs a set membership check is indistinguishable from a compile time perspective, and the two queries return equivelent results. Simplify code by using the existing function.

llvm-svn: 360976

show more ...

[LFTR] Factor out a helper function for readability purpose [NFC]

llvm-svn: 360972

Clarify comments on helpers used by LFTR [NFC]

I'm slowly wrapping my head around this code, and am making comment improvements where I can.

llvm-svn: 360968

Fix a release mode warning introduced in r360694

llvm-svn: 360696

[IndVars] Extend reasoning about loop invariant exits to non-header blocks

Noticed while glancing through the code for other reasons. The extension is trivial enough, decided to just do it.

llvm-s

[IndVars] Extend reasoning about loop invariant exits to non-header blocks

Noticed while glancing through the code for other reasons. The extension is trivial enough, decided to just do it.

llvm-svn: 360694

show more ...

[IndVars] Fix corner case with unreachable Phi inputs. PR40454

Logic in `getInsertPointForUses` doesn't account for a corner case when `Def`
only comes to a Phi user from unreachable blocks. In this

[IndVars] Fix corner case with unreachable Phi inputs. PR40454

Logic in `getInsertPointForUses` doesn't account for a corner case when `Def`
only comes to a Phi user from unreachable blocks. In this case, the incoming
value may be arbitrary (and not even available in the input block) and break
the loop-related invariants that are asserted below.

In fact, if we encounter this situation, no IR modification is needed. This
Phi will be simplified away with nearest cleanup.

Differential Revision: https://reviews.llvm.org/D58045
Reviewed By: spatel

llvm-svn: 353816

show more ...

[opaque pointer types] Pass value type to GetElementPtr creation.

This cleans up all GetElementPtr creation in LLVM to explicitly pass a
value type rather than deriving it from the pointer's element

[opaque pointer types] Pass value type to GetElementPtr creation.

This cleans up all GetElementPtr creation in LLVM to explicitly pass a
value type rather than deriving it from the pointer's element-type.

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

llvm-svn: 352913

show more ...

Update the file headers across all of the LLVM projects in the monorepo
to reflect the new license.

We understand that people may be surprised that we're moving the header
entirely to discuss the ne

Update the file headers across all of the LLVM projects in the monorepo
to reflect the new license.

We understand that people may be surprised that we're moving the header
entirely to discuss the new license. We checked this carefully with the
Foundation's lawyer and we believe this is the correct approach.

Essentially, all code in the project is now made available by the LLVM
project under our new license, so you will see that the license headers
include that license only. Some of our contributors have contributed
code under our old license, and accordingly, we have retained a copy of
our old license notice in the top-level files in each project and
repository.

llvm-svn: 351636

show more ...

Return "[IndVars] Smart hard uses detection"

The patch has been reverted because it ended up prohibiting propagation
of a constant to exit value. For such values, we should skip all checks
related t

Return "[IndVars] Smart hard uses detection"

The patch has been reverted because it ended up prohibiting propagation
of a constant to exit value. For such values, we should skip all checks
related to hard uses because propagating a constant is always profitable.

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

llvm-svn: 346397

show more ...

Revert "[IndVars] Smart hard uses detection"

This reverts commit 2f425e9c7946b9d74e64ebbfa33c1caa36914402.

It seems that the check that we still should do the transform if we
know the result is con

Revert "[IndVars] Smart hard uses detection"

This reverts commit 2f425e9c7946b9d74e64ebbfa33c1caa36914402.

It seems that the check that we still should do the transform if we
know the result is constant is missing in this code. So the logic that
has been deleted by this change is still sometimes accidentally useful.
I revert the change to see what can be done about it. The motivating
case is the following:

@Y = global [400 x i16] zeroinitializer, align 1

define i16 @foo() {
entry:
br label %for.body

for.body: ; preds = %entry, %for.body
%i = phi i16 [ 0, %entry ], [ %inc, %for.body ]

%arrayidx = getelementptr inbounds [400 x i16], [400 x i16]* @Y, i16 0, i16 %i
store i16 0, i16* %arrayidx, align 1
%inc = add nuw nsw i16 %i, 1
%cmp = icmp ult i16 %inc, 400
br i1 %cmp, label %for.body, label %for.end

for.end: ; preds = %for.body
%inc.lcssa = phi i16 [ %inc, %for.body ]
ret i16 %inc.lcssa
}

We should be able to figure out that the result is constant, but the patch
breaks it.

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

llvm-svn: 346198

show more ...

[IndVars] Smart hard uses detection

When rewriting loop exit values, IndVars considers this transform not profitable if
the loop instruction has a loop user which it believes cannot be optimized awa

[IndVars] Smart hard uses detection

When rewriting loop exit values, IndVars considers this transform not profitable if
the loop instruction has a loop user which it believes cannot be optimized away.
In current implementation only calls that immediately use the instruction are considered
as such.

This patch extends the definition of "hard" users to any side-effecting instructions
(which usually cannot be optimized away from the loop) and also allows handling
of not just immediate users, but use chains.

Differentlai Revision: https://reviews.llvm.org/D51584
Reviewed By: etherzhhb

llvm-svn: 345814

show more ...

[IndVars] Strengthen restricton in rewriteLoopExitValues

For some unclear reason rewriteLoopExitValues considers recalculation
after the loop profitable if it has some "soft uses" outside the loop (

[IndVars] Strengthen restricton in rewriteLoopExitValues

For some unclear reason rewriteLoopExitValues considers recalculation
after the loop profitable if it has some "soft uses" outside the loop (i.e. any
use other than call and return), even if we have proved that it has a user inside
the loop which we think will not be optimized away.

There is no existing unit test that would explain this. This patch provides an
example when rematerialisation of exit value is not profitable but it passes
this check due to presence of a "soft use" outside the loop.

It makes no sense to recalculate value on exit if we are going to compute it
due to some irremovable within the loop. This patch disallows applying this
transform in the described situation.

Differential Revision: https://reviews.llvm.org/D51581
Reviewed By: etherzhhb

llvm-svn: 345708

show more ...

[IndVars] Remove unreasonable checks in rewriteLoopExitValues

A piece of logic in rewriteLoopExitValues has a weird check on number of
users which allowed an unprofitable transform in case if an ins

[IndVars] Remove unreasonable checks in rewriteLoopExitValues

A piece of logic in rewriteLoopExitValues has a weird check on number of
users which allowed an unprofitable transform in case if an instruction has
more than 6 users.

Differential Revision: https://reviews.llvm.org/D51404
Reviewed By: etherzhhb

llvm-svn: 342444

show more ...

[NFC] Turn unsigned counters into boolean flags

llvm-svn: 342360

[IndVars][NFC] Refactor to make modifications of Changed transparent

IndVarSimplify's design is somewhat odd in the way how it reports that
some transform has made a change. It has a `Changed` field

[IndVars][NFC] Refactor to make modifications of Changed transparent

IndVarSimplify's design is somewhat odd in the way how it reports that
some transform has made a change. It has a `Changed` field which can
be set from within any function, which makes it hard to track whether or
not it was set properly after a transform was made. It leads to oversights
in setting this flag where needed, see example in PR38855.

This patch removes the `Changed` field, turns it into a local and unifies
the signatures of all relevant transform functions to return boolean value
which designates whether or not this transform has made a change.

Differential Revision: https://reviews.llvm.org/D51850
Reviewed By: skatkov

llvm-svn: 341893

show more ...

[IndVars] Set Changed if rewriteFirstIterationLoopExitValues changes IR. PR38863

Currently, `rewriteFirstIterationLoopExitValues` does not set Changed flag even if it makes
changes in the IR. There

[IndVars] Set Changed if rewriteFirstIterationLoopExitValues changes IR. PR38863

Currently, `rewriteFirstIterationLoopExitValues` does not set Changed flag even if it makes
changes in the IR. There is no clear evidence that it can cause a crash, but it
looks highly suspicious and likely invalid.

Differential Revision: https://reviews.llvm.org/D51779
Reviewed By: skatkov

llvm-svn: 341779

show more ...

[IndVars] Set Changed if sinkUnusedInvariants changes IR. PR38863

Currently, `sinkUnusedInvariants` does not set Changed flag even if it makes
changes in the IR. There is no clear evidence that it c

[IndVars] Set Changed if sinkUnusedInvariants changes IR. PR38863

Currently, `sinkUnusedInvariants` does not set Changed flag even if it makes
changes in the IR. There is no clear evidence that it can cause a crash, but it
looks highly suspicious and likely invalid.

Differential Revision: https://reviews.llvm.org/D51777
Reviewed By: skatkov

llvm-svn: 341777

show more ...

[SimplifyIndVar] Avoid generating truncate instructions with non-hoisted Laod operand.

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

llvm-svn: 341726

[IndVars] Set Changed when we delete dead instructions. PR38855

IndVars does not set `Changed` flag when it eliminates dead instructions. As result,
it may make IR modifications and report that it h

[IndVars] Set Changed when we delete dead instructions. PR38855

IndVars does not set `Changed` flag when it eliminates dead instructions. As result,
it may make IR modifications and report that it has done nothing. It leads to inconsistent
preserved analyzes results.

Differential Revision: https://reviews.llvm.org/D51770
Reviewed By: skatkov

llvm-svn: 341633

show more ...

Revert "[IndVars] Turn isValidRewrite into an assertion" because it seems wrong

llvm-svn: 341517

[IndVars] Turn isValidRewrite into an assertion

Function rewriteLoopExitValues contains a check on isValidRewrite which
is needed to make sure that SCEV does not convert the pattern
`gep Base, (&p[n

[IndVars] Turn isValidRewrite into an assertion

Function rewriteLoopExitValues contains a check on isValidRewrite which
is needed to make sure that SCEV does not convert the pattern
`gep Base, (&p[n] - &p[0])` into `gep &p[n], Base - &p[0]`. This problem
has been fixed in SCEV long ago, so this check is just obsolete.

This patch converts it into an assertion to make sure that the SCEV will
not mess up this case in the future.

Differential Revision: https://reviews.llvm.org/D51582
Reviewed By: atrick

llvm-svn: 341516

show more ...