The CFG simplification pass has a habit of merging the header nodes of loops
together into a single node.  To counteract this, the -loopsimplify pass should
break them back up.

For example, consider this simple matrix multiplication testcase:

    for( int i=0; i<L; i++ )
        for( int j=0; j<L; j++ ) {
            double sum = 0;
            for( int k=0; k<L; k++ )
                sum += C[L*i+k]*D[L*k+j];
            E[L*i+j] = sum;

This is currently compiled into:

no_exit.2:
        ...
        br bool %tmp.5, label %no_exit.2, label %loopexit.2

loopexit.2:
        ...
        br bool %tmp.3, label %no_exit.2, label %loopexit.1

loopexit.1:
        ...
        br bool %tmp.1, label %no_exit.2, label %return

Which is a single natural loop.

To fix this, the LoopSimplify pass should detect that a backedge dominates
another backedge, and turn the dominating backedge into an inner loop.

When looking at loop simplify, it would also be good to figure out why this
testcase:

---
target endian = little
target pointersize = 32
        "complex double" = type { double, double }
        "complex float" = type { float, float }
        "complex long double" = type { double, double }
%data = external global [100 x int]             ; <[100 x int]*> [#uses=1]

implementation   ; Functions:

int %test(int %N) {
entry:
        %tmp.11 = setne int %N, 0               ; <bool> [#uses=1]
        br bool %tmp.11, label %no_exit, label %return

no_exit:                ; preds = %entry, %no_exit
        %N_addr.0.pn = phi int [ %dec, %no_exit ], [ %N, %entry ]              
; <int> [#uses=3]
        %tmp.4 = cast int %N_addr.0.pn to long          ; <long> [#uses=1]
        %tmp.5 = getelementptr [100 x int]* %data, long 0, long %tmp.4         
; <int*> [#uses=1]
        %tmp.6 = load int* %tmp.5               ; <int> [#uses=1]
        %dec = add int %N_addr.0.pn, -1         ; <int> [#uses=1]
        %tmp.1 = setne int %N_addr.0.pn, 1              ; <bool> [#uses=1]
        br bool %tmp.1, label %no_exit, label %return

return:         ; preds = %entry, %no_exit
        %Ret.0.pn = phi int [ %tmp.6, %no_exit ], [ 0, %entry ]         ; <int>
[#uses=1]
        ret int %Ret.0.pn
}
---

Inserts a one argument PHI node, like so:

---
target endian = little
target pointersize = 32
        "complex double" = type { double, double }
        "complex float" = type { float, float }
        "complex long double" = type { double, double }
%data = external global [100 x int]             ; <[100 x int]*> [#uses=1]

implementation   ; Functions:

int %test(int %N) {
entry:
        %tmp.11 = setne int %N, 0               ; <bool> [#uses=1]
        br bool %tmp.11, label %no_exit.preheader, label %return

no_exit.preheader:              ; preds = %entry
        %N_addr.0.pn.ph = phi int [ %N, %entry ]                ; <int> [#uses=1]
        br label %no_exit

no_exit:                ; preds = %no_exit.preheader, %no_exit
        %N_addr.0.pn = phi int [ %dec, %no_exit ], [ %N_addr.0.pn.ph,
%no_exit.preheader ]              ; <int> [#uses=3]
        %tmp.4 = cast int %N_addr.0.pn to long          ; <long> [#uses=1]
        %tmp.5 = getelementptr [100 x int]* %data, long 0, long %tmp.4         
; <int*> [#uses=1]
        %tmp.6 = load int* %tmp.5               ; <int> [#uses=1]
        %dec = add int %N_addr.0.pn, -1         ; <int> [#uses=1]
        %tmp.1 = setne int %N_addr.0.pn, 1              ; <bool> [#uses=1]
        br bool %tmp.1, label %no_exit, label %return.loopexit

return.loopexit:                ; preds = %no_exit
        %Ret.0.pn.ph = phi int [ %tmp.6, %no_exit ]             ; <int> [#uses=1]
        br label %return

return:         ; preds = %entry, %return.loopexit
        %Ret.0.pn = phi int [ 0, %entry ], [ %Ret.0.pn.ph, %return.loopexit ]  
        ; <int> [#uses=1]
        ret int %Ret.0.pn
}
---

The one argument PHI node thing has been fixed:
http://mail.cs.uiuc.edu/pipermail/llvm-commits/Week-of-Mon-20031208/010030.html

Changing all of these bugs who do not have people looking at them to be assigned
to "unassignedbugs", indicating that if someone is feeling ambitious, they can
take ownership of the bug.

If I stole your bug, and you still want it, feel free to take ownership back.

-Chris

Ugh, this bug is REALLY annoying.  It is killing our performance on a lot of
programs, destroying subsequent analysis capabilities.  For example, we cannot
compute the trip count of simple nested loops, hoist invariants, etc. :(

As such, I think I'll try to work on this.

-Chris

This has been fixed for a while now.

-Chris