359 lines · plain
1; This test creates a monster SCC with a very pernicious call graph. It builds2; a cycle of cross-connected pairs of functions with interesting inlining3; decisions throughout, but ultimately trivial code complexity.4;5; Typically, a greedy approach to inlining works well for bottom-up inliners6; such as LLVM's. However, there is no way to be bottom-up over an SCC: it's7; a cycle! Greedily inlining as much as possible into each function of this8; *SCC* will have the disasterous effect of inlining all N-1 functions into the9; first one visited, N-2 functions into the second one visited, N-3 into the10; third, and so on. This is because until inlining occurs, each function in11; 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 an15; SCC there is no "right" or "wrong" answer here as long as no function blows up16; to be *huge*. The specific concerning pattern is if one or more functions get17; 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 were22; removed. The order of the fuctions is also made more predictable than Clang's23; 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; else35; 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,NEW43; RUN: opt -S < %s -passes=inliner-wrapper -inline-threshold=150 | FileCheck %s --check-prefixes=CHECK,NEW44 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: call51; NEW: call void @_Z1gi(52; NEW-NOT: call53; NEW: call void @_Z1fILb1ELi2EEvPbS0_(54; NEW-NOT: call55; NEW: call void @_Z1fILb0ELi2EEvPbS0_(56; NEW-NOT: call57; NEW: call void @_Z1fILb1ELi2EEvPbS0_(58; NEW-NOT: call59; NEW: call void @_Z1fILb0ELi2EEvPbS0_(60; NEW-NOT: call61define void @_Z1fILb0ELi0EEvPbS0_(ptr %B, ptr %E) {62entry:63 %cmp = icmp eq ptr %B, %E64 br i1 %cmp, label %if.end3, label %if.end65 66if.end:67 %0 = load i8, ptr %B, align 168 %tobool = icmp eq i8 %0, 069 %add.ptr2 = getelementptr inbounds i8, ptr %B, i64 170 br i1 %tobool, label %if.else, label %if.then171 72if.then1:73 call void @_Z1fILb1ELi1EEvPbS0_(ptr %add.ptr2, ptr %E)74 br label %if.end375 76if.else:77 call void @_Z1fILb0ELi1EEvPbS0_(ptr %add.ptr2, ptr %E)78 br label %if.end379 80if.end3:81 ret void82}83 84; CHECK-LABEL: define void @_Z1fILb1ELi0EEvPbS0_(85; NEW-NOT: call86; NEW: call void @_Z1gi(87; NEW-NOT: call88; NEW: call void @_Z1fILb1ELi1EEvPbS0_(89; NEW-NOT: call90; NEW: call void @_Z1fILb1ELi2EEvPbS0_(91; NEW-NOT: call92; NEW: call void @_Z1fILb0ELi2EEvPbS0_(93; NEW-NOT: call94define void @_Z1fILb1ELi0EEvPbS0_(ptr %B, ptr %E) {95entry:96 call void @_Z1gi(i32 0)97 %cmp = icmp eq ptr %B, %E98 br i1 %cmp, label %if.end3, label %if.end99 100if.end:101 %0 = load i8, ptr %B, align 1102 %tobool = icmp eq i8 %0, 0103 %add.ptr2 = getelementptr inbounds i8, ptr %B, i64 1104 br i1 %tobool, label %if.else, label %if.then1105 106if.then1:107 call void @_Z1fILb1ELi1EEvPbS0_(ptr %add.ptr2, ptr %E)108 br label %if.end3109 110if.else:111 call void @_Z1fILb0ELi1EEvPbS0_(ptr %add.ptr2, ptr %E)112 br label %if.end3113 114if.end3:115 ret void116}117 118; CHECK-LABEL: define void @_Z1fILb0ELi1EEvPbS0_(119; NEW-NOT: call120; NEW: call void @_Z1fILb1ELi2EEvPbS0_(121; NEW-NOT: call122; NEW: call void @_Z1fILb1ELi3EEvPbS0_(123; NEW-NOT: call124; NEW: call void @_Z1fILb0ELi3EEvPbS0_(125; NEW-NOT: call126define void @_Z1fILb0ELi1EEvPbS0_(ptr %B, ptr %E) {127entry:128 %cmp = icmp eq ptr %B, %E129 br i1 %cmp, label %if.end3, label %if.end130 131if.end:132 %0 = load i8, ptr %B, align 1133 %tobool = icmp eq i8 %0, 0134 %add.ptr2 = getelementptr inbounds i8, ptr %B, i64 1135 br i1 %tobool, label %if.else, label %if.then1136 137if.then1:138 call void @_Z1fILb1ELi2EEvPbS0_(ptr %add.ptr2, ptr %E)139 br label %if.end3140 141if.else:142 call void @_Z1fILb0ELi2EEvPbS0_(ptr %add.ptr2, ptr %E)143 br label %if.end3144 145if.end3:146 ret void147}148 149; CHECK-LABEL: define void @_Z1fILb1ELi1EEvPbS0_(150; NEW-NOT: call151; NEW: call void @_Z1gi(152; NEW-NOT: call153; NEW: call void @_Z1gi(154; NEW-NOT: call155; NEW: call void @_Z1fILb1ELi3EEvPbS0_(156; NEW-NOT: call157; NEW: call void @_Z1fILb0ELi3EEvPbS0_(158; NEW-NOT: call159; NEW: call void @_Z1fILb1ELi3EEvPbS0_(160; NEW-NOT: call161; NEW: call void @_Z1fILb0ELi3EEvPbS0_(162; NEW-NOT: call163define void @_Z1fILb1ELi1EEvPbS0_(ptr %B, ptr %E) {164entry:165 call void @_Z1gi(i32 1)166 %cmp = icmp eq ptr %B, %E167; CHECK-NOT: call168 br i1 %cmp, label %if.end3, label %if.end169 170if.end:171 %0 = load i8, ptr %B, align 1172 %tobool = icmp eq i8 %0, 0173 %add.ptr2 = getelementptr inbounds i8, ptr %B, i64 1174 br i1 %tobool, label %if.else, label %if.then1175 176if.then1:177 call void @_Z1fILb1ELi2EEvPbS0_(ptr %add.ptr2, ptr %E)178 br label %if.end3179 180if.else:181 call void @_Z1fILb0ELi2EEvPbS0_(ptr %add.ptr2, ptr %E)182 br label %if.end3183 184if.end3:185 ret void186}187 188; CHECK-LABEL: define void @_Z1fILb0ELi2EEvPbS0_(189; NEW-NOT: call190; NEW: call void @_Z1gi(191; NEW-NOT: call192; NEW: call void @_Z1fILb1ELi0EEvPbS0_(193; NEW-NOT: call194; NEW: call void @_Z1fILb0ELi0EEvPbS0_(195; NEW-NOT: call196; NEW: call void @_Z1fILb1ELi4EEvPbS0_(197; NEW-NOT: call198; NEW: call void @_Z1fILb0ELi4EEvPbS0_(199; NEW-NOT: call200define void @_Z1fILb0ELi2EEvPbS0_(ptr %B, ptr %E) {201entry:202 %cmp = icmp eq ptr %B, %E203 br i1 %cmp, label %if.end3, label %if.end204 205if.end:206 %0 = load i8, ptr %B, align 1207 %tobool = icmp eq i8 %0, 0208 %add.ptr2 = getelementptr inbounds i8, ptr %B, i64 1209 br i1 %tobool, label %if.else, label %if.then1210 211if.then1:212 call void @_Z1fILb1ELi3EEvPbS0_(ptr %add.ptr2, ptr %E)213 br label %if.end3214 215if.else:216 call void @_Z1fILb0ELi3EEvPbS0_(ptr %add.ptr2, ptr %E)217 br label %if.end3218 219if.end3:220 ret void221}222 223; CHECK-LABEL: define void @_Z1fILb1ELi2EEvPbS0_(224; NEW-NOT: call225; NEW: call void @_Z1gi(226; NEW-NOT: call227; NEW: call void @_Z1gi(228; NEW-NOT: call229; NEW: call void @_Z1fILb1ELi4EEvPbS0_(230; NEW-NOT: call231; NEW: call void @_Z1fILb0ELi4EEvPbS0_(232; NEW-NOT: call233; NEW: call void @_Z1fILb1ELi4EEvPbS0_(234; NEW-NOT: call235; NEW: call void @_Z1fILb0ELi4EEvPbS0_(236; NEW-NOT: call237define void @_Z1fILb1ELi2EEvPbS0_(ptr %B, ptr %E) {238entry:239 call void @_Z1gi(i32 2)240 %cmp = icmp eq ptr %B, %E241 br i1 %cmp, label %if.end3, label %if.end242 243if.end:244 %0 = load i8, ptr %B, align 1245 %tobool = icmp eq i8 %0, 0246 %add.ptr2 = getelementptr inbounds i8, ptr %B, i64 1247 br i1 %tobool, label %if.else, label %if.then1248 249if.then1:250 call void @_Z1fILb1ELi3EEvPbS0_(ptr %add.ptr2, ptr %E)251 br label %if.end3252 253if.else:254 call void @_Z1fILb0ELi3EEvPbS0_(ptr %add.ptr2, ptr %E)255 br label %if.end3256 257if.end3:258 ret void259}260 261; CHECK-LABEL: define void @_Z1fILb0ELi3EEvPbS0_(262; NEW-NOT: call263; NEW: call void @_Z1gi(264; NEW-NOT: call265; NEW: call void @_Z1fILb1ELi1EEvPbS0_(266; NEW-NOT: call267; NEW: call void @_Z1fILb0ELi1EEvPbS0_(268; NEW-NOT: call269; NEW: call void @_Z1fILb0ELi0EEvPbS0_(270; NEW-NOT: call271define void @_Z1fILb0ELi3EEvPbS0_(ptr %B, ptr %E) {272entry:273 %cmp = icmp eq ptr %B, %E274 br i1 %cmp, label %if.end3, label %if.end275 276if.end:277 %0 = load i8, ptr %B, align 1278 %tobool = icmp eq i8 %0, 0279 %add.ptr2 = getelementptr inbounds i8, ptr %B, i64 1280 br i1 %tobool, label %if.else, label %if.then1281 282if.then1:283 call void @_Z1fILb1ELi4EEvPbS0_(ptr %add.ptr2, ptr %E)284 br label %if.end3285 286if.else:287 call void @_Z1fILb0ELi4EEvPbS0_(ptr %add.ptr2, ptr %E)288 br label %if.end3289 290if.end3:291 ret void292}293 294; CHECK-LABEL: define void @_Z1fILb1ELi3EEvPbS0_(295; CHECK-NOT: call296; CHECK: call void @_Z1gi(297; CHECK-NOT: call298; CHECK: call void @_Z1fILb1ELi0EEvPbS0_(299; CHECK-NOT: call300; CHECK: call void @_Z1fILb0ELi0EEvPbS0_(301; CHECK-NOT: call302define void @_Z1fILb1ELi3EEvPbS0_(ptr %B, ptr %E) {303entry:304 call void @_Z1gi(i32 3)305 %cmp = icmp eq ptr %B, %E306 br i1 %cmp, label %if.end3, label %if.end307 308if.end:309 %0 = load i8, ptr %B, align 1310 %tobool = icmp eq i8 %0, 0311 %add.ptr2 = getelementptr inbounds i8, ptr %B, i64 1312 br i1 %tobool, label %if.else, label %if.then1313 314if.then1:315 call void @_Z1fILb1ELi4EEvPbS0_(ptr %add.ptr2, ptr %E)316 br label %if.end3317 318if.else:319 call void @_Z1fILb0ELi4EEvPbS0_(ptr %add.ptr2, ptr %E)320 br label %if.end3321 322if.end3:323 ret void324}325 326; CHECK-LABEL: define void @_Z1fILb0ELi4EEvPbS0_(327; CHECK-NOT: call328; CHECK: call void @_Z1fILb0ELi0EEvPbS0_(329; CHECK-NOT: call330define void @_Z1fILb0ELi4EEvPbS0_(ptr %B, ptr %E) {331entry:332 call void @_Z1fILb0ELi0EEvPbS0_(ptr %B, ptr %E)333 ret void334}335 336; CHECK-LABEL: define void @_Z1fILb1ELi4EEvPbS0_(337; NEW-NOT: call338; NEW: call void @_Z1gi(339; NEW-NOT: call340; NEW: call void @_Z1fILb1ELi1EEvPbS0_(341; NEW-NOT: call342; NEW: call void @_Z1fILb0ELi1EEvPbS0_(343; NEW-NOT: call344define void @_Z1fILb1ELi4EEvPbS0_(ptr %B, ptr %E) {345entry:346 call void @_Z1fILb1ELi0EEvPbS0_(ptr %B, ptr %E)347 ret void348}349 350; CHECK-LABEL: define void @_Z4testPbS_(351; CHECK: call352; CHECK-NOT: call353define void @_Z4testPbS_(ptr %B, ptr %E) {354entry:355 call void @_Z1fILb0ELi0EEvPbS0_(ptr %B, ptr %E)356 ret void357}358 359