* Remove RemoveUnreachableShadowNodes & UnlinkUndistinguishableShadowNodes
  to reflect the fact that they actually operate on arbitrary nodes
* Clean up public interface of FunctionDSGraph
* add getEscapingAllocations & getNonEscapingAllocations

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

Ooops, I did such a great job pruning nodes, that I accidentally deleted
ALL allocation nodes... hrm... bad.

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

Add subdirs to makefile

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

Initial checkin of first regression test for mem2reg pass

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

Makefile change for IPO's that use the Datastructure analysis stuff

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

Initial checkin of Noop pass that will be the pool allocator

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

Add hook for pool allocation pass

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

New file for new pass

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

Checking for Cameron

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

Many changes
* Simplify a lot of the inlining stuff.  There are still problems, but not
  many
* Break up the Function representation to have a vector for every different
  node type so it is fast to find nodes of a particular flavor.
* Do more intelligent merging of call values
* Allow elimination of unreachable shadow and allocation nodes
* Generalize indistinguishability testing to allow merging of identical calls.
* Increase shadow node merging power

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

* Define some operators on PointerVal and PVS's
* Nodes can determine whether they are foldable with another node
* Rename NewDSNode to AllocDSNode
* The Function graph breaks up all of the node types into individual
  vectors to alloc fast access when you are looking for a particular type
  of node.  Simplifies much code.

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

Rename constructor function for mem2reg pass.

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

* Move classes around
* rename constructor function
* Move stuff into anonymous namespaces

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

Rename constructor function

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

Implemented promote mem->reg pass.

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

* Add #define to enabled debug messages
* Move removeEdgesTo to be a member of DSNode
* Implement (but #ifdef out) the new, spiffier, method of determining
  shadow node equivalence.  This cannot be enabled until more is
  implemented.

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

* Implement DSNode::removeAllIncomingEdges
* Implement Critical Shadow node handling
* Implement routines to determine whether an allocation node is a malloc
  or alloca

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

* Add critical node support
* Optimize graph after building it.  This should be unneccesary in the future

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

* Destroy alloca nodes when a graph gets inlined
* Add links to all subtrees when a shadow node gets resolved
* Add critical node handling

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

* Add a nice utility method to DSNode
* Export interface to tell whether an alloc node represent a malloc or alloca
* Add the concept of a "critical" shadow node

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

* Optimizers return true on change
* Implement indistinguishable shadow node elimination

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

Fix long line

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

* Because of optimization, the shadow nodes between arguments might get
  removed.  Check to see if they are there.
* Repeat optimizations while changing

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

Allow isa<DSNode>(..)
Simplification routines return true on change

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

* Add support for DataStructure analysis
* Parameterize pass outputting with the printPass template, so analysis
  output can optionally take more arguments than just a stream.  The
  default output mode is just to use operator<< on the analysis.
* Remove CurrentModule hack, in favor of using printPass
* Remove special operator<<'s defined for FindUsedTypes and
  FindUnsafePointerTypes, in favor of printPass specializations
* Use std::cout instead of cout

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

Initial checkin of Datastructure analysis.

Has bugs, but shouldn't crash in theory.

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

New header file for datastructure analysis

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

Change from Method to Function

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

Change references from Method to Function
change references from MethodARgument to FunctionArgument

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

Convert to use new style casts instead of direct checking

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

change refs to Method to Function
Change references to MEthodArgument to FunctionArgument

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

Change uses of Method to Function
Change uses of methodArgument to FunctionArgument

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

Remove unneccesary forward declarations for classes

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

Transform uses of Method into uses of Function.
Rename MethodArgument to FunctionArgument
Fix some _really_ out of date comments

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

Allow clients to use FunctionType as well as MethodType for now

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

Make test more rigorous.  It was never reading the non-scalar variables
from memory!  Also, separate the writing and reading routines.

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

initialize sum variable

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

Refix bug: Add back method MachineCodeForInstruction::dropAllReferences.

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

Fix padding when allocating local variables on stack.

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

Add methods to support type inquiry.  Rename TmpInstruction values.

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

Moved to directory Scalar/ and renamed.

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

Destroy MethodLiveVarInfo after register allocation.

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

Use deterministic iterator for SchedGraphs.  This is actually not
useful right now when we only do local scheduling.

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

Bug fix: nextToTry was not being initialized in one case.

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

Add option to disable scheduling.

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

Add option to disable scheduling.
Destroy live-variable information after scheduling so it is
recomputed before later phases (e.g., reg. allocation).
Use deterministic iterator to enumerate sched graphs.

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

Minor changes.

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

Re-fix bug: Put back MachineCodeForInstruction::dropAllReferences.

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

Fix padding for variables allocated on stack.

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

Major overhaul to FoldGetElemPtr to handle mixed array and struct refs.

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

Use deterministic iterator for treeRoots.

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

Bug re-fix: put back MachineCodeForInstruction::get(*I).dropAllReferences().
Also re-enable instr. scheduling pass.

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

Change latencies for Load, Store and Branch instructions.

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

Major enhancements to how array and structure indices are handled.
Improve checking for constants in Multiply.
Simpler method to keep track of when a node is folded into its parent.
Several other bug fixes.

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

Change treeRoots data structure to make enumeration deterministic.
Also, add a flag to marked nodes that do not need code because they
have been folded into the user (parent in the BURG tree).

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

Change treeRoots data structure to make enumeration deterministic.

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

Major overhaul to support arbitrary mixed array and structure indices.
Also moved to the Scalar/ directory and renamed to "MultiDim".

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

Rename pass to DecomposeMultiDimRefs.

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

Fix out-of-date name.

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

Regression tests for DecomposeMultiDimRefs pass.

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

Rename Method to Function

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

Remove extranous forward decl

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

Remove unneccesary forward definitions

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

Add transition header file

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

Update documentation, rename Method to Function, move typedef to Value.h for now.

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

Change Method to Function

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

Add transition typedef to Function

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

New pass to convert Convert multi-dimensional
array references into 1-D references.

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

Moved to Scalar/ directory.

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

New pass to decompose multi-dimensional array references into
a sequence of 1-D references, using a sequence of getElementPtrs.

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

Remove compilation of __main because we now link -lgcc into programs

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

Add an assertion that would hopefully catch a problem that was tripping
cameron up

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

Fix bug test/Regression/Transforms/LevelRaise/2002-03-21-MissedRaise3.ll

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

New testcase

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

Fix test/Regression/Transforms/LevelRaise/2002-03-21-MissedRaise2.ll

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

New testcase

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

* AllocationInst ctor moved here from iMemory.h
* AllocationInst now always has an array size operand

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

* Make AllocationInst ctor protected
* Move AllocationInst ctor to iMemory.cpp
* AllocationInst's always have one operand, even if it is a uint 1

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

Rerun test if opt gets changed

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

Run all testcases

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

Build LevelRaise subdirectory

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

Add a debugging option to gccas to cause it to not do level raise or anything
after it.

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

Fix test/Regression/Other/2002-03-21-LevelRaiseMiss.ll

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

Testcase for a missed level raise opportunity

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

Make ConvertableToGEP handle cases where the user is indexing into the
first element of a structure type.  Before this would not be handled because
getStructOffset would either stop immediately (because StopEarly was true
and Offset = 0), or blast past the level we wanted.

Now ConvertableToGEP steps down through the type one level at a time, checking
the Offset and Scale conditions at each step

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

Implement the new InsertInstBeforeInst function

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

Fix the: test/Regression/Other/2002-03-20-LevelRaiseCrash.ll bug.  It turned
out that almost always the result of the add was the same as the GEP that
would be generated.  In this case, however, it wasn't, so bad things happened.

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

Fix bug in testcase

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

Declare the new InsertInstBeforeInst function

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

Remove a misguided API extension

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

New testcase for YALRB (yet another level raise bug)

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

Add an assertion to catch a misuse of replaceAllUsesWith

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

Checkin testcase that was just sitting in my tree.  Looks like backreferences
have some problem in the parser, oh joy.

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

1. Fix bug test/Regression/Other/2002-03-20-LevelRaiseBadCodegen.ll
2. Allow negative scales in ConvertableToGEP, so that this loop from
   alloc_tree in the Olden health benchmark is correctly raised:

       for (i = 3; i >= 0; i--)
         fval[i] = alloc_tree(level - 1, label*4 + i + 1, new);

   Stepping through the array backwards caused a negative scale.

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

Namespace qualify debugging code

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

New testcase

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

Allow implementation of all HANDLE_*_INST macros at once by defining HANDLE_INST

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

New pass to convert Convert multi-dimensional
array references into 1-D references.

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

Big bug fix: killed uses were being inserted instead of erased!
Also added a set of debug options.

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

Initial checkin of InstVisitor class

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