test/Transforms/LoopInstSimplify/basic.ll

   1 ; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
   2 ; RUN: opt -S %s -passes=loop-instsimplify | FileCheck %s
   3 ; RUN: opt -S %s -passes=loop-instsimplify -enable-mssa-loop-dependency=true -verify-memoryssa | FileCheck %s
   4
   5 ; Test very basic folding and propagation occurs within a loop body. This should
   6 ; collapse to the loop iteration structure and the LCSSA PHI node.
   7 define i32 @test1(i32 %n, i32 %x) {
   8 ; CHECK-LABEL: @test1(
   9 ; CHECK-NEXT:  entry:
  10 ; CHECK-NEXT:    br label [[LOOP:%.*]]
  11 ; CHECK:       loop:
  12 ; CHECK-NEXT:    [[I:%.*]] = phi i32 [ 0, [[ENTRY:%.*]] ], [ [[I_NEXT:%.*]], [[LOOP]] ]
  13 ; CHECK-NEXT:    [[I_NEXT]] = add nsw i32 [[I]], 1
  14 ; CHECK-NEXT:    [[I_CMP:%.*]] = icmp slt i32 [[I_NEXT]], [[N:%.*]]
  15 ; CHECK-NEXT:    br i1 [[I_CMP]], label [[LOOP]], label [[EXIT:%.*]]
  16 ; CHECK:       exit:
  17 ; CHECK-NEXT:    [[X_LCSSA:%.*]] = phi i32 [ [[X:%.*]], [[LOOP]] ]
  18 ; CHECK-NEXT:    ret i32 [[X_LCSSA]]
  19 ;
  20 entry:
  21   br label %loop
  22
  23 loop:
  24   %i = phi i32 [ 0, %entry ], [ %i.next, %loop ]
  25   %x.add = add nsw i32 %x, 0
  26   %x.sub = sub i32 %x.add, 0
  27   %x.and = and i32 %x.sub, -1
  28   %i.next = add nsw i32 %i, 1
  29   %i.cmp = icmp slt i32 %i.next, %n
  30   br i1 %i.cmp, label %loop, label %exit
  31
  32 exit:
  33   %x.lcssa = phi i32 [ %x.and, %loop ]
  34   ret i32 %x.lcssa
  35 }
  36
  37 ; Test basic loop structure that still has a simplification feed a prior PHI.
  38 define i32 @test2(i32 %n, i32 %x) {
  39 ; CHECK-LABEL: @test2(
  40 ; CHECK-NEXT:  entry:
  41 ; CHECK-NEXT:    br label [[LOOP:%.*]]
  42 ; CHECK:       loop:
  43 ; CHECK-NEXT:    [[I:%.*]] = phi i32 [ 0, [[ENTRY:%.*]] ], [ [[I_NEXT:%.*]], [[LOOP]] ]
  44 ; CHECK-NEXT:    [[I_NEXT]] = add nsw i32 [[I]], 1
  45 ; CHECK-NEXT:    [[I_CMP:%.*]] = icmp slt i32 [[I_NEXT]], [[N:%.*]]
  46 ; CHECK-NEXT:    br i1 [[I_CMP]], label [[LOOP]], label [[EXIT:%.*]]
  47 ; CHECK:       exit:
  48 ; CHECK-NEXT:    [[X_LCSSA:%.*]] = phi i32 [ [[X:%.*]], [[LOOP]] ]
  49 ; CHECK-NEXT:    ret i32 [[X_LCSSA]]
  50 ;
  51 entry:
  52   br label %loop
  53
  54 loop:
  55   %i = phi i32 [ 0, %entry ], [ %i.next, %loop ]
  56   %x.loop = phi i32 [ %x, %entry ], [ %x.next, %loop ]
  57   %x.next = add nsw i32 %x.loop, 0
  58   %i.next = add nsw i32 %i, 1
  59   %i.cmp = icmp slt i32 %i.next, %n
  60   br i1 %i.cmp, label %loop, label %exit
  61
  62 exit:
  63   %x.lcssa = phi i32 [ %x.loop, %loop ]
  64   ret i32 %x.lcssa
  65 }
  66
  67 ; Test a diamond CFG with inner PHI nodes.
  68 define i32 @test3(i32 %n, i32 %x) {
  69 ; CHECK-LABEL: @test3(
  70 ; CHECK-NEXT:  entry:
  71 ; CHECK-NEXT:    br label [[LOOP:%.*]]
  72 ; CHECK:       loop:
  73 ; CHECK-NEXT:    [[I:%.*]] = phi i32 [ 0, [[ENTRY:%.*]] ], [ [[I_NEXT:%.*]], [[LOOP_LATCH:%.*]] ]
  74 ; CHECK-NEXT:    [[X_CMP:%.*]] = icmp slt i32 [[I]], 42
  75 ; CHECK-NEXT:    br i1 [[X_CMP]], label [[LOOP_LHS:%.*]], label [[LOOP_RHS:%.*]]
  76 ; CHECK:       loop.lhs:
  77 ; CHECK-NEXT:    br label [[LOOP_LATCH]]
  78 ; CHECK:       loop.rhs:
  79 ; CHECK-NEXT:    br label [[LOOP_LATCH]]
  80 ; CHECK:       loop.latch:
  81 ; CHECK-NEXT:    [[I_NEXT]] = add nsw i32 [[I]], 1
  82 ; CHECK-NEXT:    [[I_CMP:%.*]] = icmp slt i32 [[I_NEXT]], [[N:%.*]]
  83 ; CHECK-NEXT:    br i1 [[I_CMP]], label [[LOOP]], label [[EXIT:%.*]]
  84 ; CHECK:       exit:
  85 ; CHECK-NEXT:    [[X_LCSSA:%.*]] = phi i32 [ [[X:%.*]], [[LOOP_LATCH]] ]
  86 ; CHECK-NEXT:    ret i32 [[X_LCSSA]]
  87 ;
  88 entry:
  89   br label %loop
  90
  91 loop:
  92   %i = phi i32 [ 0, %entry ], [ %i.next, %loop.latch ]
  93   %x.loop = phi i32 [ %x, %entry ], [ %x.phi, %loop.latch ]
  94   %x.add = add nsw i32 %x.loop, 0
  95   %x.cmp = icmp slt i32 %i, 42
  96   br i1 %x.cmp, label %loop.lhs, label %loop.rhs
  97
  98 loop.lhs:
  99   %x.l.add = add nsw i32 %x.add, 0
 100   br label %loop.latch
 101
 102 loop.rhs:
 103   %x.r.sub = sub nsw i32 %x.add, 0
 104   br label %loop.latch
 105
 106 loop.latch:
 107   %x.phi = phi i32 [ %x.l.add, %loop.lhs ], [ %x.r.sub, %loop.rhs ]
 108   %i.next = add nsw i32 %i, 1
 109   %i.cmp = icmp slt i32 %i.next, %n
 110   br i1 %i.cmp, label %loop, label %exit
 111
 112 exit:
 113   %x.lcssa = phi i32 [ %x.loop, %loop.latch ]
 114   ret i32 %x.lcssa
 115 }
 116
 117 ; Test an inner loop that is only simplified when processing the outer loop, and
 118 ; an outer loop only simplified when processing the inner loop.
 119 define i32 @test4(i32 %n, i32 %m, i32 %x) {
 120 ; CHECK-LABEL: @test4(
 121 ; CHECK-NEXT:  entry:
 122 ; CHECK-NEXT:    br label [[LOOP:%.*]]
 123 ; CHECK:       loop:
 124 ; CHECK-NEXT:    [[I:%.*]] = phi i32 [ 0, [[ENTRY:%.*]] ], [ [[I_NEXT:%.*]], [[LOOP_LATCH:%.*]] ]
 125 ; CHECK-NEXT:    br label [[LOOP_INNER:%.*]]
 126 ; CHECK:       loop.inner:
 127 ; CHECK-NEXT:    [[J:%.*]] = phi i32 [ 0, [[LOOP]] ], [ [[J_NEXT:%.*]], [[LOOP_INNER]] ]
 128 ; CHECK-NEXT:    [[J_NEXT]] = add nsw i32 [[J]], 1
 129 ; CHECK-NEXT:    [[J_CMP:%.*]] = icmp slt i32 [[J_NEXT]], [[M:%.*]]
 130 ; CHECK-NEXT:    br i1 [[J_CMP]], label [[LOOP_INNER]], label [[LOOP_LATCH]]
 131 ; CHECK:       loop.latch:
 132 ; CHECK-NEXT:    [[I_NEXT]] = add nsw i32 [[I]], 1
 133 ; CHECK-NEXT:    [[I_CMP:%.*]] = icmp slt i32 [[I_NEXT]], [[N:%.*]]
 134 ; CHECK-NEXT:    br i1 [[I_CMP]], label [[LOOP]], label [[EXIT:%.*]]
 135 ; CHECK:       exit:
 136 ; CHECK-NEXT:    [[X_LCSSA:%.*]] = phi i32 [ [[X:%.*]], [[LOOP_LATCH]] ]
 137 ; CHECK-NEXT:    ret i32 [[X_LCSSA]]
 138 ;
 139 entry:
 140   br label %loop
 141
 142 loop:
 143   %i = phi i32 [ 0, %entry ], [ %i.next, %loop.latch ]
 144   %x.loop = phi i32 [ %x, %entry ], [ %x.inner.lcssa, %loop.latch ]
 145   %x.add = add nsw i32 %x.loop, 0
 146   br label %loop.inner
 147
 148 loop.inner:
 149   %j = phi i32 [ 0, %loop ], [ %j.next, %loop.inner ]
 150   %x.inner.loop = phi i32 [ %x.add, %loop ], [ %x.inner.add, %loop.inner ]
 151   %x.inner.add = add nsw i32 %x.inner.loop, 0
 152   %j.next = add nsw i32 %j, 1
 153   %j.cmp = icmp slt i32 %j.next, %m
 154   br i1 %j.cmp, label %loop.inner, label %loop.latch
 155
 156 loop.latch:
 157   %x.inner.lcssa = phi i32 [ %x.inner.loop, %loop.inner ]
 158   %i.next = add nsw i32 %i, 1
 159   %i.cmp = icmp slt i32 %i.next, %n
 160   br i1 %i.cmp, label %loop, label %exit
 161
 162 exit:
 163   %x.lcssa = phi i32 [ %x.loop, %loop.latch ]
 164   ret i32 %x.lcssa
 165 }