[LLVMbugs] [Bug 12052] New: Phi node reordering on LoopRotation

[bugzilla-daemon at llvm.org]

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

             Bug #: 12052
           Summary: Phi node reordering on LoopRotation
           Product: libraries
           Version: trunk
          Platform: All
        OS/Version: All
            Status: NEW
          Severity: normal
          Priority: P
         Component: Loop Optimizer
        AssignedTo: unassignedbugs at nondot.org
        ReportedBy: arkangath at gmail.com
                CC: llvmbugs at cs.uiuc.edu
    Classification: Unclassified


The rotate loop optimisation is changing the semantics of the following code:

define void @broken_loop(i32* %a, i32 %n, i32* %buff, i32* %sum) nounwind {
entry:
  %call = call i32 bitcast (i32 (...)* @calc_base to i32 ()*)()
  %call1 = call i32 bitcast (i32 (...)* @get_first_j to i32 ()*)()
  %call2 = call i32 @func(i32 %call1, i32 1)
  br label %for.cond

for.cond:                                         ; preds = %for.inc, %entry
  %j.0 = phi i32 [ %call1, %entry ], [ %i.0, %for.inc ]
  %i.0 = phi i32 [ %call2, %entry ], [ %call7, %for.inc ]
  %cmp = icmp sgt i32 %j.0, 1
  br i1 %cmp, label %for.body, label %for.end

for.body:                                         ; preds = %for.cond
  %add = add nsw i32 %call, %i.0
  %cmp3 = icmp slt i32 %add, %j.0
  br i1 %cmp3, label %if.then, label %if.end

if.then:                                          ; preds = %for.body
  %add4 = add nsw i32 %call, %i.0
  %arrayidx = getelementptr inbounds i32* %buff, i32 %add4
  %0 = load i32* %arrayidx, align 4
  %arrayidx5 = getelementptr inbounds i32* %buff, i32 %call
  %1 = load i32* %arrayidx5, align 4
  %add6 = add nsw i32 %1, %0
  store i32 %add6, i32* %arrayidx5, align 4
  br label %if.end

if.end:                                           ; preds = %if.then, %for.body
  br label %for.inc

for.inc:                                          ; preds = %if.end
  %call7 = call i32 @func(i32 %i.0, i32 1)
  br label %for.cond

for.end:                                          ; preds = %for.cond
  ret void
}


When run with "opt code.ll -loop-rotation", the output is as follows:

define void @broken_loop(i32* %a, i32 %n, i32* %buff, i32* %sum) nounwind {
entry:
  %call = call i32 bitcast (i32 (...)* @calc_base to i32 ()*)()
  %call1 = call i32 bitcast (i32 (...)* @get_first_j to i32 ()*)()
  %call2 = call i32 @func(i32 %call1, i32 1)
  %cmp1 = icmp sgt i32 %call1, 1
  br i1 %cmp1, label %for.body.lr.ph, label %for.end

for.body.lr.ph:                                   ; preds = %entry
  br label %for.body

for.body:                                         ; preds = %for.body.lr.ph,
%for.inc
  %i.03 = phi i32 [ %call2, %for.body.lr.ph ], [ %call7, %for.inc ]
  %j.02 = phi i32 [ %call1, %for.body.lr.ph ], [ %i.03, %for.inc ]
  %add = add nsw i32 %call, %i.03
  %cmp3 = icmp slt i32 %add, %j.02
  br i1 %cmp3, label %if.then, label %if.end

if.then:                                          ; preds = %for.body
  %add4 = add nsw i32 %call, %i.03
  %arrayidx = getelementptr inbounds i32* %buff, i32 %add4
  %0 = load i32* %arrayidx, align 4
  %arrayidx5 = getelementptr inbounds i32* %buff, i32 %call
  %1 = load i32* %arrayidx5, align 4
  %add6 = add nsw i32 %1, %0
  store i32 %add6, i32* %arrayidx5, align 4
  br label %if.end

if.end:                                           ; preds = %if.then, %for.body
  br label %for.inc

for.inc:                                          ; preds = %if.end
  %call7 = call i32 @func(i32 %i.03, i32 1)
  %cmp = icmp sgt i32 %i.03, 1
  br i1 %cmp, label %for.body, label %for.cond.for.end_crit_edge

for.cond.for.end_crit_edge:                       ; preds = %for.inc
  br label %for.end

for.end:                                          ; preds =
%for.cond.for.end_crit_edge, %entry
  ret void
}


And the two phi nodes that were illegally reordered:
  %j.0 = phi i32 [ %call1, %entry ], [ %i.0, %for.inc ]
  %i.0 = phi i32 [ %call2, %entry ], [ %call7, %for.inc ]
to
  %i.03 = phi i32 [ %call2, %for.body.lr.ph ], [ %call7, %for.inc ]
  %j.02 = phi i32 [ %call1, %for.body.lr.ph ], [ %i.03, %for.inc 

Because j should keep the previous value of i of the loop iteration; this pass
changes it so that j now gets the new value of the loop.

The original C code for this is:

int func(int a, int b);
int calc_base();
int get_first_j();

void broken_loop(int *a, int n, int *buff, int *sum)
{
  int base = calc_base();
  int j = get_first_j();
  int i;

  for (i = func(j, 1); j > 1; i = func(i, 1))
  {
     if (base + i < j)
        buff[base] += buff[base + i];
     j = i; 
  }
}

-- 
Configure bugmail: http://llvm.org/bugs/userprefs.cgi?tab=email
------- You are receiving this mail because: -------
You are on the CC list for the bug.