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 simplify-cfg. 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 -inline -inline-threshold=150 | FileCheck %s --check-prefixes=CHECK,OLD
  43 ; RUN: opt -S < %s -passes=inline -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 ; OLD-NOT: call
  51 ; OLD: call void @_Z1gi(
  52 ; OLD-NOT: call
  53 ; OLD: call void @_Z1fILb1ELi2EEvPbS0_(
  54 ; OLD-NOT: call
  55 ; OLD: call void @_Z1fILb0ELi2EEvPbS0_(
  56 ; OLD-NOT: call
  57 ; OLD: call void @_Z1fILb0ELi1EEvPbS0_(
  58 ; OLD-NOT: call
  59 ; NEW-NOT: call
  60 ; NEW: call void @_Z1gi(
  61 ; NEW-NOT: call
  62 ; NEW: call void @_Z1fILb1ELi2EEvPbS0_(
  63 ; NEW-NOT: call
  64 ; NEW: call void @_Z1fILb0ELi2EEvPbS0_(
  65 ; NEW-NOT: call
  66 ; NEW: call void @_Z1fILb1ELi2EEvPbS0_(
  67 ; NEW-NOT: call
  68 ; NEW: call void @_Z1fILb0ELi2EEvPbS0_(
  69 ; NEW-NOT: call
  70 define void @_Z1fILb0ELi0EEvPbS0_(i8* %B, i8* %E) {
  71 entry:
  72   %cmp = icmp eq i8* %B, %E
  73   br i1 %cmp, label %if.end3, label %if.end
  74
  75 if.end:
  76   %0 = load i8, i8* %B, align 1
  77   %tobool = icmp eq i8 %0, 0
  78   %add.ptr2 = getelementptr inbounds i8, i8* %B, i64 1
  79   br i1 %tobool, label %if.else, label %if.then1
  80
  81 if.then1:
  82   call void @_Z1fILb1ELi1EEvPbS0_(i8* %add.ptr2, i8* %E)
  83   br label %if.end3
  84
  85 if.else:
  86   call void @_Z1fILb0ELi1EEvPbS0_(i8* %add.ptr2, i8* %E)
  87   br label %if.end3
  88
  89 if.end3:
  90   ret void
  91 }
  92
  93 ; CHECK-LABEL: define void @_Z1fILb1ELi0EEvPbS0_(
  94 ; OLD-NOT: call
  95 ; OLD: call void @_Z1gi(
  96 ; OLD-NOT: call
  97 ; OLD: call void @_Z1gi(
  98 ; OLD-NOT: call
  99 ; OLD: call void @_Z1fILb1ELi2EEvPbS0_(
 100 ; OLD-NOT: call
 101 ; OLD: call void @_Z1fILb0ELi2EEvPbS0_(
 102 ; OLD-NOT: call
 103 ; OLD: call void @_Z1fILb0ELi1EEvPbS0_(
 104 ; OLD-NOT: call
 105 ; NEW-NOT: call
 106 ; NEW: call void @_Z1gi(
 107 ; NEW-NOT: call
 108 ; NEW: call void @_Z1fILb1ELi1EEvPbS0_(
 109 ; NEW-NOT: call
 110 ; NEW: call void @_Z1fILb1ELi2EEvPbS0_(
 111 ; NEW-NOT: call
 112 ; NEW: call void @_Z1fILb0ELi2EEvPbS0_(
 113 ; NEW-NOT: call
 114 define void @_Z1fILb1ELi0EEvPbS0_(i8* %B, i8* %E) {
 115 entry:
 116   call void @_Z1gi(i32 0)
 117   %cmp = icmp eq i8* %B, %E
 118   br i1 %cmp, label %if.end3, label %if.end
 119
 120 if.end:
 121   %0 = load i8, i8* %B, align 1
 122   %tobool = icmp eq i8 %0, 0
 123   %add.ptr2 = getelementptr inbounds i8, i8* %B, i64 1
 124   br i1 %tobool, label %if.else, label %if.then1
 125
 126 if.then1:
 127   call void @_Z1fILb1ELi1EEvPbS0_(i8* %add.ptr2, i8* %E)
 128   br label %if.end3
 129
 130 if.else:
 131   call void @_Z1fILb0ELi1EEvPbS0_(i8* %add.ptr2, i8* %E)
 132   br label %if.end3
 133
 134 if.end3:
 135   ret void
 136 }
 137
 138 ; CHECK-LABEL: define void @_Z1fILb0ELi1EEvPbS0_(
 139 ; OLD-NOT: call
 140 ; OLD: call void @_Z1gi(
 141 ; OLD-NOT: call
 142 ; OLD: call void @_Z1gi(
 143 ; OLD-NOT: call
 144 ; OLD: call void @_Z1fILb1ELi0EEvPbS0_(
 145 ; OLD-NOT: call
 146 ; OLD: call void @_Z1fILb0ELi0EEvPbS0_(
 147 ; OLD-NOT: call
 148 ; OLD: call void @_Z1fILb1ELi0EEvPbS0_(
 149 ; OLD-NOT: call
 150 ; OLD: call void @_Z1fILb0ELi0EEvPbS0_(
 151 ; OLD-NOT: call
 152 ; OLD: call void @_Z1fILb0ELi2EEvPbS0_(
 153 ; OLD-NOT: call
 154 ; NEW-NOT: call
 155 ; NEW: call void @_Z1fILb1ELi2EEvPbS0_(
 156 ; NEW-NOT: call
 157 ; NEW: call void @_Z1fILb1ELi3EEvPbS0_(
 158 ; NEW-NOT: call
 159 ; NEW: call void @_Z1fILb0ELi3EEvPbS0_(
 160 ; NEW-NOT: call
 161 define void @_Z1fILb0ELi1EEvPbS0_(i8* %B, i8* %E) {
 162 entry:
 163   %cmp = icmp eq i8* %B, %E
 164   br i1 %cmp, label %if.end3, label %if.end
 165
 166 if.end:
 167   %0 = load i8, i8* %B, align 1
 168   %tobool = icmp eq i8 %0, 0
 169   %add.ptr2 = getelementptr inbounds i8, i8* %B, i64 1
 170   br i1 %tobool, label %if.else, label %if.then1
 171
 172 if.then1:
 173   call void @_Z1fILb1ELi2EEvPbS0_(i8* %add.ptr2, i8* %E)
 174   br label %if.end3
 175
 176 if.else:
 177   call void @_Z1fILb0ELi2EEvPbS0_(i8* %add.ptr2, i8* %E)
 178   br label %if.end3
 179
 180 if.end3:
 181   ret void
 182 }
 183
 184 ; CHECK-LABEL: define void @_Z1fILb1ELi1EEvPbS0_(
 185 ; OLD-NOT: call
 186 ; OLD: call void @_Z1gi(
 187 ; OLD-NOT: call
 188 ; OLD: call void @_Z1fILb1ELi2EEvPbS0_(
 189 ; OLD-NOT: call
 190 ; OLD: call void @_Z1fILb0ELi2EEvPbS0_(
 191 ; OLD-NOT: call
 192 ; NEW-NOT: call
 193 ; NEW: call void @_Z1gi(
 194 ; NEW-NOT: call
 195 ; NEW: call void @_Z1gi(
 196 ; NEW-NOT: call
 197 ; NEW: call void @_Z1fILb1ELi3EEvPbS0_(
 198 ; NEW-NOT: call
 199 ; NEW: call void @_Z1fILb0ELi3EEvPbS0_(
 200 ; NEW-NOT: call
 201 ; NEW: call void @_Z1fILb1ELi3EEvPbS0_(
 202 ; NEW-NOT: call
 203 ; NEW: call void @_Z1fILb0ELi3EEvPbS0_(
 204 ; NEW-NOT: call
 205 define void @_Z1fILb1ELi1EEvPbS0_(i8* %B, i8* %E) {
 206 entry:
 207   call void @_Z1gi(i32 1)
 208   %cmp = icmp eq i8* %B, %E
 209 ; CHECK-NOT: call
 210   br i1 %cmp, label %if.end3, label %if.end
 211
 212 if.end:
 213   %0 = load i8, i8* %B, align 1
 214   %tobool = icmp eq i8 %0, 0
 215   %add.ptr2 = getelementptr inbounds i8, i8* %B, i64 1
 216   br i1 %tobool, label %if.else, label %if.then1
 217
 218 if.then1:
 219   call void @_Z1fILb1ELi2EEvPbS0_(i8* %add.ptr2, i8* %E)
 220   br label %if.end3
 221
 222 if.else:
 223   call void @_Z1fILb0ELi2EEvPbS0_(i8* %add.ptr2, i8* %E)
 224   br label %if.end3
 225
 226 if.end3:
 227   ret void
 228 }
 229
 230 ; CHECK-LABEL: define void @_Z1fILb0ELi2EEvPbS0_(
 231 ; OLD-NOT: call
 232 ; OLD: call void @_Z1gi(
 233 ; OLD-NOT: call
 234 ; OLD: call void @_Z1fILb1ELi0EEvPbS0_(
 235 ; OLD-NOT: call
 236 ; OLD: call void @_Z1fILb0ELi0EEvPbS0_(
 237 ; OLD-NOT: call
 238 ; OLD: call void @_Z1fILb1ELi0EEvPbS0_(
 239 ; OLD-NOT: call
 240 ; OLD: call void @_Z1fILb0ELi0EEvPbS0_(
 241 ; OLD-NOT: call
 242 ; NEW-NOT: call
 243 ; NEW: call void @_Z1gi(
 244 ; NEW-NOT: call
 245 ; NEW: call void @_Z1fILb1ELi0EEvPbS0_(
 246 ; NEW-NOT: call
 247 ; NEW: call void @_Z1fILb0ELi0EEvPbS0_(
 248 ; NEW-NOT: call
 249 ; NEW: call void @_Z1fILb1ELi4EEvPbS0_(
 250 ; NEW-NOT: call
 251 ; NEW: call void @_Z1fILb0ELi4EEvPbS0_(
 252 ; NEW-NOT: call
 253 define void @_Z1fILb0ELi2EEvPbS0_(i8* %B, i8* %E) {
 254 entry:
 255   %cmp = icmp eq i8* %B, %E
 256   br i1 %cmp, label %if.end3, label %if.end
 257
 258 if.end:
 259   %0 = load i8, i8* %B, align 1
 260   %tobool = icmp eq i8 %0, 0
 261   %add.ptr2 = getelementptr inbounds i8, i8* %B, i64 1
 262   br i1 %tobool, label %if.else, label %if.then1
 263
 264 if.then1:
 265   call void @_Z1fILb1ELi3EEvPbS0_(i8* %add.ptr2, i8* %E)
 266   br label %if.end3
 267
 268 if.else:
 269   call void @_Z1fILb0ELi3EEvPbS0_(i8* %add.ptr2, i8* %E)
 270   br label %if.end3
 271
 272 if.end3:
 273   ret void
 274 }
 275
 276 ; CHECK-LABEL: define void @_Z1fILb1ELi2EEvPbS0_(
 277 ; OLD-NOT: call
 278 ; OLD: call void @_Z1gi(
 279 ; OLD-NOT: call
 280 ; OLD: call void @_Z1gi(
 281 ; OLD-NOT: call
 282 ; OLD: call void @_Z1fILb1ELi0EEvPbS0_(
 283 ; OLD-NOT: call
 284 ; OLD: call void @_Z1fILb0ELi0EEvPbS0_(
 285 ; OLD-NOT: call
 286 ; OLD: call void @_Z1fILb1ELi0EEvPbS0_(
 287 ; OLD-NOT: call
 288 ; OLD: call void @_Z1fILb0ELi0EEvPbS0_(
 289 ; OLD-NOT: call
 290 ; NEW-NOT: call
 291 ; NEW: call void @_Z1gi(
 292 ; NEW-NOT: call
 293 ; NEW: call void @_Z1gi(
 294 ; NEW-NOT: call
 295 ; NEW: call void @_Z1fILb1ELi4EEvPbS0_(
 296 ; NEW-NOT: call
 297 ; NEW: call void @_Z1fILb0ELi4EEvPbS0_(
 298 ; NEW-NOT: call
 299 ; NEW: call void @_Z1fILb1ELi4EEvPbS0_(
 300 ; NEW-NOT: call
 301 ; NEW: call void @_Z1fILb0ELi4EEvPbS0_(
 302 ; NEW-NOT: call
 303 define void @_Z1fILb1ELi2EEvPbS0_(i8* %B, i8* %E) {
 304 entry:
 305   call void @_Z1gi(i32 2)
 306   %cmp = icmp eq i8* %B, %E
 307   br i1 %cmp, label %if.end3, label %if.end
 308
 309 if.end:
 310   %0 = load i8, i8* %B, align 1
 311   %tobool = icmp eq i8 %0, 0
 312   %add.ptr2 = getelementptr inbounds i8, i8* %B, i64 1
 313   br i1 %tobool, label %if.else, label %if.then1
 314
 315 if.then1:
 316   call void @_Z1fILb1ELi3EEvPbS0_(i8* %add.ptr2, i8* %E)
 317   br label %if.end3
 318
 319 if.else:
 320   call void @_Z1fILb0ELi3EEvPbS0_(i8* %add.ptr2, i8* %E)
 321   br label %if.end3
 322
 323 if.end3:
 324   ret void
 325 }
 326
 327 ; CHECK-LABEL: define void @_Z1fILb0ELi3EEvPbS0_(
 328 ; OLD-NOT: call
 329 ; OLD: call void @_Z1fILb1ELi0EEvPbS0_(
 330 ; OLD-NOT: call
 331 ; OLD: call void @_Z1fILb0ELi0EEvPbS0_(
 332 ; OLD-NOT: call
 333 ; NEW-NOT: call
 334 ; NEW: call void @_Z1gi(
 335 ; NEW-NOT: call
 336 ; NEW: call void @_Z1fILb1ELi1EEvPbS0_(
 337 ; NEW-NOT: call
 338 ; NEW: call void @_Z1fILb0ELi1EEvPbS0_(
 339 ; NEW-NOT: call
 340 ; NEW: call void @_Z1fILb0ELi0EEvPbS0_(
 341 ; NEW-NOT: call
 342 define void @_Z1fILb0ELi3EEvPbS0_(i8* %B, i8* %E) {
 343 entry:
 344   %cmp = icmp eq i8* %B, %E
 345   br i1 %cmp, label %if.end3, label %if.end
 346
 347 if.end:
 348   %0 = load i8, i8* %B, align 1
 349   %tobool = icmp eq i8 %0, 0
 350   %add.ptr2 = getelementptr inbounds i8, i8* %B, i64 1
 351   br i1 %tobool, label %if.else, label %if.then1
 352
 353 if.then1:
 354   call void @_Z1fILb1ELi4EEvPbS0_(i8* %add.ptr2, i8* %E)
 355   br label %if.end3
 356
 357 if.else:
 358   call void @_Z1fILb0ELi4EEvPbS0_(i8* %add.ptr2, i8* %E)
 359   br label %if.end3
 360
 361 if.end3:
 362   ret void
 363 }
 364
 365 ; CHECK-LABEL: define void @_Z1fILb1ELi3EEvPbS0_(
 366 ; CHECK-NOT: call
 367 ; CHECK: call void @_Z1gi(
 368 ; CHECK-NOT: call
 369 ; CHECK: call void @_Z1fILb1ELi0EEvPbS0_(
 370 ; CHECK-NOT: call
 371 ; CHECK: call void @_Z1fILb0ELi0EEvPbS0_(
 372 ; CHECK-NOT: call
 373 define void @_Z1fILb1ELi3EEvPbS0_(i8* %B, i8* %E) {
 374 entry:
 375   call void @_Z1gi(i32 3)
 376   %cmp = icmp eq i8* %B, %E
 377   br i1 %cmp, label %if.end3, label %if.end
 378
 379 if.end:
 380   %0 = load i8, i8* %B, align 1
 381   %tobool = icmp eq i8 %0, 0
 382   %add.ptr2 = getelementptr inbounds i8, i8* %B, i64 1
 383   br i1 %tobool, label %if.else, label %if.then1
 384
 385 if.then1:
 386   call void @_Z1fILb1ELi4EEvPbS0_(i8* %add.ptr2, i8* %E)
 387   br label %if.end3
 388
 389 if.else:
 390   call void @_Z1fILb0ELi4EEvPbS0_(i8* %add.ptr2, i8* %E)
 391   br label %if.end3
 392
 393 if.end3:
 394   ret void
 395 }
 396
 397 ; CHECK-LABEL: define void @_Z1fILb0ELi4EEvPbS0_(
 398 ; CHECK-NOT: call
 399 ; CHECK: call void @_Z1fILb0ELi0EEvPbS0_(
 400 ; CHECK-NOT: call
 401 define void @_Z1fILb0ELi4EEvPbS0_(i8* %B, i8* %E) {
 402 entry:
 403   call void @_Z1fILb0ELi0EEvPbS0_(i8* %B, i8* %E)
 404   ret void
 405 }
 406
 407 ; CHECK-LABEL: define void @_Z1fILb1ELi4EEvPbS0_(
 408 ; OLD-NOT: call
 409 ; OLD: call void @_Z1fILb1ELi0EEvPbS0_(
 410 ; OLD-NOT: call
 411 ; NEW-NOT: call
 412 ; NEW: call void @_Z1gi(
 413 ; NEW-NOT: call
 414 ; NEW: call void @_Z1fILb1ELi1EEvPbS0_(
 415 ; NEW-NOT: call
 416 ; NEW: call void @_Z1fILb0ELi1EEvPbS0_(
 417 ; NEW-NOT: call
 418 define void @_Z1fILb1ELi4EEvPbS0_(i8* %B, i8* %E) {
 419 entry:
 420   call void @_Z1fILb1ELi0EEvPbS0_(i8* %B, i8* %E)
 421   ret void
 422 }
 423
 424 ; CHECK-LABEL: define void @_Z4testPbS_(
 425 ; CHECK: call
 426 ; CHECK-NOT: call
 427 define void @_Z4testPbS_(i8* %B, i8* %E) {
 428 entry:
 429   call void @_Z1fILb0ELi0EEvPbS0_(i8* %B, i8* %E)
 430   ret void
 431 }
 432