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