Add new Loop::hasExitBlock helper method

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@5663 91177308-0d34-0410-b5e6-96231b3b80d8

Simplify a bit by using a new member function

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@5662 91177308-0d34-0410-b5e6-96231b3b80d8

Change behavior of changeExitBlock function to replace all instances of exit block

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@5661 91177308-0d34-0410-b5e6-96231b3b80d8

New testcase

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@5660 91177308-0d34-0410-b5e6-96231b3b80d8

Add a new assertion to check that stuff is happening right
Ironically the exit block modification code wasn't updating the exit block
information itself.  Fix this.

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@5659 91177308-0d34-0410-b5e6-96231b3b80d8

Fix bug: 2003-02-27-StoreSinkPHIs.ll

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@5658 91177308-0d34-0410-b5e6-96231b3b80d8

New testcase

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@5657 91177308-0d34-0410-b5e6-96231b3b80d8

Fix bug: LICM/2003-02-27-PreheaderProblem.ll
There may be a single outside predecessor and
still need a new loop-preheader if the predecessor has multiple
successors.

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@5656 91177308-0d34-0410-b5e6-96231b3b80d8

  * Don't forget to update Loop information!
  * Remove bogus assertion: there may be a single outside predecessor and
    still need a new loop-preheader if the predecessor has multiple
    successors.  See bug: LICM/2003-02-27-PreheaderProblem.ll

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@5655 91177308-0d34-0410-b5e6-96231b3b80d8

Testcase for Preheaders problem

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@5654 91177308-0d34-0410-b5e6-96231b3b80d8

Replace assertion with a handler.

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@5653 91177308-0d34-0410-b5e6-96231b3b80d8

 * Significant changes to the preheader insertion pass:
   - Now we perform loop exit-block splitting to ensure exit blocks are
     always dominated by the loop header.
   - We now preserve dominance frontier information
   - This fixes bug: LICM/2003-02-26-LoopExitNotDominated.ll

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@5652 91177308-0d34-0410-b5e6-96231b3b80d8

Make the interface to update a little more efficient

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@5651 91177308-0d34-0410-b5e6-96231b3b80d8

  - LoopInfo now calculates and tracks loop exit blocks

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@5650 91177308-0d34-0410-b5e6-96231b3b80d8

  * LoopInfo now keeps track of exit blocks from the loop
  * New LoopInfo::isLoopHeader method
  * Remove some #if 0 code

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@5649 91177308-0d34-0410-b5e6-96231b3b80d8

New testcase crashing LICM

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@5648 91177308-0d34-0410-b5e6-96231b3b80d8

Make the aliassettracker much more precise by actually tracking size
information for various accesses.  What a concept.

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@5647 91177308-0d34-0410-b5e6-96231b3b80d8

Fix test

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@5646 91177308-0d34-0410-b5e6-96231b3b80d8

Fix bug: BasicAA/2003-02-26-AccessSizeTest.ll

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@5645 91177308-0d34-0410-b5e6-96231b3b80d8

New testcase for size tracking brokenness

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@5644 91177308-0d34-0410-b5e6-96231b3b80d8

Fix several bugs in basic-aa

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@5643 91177308-0d34-0410-b5e6-96231b3b80d8

Rename -no-* to -disable-*

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@5642 91177308-0d34-0410-b5e6-96231b3b80d8

Add new -no-aa implementation

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@5641 91177308-0d34-0410-b5e6-96231b3b80d8

Move BasicAA pass out to it's own header file

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@5640 91177308-0d34-0410-b5e6-96231b3b80d8

BasicAA doesn't need a public header

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@5639 91177308-0d34-0410-b5e6-96231b3b80d8

Adjust to implement new AA interface

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@5638 91177308-0d34-0410-b5e6-96231b3b80d8

Adjust to new AA interface

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@5637 91177308-0d34-0410-b5e6-96231b3b80d8

Convert to work with new AliasAnalysis interface by conservatively assuming all pointers are arbitrarily large accesses

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@5636 91177308-0d34-0410-b5e6-96231b3b80d8

Calculate and pass load sizes to the alias analysis infrastructure

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@5635 91177308-0d34-0410-b5e6-96231b3b80d8

Adjust to new AA interface
Add tracking for Mod/Ref info

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@5634 91177308-0d34-0410-b5e6-96231b3b80d8

  - Checkin of the alias analysis work:
    * Takes into account the size of the memory reference to determine aliasing.
    * Expose mod/ref information in a more consistent way
    * BasicAA can now disambiguate A[i][1] and A[j][2] for conservative request
      sizes

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@5633 91177308-0d34-0410-b5e6-96231b3b80d8

Tweak to work with new AA implementation

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@5632 91177308-0d34-0410-b5e6-96231b3b80d8

Checkin of new alias analysis interface:
  * Takes into account the size of the memory reference to determine aliasing.
  * Expose mod/ref information in a more consistent way

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@5631 91177308-0d34-0410-b5e6-96231b3b80d8

Allow ImmutablePass's to require other immutable passes and to be initialized

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@5630 91177308-0d34-0410-b5e6-96231b3b80d8

* Un "protect" the getAnalysis<> functions
* Add a new initializePass() method to ImmutablePass

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@5629 91177308-0d34-0410-b5e6-96231b3b80d8

Remove implemented projects

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@5628 91177308-0d34-0410-b5e6-96231b3b80d8

Update programmers manual for renamed method

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@5627 91177308-0d34-0410-b5e6-96231b3b80d8

Hopefully final tweak to this testcase

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@5626 91177308-0d34-0410-b5e6-96231b3b80d8

Add a new test for basicaa

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@5625 91177308-0d34-0410-b5e6-96231b3b80d8

Fix typeo

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@5624 91177308-0d34-0410-b5e6-96231b3b80d8

Remove wierd case that can never happen

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@5623 91177308-0d34-0410-b5e6-96231b3b80d8

Add new helper template function

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@5622 91177308-0d34-0410-b5e6-96231b3b80d8

Fix testcase

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@5621 91177308-0d34-0410-b5e6-96231b3b80d8

Rename Instruction::hasSideEffects() -> mayWriteToMemory()

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@5620 91177308-0d34-0410-b5e6-96231b3b80d8

This is a substantial rewrite of the AliasSetTracker class which now uses
a union-find based algorithm, is significantly faster, and is more general.
It will also scale to handle call instructions correctly, which is a nice
added bonus.

This includes a new pass -print-alias-sets which can be used to show how
alias sets are formed for a particular analysis.

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@5619 91177308-0d34-0410-b5e6-96231b3b80d8

Initial checkin of CallSite wrapper for Call/Invoke instructions

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@5618 91177308-0d34-0410-b5e6-96231b3b80d8

Fix test

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@5617 91177308-0d34-0410-b5e6-96231b3b80d8

Make printing messages nicer

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@5616 91177308-0d34-0410-b5e6-96231b3b80d8

Fix #endif

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@5615 91177308-0d34-0410-b5e6-96231b3b80d8

Add support for the slist extension

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@5614 91177308-0d34-0410-b5e6-96231b3b80d8

Initial implementation of Loop invariant memory->scalar promotion

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@5613 91177308-0d34-0410-b5e6-96231b3b80d8

Tweak testcase

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@5612 91177308-0d34-0410-b5e6-96231b3b80d8

New testcase for scalar promotion

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@5611 91177308-0d34-0410-b5e6-96231b3b80d8

Split mem2reg promotion into two parts: a function which does the work, and
a pass which wraps the function.  This allows other passes to use the functionality

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@5610 91177308-0d34-0410-b5e6-96231b3b80d8

Add a new interface file for the PromoteMemToReg interface in the Utils library

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@5609 91177308-0d34-0410-b5e6-96231b3b80d8

Clean up std namespace references

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@5608 91177308-0d34-0410-b5e6-96231b3b80d8

New testcase to check to see if LICM is performing scalar promotion

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@5607 91177308-0d34-0410-b5e6-96231b3b80d8

Dramatically simplify building of natural loops and fix a bug where the BBMap
was not correctly computed.

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@5606 91177308-0d34-0410-b5e6-96231b3b80d8

Fix the requisite bug that I introduced

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@5605 91177308-0d34-0410-b5e6-96231b3b80d8

Fix 80 character formatting

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@5604 91177308-0d34-0410-b5e6-96231b3b80d8

Fix bug: 2003-02-19-LoopInfoNestingBug.ll

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@5603 91177308-0d34-0410-b5e6-96231b3b80d8

Add a testcase for broken loopinfo

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@5602 91177308-0d34-0410-b5e6-96231b3b80d8

Make tests rerun if analyze is rebuilt

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@5601 91177308-0d34-0410-b5e6-96231b3b80d8

Fix warnings compiling C files

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@5600 91177308-0d34-0410-b5e6-96231b3b80d8

Remove support for memset

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@5599 91177308-0d34-0410-b5e6-96231b3b80d8

Add lots of functions

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@5598 91177308-0d34-0410-b5e6-96231b3b80d8

4 new transformations:
  * X*C + X --> X * (C+1)
  * X + X*C --> X * (C+1)
  * X - X*C --> X * (1-C)
  * X*C - X --> X * (C-1)

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@5592 91177308-0d34-0410-b5e6-96231b3b80d8

Add new testcases

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@5591 91177308-0d34-0410-b5e6-96231b3b80d8

Modernize testcase

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@5590 91177308-0d34-0410-b5e6-96231b3b80d8

Modernize testcases

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@5589 91177308-0d34-0410-b5e6-96231b3b80d8

test for a variety of new transformations:
  * A & ~A == 0
  * A / (2^c) == A >> c  if unsigned
  * 0 / A == 0
  * 1.0 * A == A
  * A * (2^c) == A << c
  * A ^ ~A == -1
  * A | ~A == -1
  * 0 % X = 0
  * A % (2^c) == A & (c-1) if unsigned
  * A - (A & B) == A & ~B
  * -1 - A == ~A

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@5588 91177308-0d34-0410-b5e6-96231b3b80d8

Add a variety of new transformations:
  * A & ~A == 0
  * A / (2^c) == A >> c  if unsigned
  * 0 / A == 0
  * 1.0 * A == A
  * A * (2^c) == A << c
  * A ^ ~A == -1
  * A | ~A == -1
  * 0 % X = 0
  * A % (2^c) == A & (c-1) if unsigned
  * A - (A & B) == A & ~B
  * -1 - A == ~A

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@5587 91177308-0d34-0410-b5e6-96231b3b80d8

modernize testcase

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@5586 91177308-0d34-0410-b5e6-96231b3b80d8

Modernize testcase

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@5585 91177308-0d34-0410-b5e6-96231b3b80d8

Fix resolution of indirect function calls... whoops

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@5576 91177308-0d34-0410-b5e6-96231b3b80d8

Changes to runtime framework

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@5572 91177308-0d34-0410-b5e6-96231b3b80d8

Mark function edges

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@5571 91177308-0d34-0410-b5e6-96231b3b80d8

Fix a bug that cause a crash resolving questionable function calls

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@5567 91177308-0d34-0410-b5e6-96231b3b80d8

- Eliminate provably non-pointer nodes from graphs.

This helps a lot of testcases, for example:
            New Time  New #Nodes     Old Time    Old #Nodes
254.gap:    91.1024     21605        91.1397     22657
povray31:    2.7807      8613         3.0152     10338
255.vortex:  1.2034      8153         1.2172     8822
moria:        .6756      3150          .7054     3877
300.twolf:    .1652      2010          .1851     3270

Typically, testcases which use long and ulong integers a lot get better, f.e. povray above.

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@5566 91177308-0d34-0410-b5e6-96231b3b80d8

Fix a misunderstanding of the standard associative containers

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@5565 91177308-0d34-0410-b5e6-96231b3b80d8

Don't put integer pointers (longs) into the scalar map.
This speeds stuff up by 10% on some tests, woot!

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@5564 91177308-0d34-0410-b5e6-96231b3b80d8

Clarify the Makefile.config settings

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@5563 91177308-0d34-0410-b5e6-96231b3b80d8

Fix bug: LevelRaise/2003-02-13-CallRaise.ll

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@5562 91177308-0d34-0410-b5e6-96231b3b80d8

New testcase distilled from LARN

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@5561 91177308-0d34-0410-b5e6-96231b3b80d8

Hax0r around a deficiency in the Pass infrastructure

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@5555 91177308-0d34-0410-b5e6-96231b3b80d8

Use the new tailclip property new added to graphviz CVS to make call nodes
actually intelligable

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@5554 91177308-0d34-0410-b5e6-96231b3b80d8

This speeds up processing LLVM a _lot_, 17% in the case of loading and destroying "vortex"

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@5553 91177308-0d34-0410-b5e6-96231b3b80d8

Move node forwarding code from being inlined to being out-of-line.

This brings a 11.6% speedup to steens, and a 3.6 overall speedup to ds-aa

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@5552 91177308-0d34-0410-b5e6-96231b3b80d8

Fix profile builds

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@5551 91177308-0d34-0410-b5e6-96231b3b80d8

Make more compatible with GCC 2.96

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@5550 91177308-0d34-0410-b5e6-96231b3b80d8

Remove gunk that was supposed to make space evaluation more precise, but never worked.

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@5549 91177308-0d34-0410-b5e6-96231b3b80d8

New testcase, for something we may never really want to support :)

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@5548 91177308-0d34-0410-b5e6-96231b3b80d8

Add -fomit-frame-pointer when optimizing

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@5547 91177308-0d34-0410-b5e6-96231b3b80d8

Fixed alloca declaration problem on sun.

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@5546 91177308-0d34-0410-b5e6-96231b3b80d8

Don't output times in "scientific" notation

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@5544 91177308-0d34-0410-b5e6-96231b3b80d8

Add new -no-verify option

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@5542 91177308-0d34-0410-b5e6-96231b3b80d8

Add a new -no-output option, useful for -aa-eval tests.

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@5541 91177308-0d34-0410-b5e6-96231b3b80d8

Implement more functions

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@5538 91177308-0d34-0410-b5e6-96231b3b80d8

Rename options

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@5537 91177308-0d34-0410-b5e6-96231b3b80d8

Implement a "union-findy" version of DS-Analysis, which eliminates the
Referrers list on DSNodes.

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@5536 91177308-0d34-0410-b5e6-96231b3b80d8