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