llvm/test/Transforms/Inline/monster_scc.ll

   1 ; This test creates a monster SCC with a very pernicious call graph. It builds
   2 ; a cycle of cross-connected pairs of functions with interesting inlining
   3 ; decisions throughout, but ultimately trivial code complexity.
   4 ;
   5 ; Typically, a greedy approach to inlining works well for bottom-up inliners
   6 ; such as LLVM's. However, there is no way to be bottom-up over an SCC: it's
   7 ; a cycle! Greedily inlining as much as possible into each function of this
   8 ; *SCC* will have the disasterous effect of inlining all N-1 functions into the
   9 ; first one visited, N-2 functions into the second one visited, N-3 into the
  10 ; third, and so on. This is because until inlining occurs, each function in
  11 ; isolation appears to be an excellent inline candidate.
  12 ;
  13 ; Note that the exact number of calls in each function doesn't really matter.
  14 ; It is mostly a function of cost thresholds and visit order. Because this is an
  15 ; SCC there is no "right" or "wrong" answer here as long as no function blows up
  16 ; to be *huge*. The specific concerning pattern is if one or more functions get
  17 ; more than 16 calls in them.
  18 ;
  19 ; This test is extracted from the following C++ program compiled with Clang.
  20 ; The IR is simplified with SROA, instcombine, and simplifycfg. Then C++
  21 ; linkage stuff, attributes, target specific things, metadata and comments were
  22 ; removed. The order of the fuctions is also made more predictable than Clang's
  23 ; output order.
  24 ;
  25 ;   void g(int);
  26 ;
  27 ;   template <bool K, int N> void f(bool *B, bool *E) {
  28 ;     if (K)
  29 ;       g(N);
  30 ;     if (B == E)
  31 ;       return;
  32 ;     if (*B)
  33 ;       f<true, N + 1>(B + 1, E);
  34 ;     else
  35 ;       f<false, N + 1>(B + 1, E);
  36 ;   }
  37 ;   template <> void f<false, MAX>(bool *B, bool *E) { return f<false, 0>(B, E); }
  38 ;   template <> void f<true, MAX>(bool *B, bool *E) { return f<true, 0>(B, E); }
  39 ;
  40 ;   void test(bool *B, bool *E) { f<false, 0>(B, E); }
  41 ;
  42 ; RUN: opt -S < %s -passes=inline -inline-threshold=150 | FileCheck %s --check-prefixes=CHECK,NEW
  43 ; RUN: opt -S < %s -passes=inliner-wrapper -inline-threshold=150 | FileCheck %s --check-prefixes=CHECK,NEW
  44
  45 target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
  46
  47 declare void @_Z1gi(i32)
  48
  49 ; CHECK-LABEL: define void @_Z1fILb0ELi0EEvPbS0_(
  50 ; NEW-NOT: call
  51 ; NEW: call void @_Z1gi(
  52 ; NEW-NOT: call
  53 ; NEW: call void @_Z1fILb1ELi2EEvPbS0_(
  54 ; NEW-NOT: call
  55 ; NEW: call void @_Z1fILb0ELi2EEvPbS0_(
  56 ; NEW-NOT: call
  57 ; NEW: call void @_Z1fILb1ELi2EEvPbS0_(
  58 ; NEW-NOT: call
  59 ; NEW: call void @_Z1fILb0ELi2EEvPbS0_(
  60 ; NEW-NOT: call
  61 define void @_Z1fILb0ELi0EEvPbS0_(ptr %B, ptr %E) {
  62 entry:
  63   %cmp = icmp eq ptr %B, %E
  64   br i1 %cmp, label %if.end3, label %if.end
  65
  66 if.end:
  67   %0 = load i8, ptr %B, align 1
  68   %tobool = icmp eq i8 %0, 0
  69   %add.ptr2 = getelementptr inbounds i8, ptr %B, i64 1
  70   br i1 %tobool, label %if.else, label %if.then1
  71
  72 if.then1:
  73   call void @_Z1fILb1ELi1EEvPbS0_(ptr %add.ptr2, ptr %E)
  74   br label %if.end3
  75
  76 if.else:
  77   call void @_Z1fILb0ELi1EEvPbS0_(ptr %add.ptr2, ptr %E)
  78   br label %if.end3
  79
  80 if.end3:
  81   ret void
  82 }
  83
  84 ; CHECK-LABEL: define void @_Z1fILb1ELi0EEvPbS0_(
  85 ; NEW-NOT: call
  86 ; NEW: call void @_Z1gi(
  87 ; NEW-NOT: call
  88 ; NEW: call void @_Z1fILb1ELi1EEvPbS0_(
  89 ; NEW-NOT: call
  90 ; NEW: call void @_Z1fILb1ELi2EEvPbS0_(
  91 ; NEW-NOT: call
  92 ; NEW: call void @_Z1fILb0ELi2EEvPbS0_(
  93 ; NEW-NOT: call
  94 define void @_Z1fILb1ELi0EEvPbS0_(ptr %B, ptr %E) {
  95 entry:
  96   call void @_Z1gi(i32 0)
  97   %cmp = icmp eq ptr %B, %E
  98   br i1 %cmp, label %if.end3, label %if.end
  99
 100 if.end:
 101   %0 = load i8, ptr %B, align 1
 102   %tobool = icmp eq i8 %0, 0
 103   %add.ptr2 = getelementptr inbounds i8, ptr %B, i64 1
 104   br i1 %tobool, label %if.else, label %if.then1
 105
 106 if.then1:
 107   call void @_Z1fILb1ELi1EEvPbS0_(ptr %add.ptr2, ptr %E)
 108   br label %if.end3
 109
 110 if.else:
 111   call void @_Z1fILb0ELi1EEvPbS0_(ptr %add.ptr2, ptr %E)
 112   br label %if.end3
 113
 114 if.end3:
 115   ret void
 116 }
 117
 118 ; CHECK-LABEL: define void @_Z1fILb0ELi1EEvPbS0_(
 119 ; NEW-NOT: call
 120 ; NEW: call void @_Z1fILb1ELi2EEvPbS0_(
 121 ; NEW-NOT: call
 122 ; NEW: call void @_Z1fILb1ELi3EEvPbS0_(
 123 ; NEW-NOT: call
 124 ; NEW: call void @_Z1fILb0ELi3EEvPbS0_(
 125 ; NEW-NOT: call
 126 define void @_Z1fILb0ELi1EEvPbS0_(ptr %B, ptr %E) {
 127 entry:
 128   %cmp = icmp eq ptr %B, %E
 129   br i1 %cmp, label %if.end3, label %if.end
 130
 131 if.end:
 132   %0 = load i8, ptr %B, align 1
 133   %tobool = icmp eq i8 %0, 0
 134   %add.ptr2 = getelementptr inbounds i8, ptr %B, i64 1
 135   br i1 %tobool, label %if.else, label %if.then1
 136
 137 if.then1:
 138   call void @_Z1fILb1ELi2EEvPbS0_(ptr %add.ptr2, ptr %E)
 139   br label %if.end3
 140
 141 if.else:
 142   call void @_Z1fILb0ELi2EEvPbS0_(ptr %add.ptr2, ptr %E)
 143   br label %if.end3
 144
 145 if.end3:
 146   ret void
 147 }
 148
 149 ; CHECK-LABEL: define void @_Z1fILb1ELi1EEvPbS0_(
 150 ; NEW-NOT: call
 151 ; NEW: call void @_Z1gi(
 152 ; NEW-NOT: call
 153 ; NEW: call void @_Z1gi(
 154 ; NEW-NOT: call
 155 ; NEW: call void @_Z1fILb1ELi3EEvPbS0_(
 156 ; NEW-NOT: call
 157 ; NEW: call void @_Z1fILb0ELi3EEvPbS0_(
 158 ; NEW-NOT: call
 159 ; NEW: call void @_Z1fILb1ELi3EEvPbS0_(
 160 ; NEW-NOT: call
 161 ; NEW: call void @_Z1fILb0ELi3EEvPbS0_(
 162 ; NEW-NOT: call
 163 define void @_Z1fILb1ELi1EEvPbS0_(ptr %B, ptr %E) {
 164 entry:
 165   call void @_Z1gi(i32 1)
 166   %cmp = icmp eq ptr %B, %E
 167 ; CHECK-NOT: call
 168   br i1 %cmp, label %if.end3, label %if.end
 169
 170 if.end:
 171   %0 = load i8, ptr %B, align 1
 172   %tobool = icmp eq i8 %0, 0
 173   %add.ptr2 = getelementptr inbounds i8, ptr %B, i64 1
 174   br i1 %tobool, label %if.else, label %if.then1
 175
 176 if.then1:
 177   call void @_Z1fILb1ELi2EEvPbS0_(ptr %add.ptr2, ptr %E)
 178   br label %if.end3
 179
 180 if.else:
 181   call void @_Z1fILb0ELi2EEvPbS0_(ptr %add.ptr2, ptr %E)
 182   br label %if.end3
 183
 184 if.end3:
 185   ret void
 186 }
 187
 188 ; CHECK-LABEL: define void @_Z1fILb0ELi2EEvPbS0_(
 189 ; NEW-NOT: call
 190 ; NEW: call void @_Z1gi(
 191 ; NEW-NOT: call
 192 ; NEW: call void @_Z1fILb1ELi0EEvPbS0_(
 193 ; NEW-NOT: call
 194 ; NEW: call void @_Z1fILb0ELi0EEvPbS0_(
 195 ; NEW-NOT: call
 196 ; NEW: call void @_Z1fILb1ELi4EEvPbS0_(
 197 ; NEW-NOT: call
 198 ; NEW: call void @_Z1fILb0ELi4EEvPbS0_(
 199 ; NEW-NOT: call
 200 define void @_Z1fILb0ELi2EEvPbS0_(ptr %B, ptr %E) {
 201 entry:
 202   %cmp = icmp eq ptr %B, %E
 203   br i1 %cmp, label %if.end3, label %if.end
 204
 205 if.end:
 206   %0 = load i8, ptr %B, align 1
 207   %tobool = icmp eq i8 %0, 0
 208   %add.ptr2 = getelementptr inbounds i8, ptr %B, i64 1
 209   br i1 %tobool, label %if.else, label %if.then1
 210
 211 if.then1:
 212   call void @_Z1fILb1ELi3EEvPbS0_(ptr %add.ptr2, ptr %E)
 213   br label %if.end3
 214
 215 if.else:
 216   call void @_Z1fILb0ELi3EEvPbS0_(ptr %add.ptr2, ptr %E)
 217   br label %if.end3
 218
 219 if.end3:
 220   ret void
 221 }
 222
 223 ; CHECK-LABEL: define void @_Z1fILb1ELi2EEvPbS0_(
 224 ; NEW-NOT: call
 225 ; NEW: call void @_Z1gi(
 226 ; NEW-NOT: call
 227 ; NEW: call void @_Z1gi(
 228 ; NEW-NOT: call
 229 ; NEW: call void @_Z1fILb1ELi4EEvPbS0_(
 230 ; NEW-NOT: call
 231 ; NEW: call void @_Z1fILb0ELi4EEvPbS0_(
 232 ; NEW-NOT: call
 233 ; NEW: call void @_Z1fILb1ELi4EEvPbS0_(
 234 ; NEW-NOT: call
 235 ; NEW: call void @_Z1fILb0ELi4EEvPbS0_(
 236 ; NEW-NOT: call
 237 define void @_Z1fILb1ELi2EEvPbS0_(ptr %B, ptr %E) {
 238 entry:
 239   call void @_Z1gi(i32 2)
 240   %cmp = icmp eq ptr %B, %E
 241   br i1 %cmp, label %if.end3, label %if.end
 242
 243 if.end:
 244   %0 = load i8, ptr %B, align 1
 245   %tobool = icmp eq i8 %0, 0
 246   %add.ptr2 = getelementptr inbounds i8, ptr %B, i64 1
 247   br i1 %tobool, label %if.else, label %if.then1
 248
 249 if.then1:
 250   call void @_Z1fILb1ELi3EEvPbS0_(ptr %add.ptr2, ptr %E)
 251   br label %if.end3
 252
 253 if.else:
 254   call void @_Z1fILb0ELi3EEvPbS0_(ptr %add.ptr2, ptr %E)
 255   br label %if.end3
 256
 257 if.end3:
 258   ret void
 259 }
 260
 261 ; CHECK-LABEL: define void @_Z1fILb0ELi3EEvPbS0_(
 262 ; NEW-NOT: call
 263 ; NEW: call void @_Z1gi(
 264 ; NEW-NOT: call
 265 ; NEW: call void @_Z1fILb1ELi1EEvPbS0_(
 266 ; NEW-NOT: call
 267 ; NEW: call void @_Z1fILb0ELi1EEvPbS0_(
 268 ; NEW-NOT: call
 269 ; NEW: call void @_Z1fILb0ELi0EEvPbS0_(
 270 ; NEW-NOT: call
 271 define void @_Z1fILb0ELi3EEvPbS0_(ptr %B, ptr %E) {
 272 entry:
 273   %cmp = icmp eq ptr %B, %E
 274   br i1 %cmp, label %if.end3, label %if.end
 275
 276 if.end:
 277   %0 = load i8, ptr %B, align 1
 278   %tobool = icmp eq i8 %0, 0
 279   %add.ptr2 = getelementptr inbounds i8, ptr %B, i64 1
 280   br i1 %tobool, label %if.else, label %if.then1
 281
 282 if.then1:
 283   call void @_Z1fILb1ELi4EEvPbS0_(ptr %add.ptr2, ptr %E)
 284   br label %if.end3
 285
 286 if.else:
 287   call void @_Z1fILb0ELi4EEvPbS0_(ptr %add.ptr2, ptr %E)
 288   br label %if.end3
 289
 290 if.end3:
 291   ret void
 292 }
 293
 294 ; CHECK-LABEL: define void @_Z1fILb1ELi3EEvPbS0_(
 295 ; CHECK-NOT: call
 296 ; CHECK: call void @_Z1gi(
 297 ; CHECK-NOT: call
 298 ; CHECK: call void @_Z1fILb1ELi0EEvPbS0_(
 299 ; CHECK-NOT: call
 300 ; CHECK: call void @_Z1fILb0ELi0EEvPbS0_(
 301 ; CHECK-NOT: call
 302 define void @_Z1fILb1ELi3EEvPbS0_(ptr %B, ptr %E) {
 303 entry:
 304   call void @_Z1gi(i32 3)
 305   %cmp = icmp eq ptr %B, %E
 306   br i1 %cmp, label %if.end3, label %if.end
 307
 308 if.end:
 309   %0 = load i8, ptr %B, align 1
 310   %tobool = icmp eq i8 %0, 0
 311   %add.ptr2 = getelementptr inbounds i8, ptr %B, i64 1
 312   br i1 %tobool, label %if.else, label %if.then1
 313
 314 if.then1:
 315   call void @_Z1fILb1ELi4EEvPbS0_(ptr %add.ptr2, ptr %E)
 316   br label %if.end3
 317
 318 if.else:
 319   call void @_Z1fILb0ELi4EEvPbS0_(ptr %add.ptr2, ptr %E)
 320   br label %if.end3
 321
 322 if.end3:
 323   ret void
 324 }
 325
 326 ; CHECK-LABEL: define void @_Z1fILb0ELi4EEvPbS0_(
 327 ; CHECK-NOT: call
 328 ; CHECK: call void @_Z1fILb0ELi0EEvPbS0_(
 329 ; CHECK-NOT: call
 330 define void @_Z1fILb0ELi4EEvPbS0_(ptr %B, ptr %E) {
 331 entry:
 332   call void @_Z1fILb0ELi0EEvPbS0_(ptr %B, ptr %E)
 333   ret void
 334 }
 335
 336 ; CHECK-LABEL: define void @_Z1fILb1ELi4EEvPbS0_(
 337 ; NEW-NOT: call
 338 ; NEW: call void @_Z1gi(
 339 ; NEW-NOT: call
 340 ; NEW: call void @_Z1fILb1ELi1EEvPbS0_(
 341 ; NEW-NOT: call
 342 ; NEW: call void @_Z1fILb0ELi1EEvPbS0_(
 343 ; NEW-NOT: call
 344 define void @_Z1fILb1ELi4EEvPbS0_(ptr %B, ptr %E) {
 345 entry:
 346   call void @_Z1fILb1ELi0EEvPbS0_(ptr %B, ptr %E)
 347   ret void
 348 }
 349
 350 ; CHECK-LABEL: define void @_Z4testPbS_(
 351 ; CHECK: call
 352 ; CHECK-NOT: call
 353 define void @_Z4testPbS_(ptr %B, ptr %E) {
 354 entry:
 355   call void @_Z1fILb0ELi0EEvPbS0_(ptr %B, ptr %E)
 356   ret void
 357 }
 358