Handle post dominance correctly in the case where blocks do not have a path to
the exit node.

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

Fix a nasty problem with dominance calculation for unreachable blocks.
If we had a CFG that look like Entry -> B, Unreachable -> B, then we would
not correctly determine that Entry dominated B, because Entry did not
apparently dominate "unreachable".  This patch fixes this by making the entry
node dominate all blocks, including unreachable ones.

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

Prune function nodes that are no longer referenced due to inlining

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

sgefa uses truely huge data structures nodes.  Only print part of them if they
are so big

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

The wall clock timer (implementing using the RTC or cycle counter on x86) is
so much more accurate than the per process timers that we get better results
(less noise) by sorting according to wall time than process time.

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

Handle bug exposed by power benchmark

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

Add parens around constant calls to getelemptr to properly associate the reference

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

Reimplement/port the Bottom Up Closure pass

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

New testcase

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

DataStructure.h doesn't include DSGraph.h

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

Remove commented out stuff
DataStructure.h doesn't include DSGraph.h now

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

Move GlobalDSGraph class defn to the end of the file

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

This file doesn't need Pass.h

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

I was wrong on the removing of those references on the last commit.

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

* Implement the getc() function
* Support usage of stdin, stdout & stderr correctly in LLI!

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

Cleanup #includes, expose module

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

Expose TD to ExternalFunctions.cpp

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

  - Print the predecessors of a basic block instead of the number of uses of
    the block in the AsmWriter

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

Fix bug: 2002-10-02-SignExtensionProblem.ll

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

Removed unneeded reference and dereferences.

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

New testcase for a problem discovered in the SPECINT gzip benchmark.

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

Cleaned up my last check-in.

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

No longer include malloc.h.  If protoypes are needed for memory functions they will be present in the byte code and the generated c as well.

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

* Implement fully general merging of array subscripts on demand!  This
      does not handle the initial pointer index case yet though.

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

* Implement fully general merging of array subscripts on demand!  This
      does not handle the initial pointer index case yet though.

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

When printing DS nodes, print the mergemap index as well to allow easier
debugging of merging process.

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

Checkin the "meat" of the Data structure graph itself.  I forgot to check
this in before.  :(

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

* Significant rework of DSNode to support arbitrary aliasing due to merging
* Now all and any bytes of a DSNode can be merged together individually.  This
  is neccesary to support the full generality of C and support aliasing
  correctly.

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

  - Remove the User::eraseOperand method which is never used, really
    dangerous, and not something we want to expose.

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

Do some cleanups to the Type and Constant section to remove latex stuff

There is still a lot of cleanup and fleshing out required here, but at least
it gets rid of the flagrantly bad parts.

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

Temporary change to make datastructure stuff link in right

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

Changes to work with Statistics rework
    * Renamed StatisticReporter.h/cpp to Statistic.h/cpp
    * Broke constructor to take two const char * arguments instead of one, so
      that indendation can be taken care of automatically.
    * Sort the list by pass name when printing
    * Make sure to print all statistics as a group, instead of randomly when
      the statistics dtors are called.
    * Updated ProgrammersManual with new semantics.

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

Update manual to reflect recent changes in the Statistic class.

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

Updates to work with recent Statistic's changes:

    * Renamed StatisticReporter.h/cpp to Statistic.h/cpp
    * Broke constructor to take two const char * arguments instead of one, so
      that indendation can be taken care of automatically.
    * Sort the list by pass name when printing
    * Make sure to print all statistics as a group, instead of randomly when
      the statistics dtors are called.
    * Updated ProgrammersManual with new semantics.

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

Updates to work with recent Statistic's changes:
    * Renamed StatisticReporter.h/cpp to Statistic.h/cpp
    * Broke constructor to take two const char * arguments instead of one, so
      that indendation can be taken care of automatically.
    * Sort the list by pass name when printing
    * Make sure to print all statistics as a group, instead of randomly when
      the statistics dtors are called.
    * Updated ProgrammersManual with new semantics.

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

Build subdirs in parallel

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

  - Rework Statistics:
    * Renamed StatisticReporter.h/cpp to Statistic.h/cpp
    * Broke constructor to take two const char * arguments instead of one, so
      that indendation can be taken care of automatically.
    * Sort the list by pass name when printing
    * Make sure to print all statistics as a group, instead of randomly when
      the statistics dtors are called.

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

Check in DataStructure rewrite so far.

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

Initial checkin of Steensgaards context insensitive flow insensitive
alias analysis

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

Checkin some major reworks of data structure analysis.  This is not done,
nor does it work very well, but I need to get it checked in before I break
the tree unintentionally.

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

Make sure to use the TimerGroup that we created!

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

Make sure not to count the PassManager wrapers

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

Factor timer code out of PassManager implementation, into a generic interface
exposed by Support/Timer.h.

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

Checkin generic interval timer support

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

Fixed to properly escape quotes in strings.

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

Allow production of -stats output for benchmarks by specifying
ENABLE_STATS=1 on the make command line.

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

Allow production of -stats output for benchmarks by specifying
ENABLE_STATS=1 on the make command line.

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

On this code, llc did not pass the sixth argument (%reg321) to printf.

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

Minor tweak

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

Enable buidling of programs on Linux again

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

Added several more helper functions for construction MachineInstrs.

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

Bug fix in folding getElementPtr instructions: don't fold one into
a predecessor if it has a non-zero first index and the predecessor
ends with a struct index.

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

Fix a problem that was caused by stale analyses being in CurrentAnalyses

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

Fix bug in LICM that caused the previous big win. :(

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

Minor change to interface for Create{Zero,Sign}ExtensionsInstructions.

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

Hoist the contents of Loops in depth first order in the dominator tree,
rather than in random order.  This causes LICM to be DRAMATICALLY more
effective. For example, on bzip2.c, it is able to hoist 302 loads and
2380 total instructions, as opposed to 44/338 before.  This  obviously
makes other transformations much more powerful as well!

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

Fix printing of loop information

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

Improve printing of dominator sets

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

Fix major bugs in dominator set & tree information updating

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

Simplify code a bit, add an assertion

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

Fixed errors in ReplaceInstWithValue/ReplaceInstWithInst examples.

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

Convert DIRS to PARALLEL_DIRS.  They can be built independently.

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

Regression test for llc bug that was folding two getelementptrs illegally.

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

Added a couple of helper methods for live range construction.

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

Live ranges for Return value and return address of a Call are now
created here, simply by handling all implicit operands (which should
have been done anyway).

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

Fixed method getReturnValue(): it should return NULL if the
callee does not return a value.

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

Fixed incorrect assertion: spill code for function ptr should be
handled like normal operands, not like other call arguments.

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

Return address register should be marked as "result" for the JMPL instruction
since it is defined by the instruction.

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

Live ranges for Return value and return address of a Call are no longer
created here.  Instead they are created in LiveRangeInfo.cpp.  This
simplifies the code here quite a bit.

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

Simplified code that handles call args and rets, so it no longer
needs the RegClass list to be passed in.

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

Simplify Call translation slightly.

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

Regression test for live range bug for call arguments.

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

Overhaul integer conversions to match C++ ISO standard.
Don't allow direct FP-to-uint conversion (must be eliminated by preselection).
Address arithmetic for arrays is now entirely 64-bit so no sign-ext needed.

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

Modify operand order for Create{Sign,Zero}ExtensionInstructions.

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

Bug fix: some redundant copies were not being deleted after detection :-|.

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

Sign-extend integer constants from original type size to 64 bits!

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

Decompose FP-to-UInt casts into FP-to-ULong-toUInt.

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

Simple test for constant expressions constructed from global addresses.

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

Overhauled completely.

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

First try at implementing the AliasSetTracker class. I'm sure it will need
revision as I start to use it though.

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

* Run preheaders pass tests
* Linearize list of directories so I don't have to keep dealing with
  wrapping problems.

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

Checkin the simple features tests for the preheader insertion pass.

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

 - Further cleanups of LICM pass, remove extra work from previous implementation
 - Do not clone instructions then insert clone outside of loop.  Just move them.

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

Improve comments, doxygenize more

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

Don't hardcode path to dot in the doxygen config file.  Let doxygen search the PATH

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

Don't hardcode path to doxygen

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

Clean up LICM significantly now that it is guaranteed to have loop preheaders

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

Change pass name to something sane

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

Loop invariant code motion now depends on the LoopPreheader pass.  Dead code
has not yet been removed.

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

- Cleanup break-crit-edges pass by making SplitCriticalEdge a member method.
- break-crit-edges pass does not invalidate loop-preheader pass.

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

Checkin new loop-preheader insertion pass.

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

Checkin new loop-preheader insertion pass.

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

Fix printing of loop information

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

  - Fix bug in LoopInfo causing ParentLoop to be garbage

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

 - Add methods to ImmediateDominators & DominatorTree to allow updates
 - Make DominatorTree::Node not inherit from std::vector

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

  - Add methods to ImmediateDominators & DominatorTree to allow updates
  - Make DominatorTree::Node not inherit from std::vector

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

Add a new "DominatorSet::addDominator" method to allow updates

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

  - Add new methods to LoopInfo: getLoopPreheader, addBasicBlockToLoop.
    These allow extra information to be easily gathered, and loopinfo to be
    updated.

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

  - Add new methods to LoopInfo: getLoopPreheader, addBasicBlockToLoop.
    These allow extra information to be easily gathered, and loopinfo to be
    updated.

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

  - Add new ctor to BasicBlock to allow insertion before any BB, not just at
    the end of the function.

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