Page MenuHomePhabricator

[LoopInterchange] Handle lcssa PHIs with multiple predecessors
Needs ReviewPublic

Authored by congzhe on Mon, Apr 19, 1:38 PM.

Details

Summary

This is a bugfix in the transformation phase.

If the original outer loop header branches to both the inner loop (header) and the outer loop latch, and if there is an lcssa PHI node outside the loop nest, then after interchange the new outer latch will have an lcssa PHI node inserted which has two predecessors, i.e., the original outer header and the original outer latch. Currently the transformation assumes it has only one predecessor (the original outer latch) and crashes, since the inserted lcssa PHI node does not take both predecessors as incoming BBs.

Diff Detail

Event Timeline

congzhe created this revision.Mon, Apr 19, 1:38 PM
congzhe requested review of this revision.Mon, Apr 19, 1:38 PM
congzhe edited the summary of this revision. (Show Details)Tue, Apr 20, 11:57 PM
congzhe edited the summary of this revision. (Show Details)

Just to better clarify, for the test case added in this patch, this is the IR after loop interchange (with this patch):

define i64 @lcssa_08([100 x [100 x i64]]* %Arr) {
entry:
  br label %for2.preheader

for1.header.preheader:                            ; preds = %for2
  br label %for1.header

for1.header:                                      ; preds = %for1.header.preheader, %for1.inc
  %indvars.iv23 = phi i64 [ %indvars.iv.next24, %for1.inc ], [ 0, %for1.header.preheader ]
  br i1 undef, label %for2.split1, label %for2.split

for2.preheader:                                   ; preds = %entry
  br label %for2

for2:                                             ; preds = %for2.preheader, %for2.split
  %indvars.iv = phi i64 [ %1, %for2.split ], [ 0, %for2.preheader ]
  br label %for1.header.preheader

for2.split1:                                      ; preds = %for1.header
  %arrayidx = getelementptr inbounds [100 x [100 x i64]], [100 x [100 x i64]]* %Arr, i64 0, i64 %indvars.iv, i64 %indvars.iv23
  %lv = load i64, i64* %arrayidx, align 4
  %indvars.iv.next.3 = add nuw nsw i64 %indvars.iv, 1
  %exit1 = icmp eq i64 %indvars.iv.next.3, 100
  br label %for1.inc.loopexit

for2.split:                                       ; preds = %for1.inc, %for1.header
  %0 = phi i64 [ %indvars.iv23, %for1.inc ], [ %indvars.iv23, %for1.header ]
  %1 = add nuw nsw i64 %indvars.iv, 1
  %2 = icmp eq i64 %1, 100
  br i1 %2, label %for1.loopexit, label %for2

for1.inc.loopexit:                                ; preds = %for2.split1
  br label %for1.inc

for1.inc:                                         ; preds = %for1.inc.loopexit
  %indvars.iv.next24 = add nuw nsw i64 %indvars.iv23, 1
  %exit2 = icmp eq i64 %indvars.iv.next24, 100
  br i1 %exit2, label %for2.split, label %for1.header

for1.loopexit:                                    ; preds = %for2.split
  %indvars.outer.lcssa = phi i64 [ %0, %for2.split ]
  ret i64 %indvars.outer.lcssa
}

Without this patch the compiler currently crashes with the following info:

PHINode should have one entry for each predecessor of its parent basic block!
  %0 = phi i64 [ %indvars.iv23, %for1.inc ]
in function lcssa_08
LLVM ERROR: Broken function found, compilation aborted!