llvm/test/Transforms/StructurizeCFG/post-order-traversal-bug.ll

   1 ; RUN: opt -S -structurizecfg %s -o - | FileCheck %s
   2
   3 ; The structurize cfg pass used to do a post-order traversal to generate a list
   4 ; of ; basic blocks and then operate on the list in reverse.  This led to bugs,
   5 ; because sometimes successors would be visited before their predecessors.
   6 ; The fix for this was to do a reverse post-order traversal which is what the
   7 ; algorithm requires.
   8
   9 ; Function Attrs: nounwind
  10 define void @test(ptr nocapture %out, i32 %K1, ptr nocapture readonly %nr) {
  11
  12 ; CHECK: entry:
  13 ; CHECK: br label %for.body
  14 entry:
  15   br label %for.body
  16
  17 ; CHECK: for.body:
  18 ; CHECK: br i1 %cmp1.inv, label %lor.lhs.false, label %Flow
  19 for.body:                                         ; preds = %for.body.backedge, %entry
  20   %indvars.iv = phi i64 [ %indvars.iv.be, %for.body.backedge ], [ 1, %entry ]
  21   %best_val.027 = phi float [ %best_val.027.be, %for.body.backedge ], [ 5.000000e+01, %entry ]
  22   %prev_start.026 = phi i32 [ %tmp26, %for.body.backedge ], [ 0, %entry ]
  23   %best_count.025 = phi i32 [ %best_count.025.be, %for.body.backedge ], [ 0, %entry ]
  24   %tmp0 = trunc i64 %indvars.iv to i32
  25   %cmp1 = icmp eq i32 %tmp0, %K1
  26   br i1 %cmp1, label %if.then, label %lor.lhs.false
  27
  28 ; CHECK: lor.lhs.false:
  29 ; CHECK: br label %Flow
  30 lor.lhs.false:                                    ; preds = %for.body
  31   %arrayidx = getelementptr inbounds float, ptr %nr, i64 %indvars.iv
  32   %tmp1 = load float, ptr %arrayidx, align 4
  33   %tmp2 = add nsw i64 %indvars.iv, -1
  34   %arrayidx2 = getelementptr inbounds float, ptr %nr, i64 %tmp2
  35   %tmp3 = load float, ptr %arrayidx2, align 4
  36   %cmp3 = fcmp une float %tmp1, %tmp3
  37   br i1 %cmp3, label %if.then, label %for.body.1
  38
  39 ; CHECK: Flow:
  40 ; CHECK: br i1 %{{[0-9]+}}, label %if.then, label %Flow1
  41
  42 ; CHECK: if.then:
  43 ; CHECK: br label %Flow1
  44 if.then:                                          ; preds = %lor.lhs.false, %for.body
  45   %sub4 = sub nsw i32 %tmp0, %prev_start.026
  46   %tmp4 = add nsw i64 %indvars.iv, -1
  47   %arrayidx8 = getelementptr inbounds float, ptr %nr, i64 %tmp4
  48   %tmp5 = load float, ptr %arrayidx8, align 4
  49   br i1 %cmp1, label %for.end, label %for.body.1
  50
  51 ; CHECK: for.end:
  52 ; CHECK: ret void
  53 for.end:                                          ; preds = %for.body.1, %if.then
  54   %best_val.0.lcssa = phi float [ %best_val.233, %for.body.1 ], [ %tmp5, %if.then ]
  55   store float %best_val.0.lcssa, ptr %out, align 4
  56   ret void
  57
  58 ; CHECK: Flow1
  59 ; CHECK: br i1 %{{[0-9]}}, label %for.body.1, label %Flow2
  60
  61 ; CHECK: for.body.1:
  62 ; CHECK: %cmp1.5 = icmp ne i32 %tmp22, %K1
  63 ; CHECK: br i1 %cmp1.5, label %for.body.6, label %Flow3
  64 for.body.1:                                       ; preds = %if.then, %lor.lhs.false
  65   %best_val.233 = phi float [ %tmp5, %if.then ], [ %best_val.027, %lor.lhs.false ]
  66   %best_count.231 = phi i32 [ %sub4, %if.then ], [ %best_count.025, %lor.lhs.false ]
  67   %indvars.iv.next.454 = add nsw i64 %indvars.iv, 5
  68   %tmp22 = trunc i64 %indvars.iv.next.454 to i32
  69   %cmp1.5 = icmp eq i32 %tmp22, %K1
  70   br i1 %cmp1.5, label %for.end, label %for.body.6
  71
  72 ; CHECK: Flow2:
  73 ; CHECK: br i1 %{{[0-9]+}}, label %for.end, label %for.body
  74
  75 ; CHECK: for.body.6:
  76 ; CHECK: br i1 %cmp5.6, label %if.then6.6, label %for.body.backedge
  77 for.body.6:                                       ; preds = %for.body.1
  78   %indvars.iv.next.559 = add nsw i64 %indvars.iv, 6
  79   %tmp26 = trunc i64 %indvars.iv.next.559 to i32
  80   %sub4.6 = sub nsw i32 %tmp26, %tmp22
  81   %cmp5.6 = icmp slt i32 %best_count.231, %sub4.6
  82   br i1 %cmp5.6, label %if.then6.6, label %for.body.backedge
  83
  84 ; CHECK: if.then6.6
  85 ; CHECK: br label %for.body.backedge
  86 if.then6.6:                                       ; preds = %for.body.6
  87   %arrayidx8.6 = getelementptr inbounds float, ptr %nr, i64 %indvars.iv.next.454
  88   %tmp29 = load float, ptr %arrayidx8.6, align 4
  89   br label %for.body.backedge
  90
  91 ; CHECK: Flow3:
  92 ; CHECK: br label %Flow2
  93
  94 ; CHECK: for.body.backedge:
  95 ; CHECK: br label %Flow3
  96 for.body.backedge:                                ; preds = %if.then6.6, %for.body.6
  97   %best_val.027.be = phi float [ %tmp29, %if.then6.6 ], [ %best_val.233, %for.body.6 ]
  98   %best_count.025.be = phi i32 [ %sub4.6, %if.then6.6 ], [ %best_count.231, %for.body.6 ]
  99   %indvars.iv.be = add nsw i64 %indvars.iv, 7
 100   br label %for.body
 101 }