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 @_Z1gi(
 158 ; NEW-NOT: call
 159 ; NEW: call void @_Z1fILb1ELi0EEvPbS0_(
 160 ; NEW-NOT: call
 161 ; NEW: call void @_Z1fILb0ELi0EEvPbS0_(
 162 ; NEW-NOT: call
 163 ; NEW: call void @_Z1fILb0ELi3EEvPbS0_(
 164 ; NEW-NOT: call
 165 define void @_Z1fILb0ELi1EEvPbS0_(i8* %B, i8* %E) {
 166 entry:
 167   %cmp = icmp eq i8* %B, %E
 168   br i1 %cmp, label %if.end3, label %if.end
 169
 170 if.end:
 171   %0 = load i8, i8* %B, align 1
 172   %tobool = icmp eq i8 %0, 0
 173   %add.ptr2 = getelementptr inbounds i8, i8* %B, i64 1
 174   br i1 %tobool, label %if.else, label %if.then1
 175
 176 if.then1:
 177   call void @_Z1fILb1ELi2EEvPbS0_(i8* %add.ptr2, i8* %E)
 178   br label %if.end3
 179
 180 if.else:
 181   call void @_Z1fILb0ELi2EEvPbS0_(i8* %add.ptr2, i8* %E)
 182   br label %if.end3
 183
 184 if.end3:
 185   ret void
 186 }
 187
 188 ; CHECK-LABEL: define void @_Z1fILb1ELi1EEvPbS0_(
 189 ; OLD-NOT: call
 190 ; OLD: call void @_Z1gi(
 191 ; OLD-NOT: call
 192 ; OLD: call void @_Z1fILb1ELi2EEvPbS0_(
 193 ; OLD-NOT: call
 194 ; OLD: call void @_Z1fILb0ELi2EEvPbS0_(
 195 ; OLD-NOT: call
 196 ; NEW-NOT: call
 197 ; NEW: call void @_Z1gi(
 198 ; NEW-NOT: call
 199 ; NEW: call void @_Z1gi(
 200 ; NEW-NOT: call
 201 ; NEW: call void @_Z1gi(
 202 ; NEW-NOT: call
 203 ; NEW: call void @_Z1fILb1ELi0EEvPbS0_(
 204 ; NEW-NOT: call
 205 ; NEW: call void @_Z1fILb0ELi0EEvPbS0_(
 206 ; NEW-NOT: call
 207 ; NEW: call void @_Z1fILb0ELi3EEvPbS0_(
 208 ; NEW-NOT: call
 209 ; NEW: call void @_Z1gi(
 210 ; NEW-NOT: call
 211 ; NEW: call void @_Z1fILb1ELi0EEvPbS0_(
 212 ; NEW-NOT: call
 213 ; NEW: call void @_Z1fILb0ELi0EEvPbS0_(
 214 ; NEW-NOT: call
 215 ; NEW: call void @_Z1fILb0ELi3EEvPbS0_(
 216 ; NEW-NOT: call
 217 define void @_Z1fILb1ELi1EEvPbS0_(i8* %B, i8* %E) {
 218 entry:
 219   call void @_Z1gi(i32 1)
 220   %cmp = icmp eq i8* %B, %E
 221 ; CHECK-NOT: call
 222   br i1 %cmp, label %if.end3, label %if.end
 223
 224 if.end:
 225   %0 = load i8, i8* %B, align 1
 226   %tobool = icmp eq i8 %0, 0
 227   %add.ptr2 = getelementptr inbounds i8, i8* %B, i64 1
 228   br i1 %tobool, label %if.else, label %if.then1
 229
 230 if.then1:
 231   call void @_Z1fILb1ELi2EEvPbS0_(i8* %add.ptr2, i8* %E)
 232   br label %if.end3
 233
 234 if.else:
 235   call void @_Z1fILb0ELi2EEvPbS0_(i8* %add.ptr2, i8* %E)
 236   br label %if.end3
 237
 238 if.end3:
 239   ret void
 240 }
 241
 242 ; CHECK-LABEL: define void @_Z1fILb0ELi2EEvPbS0_(
 243 ; OLD-NOT: call
 244 ; OLD: call void @_Z1gi(
 245 ; OLD-NOT: call
 246 ; OLD: call void @_Z1fILb1ELi0EEvPbS0_(
 247 ; OLD-NOT: call
 248 ; OLD: call void @_Z1fILb0ELi0EEvPbS0_(
 249 ; OLD-NOT: call
 250 ; OLD: call void @_Z1fILb1ELi0EEvPbS0_(
 251 ; OLD-NOT: call
 252 ; OLD: call void @_Z1fILb0ELi0EEvPbS0_(
 253 ; OLD-NOT: call
 254 ; NEW-NOT: call
 255 ; NEW: call void @_Z1gi(
 256 ; NEW-NOT: call
 257 ; NEW: call void @_Z1fILb1ELi0EEvPbS0_(
 258 ; NEW-NOT: call
 259 ; NEW: call void @_Z1fILb0ELi0EEvPbS0_(
 260 ; NEW-NOT: call
 261 ; NEW: call void @_Z1fILb1ELi4EEvPbS0_(
 262 ; NEW-NOT: call
 263 ; NEW: call void @_Z1fILb0ELi0EEvPbS0_(
 264 ; NEW-NOT: call
 265 define void @_Z1fILb0ELi2EEvPbS0_(i8* %B, i8* %E) {
 266 entry:
 267   %cmp = icmp eq i8* %B, %E
 268   br i1 %cmp, label %if.end3, label %if.end
 269
 270 if.end:
 271   %0 = load i8, i8* %B, align 1
 272   %tobool = icmp eq i8 %0, 0
 273   %add.ptr2 = getelementptr inbounds i8, i8* %B, i64 1
 274   br i1 %tobool, label %if.else, label %if.then1
 275
 276 if.then1:
 277   call void @_Z1fILb1ELi3EEvPbS0_(i8* %add.ptr2, i8* %E)
 278   br label %if.end3
 279
 280 if.else:
 281   call void @_Z1fILb0ELi3EEvPbS0_(i8* %add.ptr2, i8* %E)
 282   br label %if.end3
 283
 284 if.end3:
 285   ret void
 286 }
 287
 288 ; CHECK-LABEL: define void @_Z1fILb1ELi2EEvPbS0_(
 289 ; OLD-NOT: call
 290 ; OLD: call void @_Z1gi(
 291 ; OLD-NOT: call
 292 ; OLD: call void @_Z1gi(
 293 ; OLD-NOT: call
 294 ; OLD: call void @_Z1fILb1ELi0EEvPbS0_(
 295 ; OLD-NOT: call
 296 ; OLD: call void @_Z1fILb0ELi0EEvPbS0_(
 297 ; OLD-NOT: call
 298 ; OLD: call void @_Z1fILb1ELi0EEvPbS0_(
 299 ; OLD-NOT: call
 300 ; OLD: call void @_Z1fILb0ELi0EEvPbS0_(
 301 ; OLD-NOT: call
 302 ; NEW-NOT: call
 303 ; NEW: call void @_Z1gi(
 304 ; NEW-NOT: call
 305 ; NEW: call void @_Z1gi(
 306 ; NEW-NOT: call
 307 ; NEW: call void @_Z1gi(
 308 ; NEW-NOT: call
 309 ; NEW: call void @_Z1fILb1ELi1EEvPbS0_(
 310 ; NEW-NOT: call
 311 ; NEW: call void @_Z1fILb0ELi1EEvPbS0_(
 312 ; NEW-NOT: call
 313 ; NEW: call void @_Z1fILb0ELi0EEvPbS0_(
 314 ; NEW-NOT: call
 315 ; NEW: call void @_Z1gi(
 316 ; NEW-NOT: call
 317 ; NEW: call void @_Z1fILb1ELi1EEvPbS0_(
 318 ; NEW-NOT: call
 319 ; NEW: call void @_Z1fILb0ELi1EEvPbS0_(
 320 ; NEW-NOT: call
 321 ; NEW: call void @_Z1fILb0ELi0EEvPbS0_(
 322 ; NEW-NOT: call
 323 define void @_Z1fILb1ELi2EEvPbS0_(i8* %B, i8* %E) {
 324 entry:
 325   call void @_Z1gi(i32 2)
 326   %cmp = icmp eq i8* %B, %E
 327   br i1 %cmp, label %if.end3, label %if.end
 328
 329 if.end:
 330   %0 = load i8, i8* %B, align 1
 331   %tobool = icmp eq i8 %0, 0
 332   %add.ptr2 = getelementptr inbounds i8, i8* %B, i64 1
 333   br i1 %tobool, label %if.else, label %if.then1
 334
 335 if.then1:
 336   call void @_Z1fILb1ELi3EEvPbS0_(i8* %add.ptr2, i8* %E)
 337   br label %if.end3
 338
 339 if.else:
 340   call void @_Z1fILb0ELi3EEvPbS0_(i8* %add.ptr2, i8* %E)
 341   br label %if.end3
 342
 343 if.end3:
 344   ret void
 345 }
 346
 347 ; CHECK-LABEL: define void @_Z1fILb0ELi3EEvPbS0_(
 348 ; OLD-NOT: call
 349 ; OLD: call void @_Z1fILb1ELi0EEvPbS0_(
 350 ; OLD-NOT: call
 351 ; OLD: call void @_Z1fILb0ELi0EEvPbS0_(
 352 ; OLD-NOT: call
 353 ; NEW-NOT: call
 354 ; NEW: call void @_Z1gi(
 355 ; NEW-NOT: call
 356 ; NEW: call void @_Z1fILb1ELi1EEvPbS0_(
 357 ; NEW-NOT: call
 358 ; NEW: call void @_Z1fILb0ELi1EEvPbS0_(
 359 ; NEW-NOT: call
 360 ; NEW: call void @_Z1fILb0ELi0EEvPbS0_(
 361 ; NEW-NOT: call
 362 define void @_Z1fILb0ELi3EEvPbS0_(i8* %B, i8* %E) {
 363 entry:
 364   %cmp = icmp eq i8* %B, %E
 365   br i1 %cmp, label %if.end3, label %if.end
 366
 367 if.end:
 368   %0 = load i8, i8* %B, align 1
 369   %tobool = icmp eq i8 %0, 0
 370   %add.ptr2 = getelementptr inbounds i8, i8* %B, i64 1
 371   br i1 %tobool, label %if.else, label %if.then1
 372
 373 if.then1:
 374   call void @_Z1fILb1ELi4EEvPbS0_(i8* %add.ptr2, i8* %E)
 375   br label %if.end3
 376
 377 if.else:
 378   call void @_Z1fILb0ELi4EEvPbS0_(i8* %add.ptr2, i8* %E)
 379   br label %if.end3
 380
 381 if.end3:
 382   ret void
 383 }
 384
 385 ; CHECK-LABEL: define void @_Z1fILb1ELi3EEvPbS0_(
 386 ; CHECK-NOT: call
 387 ; CHECK: call void @_Z1gi(
 388 ; CHECK-NOT: call
 389 ; CHECK: call void @_Z1fILb1ELi0EEvPbS0_(
 390 ; CHECK-NOT: call
 391 ; CHECK: call void @_Z1fILb0ELi0EEvPbS0_(
 392 ; CHECK-NOT: call
 393 define void @_Z1fILb1ELi3EEvPbS0_(i8* %B, i8* %E) {
 394 entry:
 395   call void @_Z1gi(i32 3)
 396   %cmp = icmp eq i8* %B, %E
 397   br i1 %cmp, label %if.end3, label %if.end
 398
 399 if.end:
 400   %0 = load i8, i8* %B, align 1
 401   %tobool = icmp eq i8 %0, 0
 402   %add.ptr2 = getelementptr inbounds i8, i8* %B, i64 1
 403   br i1 %tobool, label %if.else, label %if.then1
 404
 405 if.then1:
 406   call void @_Z1fILb1ELi4EEvPbS0_(i8* %add.ptr2, i8* %E)
 407   br label %if.end3
 408
 409 if.else:
 410   call void @_Z1fILb0ELi4EEvPbS0_(i8* %add.ptr2, i8* %E)
 411   br label %if.end3
 412
 413 if.end3:
 414   ret void
 415 }
 416
 417 ; CHECK-LABEL: define void @_Z1fILb0ELi4EEvPbS0_(
 418 ; CHECK-NOT: call
 419 ; CHECK: call void @_Z1fILb0ELi0EEvPbS0_(
 420 ; CHECK-NOT: call
 421 define void @_Z1fILb0ELi4EEvPbS0_(i8* %B, i8* %E) {
 422 entry:
 423   call void @_Z1fILb0ELi0EEvPbS0_(i8* %B, i8* %E)
 424   ret void
 425 }
 426
 427 ; CHECK-LABEL: define void @_Z1fILb1ELi4EEvPbS0_(
 428 ; OLD-NOT: call
 429 ; OLD: call void @_Z1fILb1ELi0EEvPbS0_(
 430 ; OLD-NOT: call
 431 ; NEW-NOT: call
 432 ; NEW: call void @_Z1gi(
 433 ; NEW-NOT: call
 434 ; NEW: call void @_Z1fILb1ELi1EEvPbS0_(
 435 ; NEW-NOT: call
 436 ; NEW: call void @_Z1fILb1ELi2EEvPbS0_(
 437 ; NEW-NOT: call
 438 ; NEW: call void @_Z1gi(
 439 ; NEW-NOT: call
 440 ; NEW: call void @_Z1fILb1ELi0EEvPbS0_(
 441 ; NEW-NOT: call
 442 ; NEW: call void @_Z1fILb0ELi0EEvPbS0_(
 443 ; NEW-NOT: call
 444 ; NEW: call void @_Z1fILb0ELi3EEvPbS0_(
 445 ; NEW-NOT: call
 446 define void @_Z1fILb1ELi4EEvPbS0_(i8* %B, i8* %E) {
 447 entry:
 448   call void @_Z1fILb1ELi0EEvPbS0_(i8* %B, i8* %E)
 449   ret void
 450 }
 451
 452 ; CHECK-LABEL: define void @_Z4testPbS_(
 453 ; CHECK: call
 454 ; CHECK-NOT: call
 455 define void @_Z4testPbS_(i8* %B, i8* %E) {
 456 entry:
 457   call void @_Z1fILb0ELi0EEvPbS0_(i8* %B, i8* %E)
 458   ret void
 459 }
 460