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 45target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128" 46 47declare 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 61define void @_Z1fILb0ELi0EEvPbS0_(ptr %B, ptr %E) { 62entry: 63 %cmp = icmp eq ptr %B, %E 64 br i1 %cmp, label %if.end3, label %if.end 65 66if.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 72if.then1: 73 call void @_Z1fILb1ELi1EEvPbS0_(ptr %add.ptr2, ptr %E) 74 br label %if.end3 75 76if.else: 77 call void @_Z1fILb0ELi1EEvPbS0_(ptr %add.ptr2, ptr %E) 78 br label %if.end3 79 80if.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 94define void @_Z1fILb1ELi0EEvPbS0_(ptr %B, ptr %E) { 95entry: 96 call void @_Z1gi(i32 0) 97 %cmp = icmp eq ptr %B, %E 98 br i1 %cmp, label %if.end3, label %if.end 99 100if.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 106if.then1: 107 call void @_Z1fILb1ELi1EEvPbS0_(ptr %add.ptr2, ptr %E) 108 br label %if.end3 109 110if.else: 111 call void @_Z1fILb0ELi1EEvPbS0_(ptr %add.ptr2, ptr %E) 112 br label %if.end3 113 114if.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 126define void @_Z1fILb0ELi1EEvPbS0_(ptr %B, ptr %E) { 127entry: 128 %cmp = icmp eq ptr %B, %E 129 br i1 %cmp, label %if.end3, label %if.end 130 131if.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 137if.then1: 138 call void @_Z1fILb1ELi2EEvPbS0_(ptr %add.ptr2, ptr %E) 139 br label %if.end3 140 141if.else: 142 call void @_Z1fILb0ELi2EEvPbS0_(ptr %add.ptr2, ptr %E) 143 br label %if.end3 144 145if.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 163define void @_Z1fILb1ELi1EEvPbS0_(ptr %B, ptr %E) { 164entry: 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 170if.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 176if.then1: 177 call void @_Z1fILb1ELi2EEvPbS0_(ptr %add.ptr2, ptr %E) 178 br label %if.end3 179 180if.else: 181 call void @_Z1fILb0ELi2EEvPbS0_(ptr %add.ptr2, ptr %E) 182 br label %if.end3 183 184if.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 200define void @_Z1fILb0ELi2EEvPbS0_(ptr %B, ptr %E) { 201entry: 202 %cmp = icmp eq ptr %B, %E 203 br i1 %cmp, label %if.end3, label %if.end 204 205if.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 211if.then1: 212 call void @_Z1fILb1ELi3EEvPbS0_(ptr %add.ptr2, ptr %E) 213 br label %if.end3 214 215if.else: 216 call void @_Z1fILb0ELi3EEvPbS0_(ptr %add.ptr2, ptr %E) 217 br label %if.end3 218 219if.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 237define void @_Z1fILb1ELi2EEvPbS0_(ptr %B, ptr %E) { 238entry: 239 call void @_Z1gi(i32 2) 240 %cmp = icmp eq ptr %B, %E 241 br i1 %cmp, label %if.end3, label %if.end 242 243if.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 249if.then1: 250 call void @_Z1fILb1ELi3EEvPbS0_(ptr %add.ptr2, ptr %E) 251 br label %if.end3 252 253if.else: 254 call void @_Z1fILb0ELi3EEvPbS0_(ptr %add.ptr2, ptr %E) 255 br label %if.end3 256 257if.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 271define void @_Z1fILb0ELi3EEvPbS0_(ptr %B, ptr %E) { 272entry: 273 %cmp = icmp eq ptr %B, %E 274 br i1 %cmp, label %if.end3, label %if.end 275 276if.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 282if.then1: 283 call void @_Z1fILb1ELi4EEvPbS0_(ptr %add.ptr2, ptr %E) 284 br label %if.end3 285 286if.else: 287 call void @_Z1fILb0ELi4EEvPbS0_(ptr %add.ptr2, ptr %E) 288 br label %if.end3 289 290if.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 302define void @_Z1fILb1ELi3EEvPbS0_(ptr %B, ptr %E) { 303entry: 304 call void @_Z1gi(i32 3) 305 %cmp = icmp eq ptr %B, %E 306 br i1 %cmp, label %if.end3, label %if.end 307 308if.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 314if.then1: 315 call void @_Z1fILb1ELi4EEvPbS0_(ptr %add.ptr2, ptr %E) 316 br label %if.end3 317 318if.else: 319 call void @_Z1fILb0ELi4EEvPbS0_(ptr %add.ptr2, ptr %E) 320 br label %if.end3 321 322if.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 330define void @_Z1fILb0ELi4EEvPbS0_(ptr %B, ptr %E) { 331entry: 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 344define void @_Z1fILb1ELi4EEvPbS0_(ptr %B, ptr %E) { 345entry: 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 353define void @_Z4testPbS_(ptr %B, ptr %E) { 354entry: 355 call void @_Z1fILb0ELi0EEvPbS0_(ptr %B, ptr %E) 356 ret void 357} 358 359