[LLVMbugs] [Bug 255] NEW: [tailduplication] Single basic block loops are very rare

[bugzilla-daemon at cs.uiuc.edu]

http://llvm.cs.uiuc.edu/bugs/show_bug.cgi?id=255

           Summary: [tailduplication] Single basic block loops are very rare
           Product: libraries
           Version: 1.0
          Platform: PC
        OS/Version: Linux
            Status: NEW
          Severity: normal
          Priority: P2
         Component: Scalar Optimizations
        AssignedTo: sabre at nondot.org
        ReportedBy: sabre at nondot.org


Tail duplication is currently disabled in all but the most simple cases, as a
workaround for Bug 174 (Tail duplication does not update SSA form correctly). 
Because of this, we miss many important cases where tail duplication is needed,
for example in cases that should produce single basic block loops.

For example, this testcase:

--------------------------
int A[1000];
void test() {
  int i;
  for (i = 0; i < 1000; ++i)
    A[i] = 0;
}
--------------------------

Currently compiles into this:

---
%A = weak global [1000 x int] zeroinitializer
implementation

void %test() {
entry:
        br label %loopentry

loopentry:      ; preds = %entry, %no_exit
        %i.0 = phi int [ 0, %entry ], [ %inc, %no_exit ]
        %tmp.1 = setlt int %i.0, 1000           ; <bool> [#uses=1]
        br bool %tmp.1, label %no_exit, label %return

no_exit:        ; preds = %loopentry
        %tmp.4 = cast int %i.0 to long          ; <long> [#uses=1]
        %tmp.5 = getelementptr [1000 x int]* %A, long 0, long %tmp.4
        store int 0, int* %tmp.5
        %inc = add int %i.0, 1          ; <int> [#uses=1]
        br label %loopentry

return:        ; preds = %loopentry
        ret void
}
---

In this case, the loopentry block should be tail duplicated onto the end of the
no_exit block, turning this into a single block loop.

The general solution to this problem requires implementing a fully general
dominator tree/frontier updator, which I'm not planning to write any time in the
near future.  However, we should be able to be a bit more aggressive to handle
some of the important cases like the one above.

-Chris



------- You are receiving this mail because: -------
You are on the CC list for the bug, or are watching someone who is.