llvm/test/Transforms/InstCombine/sink_instruction.ll

   1 ; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
   2 ; RUN: opt -passes='instcombine<no-verify-fixpoint>' -S < %s | FileCheck %s
   3
   4 ; We fail to reach a fixpoint, because sunk instructions get revisited too
   5 ; early. In @test2 the sunk add is revisited before the dominating condition
   6 ; is visited and added to the DomConditionCache.
   7
   8 ;; This tests that the instructions in the entry blocks are sunk into each
   9 ;; arm of the 'if'.
  10
  11 define i32 @test1(i1 %C, i32 %A, i32 %B) {
  12 ; CHECK-LABEL: @test1(
  13 ; CHECK-NEXT:  entry:
  14 ; CHECK-NEXT:    br i1 [[C:%.*]], label [[THEN:%.*]], label [[ENDIF:%.*]]
  15 ; CHECK:       then:
  16 ; CHECK-NEXT:    [[TMP_9:%.*]] = add i32 [[B:%.*]], [[A:%.*]]
  17 ; CHECK-NEXT:    ret i32 [[TMP_9]]
  18 ; CHECK:       endif:
  19 ; CHECK-NEXT:    [[TMP_2:%.*]] = sdiv i32 [[A]], [[B]]
  20 ; CHECK-NEXT:    ret i32 [[TMP_2]]
  21 ;
  22 entry:
  23   %tmp.2 = sdiv i32 %A, %B                ; <i32> [#uses=1]
  24   %tmp.9 = add i32 %B, %A         ; <i32> [#uses=1]
  25   br i1 %C, label %then, label %endif
  26
  27 then:           ; preds = %entry
  28   ret i32 %tmp.9
  29
  30 endif:          ; preds = %entry
  31   ret i32 %tmp.2
  32 }
  33
  34
  35 ;; PHI use, sink divide before call.
  36 define i32 @test2(i32 %x) nounwind ssp {
  37 ; CHECK-LABEL: @test2(
  38 ; CHECK-NEXT:  entry:
  39 ; CHECK-NEXT:    br label [[BB:%.*]]
  40 ; CHECK:       bb:
  41 ; CHECK-NEXT:    [[X_ADDR_17:%.*]] = phi i32 [ [[X:%.*]], [[ENTRY:%.*]] ], [ [[X_ADDR_0:%.*]], [[BB2:%.*]] ]
  42 ; CHECK-NEXT:    [[I_06:%.*]] = phi i32 [ 0, [[ENTRY]] ], [ [[TMP4:%.*]], [[BB2]] ]
  43 ; CHECK-NEXT:    [[TMP0:%.*]] = icmp eq i32 [[X_ADDR_17]], 0
  44 ; CHECK-NEXT:    br i1 [[TMP0]], label [[BB1:%.*]], label [[BB2]]
  45 ; CHECK:       bb1:
  46 ; CHECK-NEXT:    [[TMP1:%.*]] = add nsw i32 [[X_ADDR_17]], 1
  47 ; CHECK-NEXT:    [[TMP2:%.*]] = sdiv i32 [[TMP1]], [[X_ADDR_17]]
  48 ; CHECK-NEXT:    [[TMP3:%.*]] = tail call i32 @bar() #[[ATTR3:[0-9]+]]
  49 ; CHECK-NEXT:    br label [[BB2]]
  50 ; CHECK:       bb2:
  51 ; CHECK-NEXT:    [[X_ADDR_0]] = phi i32 [ [[TMP2]], [[BB1]] ], [ [[X_ADDR_17]], [[BB]] ]
  52 ; CHECK-NEXT:    [[TMP4]] = add nuw nsw i32 [[I_06]], 1
  53 ; CHECK-NEXT:    [[EXITCOND:%.*]] = icmp eq i32 [[TMP4]], 1000000
  54 ; CHECK-NEXT:    br i1 [[EXITCOND]], label [[BB4:%.*]], label [[BB]]
  55 ; CHECK:       bb4:
  56 ; CHECK-NEXT:    ret i32 [[X_ADDR_0]]
  57 ;
  58 entry:
  59   br label %bb
  60
  61 bb:                                               ; preds = %bb2, %entry
  62   %x_addr.17 = phi i32 [ %x, %entry ], [ %x_addr.0, %bb2 ] ; <i32> [#uses=4]
  63   %i.06 = phi i32 [ 0, %entry ], [ %4, %bb2 ]     ; <i32> [#uses=1]
  64   %0 = add nsw i32 %x_addr.17, 1                  ; <i32> [#uses=1]
  65   %1 = sdiv i32 %0, %x_addr.17                    ; <i32> [#uses=1]
  66   %2 = icmp eq i32 %x_addr.17, 0                  ; <i1> [#uses=1]
  67   br i1 %2, label %bb1, label %bb2
  68
  69 bb1:                                              ; preds = %bb
  70   %3 = tail call i32 @bar() nounwind       ; <i32> [#uses=0]
  71   br label %bb2
  72
  73 bb2:                                              ; preds = %bb, %bb1
  74   %x_addr.0 = phi i32 [ %1, %bb1 ], [ %x_addr.17, %bb ] ; <i32> [#uses=2]
  75   %4 = add nsw i32 %i.06, 1                       ; <i32> [#uses=2]
  76   %exitcond = icmp eq i32 %4, 1000000             ; <i1> [#uses=1]
  77   br i1 %exitcond, label %bb4, label %bb
  78
  79 bb4:                                              ; preds = %bb2
  80   ret i32 %x_addr.0
  81 }
  82
  83 declare i32 @bar()
  84
  85 define i32 @test3(ptr nocapture readonly %P, i32 %i) {
  86 ; CHECK-LABEL: @test3(
  87 ; CHECK-NEXT:  entry:
  88 ; CHECK-NEXT:    switch i32 [[I:%.*]], label [[SW_EPILOG:%.*]] [
  89 ; CHECK-NEXT:    i32 5, label [[SW_BB:%.*]]
  90 ; CHECK-NEXT:    i32 2, label [[SW_BB]]
  91 ; CHECK-NEXT:    ]
  92 ; CHECK:       sw.bb:
  93 ; CHECK-NEXT:    [[IDXPROM:%.*]] = sext i32 [[I]] to i64
  94 ; CHECK-NEXT:    [[ARRAYIDX:%.*]] = getelementptr inbounds i32, ptr [[P:%.*]], i64 [[IDXPROM]]
  95 ; CHECK-NEXT:    [[TMP0:%.*]] = load i32, ptr [[ARRAYIDX]], align 4
  96 ; CHECK-NEXT:    [[ADD:%.*]] = add nsw i32 [[TMP0]], [[I]]
  97 ; CHECK-NEXT:    br label [[SW_EPILOG]]
  98 ; CHECK:       sw.epilog:
  99 ; CHECK-NEXT:    [[SUM_0:%.*]] = phi i32 [ [[ADD]], [[SW_BB]] ], [ 0, [[ENTRY:%.*]] ]
 100 ; CHECK-NEXT:    ret i32 [[SUM_0]]
 101 ;
 102 entry:
 103   %idxprom = sext i32 %i to i64
 104   %arrayidx = getelementptr inbounds i32, ptr %P, i64 %idxprom
 105   %0 = load i32, ptr %arrayidx, align 4
 106   switch i32 %i, label %sw.epilog [
 107   i32 5, label %sw.bb
 108   i32 2, label %sw.bb
 109   ]
 110
 111 sw.bb:                                            ; preds = %entry, %entry
 112   %add = add nsw i32 %0, %i
 113   br label %sw.epilog
 114
 115 sw.epilog:                                        ; preds = %entry, %sw.bb
 116   %sum.0 = phi i32 [ %add, %sw.bb ], [ 0, %entry ]
 117   ret i32 %sum.0
 118 }
 119
 120 declare i32 @foo(i32, i32)
 121 ; Two uses in a single user. We can still sink the instruction (tmp.9).
 122 define i32 @test4(i32 %A, i32 %B, i1 %C) {
 123 ; CHECK-LABEL: @test4(
 124 ; CHECK-NEXT:  entry:
 125 ; CHECK-NEXT:    br i1 [[C:%.*]], label [[THEN:%.*]], label [[ENDIF:%.*]]
 126 ; CHECK:       then:
 127 ; CHECK-NEXT:    [[TMP_9:%.*]] = add i32 [[B:%.*]], [[A:%.*]]
 128 ; CHECK-NEXT:    [[RES:%.*]] = call i32 @foo(i32 [[TMP_9]], i32 [[TMP_9]])
 129 ; CHECK-NEXT:    ret i32 [[RES]]
 130 ; CHECK:       endif:
 131 ; CHECK-NEXT:    [[TMP_2:%.*]] = sdiv i32 [[A]], [[B]]
 132 ; CHECK-NEXT:    ret i32 [[TMP_2]]
 133 ;
 134 entry:
 135   %tmp.2 = sdiv i32 %A, %B                ; <i32> [#uses=1]
 136   %tmp.9 = add i32 %B, %A         ; <i32> [#uses=1]
 137   br i1 %C, label %then, label %endif
 138
 139 then:           ; preds = %entry
 140   %res = call i32 @foo(i32  %tmp.9, i32 %tmp.9)
 141   ret i32 %res
 142
 143 endif:          ; preds = %entry
 144   ret i32 %tmp.2
 145 }
 146
 147 ; Two uses in a single user (phi node). We just bail out.
 148 define i32 @test5(ptr nocapture readonly %P, i32 %i, i1 %cond) {
 149 ; CHECK-LABEL: @test5(
 150 ; CHECK-NEXT:  entry:
 151 ; CHECK-NEXT:    [[IDXPROM:%.*]] = sext i32 [[I:%.*]] to i64
 152 ; CHECK-NEXT:    [[ARRAYIDX:%.*]] = getelementptr inbounds i32, ptr [[P:%.*]], i64 [[IDXPROM]]
 153 ; CHECK-NEXT:    [[TMP0:%.*]] = load i32, ptr [[ARRAYIDX]], align 4
 154 ; CHECK-NEXT:    br i1 [[COND:%.*]], label [[DISPATCHBB:%.*]], label [[SW_EPILOG:%.*]]
 155 ; CHECK:       dispatchBB:
 156 ; CHECK-NEXT:    [[ADD:%.*]] = shl nsw i32 [[I]], 1
 157 ; CHECK-NEXT:    br label [[SW_EPILOG]]
 158 ; CHECK:       sw.bb:
 159 ; CHECK-NEXT:    br label [[SW_EPILOG]]
 160 ; CHECK:       sw.epilog:
 161 ; CHECK-NEXT:    [[SUM_0:%.*]] = phi i32 [ [[TMP0]], [[SW_BB:%.*]] ], [ [[ADD]], [[DISPATCHBB]] ], [ [[TMP0]], [[ENTRY:%.*]] ]
 162 ; CHECK-NEXT:    ret i32 [[SUM_0]]
 163 ;
 164 entry:
 165   %idxprom = sext i32 %i to i64
 166   %arrayidx = getelementptr inbounds i32, ptr %P, i64 %idxprom
 167   %0 = load i32, ptr %arrayidx, align 4
 168   br i1 %cond, label %dispatchBB, label %sw.epilog
 169
 170 dispatchBB:
 171   %add = add nsw i32 %i, %i
 172   br label %sw.epilog
 173
 174 sw.bb:                                            ; preds = %entry, %entry
 175   br label %sw.epilog
 176
 177 sw.epilog:                                        ; preds = %entry, %sw.bb
 178   %sum.0 = phi i32 [ %0, %sw.bb ], [ %add, %dispatchBB ], [ %0, %entry ]
 179   ret i32 %sum.0
 180 }
 181
 182 ; Multiple uses but from same BB. We can sink.
 183 define i32 @test6(ptr nocapture readonly %P, i32 %i, i1 %cond) {
 184 ; CHECK-LABEL: @test6(
 185 ; CHECK-NEXT:  entry:
 186 ; CHECK-NEXT:    [[ADD:%.*]] = shl nsw i32 [[I:%.*]], 1
 187 ; CHECK-NEXT:    br label [[DISPATCHBB:%.*]]
 188 ; CHECK:       dispatchBB:
 189 ; CHECK-NEXT:    [[IDXPROM:%.*]] = sext i32 [[I]] to i64
 190 ; CHECK-NEXT:    [[ARRAYIDX:%.*]] = getelementptr inbounds i32, ptr [[P:%.*]], i64 [[IDXPROM]]
 191 ; CHECK-NEXT:    [[TMP0:%.*]] = load i32, ptr [[ARRAYIDX]], align 4
 192 ; CHECK-NEXT:    switch i32 [[I]], label [[SW_BB:%.*]] [
 193 ; CHECK-NEXT:    i32 5, label [[SW_EPILOG:%.*]]
 194 ; CHECK-NEXT:    i32 2, label [[SW_EPILOG]]
 195 ; CHECK-NEXT:    ]
 196 ; CHECK:       sw.bb:
 197 ; CHECK-NEXT:    br label [[SW_EPILOG]]
 198 ; CHECK:       sw.epilog:
 199 ; CHECK-NEXT:    [[SUM_0:%.*]] = phi i32 [ [[ADD]], [[SW_BB]] ], [ [[TMP0]], [[DISPATCHBB]] ], [ [[TMP0]], [[DISPATCHBB]] ]
 200 ; CHECK-NEXT:    ret i32 [[SUM_0]]
 201 ;
 202 entry:
 203   %idxprom = sext i32 %i to i64
 204   %arrayidx = getelementptr inbounds i32, ptr %P, i64 %idxprom
 205   %0 = load i32, ptr %arrayidx, align 4
 206   %add = add nsw i32 %i, %i
 207   br label %dispatchBB
 208
 209 dispatchBB:
 210   switch i32 %i, label %sw.bb [
 211   i32 5, label %sw.epilog
 212   i32 2, label %sw.epilog
 213   ]
 214
 215 sw.bb:                                            ; preds = %entry, %entry
 216   br label %sw.epilog
 217
 218 sw.epilog:                                        ; preds = %entry, %sw.bb
 219   %sum.0 = phi i32 [ %add, %sw.bb ], [ %0, %dispatchBB ], [ %0, %dispatchBB ]
 220   ret i32 %sum.0
 221 }
 222
 223 declare void @checkd(double)
 224 declare double @log(double) willreturn nounwind readnone
 225 define void @test7(i1 %cond, double %d) {
 226 ; CHECK-LABEL: @test7(
 227 ; CHECK-NEXT:    br i1 [[COND:%.*]], label [[IF:%.*]], label [[ELSE:%.*]]
 228 ; CHECK:       if:
 229 ; CHECK-NEXT:    [[A:%.*]] = call double @log(double [[D:%.*]])
 230 ; CHECK-NEXT:    call void @checkd(double [[A]])
 231 ; CHECK-NEXT:    ret void
 232 ; CHECK:       else:
 233 ; CHECK-NEXT:    ret void
 234 ;
 235   %A = call double @log(double %d)
 236   br i1 %cond, label %if, label %else
 237
 238 if:
 239   call void @checkd(double %A)
 240   ret void
 241 else:
 242   ret void
 243 }
 244
 245 declare void @abort()
 246 declare { i64, i1 } @llvm.umul.with.overflow.i64(i64, i64)
 247 declare void @dummy(i64)
 248 ; Two uses in two different users of a single successor block. We can sink.
 249 define i64 @test8(i64 %c) {
 250 ; CHECK-LABEL: @test8(
 251 ; CHECK-NEXT:  bb1:
 252 ; CHECK-NEXT:    [[OVERFLOW:%.*]] = icmp ugt i64 [[C:%.*]], 2305843009213693951
 253 ; CHECK-NEXT:    br i1 [[OVERFLOW]], label [[ABORT:%.*]], label [[BB2:%.*]]
 254 ; CHECK:       bb2:
 255 ; CHECK-NEXT:    call void @dummy(i64 8)
 256 ; CHECK-NEXT:    ret i64 8
 257 ; CHECK:       abort:
 258 ; CHECK-NEXT:    call void @abort()
 259 ; CHECK-NEXT:    unreachable
 260 ;
 261 bb1:
 262   %mul = tail call { i64, i1 } @llvm.umul.with.overflow.i64(i64 %c, i64 8)
 263   %overflow = extractvalue { i64, i1 } %mul, 1
 264   %select = select i1 %overflow, i64 0, i64 8
 265   br i1 %overflow, label %abort, label %bb2
 266
 267 bb2:
 268   call void @dummy(i64 %select)
 269   ret i64 %select
 270
 271 abort:
 272   call void @abort()
 273   unreachable
 274 }