[LLVMbugs] [Bug 15470] New: LLVM 3.1 miscompiles loop like "((unsigned char*)(table) + 13 )[i*e + j]"

[bugzilla-daemon at llvm.org]

http://llvm.org/bugs/show_bug.cgi?id=15470

            Bug ID: 15470
           Summary: LLVM 3.1 miscompiles loop like "((unsigned
                    char*)(table) + 13 )[i*e + j]"
           Product: libraries
           Version: 3.1
          Hardware: Macintosh
                OS: All
            Status: NEW
          Severity: release blocker
          Priority: P
         Component: Loop Optimizer
          Assignee: unassignedbugs at nondot.org
          Reporter: spam_hole at shaw.ca
                CC: llvmbugs at cs.uiuc.edu
    Classification: Unclassified

[Source:
http://stackoverflow.com/questions/15280506/llvm-optimisation-bug-or-undefined-behaviour]

LLVM miscompiles the following code:

/* --------8<-------- */
#include <stdio.h>

unsigned long int * table;

void foo( unsigned long int q )
{
  unsigned long int i,j,e;

  e = 0;
  for (i = 1; i <= 256; i *= q)
    e++;
  e--;

  for (i = 0; i < q; i++)
    for (j = 0; j < e; j++)
      ((unsigned char*)(table) + 13 )[i*e + j] = 0;   // bug here
}

int main() {
    unsigned long int v[8];
    int i;
    for(i=0; i<sizeof(v)/sizeof(v[0]); i++) {
        v[i] = 0x0101010101010101ULL;
    }

    table = v;
    foo(2);

    for(i=0; i<sizeof(v); i++) {
        printf("%d", ((unsigned char*)v)[i]);
    }
    puts("");
    return 0;
}
/* --------8<-------- */

The correct output according to "gcc -O1" and "clang -O0" is

11111111111110000000000000000111

But, "clang -O1" miscompiles this and results in the output

00000000111111111111100000000111

This is noted as an LLVM bug because the IR generated by Clang appears to be
correct:

/* --------8<-------- */
define void @foo(i64 %q) nounwind uwtable ssp {
  br label %1

; <label>:1                                       ; preds = %0, %1
  %indvars.iv = phi i64 [ 0, %0 ], [ %indvars.iv.next, %1 ]
  %i.04 = phi i64 [ 1, %0 ], [ %2, %1 ]
  %indvars.iv.next = add i64 %indvars.iv, 1
  %2 = mul i64 %i.04, %q
  %3 = icmp ult i64 %2, 257
  br i1 %3, label %1, label %4

; <label>:4                                       ; preds = %1
  %5 = icmp eq i64 %q, 0
  br i1 %5, label %._crit_edge3, label %.preheader.lr.ph

.preheader.lr.ph:                                 ; preds = %4
  %6 = icmp eq i64 %indvars.iv, 0
  br label %.preheader

.preheader:                                       ; preds = %._crit_edge,
%.preheader.lr.ph
  %i.12 = phi i64 [ 0, %.preheader.lr.ph ], [ %14, %._crit_edge ]
  br i1 %6, label %._crit_edge, label %.lr.ph

.lr.ph:                                           ; preds = %.preheader
  %7 = mul i64 %i.12, %indvars.iv
  %8 = add i64 %7, 13
  br label %9

; <label>:9                                       ; preds = %9, %.lr.ph
  %j.01 = phi i64 [ 0, %.lr.ph ], [ %13, %9 ]
  %10 = load i64** @table, align 8, !tbaa !0
  %11 = bitcast i64* %10 to i8*
  %.sum = add i64 %8, %j.01
  %12 = getelementptr inbounds i8* %11, i64 %.sum
  store i8 0, i8* %12, align 1, !tbaa !1
  %13 = add i64 %j.01, 1
  %exitcond = icmp eq i64 %13, %indvars.iv
  br i1 %exitcond, label %._crit_edge, label %9

._crit_edge:                                      ; preds = %9, %.preheader
  %14 = add i64 %i.12, 1
  %exitcond6 = icmp eq i64 %14, %q
  br i1 %exitcond6, label %._crit_edge3, label %.preheader

._crit_edge3:                                     ; preds = %._crit_edge, %4
  ret void
}
/* --------8<-------- */

However, at some point during the loop optimizer, the "add i64 X, 13" gets
moved to before the multiply, causing the code to improperly access [i*(e+13) +
j].

This bug has been reproduced on LLVM 2.7, the only other version of LLVM I have
easy access to.

-- 
You are receiving this mail because:
You are on the CC list for the bug.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.llvm.org/pipermail/llvm-bugs/attachments/20130307/73e0dbc1/attachment.html>