GCSE is faster than SCCP, and it makes SCCP's job easier, so run it first.

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

* Eliminate dead code that should have been removed in last revision
* Convert main constant propogation pass to be worklist driven instead of
  iterative.
* -constprop pass no longer "constant propogates" terminator instructions
   - CFG is now preserved!

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

Handle X = phi Y  --> X = Y

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

Make the testcase more interesting so that DCE does not eliminate it.
Use DIE instead of DCE anyway

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

Move a bunch of code to a .cpp file, don't #include Instruction.h

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

Move code out of header file

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

* Use simplified interface to constant propogation stuff.
* Remove dead PHI case (which could not work due to getNumOperands rather than
  getNumIncomingValues.  This really belongs in InstCombine, anyway so we'll
  move it there.

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

Add #include removed from ConstantHandling.h

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

New testcase for PHI folding

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

Clean up ADCE by removing extraneous wrapper class

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

Combine not (not X) -> X

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

New testcase to make sure not instructions get combined

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

Instruction Combination can create a ton of trivially dead instructions.  Remove
them with an DIE pass before more expensive optimizations are run.

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

Support more cases...

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

More tests

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

Add testcase for -(-A)

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

Change usage of isPointerType to use isa

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

Replace all usages of Type::isPointerType with isa<PointerType>

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

Implement getPrimitiveSize()
don't use isPointerType()

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

Add many more instruction combination simplifications

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

* Add getPrimitiveSize method
* Remove isPointerType, isMethodType, etc... methods.  Use isa<> instead
* Added specialization of isa for pointer types so that DerivedTypes.h doesn't
  have to be #included to use isa<PointerType>(..)

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

Fix testcase, the 'shift out all bits' doesn't apply to signed types.

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

Void and Label values cannot be acted on directly so they have zero size

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

More testcases I don't want to forget about

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

New testcases so I don't forget about these algebraic simplifications

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

New testcase so I don't forget about this.

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

Testcase for missed merge opportunity

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

Run DCE AFTER SCCP and GCSE!

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

Build CFGsimplify directory

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

Updated documentation a _LOT_

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

Remove dead code

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

Merge blocks like this:

void "test3"(bool %T) {
        br bool %T, label %BB1, label %BB1
BB1:
        ret void
}

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

Implement constant propogation of shift instructions

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

Implement constant propogation of shifts

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

Print functions with curly braces instead of begin/end

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

Add a range remove method

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

Implement two iterator remove method

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

Initial testcases for CFG simplify (which is part of DCE for now)

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

Test moved to SCCP test directory

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

Implement remainder
Fix implementation of Not

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

Implement remainder

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

New testcase for bugs in the constant propogator

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

Add tests for floating point remainder elimination

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

New testcase to see if constant propogation of remainder is implemented

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

This testcase is a sanity check

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

Fix bug: test/Regression/Transforms/SCCP/2002-05-03-NotOperator.ll
by using the ~ operator instead of !

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

Add new testcase for general constant prop.

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

Add const prop pass to eliminate dead branches

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

Implement the NOT operator.

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

We currently don't allow unresolved opaque types!

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

Add -d switch to test AsmWriter as well

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

Allow open/closing curly braces instead of begin/end to define the body of a function

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

Eliminate usage of function level constant pool

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

Use unified diffs with gnu diff instead of old diffs

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

Ok, really it only takes me 3 times to get this right!
Now use #if 0 instead of #ifdef 0

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

Oops, disable debugging code all the way.  :)

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

* Finish the implementation of isEdgeFeasible this fixes bug:
    test/Regression/Transforms/SCCP/2002-05-02-EdgeFailure.ll
* SCCP now preserves the CFG:  It leaves conditional branches the way they
  are in the program, not simplifying them.  A seperate pass should eliminate
  the potentially dead basic blocks and edges in the CFG.

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

* Enable SCCP debugging to be turned on with a simple change of #define
* Change worklist to a set so that duplicates cannot happen
* Add support for the invoke instruction
* Avoid marking store and free instructions as overdefined, since they
  cannot produce a value anyway.
* Inline the OperandChangedState implementation
* Add isEdgeFeasible in preparation to fix a bug.  Right now it behaves
  exactly as before.
* Remove obsolete comment about constant pools

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

More testcases for SCCP

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

* Simplify the code by not bothering to name the folded constant
* Do not skip the instruction immediately after a folded instruction.  This
  was causing the testcase failure:
test/Regression/Transforms/SCCP/2002-05-02-MissSecondInst.ll

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

Additional testcase

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

Run the SCCP test

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

First testcase for SCCP pass

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

Simplify the testcase a bit

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

New testcase

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

Implement cast operations on booleans to allow casting bools to ints, f.e.

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

* Fix a bug (test/Regression/Assembler/2002-05-02-InvalidForwardRef.ll)
  introduced in the 1.66 revision of this file.
* Convert a hard coded constant to a symbolic value.

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

New testcase for assembler failure

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

The implementation keyword is no longer neccesary

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

The "implementation" is now allowed but not required by the parser.  All type
definitions must still occur before function bodies, but the wierd keyword is
no longer neccesary.

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

ExprTypeConvert will already do this transformation, no need to specialize
it here.

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

Be a little more efficient, do not generate loads and stores with indices in them.

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

Fix bug: test/Regression/Transforms/LevelRaise/2002-05-02-BadCastElimination.ll

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

* Add ability to eliminate a bunch of different cascading cast variations
* Allow elimination of getelementptr X, uint 0 (which is a noop)

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

Intitial checkin of cast tests

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

New testcase for bug found by Vikram

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

Check another case

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

Fixed bug: test/Regression/Transforms/Mem2Reg/2002-05-01-ShouldNotPromoteThisAlloca.ll

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

New bug testcase

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

Remove unneccesary pass.

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

Remove unneccesary pass

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

New testcase

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

Fix problem where subpasses would invalidate all analyses outstanding

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

Add folding rules for mul X, 0 and mul X, 2

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

New test cases for mul folding

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

Significantly clean up SCCP pass.  Now the two classes are merged and in
an anonymous namespace where they belong.

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

Range insertion now returns an iterator

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

Make the range insert operation return an iterator, even though the STL
range insert doesn't

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

These aren't tools

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

Remove unused files:  This is the old induction varaible cannonicalization
pass built on top of interval analysis

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

Move constant merging pass earlier
Include the SCCP pass in gccas

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

Fix for problem when allocating something like this:
   malloc(100-i);

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

Merge Chris's script with the one already checked in

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

Fix #include broken by iMemory.h not including DerivedTypes.h

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

Add neccesary #include

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

changes because iMemory.h no longer #includes DerivedTypes.h
This only requires Type.h anyway

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

Changes so that iMemory.h doesn't include DerivedTypes.h

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

Change to allow iMemory.h to avoid including DerivedTypes.h

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

Fix bug: test/Regression/Other/2002-04-29-NameBinding.ll

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

Remove InstForest from analysis namespace

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