llvm/test/Transforms/SimpleLoopUnswitch/exponential-nontrivial-unswitch-nested2.ll

   1 ;
   2 ; Here all the branches we unswitch are exiting from the inner loop.
   3 ; That means we should not be getting exponential behavior on inner-loop
   4 ; unswitch. In fact there should be just a single version of inner-loop,
   5 ; with possibly some outer loop copies.
   6 ;
   7 ; There should be just a single copy of each loop when strictest mutiplier
   8 ; candidates formula (unscaled candidates == 0) is enforced:
   9
  10 ; RUN: opt < %s -enable-unswitch-cost-multiplier=true \
  11 ; RUN:     -unswitch-num-initial-unscaled-candidates=0 -unswitch-siblings-toplevel-div=1 \
  12 ; RUN:     -passes='loop(simple-loop-unswitch<nontrivial>),print<loops>' -disable-output 2>&1 | FileCheck %s --check-prefixes=LOOP1
  13 ;
  14 ; RUN: opt < %s -enable-unswitch-cost-multiplier=true \
  15 ; RUN:     -unswitch-num-initial-unscaled-candidates=0 -unswitch-siblings-toplevel-div=16 \
  16 ; RUN:     -passes='loop(simple-loop-unswitch<nontrivial>),print<loops>' -disable-output 2>&1 | FileCheck %s --check-prefixes=LOOP1
  17 ;
  18 ; RUN: opt < %s -enable-unswitch-cost-multiplier=true \
  19 ; RUN:     -unswitch-num-initial-unscaled-candidates=0 -unswitch-siblings-toplevel-div=1 \
  20 ; RUN:     -passes='loop-mssa(simple-loop-unswitch<nontrivial>),print<loops>' -disable-output 2>&1 | FileCheck %s --check-prefixes=LOOP1
  21 ;
  22 ; RUN: opt < %s -enable-unswitch-cost-multiplier=true \
  23 ; RUN:     -unswitch-num-initial-unscaled-candidates=0 -unswitch-siblings-toplevel-div=16 \
  24 ; RUN:     -passes='loop-mssa(simple-loop-unswitch<nontrivial>),print<loops>' -disable-output 2>&1 | FileCheck %s --check-prefixes=LOOP1
  25 ;
  26 ; When we relax the candidates part of a multiplier formula
  27 ; When we relax the candidates part of a multiplier formula
  28 ; (unscaled candidates == 2) we start getting some unswitches in outer loops,
  29 ; which leads to siblings multiplier kicking in.
  30 ;
  31 ; RUN: opt < %s -enable-unswitch-cost-multiplier=true \
  32 ; RUN:     -unswitch-num-initial-unscaled-candidates=3 -unswitch-siblings-toplevel-div=1 \
  33 ; RUN:     -passes='loop(simple-loop-unswitch<nontrivial>),print<loops>' -disable-output 2>&1 | \
  34 ; RUN:     sort -b -k 1 | FileCheck %s --check-prefixes=LOOP-UNSCALE3-DIV1
  35 ;
  36 ; RUN: opt < %s -enable-unswitch-cost-multiplier=true \
  37 ; RUN:     -unswitch-num-initial-unscaled-candidates=3 -unswitch-siblings-toplevel-div=1 \
  38 ; RUN:     -passes='loop-mssa(simple-loop-unswitch<nontrivial>),print<loops>' -disable-output 2>&1 | \
  39 ; RUN:     sort -b -k 1 | FileCheck %s --check-prefixes=LOOP-UNSCALE3-DIV1
  40 ;
  41 ; NB: sort -b is essential here and below, otherwise blanks might lead to different
  42 ; order depending on locale.
  43 ;
  44 ; RUN: opt < %s -enable-unswitch-cost-multiplier=true \
  45 ; RUN:     -unswitch-num-initial-unscaled-candidates=3 -unswitch-siblings-toplevel-div=2 \
  46 ; RUN:     -passes='loop(simple-loop-unswitch<nontrivial>),print<loops>' -disable-output 2>&1 | \
  47 ; RUN:     sort -b -k 1 | FileCheck %s --check-prefixes=LOOP-UNSCALE3-DIV2
  48 ;
  49 ; RUN: opt < %s -enable-unswitch-cost-multiplier=true \
  50 ; RUN:     -unswitch-num-initial-unscaled-candidates=3 -unswitch-siblings-toplevel-div=2 \
  51 ; RUN:     -passes='loop-mssa(simple-loop-unswitch<nontrivial>),print<loops>' -disable-output 2>&1 | \
  52 ; RUN:     sort -b -k 1 | FileCheck %s --check-prefixes=LOOP-UNSCALE3-DIV2
  53 ;
  54 ; With disabled cost-multiplier we get maximal possible amount of unswitches.
  55 ;
  56 ; RUN: opt < %s -enable-unswitch-cost-multiplier=false \
  57 ; RUN:     -passes='loop(simple-loop-unswitch<nontrivial>),print<loops>' -disable-output 2>&1 | \
  58 ; RUN:     sort -b -k 1 | FileCheck %s --check-prefixes=LOOP-MAX
  59 ;
  60 ; RUN: opt < %s -enable-unswitch-cost-multiplier=false \
  61 ; RUN:     -passes='loop-mssa(simple-loop-unswitch<nontrivial>),print<loops>' -disable-output 2>&1 | \
  62 ; RUN:     sort -b -k 1 | FileCheck %s --check-prefixes=LOOP-MAX
  63 ;
  64 ; Single loop nest, not unswitched
  65 ; LOOP1:     Loop at depth 1 containing:
  66 ; LOOP1-NOT:  Loop at depth 1 containing:
  67 ; LOOP1:     Loop at depth 2 containing:
  68 ; LOOP1-NOT:  Loop at depth 2 containing:
  69 ; LOOP1:     Loop at depth 3 containing:
  70 ; LOOP1-NOT:  Loop at depth 3 containing:
  71 ;
  72 ; Half unswitched loop nests, with unscaled3 and div1 it gets less depth1 loops unswitched
  73 ; since they have more cost.
  74 ; LOOP-UNSCALE3-DIV1-COUNT-4: Loop at depth 1 containing:
  75 ; LOOP-UNSCALE3-DIV1-NOT:      Loop at depth 1 containing:
  76 ; LOOP-UNSCALE3-DIV1-COUNT-1: Loop at depth 2 containing:
  77 ; LOOP-UNSCALE3-DIV1-NOT:      Loop at depth 2 containing:
  78 ; LOOP-UNSCALE3-DIV1-COUNT-1: Loop at depth 3 containing:
  79 ; LOOP-UNSCALE3-DIV1-NOT:      Loop at depth 3 containing:
  80 ;
  81 ; Half unswitched loop nests, with unscaled3 and div2 it gets more depth1 loops unswitched
  82 ; as div2 kicks in.
  83 ; LOOP-UNSCALE3-DIV2-COUNT-6: Loop at depth 1 containing:
  84 ; LOOP-UNSCALE3-DIV2-NOT:      Loop at depth 1 containing:
  85 ; LOOP-UNSCALE3-DIV2-COUNT-1: Loop at depth 2 containing:
  86 ; LOOP-UNSCALE3-DIV2-NOT:      Loop at depth 2 containing:
  87 ; LOOP-UNSCALE3-DIV2-COUNT-1: Loop at depth 3 containing:
  88 ; LOOP-UNSCALE3-DIV2-NOT:      Loop at depth 3 containing:
  89 ;
  90 ; Maximally unswitched (copy of the outer loop per each condition)
  91 ; LOOP-MAX-COUNT-6: Loop at depth 1 containing:
  92 ; LOOP-MAX-NOT:      Loop at depth 1 containing:
  93 ; LOOP-MAX-COUNT-1: Loop at depth 2 containing:
  94 ; LOOP-MAX-NOT:      Loop at depth 2 containing:
  95 ; LOOP-MAX-COUNT-1: Loop at depth 3 containing:
  96 ; LOOP-MAX-NOT:      Loop at depth 3 containing:
  97
  98 declare void @bar()
  99
 100 define void @loop_nested3_conds5(i32* %addr, i1 %c1, i1 %c2, i1 %c3, i1 %c4, i1 %c5) {
 101 entry:
 102   %addr1 = getelementptr i32, i32* %addr, i64 0
 103   %addr2 = getelementptr i32, i32* %addr, i64 1
 104   %addr3 = getelementptr i32, i32* %addr, i64 2
 105   br label %outer
 106 outer:
 107   %iv1 = phi i32 [0, %entry], [%iv1.next, %outer_latch]
 108   %iv1.next = add i32 %iv1, 1
 109   ;; skip nontrivial unswitch
 110   call void @bar()
 111   br label %middle
 112 middle:
 113   %iv2 = phi i32 [0, %outer], [%iv2.next, %middle_latch]
 114   %iv2.next = add i32 %iv2, 1
 115   ;; skip nontrivial unswitch
 116   call void @bar()
 117   br label %loop
 118 loop:
 119   %iv3 = phi i32 [0, %middle], [%iv3.next, %loop_latch]
 120   %iv3.next = add i32 %iv3, 1
 121   ;; skip nontrivial unswitch
 122   call void @bar()
 123   br i1 %c1, label %loop_next1_left, label %outer_latch
 124 loop_next1_left:
 125   br label %loop_next1
 126 loop_next1_right:
 127   br label %loop_next1
 128
 129 loop_next1:
 130   br i1 %c2, label %loop_next2_left, label %outer_latch
 131 loop_next2_left:
 132   br label %loop_next2
 133 loop_next2_right:
 134   br label %loop_next2
 135
 136 loop_next2:
 137   br i1 %c3, label %loop_next3_left, label %outer_latch
 138 loop_next3_left:
 139   br label %loop_next3
 140 loop_next3_right:
 141   br label %loop_next3
 142
 143 loop_next3:
 144   br i1 %c4, label %loop_next4_left, label %outer_latch
 145 loop_next4_left:
 146   br label %loop_next4
 147 loop_next4_right:
 148   br label %loop_next4
 149
 150 loop_next4:
 151   br i1 %c5, label %loop_latch_left, label %outer_latch
 152 loop_latch_left:
 153   br label %loop_latch
 154 loop_latch_right:
 155   br label %loop_latch
 156
 157 loop_latch:
 158   store volatile i32 0, i32* %addr1
 159   %test_loop = icmp slt i32 %iv3, 50
 160   br i1 %test_loop, label %loop, label %middle_latch
 161 middle_latch:
 162   store volatile i32 0, i32* %addr2
 163   %test_middle = icmp slt i32 %iv2, 50
 164   br i1 %test_middle, label %middle, label %outer_latch
 165 outer_latch:
 166   store volatile i32 0, i32* %addr3
 167   %test_outer = icmp slt i32 %iv1, 50
 168   br i1 %test_outer, label %outer, label %exit
 169 exit:
 170   ret void
 171 }