History log of /external/llvm/lib/Transforms/Scalar/LoopIdiomRecognize.cpp
Revision Date Author Comments (<<< Hide modified files) (Show modified files >>>)
cd81d94322a39503e4a3e87b6ee03d4fcb3465fb 21-Jul-2014 Stephen Hines <srhines@google.com> Update LLVM for rebase to r212749.

Includes a cherry-pick of:
r212948 - fixes a small issue with atomic calls

Change-Id: Ib97bd980b59f18142a69506400911a6009d9df18
/external/llvm/lib/Transforms/Scalar/LoopIdiomRecognize.cpp
dce4a407a24b04eebc6a376f8e62b41aaa7b071f 29-May-2014 Stephen Hines <srhines@google.com> Update LLVM for 3.5 rebase (r209712).

Change-Id: I149556c940fb7dc92d075273c87ff584f400941f
/external/llvm/lib/Transforms/Scalar/LoopIdiomRecognize.cpp
36b56886974eae4f9c5ebc96befd3e7bfe5de338 24-Apr-2014 Stephen Hines <srhines@google.com> Update to LLVM 3.5a.

Change-Id: Ifadecab779f128e62e430c2b4f6ddd84953ed617
/external/llvm/lib/Transforms/Scalar/LoopIdiomRecognize.cpp
3f4f420ab7acb10221ba971543a7eed5489fb626 28-Sep-2013 Robert Wilhelm <robert.wilhelm@gmx.net> Even more spelling fixes for "instruction".


git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@191611 91177308-0d34-0410-b5e6-96231b3b80d8
/external/llvm/lib/Transforms/Scalar/LoopIdiomRecognize.cpp
11250c1194830aa4cec72788dcd04f06cfe33f50 11-Sep-2013 Matt Arsenault <Matthew.Arsenault@amd.com> Teach loop-idiom about address space pointer sizes

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@190491 91177308-0d34-0410-b5e6-96231b3b80d8
/external/llvm/lib/Transforms/Scalar/LoopIdiomRecognize.cpp
f834dce7c7d13af85be5bc8b789c1d7793db8a58 11-Sep-2013 Matt Arsenault <Matthew.Arsenault@amd.com> Add braces

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@190490 91177308-0d34-0410-b5e6-96231b3b80d8
/external/llvm/lib/Transforms/Scalar/LoopIdiomRecognize.cpp
1f4492e0b0d3b2d58a0243f7b3d1a45ba0261075 22-Jul-2013 Matt Arsenault <Matthew.Arsenault@amd.com> Fix spelling and grammar

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@186858 91177308-0d34-0410-b5e6-96231b3b80d8
/external/llvm/lib/Transforms/Scalar/LoopIdiomRecognize.cpp
253449db20f86b655852a397245ba16ff262452f 11-Jan-2013 Shuxin Yang <shuxin.llvm@gmail.com> PR14904: Segmentation fault running pass 'Recognize loop idioms'

The root cause is mistakenly taking for granted that
"dyn_cast<Instruction>(a-Value)"
return a non-NULL instruction.


git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@172145 91177308-0d34-0410-b5e6-96231b3b80d8
/external/llvm/lib/Transforms/Scalar/LoopIdiomRecognize.cpp
d12aae6c0535bd2713207ef84b7098f905a89b78 07-Jan-2013 Chandler Carruth <chandlerc@gmail.com> Switch LoopIdiom pass to directly require target transform information.

I'm sorry for duplicating bad style here, but I wanted to keep
consistency. I've pinged the code review thread where this style was
reviewed and changes were requested.

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@171714 91177308-0d34-0410-b5e6-96231b3b80d8
/external/llvm/lib/Transforms/Scalar/LoopIdiomRecognize.cpp
d1b8ef97c47d347f2a2261a0d6de4872f248321f 07-Jan-2013 Chandler Carruth <chandlerc@gmail.com> Make the popcnt support enums and methods have more clear names and
follow the conding conventions regarding enumerating a set of "kinds" of
things.

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@171687 91177308-0d34-0410-b5e6-96231b3b80d8
/external/llvm/lib/Transforms/Scalar/LoopIdiomRecognize.cpp
be04929f7fd76a921540e9901f24563e51dc1219 07-Jan-2013 Chandler Carruth <chandlerc@gmail.com> Move TargetTransformInfo to live under the Analysis library. This no
longer would violate any dependency layering and it is in fact an
analysis. =]

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@171686 91177308-0d34-0410-b5e6-96231b3b80d8
/external/llvm/lib/Transforms/Scalar/LoopIdiomRecognize.cpp
9980b8a0bd4c5dfb67909a2de7720076881e6525 05-Jan-2013 Chandler Carruth <chandlerc@gmail.com> Switch LoopIdiomRecognize to directly use the TargetTransformInfo
interface rather than the ScalarTargetTransformInterface.

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@171616 91177308-0d34-0410-b5e6-96231b3b80d8
/external/llvm/lib/Transforms/Scalar/LoopIdiomRecognize.cpp
cbf5373603991b7196f096ddf2b5962ed7708b7e 02-Jan-2013 Shuxin Yang <shuxin.llvm@gmail.com> - Add comment to two functions which might be considered as dead code.
- Fix a typo


git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@171399 91177308-0d34-0410-b5e6-96231b3b80d8
/external/llvm/lib/Transforms/Scalar/LoopIdiomRecognize.cpp
0b8c9a80f20772c3793201ab5b251d3520b9cea3 02-Jan-2013 Chandler Carruth <chandlerc@gmail.com> Move all of the header files which are involved in modelling the LLVM IR
into their new header subdirectory: include/llvm/IR. This matches the
directory structure of lib, and begins to correct a long standing point
of file layout clutter in LLVM.

There are still more header files to move here, but I wanted to handle
them in separate commits to make tracking what files make sense at each
layer easier.

The only really questionable files here are the target intrinsic
tablegen files. But that's a battle I'd rather not fight today.

I've updated both CMake and Makefile build systems (I think, and my
tests think, but I may have missed something).

I've also re-sorted the includes throughout the project. I'll be
committing updates to Clang, DragonEgg, and Polly momentarily.

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@171366 91177308-0d34-0410-b5e6-96231b3b80d8
/external/llvm/lib/Transforms/Scalar/LoopIdiomRecognize.cpp
5518a1355b8b09bf92419b65ea4e4854734b0ebc 09-Dec-2012 Shuxin Yang <shuxin.llvm@gmail.com> - Re-enable population count loop idiom recognization
- fix a bug which cause sigfault.
- add two testing cases which was causing crash


git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@169687 91177308-0d34-0410-b5e6-96231b3b80d8
/external/llvm/lib/Transforms/Scalar/LoopIdiomRecognize.cpp
7065a2bcec3b775da12cf8fbcd6fa972d5f2afeb 08-Dec-2012 Chandler Carruth <chandlerc@gmail.com> Revert the patches adding a popcount loop idiom recognition pass.

There are still bugs in this pass, as well as other issues that are
being worked on, but the bugs are crashers that occur pretty easily in
the wild. Test cases have been sent to the original commit's review
thread.

This reverts the commits:
r169671: Fix a logic error.
r169604: Move the popcnt tests to an X86 subdirectory.
r168931: Initial commit adding the pass.

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@169683 91177308-0d34-0410-b5e6-96231b3b80d8
/external/llvm/lib/Transforms/Scalar/LoopIdiomRecognize.cpp
19bfae479708a2f212513d6060b40334b67f4d80 08-Dec-2012 Shuxin Yang <shuxin.llvm@gmail.com> Fix an inadvertent typo error.


git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@169671 91177308-0d34-0410-b5e6-96231b3b80d8
/external/llvm/lib/Transforms/Scalar/LoopIdiomRecognize.cpp
d04a8d4b33ff316ca4cf961e06c9e312eff8e64f 03-Dec-2012 Chandler Carruth <chandlerc@gmail.com> Use the new script to sort the includes of every file under lib.

Sooooo many of these had incorrect or strange main module includes.
I have manually inspected all of these, and fixed the main module
include to be the nearest plausible thing I could find. If you own or
care about any of these source files, I encourage you to take some time
and check that these edits were sensible. I can't have broken anything
(I strictly added headers, and reordered them, never removed), but they
may not be the headers you'd really like to identify as containing the
API being implemented.

Many forward declarations and missing includes were added to a header
files to allow them to parse cleanly when included first. The main
module rule does in fact have its merits. =]

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@169131 91177308-0d34-0410-b5e6-96231b3b80d8
/external/llvm/lib/Transforms/Scalar/LoopIdiomRecognize.cpp
84fca61ca5fba5c33a799d9133750b6832ddef7e 29-Nov-2012 Shuxin Yang <shuxin.llvm@gmail.com> rdar://12100355 (part 1)

This revision attempts to recognize following population-count pattern:

while(a) { c++; ... ; a &= a - 1; ... },
where <c> and <a>could be used multiple times in the loop body.

TODO: On X8664 and ARM, __buildin_ctpop() are not expanded to a efficent
instruction sequence, which need to be improved in the following commits.

Reviewed by Nadav, really appreciate!


git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@168931 91177308-0d34-0410-b5e6-96231b3b80d8
/external/llvm/lib/Transforms/Scalar/LoopIdiomRecognize.cpp
a864748284f4bab974ffb13b840a611c1f9bc7ac 02-Nov-2012 Chandler Carruth <chandlerc@gmail.com> Revert the switch of loop-idiom to use the new dependence analysis.

The new analysis is not yet ready for prime time. It has a *critical*
flawed assumption, and some troubling shortages of testing. Until it's
been hammered into better shape, let's stick with the working code. This
should be easy to revert itself when the analysis is ready.

Fixes PR14241, a miscompile of any memcpy-able loop which uses a pointer
as the induction mechanism. If you have been seeing miscompiles in this
revision range, you really want to test with this backed out. The
results of this miscompile are a bit subtle as they can lead to
downstream passes concluding things are impossible which are in fact
possible.

Thanks to David Blaikie for the majority of the reduction of this
miscompile. I'll be checking in the test case in a non-revert commit.

Revesions reverted here:

r167045: LoopIdiom: Fix a serious missed optimization: we only turned
top-level loops into memmove.
r166877: LoopIdiom: Add checks to avoid turning memmove into an infinite
loop.
r166875: LoopIdiom: Recognize memmove loops.
r166874: LoopIdiom: Replace custom dependence analysis with
DependenceAnalysis.

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@167286 91177308-0d34-0410-b5e6-96231b3b80d8
/external/llvm/lib/Transforms/Scalar/LoopIdiomRecognize.cpp
ece6c6bb6329748b92403c06ac87f45c43485911 01-Nov-2012 Chandler Carruth <chandlerc@gmail.com> Revert the series of commits starting with r166578 which introduced the
getIntPtrType support for multiple address spaces via a pointer type,
and also introduced a crasher bug in the constant folder reported in
PR14233.

These commits also contained several problems that should really be
addressed before they are re-committed. I have avoided reverting various
cleanups to the DataLayout APIs that are reasonable to have moving
forward in order to reduce the amount of churn, and minimize the number
of commits that were reverted. I've also manually updated merge
conflicts and manually arranged for the getIntPtrType function to stay
in DataLayout and to be defined in a plausible way after this revert.

Thanks to Duncan for working through this exact strategy with me, and
Nick Lewycky for tracking down the really annoying crasher this
triggered. (Test case to follow in its own commit.)

After discussing with Duncan extensively, and based on a note from
Micah, I'm going to continue to back out some more of the more
problematic patches in this series in order to ensure we go into the
LLVM 3.2 branch with a reasonable story here. I'll send a note to
llvmdev explaining what's going on and why.

Summary of reverted revisions:

r166634: Fix a compiler warning with an unused variable.
r166607: Add some cleanup to the DataLayout changes requested by
Chandler.
r166596: Revert "Back out r166591, not sure why this made it through
since I cancelled the command. Bleh, sorry about this!
r166591: Delete a directory that wasn't supposed to be checked in yet.
r166578: Add in support for getIntPtrType to get the pointer type based
on the address space.

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@167221 91177308-0d34-0410-b5e6-96231b3b80d8
/external/llvm/lib/Transforms/Scalar/LoopIdiomRecognize.cpp
415f869cf30a272072c0533a2dea85496a210309 30-Oct-2012 Benjamin Kramer <benny.kra@googlemail.com> LoopIdiom: Fix a serious missed optimization: we only turned top-level loops into memmove.

Thanks to Preston Briggs for catching this!

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@167045 91177308-0d34-0410-b5e6-96231b3b80d8
/external/llvm/lib/Transforms/Scalar/LoopIdiomRecognize.cpp
badffcf8fddf3978acf9843a43e66766e9e830c6 27-Oct-2012 Benjamin Kramer <benny.kra@googlemail.com> LoopIdiom: Add checks to avoid turning memmove into an infinite loop.

I don't think this is possible with the current implementation but that may change eventually.

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@166877 91177308-0d34-0410-b5e6-96231b3b80d8
/external/llvm/lib/Transforms/Scalar/LoopIdiomRecognize.cpp
d11c5d08a5f4f030d6e357378d0d46d93efd9a59 27-Oct-2012 Benjamin Kramer <benny.kra@googlemail.com> LoopIdiom: Recognize memmove loops.

This turns loops like
for (unsigned i = 0; i != n; ++i)
p[i] = p[i+1];
into memmove, which has a highly optimized implementation in most libcs.

This was really easy with the new DependenceAnalysis :)

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@166875 91177308-0d34-0410-b5e6-96231b3b80d8
/external/llvm/lib/Transforms/Scalar/LoopIdiomRecognize.cpp
96c8735e28f2f89be37cdd907f680c6c1bf16052 27-Oct-2012 Benjamin Kramer <benny.kra@googlemail.com> LoopIdiom: Replace custom dependence analysis with DependenceAnalysis.

Requires a lot less code and complexity on loop-idiom's side and the more
precise analysis can catch more cases, like the one I included as a test case.
This also fixes the edge-case miscompilation from PR9481.

Compile time performance seems to be slightly worse, but this is mostly due
to an extra LCSSA run scheduled by the PassManager and should be fixed there.

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@166874 91177308-0d34-0410-b5e6-96231b3b80d8
/external/llvm/lib/Transforms/Scalar/LoopIdiomRecognize.cpp
aa76e9e2cf50af190de90bc778b7f7e42ef9ceff 24-Oct-2012 Micah Villmow <villmow@gmail.com> Add in support for getIntPtrType to get the pointer type based on the address space.
This checkin also adds in some tests that utilize these paths and updates some of the
clients.


git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@166578 91177308-0d34-0410-b5e6-96231b3b80d8
/external/llvm/lib/Transforms/Scalar/LoopIdiomRecognize.cpp
3740e798bc850cd5d40185959801606433b0221f 21-Oct-2012 Benjamin Kramer <benny.kra@googlemail.com> Revert r166390 "LoopIdiom: Replace custom dependence analysis with LoopDependenceAnalysis."

It passes all tests, produces better results than the old code but uses the
wrong pass, LoopDependenceAnalysis, which is old and unmaintained. "Why is it
still in tree?", you might ask. The answer is obviously: "To confuse developers."

Just swapping in the new dependency pass sends the pass manager into an infinte
loop, I'll try to figure out why tomorrow.

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@166399 91177308-0d34-0410-b5e6-96231b3b80d8
/external/llvm/lib/Transforms/Scalar/LoopIdiomRecognize.cpp
5c6e9ae14e012bfe1fdf0e19957922d3c4d85670 21-Oct-2012 Benjamin Kramer <benny.kra@googlemail.com> LoopIdiom: Replace custom dependence analysis with LoopDependenceAnalysis.

Requires a lot less code and complexity on loop-idiom's side and the more
precise analysis can catch more cases, like the one I included as a test case.
This also fixes the edge-case miscompilation from PR9481. I'm not entirely
sure that all cases are handled that the old checks handled but LDA will
certainly become smarter in the future.

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@166390 91177308-0d34-0410-b5e6-96231b3b80d8
/external/llvm/lib/Transforms/Scalar/LoopIdiomRecognize.cpp
3574eca1b02600bac4e625297f4ecf745f4c4f32 08-Oct-2012 Micah Villmow <villmow@gmail.com> Move TargetData to DataLayout.

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@165402 91177308-0d34-0410-b5e6-96231b3b80d8
/external/llvm/lib/Transforms/Scalar/LoopIdiomRecognize.cpp
28aff84ceb2fcf0e4b05ed95b81e46fcd4cd373f 21-Sep-2012 Benjamin Kramer <benny.kra@googlemail.com> LoopIdiom: Give up when the loop is not in canonical form.

We rely on it when doing the transforms. This can happen when there is an
indirectbr in the loop.

Fixes PR13892.

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@164383 91177308-0d34-0410-b5e6-96231b3b80d8
/external/llvm/lib/Transforms/Scalar/LoopIdiomRecognize.cpp
8e0d1c03ca7fd86e6879b4e37d0d7f0e982feef6 29-Aug-2012 Benjamin Kramer <benny.kra@googlemail.com> Make MemoryBuiltins aware of TargetLibraryInfo.

This disables malloc-specific optimization when -fno-builtin (or -ffreestanding)
is specified. This has been a problem for a long time but became more severe
with the recent memory builtin improvements.

Since the memory builtin functions are used everywhere, this required passing
TLI in many places. This means that functions that now have an optional TLI
argument, like RecursivelyDeleteTriviallyDeadFunctions, won't remove dead
mallocs anymore if the TLI argument is missing. I've updated most passes to do
the right thing.

Fixes PR13694 and probably others.

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@162841 91177308-0d34-0410-b5e6-96231b3b80d8
/external/llvm/lib/Transforms/Scalar/LoopIdiomRecognize.cpp
a94d6e87c4c49f2e81b01d66d8bfb591277f8f96 24-Jul-2012 Nadav Rotem <nadav.rotem@intel.com> Clean whitespaces.

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@160668 91177308-0d34-0410-b5e6-96231b3b80d8
/external/llvm/lib/Transforms/Scalar/LoopIdiomRecognize.cpp
06cb8ed00696eb14d1b831921452e50ec0568ea2 29-Jun-2012 Chandler Carruth <chandlerc@gmail.com> Move llvm/Support/IRBuilder.h -> llvm/IRBuilder.h

This was always part of the VMCore library out of necessity -- it deals
entirely in the IR. The .cpp file in fact was already part of the VMCore
library. This is just a mechanical move.

I've tried to go through and re-apply the coding standard's preferred
header sort, but at 40-ish files, I may have gotten some wrong. Please
let me know if so.

I'll be committing the corresponding updates to Clang and Polly, and
Duncan has DragonEgg.

Thanks to Bill and Eric for giving the green light for this bit of cleanup.

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@159421 91177308-0d34-0410-b5e6-96231b3b80d8
/external/llvm/lib/Transforms/Scalar/LoopIdiomRecognize.cpp
5ac7c7da3ebfd1aa95226aeefb8cfa3ba34fd72a 13-Sep-2011 Eli Friedman <eli.friedman@gmail.com> Correct grammar.



git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@139565 91177308-0d34-0410-b5e6-96231b3b80d8
/external/llvm/lib/Transforms/Scalar/LoopIdiomRecognize.cpp
2bc3d52b9ab422ee9f7e42a1a4e3b818e623a5f7 12-Sep-2011 Eli Friedman <eli.friedman@gmail.com> Change a bunch of isVolatile() checks to check for atomic load/store as well.

No tests; these changes aren't really interesting in the sense that the logic is the same for volatile and atomic.

I believe this completes all of the changes necessary for the optimizer to handle loads and stores correctly. I'm going to try and come up with some additional testing, though.



git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@139533 91177308-0d34-0410-b5e6-96231b3b80d8
/external/llvm/lib/Transforms/Scalar/LoopIdiomRecognize.cpp
db125cfaf57cc83e7dd7453de2d509bc8efd0e5e 18-Jul-2011 Chris Lattner <sabre@nondot.org> land David Blaikie's patch to de-constify Type, with a few tweaks.



git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@135375 91177308-0d34-0410-b5e6-96231b3b80d8
/external/llvm/lib/Transforms/Scalar/LoopIdiomRecognize.cpp
71400b6afa3a650cac0ace1beb24a35518555f56 15-Jul-2011 Chad Rosier <mcrosier@apple.com> Disable loop idiom recognition of memset/memcpy if the function being compiled
is named after a common idiom (i.e., memset/memcpy). Otherwise, we can run into
infinite recursion. Ideally, the user should use the correct -fno-builtin flag,
but in case they don't we should play nicely.
rdar://9763412

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@135286 91177308-0d34-0410-b5e6-96231b3b80d8
/external/llvm/lib/Transforms/Scalar/LoopIdiomRecognize.cpp
5e7645be4c9dd2193add44d30b5fef8036d7a3ce 28-Jun-2011 Andrew Trick <atrick@apple.com> SCEVExpander: give new insts a name that identifies the reponsible pass.


git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@133992 91177308-0d34-0410-b5e6-96231b3b80d8
/external/llvm/lib/Transforms/Scalar/LoopIdiomRecognize.cpp
a5d950f673c29710d0e9e2afefe74b7003362a06 28-Jun-2011 Andrew Trick <atrick@apple.com> whitespace


git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@133991 91177308-0d34-0410-b5e6-96231b3b80d8
/external/llvm/lib/Transforms/Scalar/LoopIdiomRecognize.cpp
4f81b5419295cfc26a1349d6c23a55c6d2a683e1 22-May-2011 Chris Lattner <sabre@nondot.org> Fix PR9815: I was trying to get out of "generating code and then
failing to form a memset, then having to delete it" but my approximation
isn't safe for self recurrent loops. Instead of doign a hack, just
do it the right way.


git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@131858 91177308-0d34-0410-b5e6-96231b3b80d8
/external/llvm/lib/Transforms/Scalar/LoopIdiomRecognize.cpp
af35841f2e346f9259606886698c188280406cdb 04-May-2011 Devang Patel <dpatel@apple.com> preserve line number info.


git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@130869 91177308-0d34-0410-b5e6-96231b3b80d8
/external/llvm/lib/Transforms/Scalar/LoopIdiomRecognize.cpp
3228cc259b5ca00e46af36da369a451f5736cbf4 14-Mar-2011 Andrew Trick <atrick@apple.com> Added SCEV::NoWrapFlags to manage unsigned, signed, and self wrap
properties.
Added the self-wrap flag for SCEV::AddRecExpr.
A slew of temporary FIXMEs indicate the intention of the no-self-wrap flag
without changing behavior in this revision.


git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@127590 91177308-0d34-0410-b5e6-96231b3b80d8
/external/llvm/lib/Transforms/Scalar/LoopIdiomRecognize.cpp
d99b39e43b6e8263c80425c99d4e924f08e86e43 14-Mar-2011 Andrew Trick <atrick@apple.com> whitespace


git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@127589 91177308-0d34-0410-b5e6-96231b3b80d8
/external/llvm/lib/Transforms/Scalar/LoopIdiomRecognize.cpp
cd77a50e638be5e7153ebe2a8ba875de7df48bea 07-Mar-2011 Devang Patel <dpatel@apple.com> Preserve line no. info.
Radar 9097659


git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@127182 91177308-0d34-0410-b5e6-96231b3b80d8
/external/llvm/lib/Transforms/Scalar/LoopIdiomRecognize.cpp
0e68cee62f251c45df92c71ca536142bc7d82631 21-Feb-2011 Chris Lattner <sabre@nondot.org> fix a crasher in disabled code (on variable stride loops)


git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@126125 91177308-0d34-0410-b5e6-96231b3b80d8
/external/llvm/lib/Transforms/Scalar/LoopIdiomRecognize.cpp
408b534e431cc317f1116cd78df96da2af7cafd9 21-Feb-2011 Chris Lattner <sabre@nondot.org> Add some (disabled code) to print out negative strides.


git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@126102 91177308-0d34-0410-b5e6-96231b3b80d8
/external/llvm/lib/Transforms/Scalar/LoopIdiomRecognize.cpp
80e8b506b8134d63dc3cb6211cccc34be4b19d40 19-Feb-2011 Chris Lattner <sabre@nondot.org> rewrite the memset_pattern pattern generation stuff to accept any 2/4/8/16-byte
constant, including globals. This makes us generate much more "pretty" pattern
globals as well because it doesn't break it down to an array of bytes all the
time.

This enables us to handle stores of relocatable globals. This kicks in about
48 times in 254.gap, giving us stuff like this:

@.memset_pattern40 = internal constant [2 x %struct.TypHeader* (%struct.TypHeader*, %struct.TypHeader*)*] [%struct.TypHeader* (%struct.TypHeader*, %struct
.TypHeader*)* @IsFalse, %struct.TypHeader* (%struct.TypHeader*, %struct.TypHeader*)* @IsFalse], align 16

...
call void @memset_pattern16(i8* %scevgep5859, i8* bitcast ([2 x %struct.TypHeader* (%struct.TypHeader*, %struct.TypHeader*)*]* @.memset_pattern40 to i8*
), i64 %tmp75) nounwind



git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@126044 91177308-0d34-0410-b5e6-96231b3b80d8
/external/llvm/lib/Transforms/Scalar/LoopIdiomRecognize.cpp
3a393728a62122d7009d8e2cbe52a221874e576a 19-Feb-2011 Chris Lattner <sabre@nondot.org> Implement rdar://9009151, transforming strided loop stores of
unsplatable values into memset_pattern16 when it is available
(recent darwins). This transforms lots of strided loop stores
of ints for example, like 5 in vpr:

Formed memset: call void @memset_pattern16(i8* %4, i8* getelementptr inbounds ([16 x i8]* @.memset_pattern9, i32 0, i32 0), i64 %tmp25)
from store to: {%3,+,4}<%11> at: store i32 3, i32* %scevgep, align 4, !tbaa !4




git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@126040 91177308-0d34-0410-b5e6-96231b3b80d8
/external/llvm/lib/Transforms/Scalar/LoopIdiomRecognize.cpp
c19175c9d8d3c2663b682a7fe34bb22da370d5c1 18-Feb-2011 Chris Lattner <sabre@nondot.org> Make loop-idiom use TargetLibraryInfo to determine whether it is allowed
to hack on memset, memcpy etc.


git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@125974 91177308-0d34-0410-b5e6-96231b3b80d8
/external/llvm/lib/Transforms/Scalar/LoopIdiomRecognize.cpp
ab4c366274a582dd8146b2820c6b999cad5fce36 15-Feb-2011 Duncan Sands <baldrick@free.fr> Spelling fix: consequtive -> consecutive.


git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@125563 91177308-0d34-0410-b5e6-96231b3b80d8
/external/llvm/lib/Transforms/Scalar/LoopIdiomRecognize.cpp
e41d3c015ce5cafde305d9a6d9baaae1c41bf46a 04-Jan-2011 Chris Lattner <sabre@nondot.org> Teach loop-idiom to turn a loop containing a memset into a larger memset
when safe.

The testcase is basically this nested loop:
void foo(char *X) {
for (int i = 0; i != 100; ++i)
for (int j = 0; j != 100; ++j)
X[j+i*100] = 0;
}

which gets turned into a single memset now. clang -O3 doesn't optimize
this yet though due to a phase ordering issue I haven't analyzed yet.



git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@122806 91177308-0d34-0410-b5e6-96231b3b80d8
/external/llvm/lib/Transforms/Scalar/LoopIdiomRecognize.cpp
b7e9ef0ed1e246bd64d97a768555c8334c0d86e9 04-Jan-2011 Chris Lattner <sabre@nondot.org> restructure this a bit. Initialize the WeakVH with "I", the
instruction *after* the store. The store will always be deleted
if the transformation kicks in, so we'd do an N^2 scan of every
loop block. Whoops.



git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@122805 91177308-0d34-0410-b5e6-96231b3b80d8
/external/llvm/lib/Transforms/Scalar/LoopIdiomRecognize.cpp
7c90b90f4e9b0c421f0e45d7de03f6edce113a90 04-Jan-2011 Chris Lattner <sabre@nondot.org> use the very-handy getTruncateOrZeroExtend helper function, and
stop setting NSW: signed overflow is possible. Thanks to Dan
for pointing these out.



git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@122790 91177308-0d34-0410-b5e6-96231b3b80d8
/external/llvm/lib/Transforms/Scalar/LoopIdiomRecognize.cpp
6f96b275b62529c341168d516c290189bf408a7c 04-Jan-2011 Owen Anderson <resistor@mac.com> Fix comment.


git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@122788 91177308-0d34-0410-b5e6-96231b3b80d8
/external/llvm/lib/Transforms/Scalar/LoopIdiomRecognize.cpp
d957c717918c412402157b85fc51b4c6d2631381 03-Jan-2011 Chris Lattner <sabre@nondot.org> reduce redundancy in the hashing code and other misc cleanups.


git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@122720 91177308-0d34-0410-b5e6-96231b3b80d8
/external/llvm/lib/Transforms/Scalar/LoopIdiomRecognize.cpp
91139ccd995149dd0d5e4ab3604d9239e1f90a54 03-Jan-2011 Chris Lattner <sabre@nondot.org> add DEBUG and -stats output to earlycse.
Teach it to CSE the rest of the non-side-effecting instructions.



git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@122716 91177308-0d34-0410-b5e6-96231b3b80d8
/external/llvm/lib/Transforms/Scalar/LoopIdiomRecognize.cpp
63f9c3c49ac7011e6366fbec42716f3f70f1beee 02-Jan-2011 Chris Lattner <sabre@nondot.org> fix a miscompilation of tramp3d-v4: when forming a memcpy, we have to make
sure that the loop we're promoting into a memcpy doesn't mutate the input
of the memcpy. Before we were just checking that the dest of the memcpy
wasn't mod/ref'd by the loop.


git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@122712 91177308-0d34-0410-b5e6-96231b3b80d8
/external/llvm/lib/Transforms/Scalar/LoopIdiomRecognize.cpp
8e08e73f0e12c9e669f2d7d0a5c9213df3046c01 02-Jan-2011 Chris Lattner <sabre@nondot.org> If a loop iterates exactly once (has backedge count = 0) then don't
mess with it. We'd rather peel/unroll it than convert all of its
stores into memsets.


git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@122711 91177308-0d34-0410-b5e6-96231b3b80d8
/external/llvm/lib/Transforms/Scalar/LoopIdiomRecognize.cpp
62c50fdf69064c0d086aedfadb6ceb7c303bbcb9 02-Jan-2011 Chris Lattner <sabre@nondot.org> enhance loop idiom recognition to scan *all* unconditionally executed
blocks in a loop, instead of just the header block. This makes it more
aggressive, able to handle Duncan's Ada examples.


git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@122704 91177308-0d34-0410-b5e6-96231b3b80d8
/external/llvm/lib/Transforms/Scalar/LoopIdiomRecognize.cpp
bdce5720ad878259544e6a4e3621dac32cf2d134 02-Jan-2011 Chris Lattner <sabre@nondot.org> add a list of opportunities for future improvement.


git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@122701 91177308-0d34-0410-b5e6-96231b3b80d8
/external/llvm/lib/Transforms/Scalar/LoopIdiomRecognize.cpp
cf078f2b20899a3a19fb2044cc08dff409f13276 02-Jan-2011 Chris Lattner <sabre@nondot.org> Allow loop-idiom to run on multiple BB loops, but still only scan the loop
header for now for memset/memcpy opportunities. It turns out that loop-rotate
is successfully rotating loops, but *DOESN'T MERGE THE BLOCKS*, turning "for
loops" into 2 basic block loops that loop-idiom was ignoring.

With this fix, we form many *many* more memcpy and memsets than before, including
on the "history" loops in the viterbi benchmark, which look like this:

for (j=0; j<MAX_history; ++j) {
history_new[i][j+1] = history[2*i][j];
}

Transforming these loops into memcpy's speeds up the viterbi benchmark from
11.98s to 3.55s on my machine. Woo.



git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@122685 91177308-0d34-0410-b5e6-96231b3b80d8
/external/llvm/lib/Transforms/Scalar/LoopIdiomRecognize.cpp
6b04160dd8f306b8384fd98524f7ea1511798da6 02-Jan-2011 Chris Lattner <sabre@nondot.org> remove debugging code.


git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@122683 91177308-0d34-0410-b5e6-96231b3b80d8
/external/llvm/lib/Transforms/Scalar/LoopIdiomRecognize.cpp
4ce31fb57412b16cd61337ba41c60112dfbecfb6 02-Jan-2011 Chris Lattner <sabre@nondot.org> add some -stats output.


git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@122682 91177308-0d34-0410-b5e6-96231b3b80d8
/external/llvm/lib/Transforms/Scalar/LoopIdiomRecognize.cpp
e2c43920919c6fe376613d1d8331897dc1ba3d57 02-Jan-2011 Chris Lattner <sabre@nondot.org> teach loop idiom recognition to form memcpy's from simple loops.


git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@122678 91177308-0d34-0410-b5e6-96231b3b80d8
/external/llvm/lib/Transforms/Scalar/LoopIdiomRecognize.cpp
bafa117e8f2e3532f391227ebc9d4513b17edbad 01-Jan-2011 Chris Lattner <sabre@nondot.org> add a validity check that was missed, fixing a crash on the
new testcase.


git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@122662 91177308-0d34-0410-b5e6-96231b3b80d8
/external/llvm/lib/Transforms/Scalar/LoopIdiomRecognize.cpp
a64cbf067d6315522d13b606774bbadb4e328d1b 01-Jan-2011 Chris Lattner <sabre@nondot.org> improve validity check to handle constant-trip-count loops more
aggressively. In practice, this doesn't help anything though,
see the todo.


git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@122660 91177308-0d34-0410-b5e6-96231b3b80d8
/external/llvm/lib/Transforms/Scalar/LoopIdiomRecognize.cpp
30980b68151a1c1527306aa0f39e3b297af05583 01-Jan-2011 Chris Lattner <sabre@nondot.org> implement the "no aliasing accesses in loop" safety check. This pass
should be correct now.


git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@122659 91177308-0d34-0410-b5e6-96231b3b80d8
/external/llvm/lib/Transforms/Scalar/LoopIdiomRecognize.cpp
95ae676bc89b4cb9166576b74f1220ab5b0ff0ad 28-Dec-2010 Chris Lattner <sabre@nondot.org> simplify this, isBytewiseValue handles the extra check. We still
check for "multiple of a byte" in size to make it clear that the
>> 3 below is safe.


git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@122604 91177308-0d34-0410-b5e6-96231b3b80d8
/external/llvm/lib/Transforms/Scalar/LoopIdiomRecognize.cpp
7922d34b6073712cb62f7d4d74810509c19a84df 28-Dec-2010 Duncan Sands <baldrick@free.fr> Silence gcc warning about an unused variable when doing a release build.


git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@122593 91177308-0d34-0410-b5e6-96231b3b80d8
/external/llvm/lib/Transforms/Scalar/LoopIdiomRecognize.cpp
2e12f1ac6ebd49e5c41b7e9dcd802f3df40a1bc7 27-Dec-2010 Chris Lattner <sabre@nondot.org> fix some issues Frits noticed, add AliasAnalysis as a dependency


git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@122585 91177308-0d34-0410-b5e6-96231b3b80d8
/external/llvm/lib/Transforms/Scalar/LoopIdiomRecognize.cpp
9f39188def2b4102817945522fac1209083efa06 27-Dec-2010 Chris Lattner <sabre@nondot.org> have loop-idiom nuke instructions that feed stores that get removed.


git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@122574 91177308-0d34-0410-b5e6-96231b3b80d8
/external/llvm/lib/Transforms/Scalar/LoopIdiomRecognize.cpp
a92ff91a967c63a2395a34c9e8331a7d50d6ab10 27-Dec-2010 Chris Lattner <sabre@nondot.org> implement enough of the memset inference algorithm to recognize and insert
memsets. This is still missing one important validity check, but this is enough
to compile stuff like this:

void test0(std::vector<char> &X) {
for (std::vector<char>::iterator I = X.begin(), E = X.end(); I != E; ++I)
*I = 0;
}

void test1(std::vector<int> &X) {
for (long i = 0, e = X.size(); i != e; ++i)
X[i] = 0x01010101;
}

With:
$ clang t.cpp -S -o - -O2 -emit-llvm | opt -loop-idiom | opt -O3 | llc

to:

__Z5test0RSt6vectorIcSaIcEE: ## @_Z5test0RSt6vectorIcSaIcEE
## BB#0: ## %entry
subq $8, %rsp
movq (%rdi), %rax
movq 8(%rdi), %rsi
cmpq %rsi, %rax
je LBB0_2
## BB#1: ## %bb.nph
subq %rax, %rsi
movq %rax, %rdi
callq ___bzero
LBB0_2: ## %for.end
addq $8, %rsp
ret
...
__Z5test1RSt6vectorIiSaIiEE: ## @_Z5test1RSt6vectorIiSaIiEE
## BB#0: ## %entry
subq $8, %rsp
movq (%rdi), %rax
movq 8(%rdi), %rdx
subq %rax, %rdx
cmpq $4, %rdx
jb LBB1_2
## BB#1: ## %for.body.preheader
andq $-4, %rdx
movl $1, %esi
movq %rax, %rdi
callq _memset
LBB1_2: ## %for.end
addq $8, %rsp
ret



git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@122573 91177308-0d34-0410-b5e6-96231b3b80d8
/external/llvm/lib/Transforms/Scalar/LoopIdiomRecognize.cpp
22920b59864cac3b62d158fd4111cfda3c09c67a 26-Dec-2010 Chris Lattner <sabre@nondot.org> sketch more of this out.


git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@122567 91177308-0d34-0410-b5e6-96231b3b80d8
/external/llvm/lib/Transforms/Scalar/LoopIdiomRecognize.cpp
e6bb649ec63059d795a31198c3c569c137e7ad59 26-Dec-2010 Chris Lattner <sabre@nondot.org> actually add the file...


git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@122563 91177308-0d34-0410-b5e6-96231b3b80d8
/external/llvm/lib/Transforms/Scalar/LoopIdiomRecognize.cpp