[LLVMbugs] [Bug 22893] New: InstCombine: GEP merging handles loop backedges poorly

[bugzilla-daemon at llvm.org]

https://llvm.org/bugs/show_bug.cgi?id=22893

            Bug ID: 22893
           Summary: InstCombine: GEP merging handles loop backedges poorly
           Product: libraries
           Version: trunk
          Hardware: PC
                OS: All
            Status: NEW
          Severity: normal
          Priority: P
         Component: Scalar Optimizations
          Assignee: unassignedbugs at nondot.org
          Reporter: james.molloy at arm.com
                CC: llvmbugs at cs.uiuc.edu
    Classification: Unclassified

Consider the following code:

int f (int n, int **g_h1) {
    int *h1 = *g_h1;
    int i1, s1=0;
    *h1++ = 2;
    for (i1 = 2; i1 < n; ++i1) {
    s1 += *h1++;
    }
    *g_h1 = h1;
    return s1;
}

We end up with a PHI recurrence for h1:

entry:
  h1_next = gep h1, 1

loop:
  h1_ind = phi h1_next, h1_ind_next
  ...
  h1_ind_next = gep h1_ind, 1
  br loop

GEP merging sees this, and converts it into:

entry:
  h1_next = gep h1, 1

loop:
  h1_prev = phi h1_this, h1
  h1_this = phi h1_ind_next, h1_next
  ...
  h1_ind_next = gep h1_prev, 2

An extra PHI node has been created to hold the value of h1 in the *previous*
iteration, and that is being used to calculate the next iteration. This is
obviously crazy.

The faulty transform is in InstructionCombining.cpp:1392. I see two things iffy
here:
  1. The "Is GEP similar?" logic allows two GEPs that differ only by the *base*
operand. I can't imagine that's particularly useful especially for trivial
GEPs.
  2. The log message clearly says it's trying to deal with merge PHIs / diamond
PHIs, rather than loop backedge PHIs, but it acts on loop backedge PHIs too.

Perhaps (2) above is wrong, and the cost model "is this newly created GEP going
to be merged efficiently?" is wrong? I'm not sure.

Generated IR shown below for posterity.

define i32 @f(i32 %n, i32** nocapture %g_h1, i32** nocapture readnone %g_h2,
i32** nocapture readnone %g_c) #0 {
entry:
  %0 = load i32*, i32** %g_h1, align 8, !tbaa !2
  store i32 2, i32* %0, align 4, !tbaa !6
  %h1.06 = getelementptr inbounds i32, i32* %0, i64 1
  %cmp7 = icmp sgt i32 %n, 2
  br i1 %cmp7, label %for.body.preheader, label %for.end

for.body.preheader:                               ; preds = %entry
  br label %for.body

for.body:                                         ; preds =
%for.body.preheader, %for.body
  %1 = phi i32* [ %h1.010, %for.body ], [ %0, %for.body.preheader ]
  %h1.010 = phi i32* [ %h1.0, %for.body ], [ %h1.06, %for.body.preheader ]
  %s1.09 = phi i32 [ %add, %for.body ], [ 0, %for.body.preheader ]
  %i1.08 = phi i32 [ %inc, %for.body ], [ 2, %for.body.preheader ]
  %2 = load i32, i32* %h1.010, align 4, !tbaa !6
  %add = add nsw i32 %2, %s1.09
  %inc = add nuw nsw i32 %i1.08, 1
  %h1.0 = getelementptr inbounds i32, i32* %1, i64 2
  %exitcond = icmp eq i32 %inc, %n
  br i1 %exitcond, label %for.end.loopexit, label %for.body

for.end.loopexit:                                 ; preds = %for.body
  %h1.0.lcssa15 = phi i32* [ %h1.0, %for.body ]
  %add.lcssa = phi i32 [ %add, %for.body ]
  br label %for.end

for.end:                                          ; preds = %for.end.loopexit,
%entry
  %h1.0.lcssa = phi i32* [ %h1.06, %entry ], [ %h1.0.lcssa15, %for.end.loopexit
]
  %s1.0.lcssa = phi i32 [ 0, %entry ], [ %add.lcssa, %for.end.loopexit ]
  store i32* %h1.0.lcssa, i32** %g_h1, align 8, !tbaa !2
  ret i32 %s1.0.lcssa
}

-- 
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/20150313/e70cabd6/attachment.html>