optimizer, which just happen to frequently involve optimizing GEPs.

llvm-svn: 69295

since the operand is always a constant.

llvm-svn: 69291

new instruction with SCEVExpander::InsertCastOfTo.

llvm-svn: 69290

have pointer types, though in contrast to C pointer types, SCEV
addition is never implicitly scaled. This not only eliminates the
need for special code like IndVars' EliminatePointerRecurrence
and LSR's own GEP expansion code, it also does a better job because
it lets the normal optimizations handle pointer expressions just
like integer expressions.

Also, since LLVM IR GEPs can't directly index into multi-dimensional
VLAs, moving the GEP analysis out of client code and into the SCEV
framework makes it easier for clients to handle multi-dimensional
VLAs the same way as other arrays.

Some existing regression tests show improved optimization.
test/CodeGen/ARM/2007-03-13-InstrSched.ll in particular improved to
the point where if-conversion started kicking in; I turned it off
for this test to preserve the intent of the test.

llvm-svn: 69258

it is not APInt clean, but even when it is it needs to be evaluated carefully
to determine whether it is actually profitable.

This fixes a crash on PR3806

llvm-svn: 67134

if needed. This simplifies the code a little, and is needed for an
upcoming refactoring.

llvm-svn: 66479

where memory access types are needed.

llvm-svn: 66470

llvm-svn: 66469

llvm-svn: 66467

Use VoidTy instead, to be properly conservative.

llvm-svn: 66463

of an instruction into a helper function.

llvm-svn: 66460

have to be done twice.

llvm-svn: 66449

llvm-svn: 66446

before it does any processing.

llvm-svn: 66443

llvm-svn: 66065

immediately obvious.

llvm-svn: 66062

to more accurately describe what it does. Expand its doxygen comment
to describe what the backedge-taken count is and how it differs
from the actual iteration count of the loop. Adjust names and
comments in associated code accordingly.

llvm-svn: 65382

handling non-constant strides. No functionality change.

llvm-svn: 65363

-full-lsr code, as well as a GCC warning.

llvm-svn: 65288

Only try to sink immediate when TLI is not null. It needs to check if immediate would fit in target addressing field.

llvm-svn: 65268

Teach LSR sink to sink the immediate portion of the common expression back into uses if they fit in address modes of all the uses.

llvm-svn: 65215

addresses, part 1. This fixes an obvious logic bug. Previously if the only
in-loop use is a PHI, it would return AllUsesAreAddresses as true.

llvm-svn: 65178

llvm-svn: 65167

llvm-svn: 65159

llvm-svn: 65157

llvm-svn: 65147

reduction of address calculations down to basic pointer arithmetic.
This is currently off by default, as it needs a few other features
before it becomes generally useful. And even when enabled, full
strength reduction is only performed when it doesn't increase
register pressure, and when several other conditions are true.

This also factors out a bunch of exisiting LSR code out of
StrengthReduceStridedIVUsers into separate functions, and tidies
up IV insertion. This actually decreases register pressure even
in non-superhero mode. The change in iv-users-in-other-loops.ll
is an example of this; there are two more adds because there are
two fewer leas, and there is less spilling.

llvm-svn: 65108

since the latter just passes a null reference when
debugging is not enabled.

llvm-svn: 65060

llvm-svn: 65057

llvm-svn: 64859

llvm-svn: 64703

Fix pr3571: If stride is a value defined by an instruction, make sure it dominates the loop preheader. When IV users are strength reduced, the stride is inserted into the preheader. It could create a use before def situation.

llvm-svn: 64579

llvm-svn: 64575

about the code it describes, but at least now the comment
is right.

llvm-svn: 64465

addrec in a different loop to check the value being added to
the accumulated Start value, not the Start value before it has
the new value added to it. This prevents LSR from going crazy
on the included testcase. Dale, please review.

llvm-svn: 64440

after sorting by stride value. This prevents it from missing
IV reuse opportunities in a host-sensitive manner.

llvm-svn: 64415

llvm-svn: 64177

my earlier patch to this file.

The issue there was that all uses of an IV inside a loop
are actually references to Base[IV*2], and there was one
use outside that was the same but LSR didn't see the base
or the scaling because it didn't recurse into uses outside
the loop; thus, it used base+IV*scale mode inside the loop
instead of pulling base out of the loop.  This was extra bad
because register pressure later forced both base and IV into
memory.  Doing that recursion, at least enough
to figure out addressing modes, is a good idea in general;
the change in AddUsersIfInteresting does this.  However,
there were side effects....

It is also possible for recursing outside the loop to
introduce another IV where there was only 1 before (if
the refs inside are not scaled and the ref outside is).
I don't think this is a common case, but it's in the testsuite.
It is right to be very aggressive about getting rid of
such introduced IVs (CheckForIVReuse and the handling of
nonzero RewriteFactor in StrengthReduceStridedIVUsers).
In the testcase in question the new IV produced this way
has both a nonconstant stride and a nonzero base, neither
of which was handled before.  And when inserting 
new code that feeds into a PHI, it's right to put such 
code at the original location rather than in the PHI's 
immediate predecessor(s) when the original location is outside 
the loop (a case that couldn't happen before)
(RewriteInstructionToUseNewBase); better to avoid making
multiple copies of it in this case.

Also, the mechanism for keeping SCEV's corresponding to GEP's
no longer works, as the GEP might change after its SCEV
is remembered, invalidating the SCEV, and we might get a bad
SCEV value when looking up the GEP again for a later loop.  
This also couldn't happen before, as we weren't recursing
into GEP's outside the loop.

Also, when we build an expression that involves a (possibly
non-affine) IV from a different loop as well as an IV from
the one we're interested in (containsAddRecFromDifferentLoop),
don't recurse into that.  We can't do much with it and will
get in trouble if we try to create new non-affine IVs or something.

More testcases are coming.

llvm-svn: 62212

suggested by Chris.

llvm-svn: 62099

llvm-svn: 61403