test/CodeGen/X86/move_latch_to_loop_top.ll

   1 ; RUN: llc  -mcpu=corei7 -mtriple=x86_64-linux < %s | FileCheck %s
   2
   3 ; The block latch should be moved before header.
   4 ;CHECK-LABEL: test1:
   5 ;CHECK:       %latch
   6 ;CHECK:       %header
   7 ;CHECK:       %false
   8 define i32 @test1(i32* %p) {
   9 entry:
  10   br label %header
  11
  12 header:
  13   %x1 = phi i64 [0, %entry], [%x2, %latch]
  14   %count1 = phi i32 [0, %entry], [%count4, %latch]
  15   %0 = ptrtoint i32* %p to i64
  16   %1 = add i64 %0, %x1
  17   %2 = inttoptr i64 %1 to i32*
  18   %data = load i32, i32* %2
  19   %3 = icmp eq i32 %data, 0
  20   br i1 %3, label %latch, label %false
  21
  22 false:
  23   %count2 = add i32 %count1, 1
  24   br label %latch
  25
  26 latch:
  27   %count4 = phi i32 [%count2, %false], [%count1, %header]
  28   %x2 = add i64 %x1, 1
  29   %4 = icmp eq i64 %x2, 100
  30   br i1 %4, label %exit, label %header
  31
  32 exit:
  33   ret i32 %count4
  34 }
  35
  36 ; The block latch and one of false/true should be moved before header.
  37 ;CHECK-LABEL: test2:
  38 ;CHECK:       %true
  39 ;CHECK:       %latch
  40 ;CHECK:       %header
  41 ;CHECK:       %false
  42 define i32 @test2(i32* %p) {
  43 entry:
  44   br label %header
  45
  46 header:
  47   %x1 = phi i64 [0, %entry], [%x2, %latch]
  48   %count1 = phi i32 [0, %entry], [%count4, %latch]
  49   %0 = ptrtoint i32* %p to i64
  50   %1 = add i64 %0, %x1
  51   %2 = inttoptr i64 %1 to i32*
  52   %data = load i32, i32* %2
  53   %3 = icmp eq i32 %data, 0
  54   br i1 %3, label %true, label %false
  55
  56 false:
  57   %count2 = add i32 %count1, 1
  58   br label %latch
  59
  60 true:
  61   %count3 = add i32 %count1, 2
  62   br label %latch
  63
  64 latch:
  65   %count4 = phi i32 [%count2, %false], [%count3, %true]
  66   %x2 = add i64 %x1, 1
  67   %4 = icmp eq i64 %x2, 100
  68   br i1 %4, label %exit, label %header
  69
  70 exit:
  71   ret i32 %count4
  72 }
  73
  74 ; More blocks can be moved before header.
  75 ;            header <------------
  76 ;              /\               |
  77 ;             /  \              |
  78 ;            /    \             |
  79 ;           /      \            |
  80 ;          /        \           |
  81 ;        true      false        |
  82 ;         /\         /\         |
  83 ;        /  \       /  \        |
  84 ;       /    \     /    \       |
  85 ;    true3 false3 /      \      |
  86 ;      \    /   true2  false2   |
  87 ;       \  /      \      /      |
  88 ;        \/        \    /       |
  89 ;      endif3       \  /        |
  90 ;         \          \/         |
  91 ;          \       endif2       |
  92 ;           \        /          |
  93 ;            \      /           |
  94 ;             \    /            |
  95 ;              \  /             |
  96 ;               \/              |
  97 ;              latch-------------
  98 ;                |
  99 ;                |
 100 ;              exit
 101 ;
 102 ; Blocks true3,endif3,latch should be moved before header.
 103 ;
 104 ;CHECK-LABEL: test3:
 105 ;CHECK:       %true3
 106 ;CHECK:       %endif3
 107 ;CHECK:       %latch
 108 ;CHECK:       %header
 109 ;CHECK:       %false
 110 define i32 @test3(i32* %p) {
 111 entry:
 112   br label %header
 113
 114 header:
 115   %x1 = phi i64 [0, %entry], [%x2, %latch]
 116   %count1 = phi i32 [0, %entry], [%count12, %latch]
 117   %0 = ptrtoint i32* %p to i64
 118   %1 = add i64 %0, %x1
 119   %2 = inttoptr i64 %1 to i32*
 120   %data = load i32, i32* %2
 121   %3 = icmp eq i32 %data, 0
 122   br i1 %3, label %true, label %false, !prof !3
 123
 124 false:
 125   %count2 = add i32 %count1, 1
 126   %cond = icmp sgt i32 %count2, 10
 127   br i1 %cond, label %true2, label %false2
 128
 129 false2:
 130   %count3 = and i32 %count2, 7
 131   br label %endif2
 132
 133 true2:
 134   %count4 = mul i32 %count2, 3
 135   br label %endif2
 136
 137 endif2:
 138   %count5 = phi i32 [%count3, %false2], [%count4, %true2]
 139   %count6 = sub i32 %count5, 5
 140   br label %latch
 141
 142 true:
 143   %count7 = add i32 %count1, 2
 144   %cond2 = icmp slt i32 %count7, 20
 145   br i1 %cond2, label %true3, label %false3
 146
 147 false3:
 148   %count8 = or i32 %count7, 3
 149   br label %endif3
 150
 151 true3:
 152   %count9 = xor i32 %count7, 55
 153   br label %endif3
 154
 155 endif3:
 156   %count10 = phi i32 [%count8, %false3], [%count9, %true3]
 157   %count11 = add i32 %count10, 3
 158   br label %latch
 159
 160 latch:
 161   %count12 = phi i32 [%count6, %endif2], [%count11, %endif3]
 162   %x2 = add i64 %x1, 1
 163   %4 = icmp eq i64 %x2, 100
 164   br i1 %4, label %exit, label %header
 165
 166 exit:
 167   ret i32 %count12
 168 }
 169
 170 ; The exit block has higher frequency than false block, so latch block
 171 ; should not moved before header.
 172 ;CHECK-LABEL: test4:
 173 ;CHECK:       %header
 174 ;CHECK:       %true
 175 ;CHECK:       %latch
 176 ;CHECK:       %false
 177 ;CHECK:       %exit
 178 define i32 @test4(i32 %t, i32* %p) {
 179 entry:
 180   br label %header
 181
 182 header:
 183   %x1 = phi i64 [0, %entry], [%x2, %latch]
 184   %count1 = phi i32 [0, %entry], [%count4, %latch]
 185   %0 = ptrtoint i32* %p to i64
 186   %1 = add i64 %0, %x1
 187   %2 = inttoptr i64 %1 to i32*
 188   %data = load i32, i32* %2
 189   %3 = icmp eq i32 %data, 0
 190   br i1 %3, label %true, label %false, !prof !1
 191
 192 false:
 193   %count2 = add i32 %count1, 1
 194   br label %latch
 195
 196 true:
 197   %count3 = add i32 %count1, 2
 198   br label %latch
 199
 200 latch:
 201   %count4 = phi i32 [%count2, %false], [%count3, %true]
 202   %x2 = add i64 %x1, 1
 203   %4 = icmp eq i64 %x2, 100
 204   br i1 %4, label %exit, label %header, !prof !2
 205
 206 exit:
 207   ret i32 %count4
 208 }
 209
 210 !1 = !{!"branch_weights", i32 100, i32 1}
 211 !2 = !{!"branch_weights", i32 16, i32 16}
 212 !3 = !{!"branch_weights", i32 51, i32 49}
 213
 214 ; If move latch to loop top doesn't reduce taken branch, don't do it.
 215 ;CHECK-LABEL: test5:
 216 ;CHECK:       %entry
 217 ;CHECK:       %header
 218 ;CHECK:       %latch
 219 define void @test5(i32* %p) {
 220 entry:
 221   br label %header
 222
 223 header:
 224   %x1 = phi i64 [0, %entry], [%x1, %header], [%x2, %latch]
 225   %0 = ptrtoint i32* %p to i64
 226   %1 = add i64 %0, %x1
 227   %2 = inttoptr i64 %1 to i32*
 228   %data = load i32, i32* %2
 229   %3 = icmp eq i32 %data, 0
 230   br i1 %3, label %latch, label %header
 231
 232 latch:
 233   %x2 = add i64 %x1, 1
 234   br label %header
 235
 236 exit:
 237   ret void
 238 }
 239