llvm/test/Transforms/InstCombine/sink_instruction.ll

   1 ; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
   2 ; RUN: opt -passes=instcombine -S < %s | FileCheck %s
   3
   4 ;; This tests that the instructions in the entry blocks are sunk into each
   5 ;; arm of the 'if'.
   6
   7 define i32 @test1(i1 %C, i32 %A, i32 %B) {
   8 ; CHECK-LABEL: @test1(
   9 ; CHECK-NEXT:  entry:
  10 ; CHECK-NEXT:    br i1 [[C:%.*]], label [[THEN:%.*]], label [[ENDIF:%.*]]
  11 ; CHECK:       then:
  12 ; CHECK-NEXT:    [[TMP_9:%.*]] = add i32 [[B:%.*]], [[A:%.*]]
  13 ; CHECK-NEXT:    ret i32 [[TMP_9]]
  14 ; CHECK:       endif:
  15 ; CHECK-NEXT:    [[TMP_2:%.*]] = sdiv i32 [[A]], [[B]]
  16 ; CHECK-NEXT:    ret i32 [[TMP_2]]
  17 ;
  18 entry:
  19   %tmp.2 = sdiv i32 %A, %B                ; <i32> [#uses=1]
  20   %tmp.9 = add i32 %B, %A         ; <i32> [#uses=1]
  21   br i1 %C, label %then, label %endif
  22
  23 then:           ; preds = %entry
  24   ret i32 %tmp.9
  25
  26 endif:          ; preds = %entry
  27   ret i32 %tmp.2
  28 }
  29
  30 ; We fail to reach a fixpoint, because sunk instructions get revisited too
  31 ; early. In @test2 the sunk add is revisited before the dominating condition
  32 ; is visited and added to the DomConditionCache.
  33
  34 ;; PHI use, sink divide before call.
  35 define i32 @test2(i32 %x) nounwind ssp "instcombine-no-verify-fixpoint" {
  36 ; CHECK-LABEL: @test2(
  37 ; CHECK-NEXT:  entry:
  38 ; CHECK-NEXT:    br label [[BB:%.*]]
  39 ; CHECK:       bb:
  40 ; CHECK-NEXT:    [[X_ADDR_17:%.*]] = phi i32 [ [[X:%.*]], [[ENTRY:%.*]] ], [ [[X_ADDR_0:%.*]], [[BB2:%.*]] ]
  41 ; CHECK-NEXT:    [[I_06:%.*]] = phi i32 [ 0, [[ENTRY]] ], [ [[TMP4:%.*]], [[BB2]] ]
  42 ; CHECK-NEXT:    [[TMP0:%.*]] = icmp eq i32 [[X_ADDR_17]], 0
  43 ; CHECK-NEXT:    br i1 [[TMP0]], label [[BB1:%.*]], label [[BB2]]
  44 ; CHECK:       bb1:
  45 ; CHECK-NEXT:    [[TMP1:%.*]] = add nsw i32 [[X_ADDR_17]], 1
  46 ; CHECK-NEXT:    [[TMP2:%.*]] = sdiv i32 [[TMP1]], [[X_ADDR_17]]
  47 ; CHECK-NEXT:    [[TMP3:%.*]] = tail call i32 @bar() #[[ATTR3:[0-9]+]]
  48 ; CHECK-NEXT:    br label [[BB2]]
  49 ; CHECK:       bb2:
  50 ; CHECK-NEXT:    [[X_ADDR_0]] = phi i32 [ [[TMP2]], [[BB1]] ], [ [[X_ADDR_17]], [[BB]] ]
  51 ; CHECK-NEXT:    [[TMP4]] = add nuw nsw i32 [[I_06]], 1
  52 ; CHECK-NEXT:    [[EXITCOND:%.*]] = icmp eq i32 [[TMP4]], 1000000
  53 ; CHECK-NEXT:    br i1 [[EXITCOND]], label [[BB4:%.*]], label [[BB]]
  54 ; CHECK:       bb4:
  55 ; CHECK-NEXT:    ret i32 [[X_ADDR_0]]
  56 ;
  57 entry:
  58   br label %bb
  59
  60 bb:                                               ; preds = %bb2, %entry
  61   %x_addr.17 = phi i32 [ %x, %entry ], [ %x_addr.0, %bb2 ] ; <i32> [#uses=4]
  62   %i.06 = phi i32 [ 0, %entry ], [ %4, %bb2 ]     ; <i32> [#uses=1]
  63   %0 = add nsw i32 %x_addr.17, 1                  ; <i32> [#uses=1]
  64   %1 = sdiv i32 %0, %x_addr.17                    ; <i32> [#uses=1]
  65   %2 = icmp eq i32 %x_addr.17, 0                  ; <i1> [#uses=1]
  66   br i1 %2, label %bb1, label %bb2
  67
  68 bb1:                                              ; preds = %bb
  69   %3 = tail call i32 @bar() nounwind       ; <i32> [#uses=0]
  70   br label %bb2
  71
  72 bb2:                                              ; preds = %bb, %bb1
  73   %x_addr.0 = phi i32 [ %1, %bb1 ], [ %x_addr.17, %bb ] ; <i32> [#uses=2]
  74   %4 = add nsw i32 %i.06, 1                       ; <i32> [#uses=2]
  75   %exitcond = icmp eq i32 %4, 1000000             ; <i1> [#uses=1]
  76   br i1 %exitcond, label %bb4, label %bb
  77
  78 bb4:                                              ; preds = %bb2
  79   ret i32 %x_addr.0
  80 }
  81
  82 declare i32 @bar()
  83
  84 define i32 @test3(ptr nocapture readonly %P, i32 %i) {
  85 ; CHECK-LABEL: @test3(
  86 ; CHECK-NEXT:  entry:
  87 ; CHECK-NEXT:    switch i32 [[I:%.*]], label [[SW_EPILOG:%.*]] [
  88 ; CHECK-NEXT:      i32 5, label [[SW_BB:%.*]]
  89 ; CHECK-NEXT:      i32 2, label [[SW_BB]]
  90 ; CHECK-NEXT:    ]
  91 ; CHECK:       sw.bb:
  92 ; CHECK-NEXT:    [[IDXPROM:%.*]] = sext i32 [[I]] to i64
  93 ; CHECK-NEXT:    [[ARRAYIDX:%.*]] = getelementptr inbounds i32, ptr [[P:%.*]], i64 [[IDXPROM]]
  94 ; CHECK-NEXT:    [[TMP0:%.*]] = load i32, ptr [[ARRAYIDX]], align 4
  95 ; CHECK-NEXT:    [[ADD:%.*]] = add nsw i32 [[TMP0]], [[I]]
  96 ; CHECK-NEXT:    br label [[SW_EPILOG]]
  97 ; CHECK:       sw.epilog:
  98 ; CHECK-NEXT:    [[SUM_0:%.*]] = phi i32 [ [[ADD]], [[SW_BB]] ], [ 0, [[ENTRY:%.*]] ]
  99 ; CHECK-NEXT:    ret i32 [[SUM_0]]
 100 ;
 101 entry:
 102   %idxprom = sext i32 %i to i64
 103   %arrayidx = getelementptr inbounds i32, ptr %P, i64 %idxprom
 104   %0 = load i32, ptr %arrayidx, align 4
 105   switch i32 %i, label %sw.epilog [
 106   i32 5, label %sw.bb
 107   i32 2, label %sw.bb
 108   ]
 109
 110 sw.bb:                                            ; preds = %entry, %entry
 111   %add = add nsw i32 %0, %i
 112   br label %sw.epilog
 113
 114 sw.epilog:                                        ; preds = %entry, %sw.bb
 115   %sum.0 = phi i32 [ %add, %sw.bb ], [ 0, %entry ]
 116   ret i32 %sum.0
 117 }
 118
 119 declare i32 @foo(i32, i32)
 120 ; Two uses in a single user. We can still sink the instruction (tmp.9).
 121 define i32 @test4(i32 %A, i32 %B, i1 %C) {
 122 ; CHECK-LABEL: @test4(
 123 ; CHECK-NEXT:  entry:
 124 ; CHECK-NEXT:    br i1 [[C:%.*]], label [[THEN:%.*]], label [[ENDIF:%.*]]
 125 ; CHECK:       then:
 126 ; CHECK-NEXT:    [[TMP_9:%.*]] = add i32 [[B:%.*]], [[A:%.*]]
 127 ; CHECK-NEXT:    [[RES:%.*]] = call i32 @foo(i32 [[TMP_9]], i32 [[TMP_9]])
 128 ; CHECK-NEXT:    ret i32 [[RES]]
 129 ; CHECK:       endif:
 130 ; CHECK-NEXT:    [[TMP_2:%.*]] = sdiv i32 [[A]], [[B]]
 131 ; CHECK-NEXT:    ret i32 [[TMP_2]]
 132 ;
 133 entry:
 134   %tmp.2 = sdiv i32 %A, %B                ; <i32> [#uses=1]
 135   %tmp.9 = add i32 %B, %A         ; <i32> [#uses=1]
 136   br i1 %C, label %then, label %endif
 137
 138 then:           ; preds = %entry
 139   %res = call i32 @foo(i32  %tmp.9, i32 %tmp.9)
 140   ret i32 %res
 141
 142 endif:          ; preds = %entry
 143   ret i32 %tmp.2
 144 }
 145
 146 ; Two uses in a single user (phi node). We just bail out.
 147 define i32 @test5(ptr nocapture readonly %P, i32 %i, i1 %cond) {
 148 ; CHECK-LABEL: @test5(
 149 ; CHECK-NEXT:  entry:
 150 ; CHECK-NEXT:    [[IDXPROM:%.*]] = sext i32 [[I:%.*]] to i64
 151 ; CHECK-NEXT:    [[ARRAYIDX:%.*]] = getelementptr inbounds i32, ptr [[P:%.*]], i64 [[IDXPROM]]
 152 ; CHECK-NEXT:    [[TMP0:%.*]] = load i32, ptr [[ARRAYIDX]], align 4
 153 ; CHECK-NEXT:    br i1 [[COND:%.*]], label [[DISPATCHBB:%.*]], label [[SW_EPILOG:%.*]]
 154 ; CHECK:       dispatchBB:
 155 ; CHECK-NEXT:    [[ADD:%.*]] = shl nsw i32 [[I]], 1
 156 ; CHECK-NEXT:    br label [[SW_EPILOG]]
 157 ; CHECK:       sw.bb:
 158 ; CHECK-NEXT:    br label [[SW_EPILOG]]
 159 ; CHECK:       sw.epilog:
 160 ; CHECK-NEXT:    [[SUM_0:%.*]] = phi i32 [ [[TMP0]], [[SW_BB:%.*]] ], [ [[ADD]], [[DISPATCHBB]] ], [ [[TMP0]], [[ENTRY:%.*]] ]
 161 ; CHECK-NEXT:    ret i32 [[SUM_0]]
 162 ;
 163 entry:
 164   %idxprom = sext i32 %i to i64
 165   %arrayidx = getelementptr inbounds i32, ptr %P, i64 %idxprom
 166   %0 = load i32, ptr %arrayidx, align 4
 167   br i1 %cond, label %dispatchBB, label %sw.epilog
 168
 169 dispatchBB:
 170   %add = add nsw i32 %i, %i
 171   br label %sw.epilog
 172
 173 sw.bb:                                            ; preds = %entry, %entry
 174   br label %sw.epilog
 175
 176 sw.epilog:                                        ; preds = %entry, %sw.bb
 177   %sum.0 = phi i32 [ %0, %sw.bb ], [ %add, %dispatchBB ], [ %0, %entry ]
 178   ret i32 %sum.0
 179 }
 180
 181 ; Multiple uses but from same BB. We can sink.
 182 define i32 @test6(ptr nocapture readonly %P, i32 %i, i1 %cond) {
 183 ; CHECK-LABEL: @test6(
 184 ; CHECK-NEXT:  entry:
 185 ; CHECK-NEXT:    [[ADD:%.*]] = shl nsw i32 [[I:%.*]], 1
 186 ; CHECK-NEXT:    br label [[DISPATCHBB:%.*]]
 187 ; CHECK:       dispatchBB:
 188 ; CHECK-NEXT:    [[IDXPROM:%.*]] = sext i32 [[I]] to i64
 189 ; CHECK-NEXT:    [[ARRAYIDX:%.*]] = getelementptr inbounds i32, ptr [[P:%.*]], i64 [[IDXPROM]]
 190 ; CHECK-NEXT:    [[TMP0:%.*]] = load i32, ptr [[ARRAYIDX]], align 4
 191 ; CHECK-NEXT:    switch i32 [[I]], label [[SW_BB:%.*]] [
 192 ; CHECK-NEXT:      i32 5, label [[SW_EPILOG:%.*]]
 193 ; CHECK-NEXT:      i32 2, label [[SW_EPILOG]]
 194 ; CHECK-NEXT:    ]
 195 ; CHECK:       sw.bb:
 196 ; CHECK-NEXT:    br label [[SW_EPILOG]]
 197 ; CHECK:       sw.epilog:
 198 ; CHECK-NEXT:    [[SUM_0:%.*]] = phi i32 [ [[ADD]], [[SW_BB]] ], [ [[TMP0]], [[DISPATCHBB]] ], [ [[TMP0]], [[DISPATCHBB]] ]
 199 ; CHECK-NEXT:    ret i32 [[SUM_0]]
 200 ;
 201 entry:
 202   %idxprom = sext i32 %i to i64
 203   %arrayidx = getelementptr inbounds i32, ptr %P, i64 %idxprom
 204   %0 = load i32, ptr %arrayidx, align 4
 205   %add = add nsw i32 %i, %i
 206   br label %dispatchBB
 207
 208 dispatchBB:
 209   switch i32 %i, label %sw.bb [
 210   i32 5, label %sw.epilog
 211   i32 2, label %sw.epilog
 212   ]
 213
 214 sw.bb:                                            ; preds = %entry, %entry
 215   br label %sw.epilog
 216
 217 sw.epilog:                                        ; preds = %entry, %sw.bb
 218   %sum.0 = phi i32 [ %add, %sw.bb ], [ %0, %dispatchBB ], [ %0, %dispatchBB ]
 219   ret i32 %sum.0
 220 }
 221
 222 declare void @checkd(double)
 223 declare double @log(double) willreturn nounwind readnone
 224 define void @test7(i1 %cond, double %d) {
 225 ; CHECK-LABEL: @test7(
 226 ; CHECK-NEXT:    br i1 [[COND:%.*]], label [[IF:%.*]], label [[ELSE:%.*]]
 227 ; CHECK:       if:
 228 ; CHECK-NEXT:    [[A:%.*]] = call double @log(double [[D:%.*]])
 229 ; CHECK-NEXT:    call void @checkd(double [[A]])
 230 ; CHECK-NEXT:    ret void
 231 ; CHECK:       else:
 232 ; CHECK-NEXT:    ret void
 233 ;
 234   %A = call double @log(double %d)
 235   br i1 %cond, label %if, label %else
 236
 237 if:
 238   call void @checkd(double %A)
 239   ret void
 240 else:
 241   ret void
 242 }
 243
 244 declare void @abort()
 245 declare { i64, i1 } @llvm.umul.with.overflow.i64(i64, i64)
 246 declare void @dummy(i64)
 247 ; Two uses in two different users of a single successor block. We can sink.
 248 define i64 @test8(i64 %c) {
 249 ; CHECK-LABEL: @test8(
 250 ; CHECK-NEXT:  bb1:
 251 ; CHECK-NEXT:    [[OVERFLOW:%.*]] = icmp ugt i64 [[C:%.*]], 2305843009213693951
 252 ; CHECK-NEXT:    br i1 [[OVERFLOW]], label [[ABORT:%.*]], label [[BB2:%.*]]
 253 ; CHECK:       bb2:
 254 ; CHECK-NEXT:    call void @dummy(i64 8)
 255 ; CHECK-NEXT:    ret i64 8
 256 ; CHECK:       abort:
 257 ; CHECK-NEXT:    call void @abort()
 258 ; CHECK-NEXT:    unreachable
 259 ;
 260 bb1:
 261   %mul = tail call { i64, i1 } @llvm.umul.with.overflow.i64(i64 %c, i64 8)
 262   %overflow = extractvalue { i64, i1 } %mul, 1
 263   %select = select i1 %overflow, i64 0, i64 8
 264   br i1 %overflow, label %abort, label %bb2
 265
 266 bb2:
 267   call void @dummy(i64 %select)
 268   ret i64 %select
 269
 270 abort:
 271   call void @abort()
 272   unreachable
 273 }
 274
 275 ; Loads marked invariant can be sunk past potential memory writes.
 276
 277 define i32 @invariant_load_metadata(ptr %p, i1 %cond) {
 278 ; CHECK-LABEL: @invariant_load_metadata(
 279 ; CHECK-NEXT:  entry:
 280 ; CHECK-NEXT:    br i1 [[COND:%.*]], label [[BLOCK:%.*]], label [[END:%.*]]
 281 ; CHECK:       block:
 282 ; CHECK-NEXT:    call void @fn()
 283 ; CHECK-NEXT:    br label [[END]]
 284 ; CHECK:       end:
 285 ; CHECK-NEXT:    [[V:%.*]] = load i32, ptr [[P:%.*]], align 4, !invariant.load [[META0:![0-9]+]]
 286 ; CHECK-NEXT:    ret i32 [[V]]
 287 ;
 288 entry:
 289   %v = load i32, ptr %p, !invariant.load !0
 290   br i1 %cond, label %block, label %end
 291 block:
 292   call void @fn()
 293   br label %end
 294 end:
 295   ret i32 %v
 296 }
 297
 298 ; Loads not marked invariant cannot be sunk past potential memory writes.
 299
 300 define i32 @invariant_load_neg(ptr %p, i1 %cond) {
 301 ; CHECK-LABEL: @invariant_load_neg(
 302 ; CHECK-NEXT:  entry:
 303 ; CHECK-NEXT:    [[V:%.*]] = load i32, ptr [[P:%.*]], align 4
 304 ; CHECK-NEXT:    br i1 [[COND:%.*]], label [[BLOCK:%.*]], label [[END:%.*]]
 305 ; CHECK:       block:
 306 ; CHECK-NEXT:    call void @fn()
 307 ; CHECK-NEXT:    br label [[END]]
 308 ; CHECK:       end:
 309 ; CHECK-NEXT:    ret i32 [[V]]
 310 ;
 311 entry:
 312   %v = load i32, ptr %p
 313   br i1 %cond, label %block, label %end
 314 block:
 315   call void @fn()
 316   br label %end
 317 end:
 318   ret i32 %v
 319 }
 320
 321 ; Loads that aren't marked invariant but used in one branch
 322 ; can be sunk to that branch.
 323
 324 define void @invariant_load_use_in_br(ptr %p, i1 %cond) {
 325 ; CHECK-LABEL: @invariant_load_use_in_br(
 326 ; CHECK-NEXT:  entry:
 327 ; CHECK-NEXT:    br i1 [[COND:%.*]], label [[TRUE_BR:%.*]], label [[FALSE_BR:%.*]]
 328 ; CHECK:       true.br:
 329 ; CHECK-NEXT:    call void @fn()
 330 ; CHECK-NEXT:    br label [[EXIT:%.*]]
 331 ; CHECK:       false.br:
 332 ; CHECK-NEXT:    [[VAL:%.*]] = load i32, ptr [[P:%.*]], align 4
 333 ; CHECK-NEXT:    call void @fn(i32 [[VAL]])
 334 ; CHECK-NEXT:    br label [[EXIT]]
 335 ; CHECK:       exit:
 336 ; CHECK-NEXT:    ret void
 337 ;
 338 entry:
 339   %val = load i32, ptr %p
 340   br i1 %cond, label %true.br, label %false.br
 341 true.br:
 342   call void @fn()
 343   br label %exit
 344 false.br:
 345   call void @fn(i32 %val)
 346   br label %exit
 347 exit:
 348   ret void
 349 }
 350
 351 ; Invariant loads marked with metadata can be sunk past calls.
 352
 353 define void @invariant_load_metadata_call(ptr %p, i1 %cond) {
 354 ; CHECK-LABEL: @invariant_load_metadata_call(
 355 ; CHECK-NEXT:  entry:
 356 ; CHECK-NEXT:    call void @fn()
 357 ; CHECK-NEXT:    br i1 [[COND:%.*]], label [[TRUE_BR:%.*]], label [[FALSE_BR:%.*]]
 358 ; CHECK:       true.br:
 359 ; CHECK-NEXT:    call void @fn()
 360 ; CHECK-NEXT:    br label [[EXIT:%.*]]
 361 ; CHECK:       false.br:
 362 ; CHECK-NEXT:    [[VAL:%.*]] = load i32, ptr [[P:%.*]], align 4, !invariant.load [[META0]]
 363 ; CHECK-NEXT:    call void @fn(i32 [[VAL]])
 364 ; CHECK-NEXT:    br label [[EXIT]]
 365 ; CHECK:       exit:
 366 ; CHECK-NEXT:    ret void
 367 ;
 368 entry:
 369   %val = load i32, ptr %p, !invariant.load !0
 370   call void @fn()
 371   br i1 %cond, label %true.br, label %false.br
 372 true.br:
 373   call void @fn()
 374   br label %exit
 375 false.br:
 376   call void @fn(i32 %val)
 377   br label %exit
 378 exit:
 379   ret void
 380 }
 381
 382 declare void @fn()
 383
 384 !0 = !{}