Create an equivalence class of global variables that DSA will never be able
to tell apart anyway, and only track the leader for of these equivalence
classes in our graphs.

This dramatically reduces the number of GlobalValue*'s that appear in scalar
maps, which A) reduces memory usage, by eliminating many many scalarmap entries
and B) reduces time for operations that need to execute an operation for each
global in the scalar map.

As an example, this reduces the memory used to analyze 176.gcc from 1GB to
511MB, which (while it's still way too much) is better because it doesn't hit
swap anymore.  On eon, this shrinks the local graphs from 14MB to 6.8MB,
shrinks the bu+td graphs of povray from 50M to 40M, shrinks the TD graphs of
130.li from 8.8M to 3.6M, etc.

This change also speeds up DSA on large programs where this makes a big
difference.  For example, 130.li goes from 1.17s -> 0.56s, 134.perl goes
from 2.14 -> 0.93s, povray goes from 15.63s->7.99s (!!!).

This also apparently either fixes the problem that caused DSA to crash on
perlbmk and gcc, or it hides it, because DSA now works on these.  These
both take entirely too much time in the TD pass (147s for perl, 538s for
gcc, vs 7.67/5.9s in the bu pass for either one), but this is a known
problem that I'll deal with later.

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

Make each scalar map contain a reference to an equivalence class of global
variables.  Do not insert a global into the scalar map unless it is the
leader of its equivalence class.

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

Each DS collection now contains an equivalence class of globals values.

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

add a method to clear globals from a node

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

Two fixes for the copy ctor/operator=:
  1. Make sure to clear() 'this' before adding elements to it
  2. Make sure that the leaders of the RHS EC are the leaders of the LHS EC.

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

add some methods, fix a major bug in getLeader() that was causing things to
not be unified correctly.

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

implement a proper copy ctor, operator= and add a helper method.

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

Fix the 3 regressions last night, due to my buggy patch from yesterday.

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

Add new function getPtrPtrFromArrayPtr().

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

Stop using deprecated interface.

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

Switch to use the new interface for the EquivalenceClasses class, and fix
a bug involving SCC's who have multiple members that are part of an EC.

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

Rewrite this class, making the following improvements:

  1. It now actually uses tarjan's algorithm, so it is a efficient inverse
     ackerman's function for union operations, not linear time.
  2. It now stores one copy of the data in the set instead of two.
  3. It now works for elements other than pointers.
  4. It now has a more STL-like interface that exposes iterators instead
     of internal implementation details.

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

do not bother inlining nullary functions without return values.  The only
effect these calls can have is due to global variables, and these passes
all use the globals graph to capture their effect anyway.  This speeds up
the BU pass very slightly on perlbmk, reducing the number of dsnodes
allocated from 98913 to 96423.

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

fix a bogus assertion

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

another fastpath

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

remove use of getPrev() and getNext() on ilist nodes.

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

expose this pass to both opt and analyze

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

We shall have IA64 as a new experimental backend released with LLVM 1.5

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

remove a bogus optimization.  This only works if there are no globals in the
graph, and the combination of a function that does not reference globals, takes
not arguments and returns no value is pretty rare.

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

Rewrite DSAA::getModRefInfo to compute the mapping between caller and callee
to determine mod/ref behavior, instead of creating a *copy* of the caller
graph and inlining the callee graph into the copy.

This speeds up aa-eval on Ptrdist/yacr2 from 109.13s to 3.98s, and gives
identical results.  The speedup is similar on other programs.

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

implement a new method.

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

add 3 methods

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

Recognize an IA64 when we see one

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

add some possibly bogus assertions.

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

Do not include the Function* for direct call/invoke instructions in the
alias evaluation.  Clients really don't care.

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

typo/denial

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

simplify this function a bit, allow DS-AA to build on/improve the mod/ref
results returned by AA, not just use one or the other.

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

Clean up some code, handle null pointer specially to avoid an assertion

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

Two changes:
  1. Chain to the parent implementation of M/R analysis if we can't find
     any information.  It has some heuristics that often do well.
  2. Do not clear all flags, this can make invalid nodes by turning nodes
     that used to be collapsed into non-collapsed nodes (fixing crashes)

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

clean up warnings when building in release mode

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

now the angry bug reports have somewhere to go!

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

statically link ia64 into llc

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

OK, IA64 is statically linked into llc

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

build the IA64 target as a .so for now

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

dainty

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

and so it begins...

PHASE 1: write instruction selector
PHASE 2: ???
PHASE 3: profit!

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

Don't emit two comparisons when comparing a FP value against zero!

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

spiff up the nightly tester output one more notch

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

Fix the missing symbols problem Bill was hitting.  Patch contributed by
Bill Wendling!!

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

Do not create ridiculously huge DSNodes, as described in the comments.
This speeds up the BU pass on 172.mgrid from 62.3 -> 0.1242s.

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

Fix a bug where we would consider " .99" and "1.0" different because of the
leading whitespace.

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

remove compat_iterator, which is dead in the tree.

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

remove use of compat_iterator.

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

remove use of compat_iterator

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

Print out who commits and what files were modified at the bottom of the test summary log sent to llvm-commits.

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

Do #include HashExtras.h with VC++

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

Don't provide default hash struct instantiation.

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

Convert tabs to spaces

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

Add adapter class to let VC++ hash_map use GCC's hash struct.

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

Remove deleted files from VC++ project.

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

Fix grammar wrt apostrophe's

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

Convert tabs to spaces

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

fix some 80 column violations
Add support for programs that define main in a .a file, such as f2c'd programs.

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

consolidate LinkFiles into LinkItems, use lib_* iterators.

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

consolidate LinkLibraries into LinkItems

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

make sure to mark nodes in the globals graph incomplete after computing it
so that external globals (and whatever they point to) are marked incomplete.

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

fix crashes when we only have a prototype for main.

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

Fix a crash that happens when mapping something like this:

 { short, short }

to
  short

where the second short maps onto the second field of the first struct.  In
this case, the struct index is not aligned, so we should avoid calling
getLink(2), which asserts out.

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

sure, I can set a flag, but if I never check it, why bother setting it?  Should fix 20 programs :)

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

Make computeGGToGMapping compute an invnodemap

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

remove warning, make computeGGToGMapping return an invnodemap.

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

add support for hashing nodehandles.

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

Finally fix (the right way) the problem where functions like this:

void foo() {
  G = 1;
}

would have an empty DSGraph even though G (a global) is directly used
in the function.

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

Start using retnodes_* for iteration.

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

add iterators for return nodes list.

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

method renamed

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

Replace more a*'s with arg_*'s, thanks to Gabor Greif!

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

add missing copyright header

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

Stop using abegin and aend.

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

Stop using abegin.

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

Use arg_iterator and arg_begin and arg_end functions.

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

Add EquivClassGraphs.cpp to VC++ project.

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

avoid varialbe name collisions

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

Do it right...

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

Fix VC++ breakage.

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

stop using method.

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

methods removed.

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

remove reverse BB iterators.

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

remove a whole bunch of dead methods.  Noone should use reverse iterators anyway.

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

stop using arg_front

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

stop using arg_back

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

This mega patch converts us from using Function::a{iterator|begin|end} to
using Function::arg_{iterator|begin|end}.  Likewise Module::g* -> Module::global_*.

This patch is contributed by Gabor Greif, thanks!

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

switch from a* to arg_* and g* to global_* for argument/global var iterators

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

Don't crash if computing a mapping to a node with zero size

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

rename method, add counterpart

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

Rename method, add counterpart.

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

Remove the reverse iterators for arguments and global vars.
Rename argument iterators arg_* instead of a*
Remove global variable iterators global_* instead of g*.

Keep the old names for temporary compatibility.

Patch contributed by Gabor Greif!

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

FP 0.0 setcc optimization, and generate short branch sequence for setcc(FP) rather than stack usage

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

add a method to compute a commonly used mapping.

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

Add a useful method.

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

regardless of whether or not the client things we should mark globals incomplete,
ALWAYS mark them incomplete if they are external!

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

Make sure to remove incomplete markers before we add to them! :)

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

The incoming arguments to main (the argv list) are not complete!

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

After finishing BU analysis, move all global variables from the globals
graph into main and mark them complete.

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

ADd support for printing eqgraphs.

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

Add support for printing EQ graphs

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

Replace linear search with logrithmic one.

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

add a StructLayout::getElementContainingOffset method.

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

add a helper method

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

Should fix mesa

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