[Modules] Move the ConstantRange class into the IR library. This is
a bit surprising, as the class is almost entirely abstracted away from
any particular IR, however it encodes the comparsion predica

[Modules] Move the ConstantRange class into the IR library. This is
a bit surprising, as the class is almost entirely abstracted away from
any particular IR, however it encodes the comparsion predicates which
mutate ranges as ICmp predicate codes. This is reasonable as they're
used for both instructions and constants. Thus, it belongs in the IR
library with instructions and constants.

llvm-svn: 202838

show more ...

[Modules] Move GetElementPtrTypeIterator into the IR library. As its
name might indicate, it is an iterator over the types in an instruction
in the IR.... You see where this is going.

Another step o

[Modules] Move GetElementPtrTypeIterator into the IR library. As its
name might indicate, it is an iterator over the types in an instruction
in the IR.... You see where this is going.

Another step of modularizing the support library.

llvm-svn: 202815

show more ...

[Modules] Move InstIterator out of the Support library, where it had no
business.

This header includes Function and BasicBlock and directly uses the
interfaces of both classes. It has to do with the

[Modules] Move InstIterator out of the Support library, where it had no
business.

This header includes Function and BasicBlock and directly uses the
interfaces of both classes. It has to do with the IR, it even has that
in the name. =] Put it in the library it belongs to.

This is one step toward making LLVM's Support library survive a C++
modules bootstrap.

llvm-svn: 202814

show more ...

[C++11] Replace llvm::next and llvm::prior with std::next and std::prev.

Remove the old functions.

llvm-svn: 202636

Make DataLayout a plain object, not a pass.

Instead, have a DataLayoutPass that holds one. This will allow parts of LLVM
don't don't handle passes to also use DataLayout.

llvm-svn: 202168

fix a corner case in delinearization

handle special cases Step==1, Step==-1, GCD==1, and GCD==-1

llvm-svn: 201868

Rename some member variables from TD to DL.

TargetData was renamed DataLayout back in r165242.

llvm-svn: 201581

SCEV: Cast switched values to make -Wswitch more useful.

llvm-svn: 201170

ScalarEvolution: Analyze trip count of loops with a switch guarding the exit.

llvm-svn: 201159

Fix crasher introduced in r200203 and caught by a libc++ buildbot. Don't assume that getMulExpr returns a SCEVMulExpr, it may have simplified it to something else!

llvm-svn: 200210

Teach SCEV to handle more cases of 'and X, CST', specifically where CST is any number of contiguous 1 bits in a row, with any number of leading and trailing 0 bits.

Unfortunately, this in turn led t

Teach SCEV to handle more cases of 'and X, CST', specifically where CST is any number of contiguous 1 bits in a row, with any number of leading and trailing 0 bits.

Unfortunately, this in turn led to some lower quality SCEVs due to some different paths through expression simplification, so add getUDivExactExpr and use it. This fixes all instances of the problems that I found, but we can make that function smarter as necessary.

Merge test "xor-and.ll" into "and-xor.ll" since I needed to update it anyways. Test 'nsw-offset.ll' analyzes a little deeper, %n now gets a scev in terms of %no instead of a SCEVUnknown.

llvm-svn: 200203

show more ...

Fix known typos

Sweep the codebase for common typos. Includes some changes to visible function
names that were misspelt.

llvm-svn: 200018

Fix PR18449: SCEV needs more precise max BECount for multi-exit loop.

llvm-svn: 199299

[PM] Split DominatorTree into a concrete analysis result object which
can be used by both the new pass manager and the old.

This removes it from any of the virtual mess of the pass interfaces and
le

[PM] Split DominatorTree into a concrete analysis result object which
can be used by both the new pass manager and the old.

This removes it from any of the virtual mess of the pass interfaces and
lets it derive cleanly from the DominatorTreeBase<> template. In turn,
tons of boilerplate interface can be nuked and it turns into a very
straightforward extension of the base DominatorTree interface.

The old analysis pass is now a simple wrapper. The names and style of
this split should match the split between CallGraph and
CallGraphWrapperPass. All of the users of DominatorTree have been
updated to match using many of the same tricks as with CallGraph. The
goal is that the common type remains the resulting DominatorTree rather
than the pass. This will make subsequent work toward the new pass
manager significantly easier.

Also in numerous places things became cleaner because I switched from
re-running the pass (!!! mid way through some other passes run!!!) to
directly recomputing the domtree.

llvm-svn: 199104

show more ...

[cleanup] Move the Dominators.h and Verifier.h headers into the IR
directory. These passes are already defined in the IR library, and it
doesn't make any sense to have the headers in Analysis.

Long

[cleanup] Move the Dominators.h and Verifier.h headers into the IR
directory. These passes are already defined in the IR library, and it
doesn't make any sense to have the headers in Analysis.

Long term, I think there is going to be a much better way to divide
these matters. The dominators code should be fully separated into the
abstract graph algorithm and have that put in Support where it becomes
obvious that evn Clang's CFGBlock's can use it. Then the verifier can
manually construct dominance information from the Support-driven
interface while the Analysis library can provide a pass which both
caches, reconstructs, and supports a nice update API.

But those are very long term, and so I don't want to leave the really
confusing structure until that day arrives.

llvm-svn: 199082

show more ...

Fixed old typo in ScalarEvolution, that caused wrong SCEVs zext operation.
Detailed description is here:
http://llvm.org/bugs/show_bug.cgi?id=18000#c16

For participation in bugfix process special th

Fixed old typo in ScalarEvolution, that caused wrong SCEVs zext operation.
Detailed description is here:
http://llvm.org/bugs/show_bug.cgi?id=18000#c16

For participation in bugfix process special thanks to David Wiberg.

llvm-svn: 198863

show more ...

Put the functionality for printing a value to a raw_ostream as an
operand into the Value interface just like the core print method is.
That gives a more conistent organization to the IR printing inte

Put the functionality for printing a value to a raw_ostream as an
operand into the Value interface just like the core print method is.
That gives a more conistent organization to the IR printing interfaces
-- they are all attached to the IR objects themselves. Also, update all
the users.

This removes the 'Writer.h' header which contained only a single function
declaration.

llvm-svn: 198836

show more ...

Move the LLVM IR asm writer header files into the IR directory, as they
are part of the core IR library in order to support dumping and other
basic functionality.

Rename the 'Assembly' include direc

Move the LLVM IR asm writer header files into the IR directory, as they
are part of the core IR library in order to support dumping and other
basic functionality.

Rename the 'Assembly' include directory to 'AsmParser' to match the
library name and the only functionality left their -- printing has been
in the core IR library for quite some time.

Update all of the #includes to match.

All of this started because I wanted to have the layering in good shape
before I started adding support for printing LLVM IR using the new pass
infrastructure, and commandline support for the new pass infrastructure.

llvm-svn: 198688

show more ...

Annotate APInt methods where it's not clear whether they are in place with warn_unused_result.

Fix ScalarEvolution bugs uncovered by this.

llvm-svn: 194928

add more comments around the delinearization of arrays

llvm-svn: 194612

delinearization of arrays

llvm-svn: 194527

Change data structure to memorize computed result in ScalarEvolution

Replace std::map with SmallVector to memorize the cached result since SCEV usually belongs to little Loop/BB
Linear scan on Small

Change data structure to memorize computed result in ScalarEvolution

Replace std::map with SmallVector to memorize the cached result since SCEV usually belongs to little Loop/BB
Linear scan on SmallVector is faster than std::map.

Code reviewer : Andrew Trick.
Test result : Pass Unit Test & LLVM Test Suite

401.bzip2 0.425721 0.419981 101.37%
403.gcc 24.53855 24.2667 101.12%
429.mcf 0.060847 0.059944 101.51%
433.milc 0.646009 0.636119 101.55%
444.namd 1.383928 1.370614 100.97%
445.gobmk 5.836575 5.800225 100.63%
450.soplex 1.911257 1.895963 100.81%
456.hmmer 1.039565 1.032534 100.68%
458.sjeng 0.897401 0.885567 101.34%
464.h264ref 3.645908 3.577991 101.90%
470.lbm 0.049456 0.048398 102.19%
471.omnetpp 5.638575 5.60435 100.61%
bitmnp01 0.045738 0.045291 100.99%
cjpegv2data 0.304359 0.302833 100.50%
idctrn01 0.046433 0.045763 101.46%
quake2 4.534416 4.4952 100.87%
quake 2.688566 2.659208 101.10%
xcsoar 12.42545 12.30385 100.99%
linpack 0.038739 0.03803 101.86%
matrix01 0.053564 0.0528 101.45%
nbench 0.402867 0.395803 101.78%
tblook01 0.021265 0.021015 101.19%
ttsprk01 0.066384 0.065566 101.25%

llvm-svn: 194459

show more ...

Rewrite SCEV's backedge taken count computation.

Patch by Michele Scandale!

Rewrite of the functions used to compute the backedge taken count of a
loop on LT and GT comparisons.

I decided to split

Rewrite SCEV's backedge taken count computation.

Patch by Michele Scandale!

Rewrite of the functions used to compute the backedge taken count of a
loop on LT and GT comparisons.

I decided to split the handling of LT and GT cases becasue the trick
"a > b == -a < -b" in some cases prevents the trip count computation
due to the multiplication by -1 on the two operands of the
comparison. This issue comes from the conservative computation of
value range of SCEVs: taking the negative SCEV of an expression that
have a small positive range (e.g. [0,31]), we would have a SCEV with a
fullset as value range.

Indeed, in the new rewritten function I tried to better handle the
maximum backedge taken count computation when MAX/MIN expression are
used to handle the cases where no entry guard is found.

Some test have been modified in order to check the new value correctly
(I manually check them and reasoning on possible overflow the new
values seem correct).

I finally added a new test case related to the multiplication by -1
issue on GT comparisons.

llvm-svn: 194116

show more ...

SCEV: Make the final add of an inbounds GEP nuw if we know that the index is positive.

We can't do this for the general case as saying a GEP with a negative index
doesn't have unsigned wrap isn't va

SCEV: Make the final add of an inbounds GEP nuw if we know that the index is positive.

We can't do this for the general case as saying a GEP with a negative index
doesn't have unsigned wrap isn't valid for negative indices.
%gep = getelementptr inbounds i32* %p, i64 -1

But an inbounds GEP cannot run past the end of address space. So we check for
the very common case of a positive index and make GEPs derived from that NUW.
Together with Andy's recent non-unit stride work this lets us analyze loops
like

void foo3(int *a, int *b) {
for (; a < b; a++) {}
}

PR12375, PR12376.

Differential Revision: http://llvm-reviews.chandlerc.com/D2033

llvm-svn: 193514

show more ...

Clarify SCEV comments.

We handle for(i=n; i>0; i -= s) by canonicalizing within SCEV to for(i=-n; i<0; i += s).

llvm-svn: 193147