xref: /llvm-project/llvm/unittests/Analysis/FunctionPropertiesAnalysisTest.cpp (revision b8c39eb2756f140c506a5c957fb0f3eaed657316) 
1 //===- FunctionPropertiesAnalysisTest.cpp - Function Properties Unit Tests-===//
2 //
3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4 // See https://llvm.org/LICENSE.txt for license information.
5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6 //
7 //===----------------------------------------------------------------------===//
8 
9 #include "llvm/Analysis/FunctionPropertiesAnalysis.h"
10 #include "llvm/ADT/iterator_range.h"
11 #include "llvm/Analysis/AliasAnalysis.h"
12 #include "llvm/Analysis/LoopInfo.h"
13 #include "llvm/AsmParser/Parser.h"
14 #include "llvm/IR/Dominators.h"
15 #include "llvm/IR/Instructions.h"
16 #include "llvm/IR/LLVMContext.h"
17 #include "llvm/IR/Module.h"
18 #include "llvm/IR/PassManager.h"
19 #include "llvm/Passes/PassBuilder.h"
20 #include "llvm/Support/SourceMgr.h"
21 #include "llvm/Transforms/Utils/Cloning.h"
22 #include "gtest/gtest.h"
23 #include <cstring>
24 
25 using namespace llvm;
26 namespace {
27 
28 class FunctionPropertiesAnalysisTest : public testing::Test {
29 protected:
30   std::unique_ptr<DominatorTree> DT;
31   std::unique_ptr<LoopInfo> LI;
32 
33   FunctionPropertiesInfo buildFPI(Function &F) {
34     DT.reset(new DominatorTree(F));
35     LI.reset(new LoopInfo(*DT));
36     return FunctionPropertiesInfo::getFunctionPropertiesInfo(F, *LI);
37   }
38 
39   std::unique_ptr<Module> makeLLVMModule(LLVMContext &C, const char *IR) {
40     SMDiagnostic Err;
41     std::unique_ptr<Module> Mod = parseAssemblyString(IR, Err, C);
42     if (!Mod)
43       Err.print("MLAnalysisTests", errs());
44     return Mod;
45   }
46 
47   CallBase* findCall(Function& F, const char* Name = nullptr) {
48     for (auto &BB : F)
49       for (auto &I : BB )
50         if (auto *CB = dyn_cast<CallBase>(&I))
51           if (!Name || CB->getName() == Name)
52             return CB;
53     return nullptr;
54   }
55 };
56 
57 TEST_F(FunctionPropertiesAnalysisTest, BasicTest) {
58   LLVMContext C;
59   std::unique_ptr<Module> M = makeLLVMModule(C,
60                                              R"IR(
61 target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
62 target triple = "x86_64-pc-linux-gnu"
63 declare i32 @f1(i32)
64 declare i32 @f2(i32)
65 define i32 @branches(i32) {
66   %cond = icmp slt i32 %0, 3
67   br i1 %cond, label %then, label %else
68 then:
69   %ret.1 = call i32 @f1(i32 %0)
70   br label %last.block
71 else:
72   %ret.2 = call i32 @f2(i32 %0)
73   br label %last.block
74 last.block:
75   %ret = phi i32 [%ret.1, %then], [%ret.2, %else]
76   ret i32 %ret
77 }
78 define internal i32 @top() {
79   %1 = call i32 @branches(i32 2)
80   %2 = call i32 @f1(i32 %1)
81   ret i32 %2
82 }
83 )IR");
84 
85   Function *BranchesFunction = M->getFunction("branches");
86   FunctionPropertiesInfo BranchesFeatures = buildFPI(*BranchesFunction);
87   EXPECT_EQ(BranchesFeatures.BasicBlockCount, 4);
88   EXPECT_EQ(BranchesFeatures.BlocksReachedFromConditionalInstruction, 2);
89   // 2 Users: top is one. The other is added because @branches is not internal,
90   // so it may have external callers.
91   EXPECT_EQ(BranchesFeatures.Uses, 2);
92   EXPECT_EQ(BranchesFeatures.DirectCallsToDefinedFunctions, 0);
93   EXPECT_EQ(BranchesFeatures.LoadInstCount, 0);
94   EXPECT_EQ(BranchesFeatures.StoreInstCount, 0);
95   EXPECT_EQ(BranchesFeatures.MaxLoopDepth, 0);
96   EXPECT_EQ(BranchesFeatures.TopLevelLoopCount, 0);
97 
98   Function *TopFunction = M->getFunction("top");
99   FunctionPropertiesInfo TopFeatures = buildFPI(*TopFunction);
100   EXPECT_EQ(TopFeatures.BasicBlockCount, 1);
101   EXPECT_EQ(TopFeatures.BlocksReachedFromConditionalInstruction, 0);
102   EXPECT_EQ(TopFeatures.Uses, 0);
103   EXPECT_EQ(TopFeatures.DirectCallsToDefinedFunctions, 1);
104   EXPECT_EQ(BranchesFeatures.LoadInstCount, 0);
105   EXPECT_EQ(BranchesFeatures.StoreInstCount, 0);
106   EXPECT_EQ(BranchesFeatures.MaxLoopDepth, 0);
107   EXPECT_EQ(BranchesFeatures.TopLevelLoopCount, 0);
108 }
109 
110 TEST_F(FunctionPropertiesAnalysisTest, InlineSameBBSimple) {
111   LLVMContext C;
112   std::unique_ptr<Module> M = makeLLVMModule(C,
113                                              R"IR(
114 target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
115 target triple = "x86_64-pc-linux-gnu"
116 define i32 @f1(i32 %a) {
117   %b = call i32 @f2(i32 %a)
118   %c = add i32 %b, 2
119   ret i32 %c
120 }
121 
122 define i32 @f2(i32 %a) {
123   %b = add i32 %a, 1
124   ret i32 %b
125 }
126 )IR");
127 
128   Function *F1 = M->getFunction("f1");
129   CallBase* CB = findCall(*F1, "b");
130   EXPECT_NE(CB, nullptr);
131 
132   FunctionPropertiesInfo ExpectedInitial;
133   ExpectedInitial.BasicBlockCount = 1;
134   ExpectedInitial.TotalInstructionCount = 3;
135   ExpectedInitial.Uses = 1;
136   ExpectedInitial.DirectCallsToDefinedFunctions = 1;
137 
138   FunctionPropertiesInfo ExpectedFinal = ExpectedInitial;
139   ExpectedFinal.DirectCallsToDefinedFunctions = 0;
140 
141   auto FPI = buildFPI(*F1);
142   EXPECT_EQ(FPI, ExpectedInitial);
143 
144   FunctionPropertiesUpdater FPU(FPI, *CB);
145   InlineFunctionInfo IFI;
146   auto IR = llvm::InlineFunction(*CB, IFI);
147   EXPECT_TRUE(IR.isSuccess());
148   FPU.finish(*LI);
149   EXPECT_EQ(FPI, ExpectedFinal);
150 }
151 
152 TEST_F(FunctionPropertiesAnalysisTest, InlineSameBBLargerCFG) {
153   LLVMContext C;
154   std::unique_ptr<Module> M = makeLLVMModule(C,
155                                              R"IR(
156 target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
157 target triple = "x86_64-pc-linux-gnu"
158 define i32 @f1(i32 %a) {
159 entry:
160   %i = icmp slt i32 %a, 0
161   br i1 %i, label %if.then, label %if.else
162 if.then:
163   %b = call i32 @f2(i32 %a)
164   %c1 = add i32 %b, 2
165   br label %end
166 if.else:
167   %c2 = add i32 %a, 1
168   br label %end
169 end:
170   %ret = phi i32 [%c1, %if.then],[%c2, %if.else]
171   ret i32 %ret
172 }
173 
174 define i32 @f2(i32 %a) {
175   %b = add i32 %a, 1
176   ret i32 %b
177 }
178 )IR");
179 
180   Function *F1 = M->getFunction("f1");
181   CallBase* CB = findCall(*F1, "b");
182   EXPECT_NE(CB, nullptr);
183 
184   FunctionPropertiesInfo ExpectedInitial;
185   ExpectedInitial.BasicBlockCount = 4;
186   ExpectedInitial.BlocksReachedFromConditionalInstruction = 2;
187   ExpectedInitial.TotalInstructionCount = 9;
188   ExpectedInitial.Uses = 1;
189   ExpectedInitial.DirectCallsToDefinedFunctions = 1;
190 
191   FunctionPropertiesInfo ExpectedFinal = ExpectedInitial;
192   ExpectedFinal.DirectCallsToDefinedFunctions = 0;
193 
194   auto FPI = buildFPI(*F1);
195   EXPECT_EQ(FPI, ExpectedInitial);
196 
197   FunctionPropertiesUpdater FPU(FPI, *CB);
198   InlineFunctionInfo IFI;
199   auto IR = llvm::InlineFunction(*CB, IFI);
200   EXPECT_TRUE(IR.isSuccess());
201   FPU.finish(*LI);
202   EXPECT_EQ(FPI, ExpectedFinal);
203 }
204 
205 TEST_F(FunctionPropertiesAnalysisTest, InlineSameBBLoops) {
206   LLVMContext C;
207   std::unique_ptr<Module> M = makeLLVMModule(C,
208                                              R"IR(
209 target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
210 target triple = "x86_64-pc-linux-gnu"
211 define i32 @f1(i32 %a) {
212 entry:
213   %i = icmp slt i32 %a, 0
214   br i1 %i, label %if.then, label %if.else
215 if.then:
216   %b = call i32 @f2(i32 %a)
217   %c1 = add i32 %b, 2
218   br label %end
219 if.else:
220   %c2 = add i32 %a, 1
221   br label %end
222 end:
223   %ret = phi i32 [%c1, %if.then],[%c2, %if.else]
224   ret i32 %ret
225 }
226 
227 define i32 @f2(i32 %a) {
228 entry:
229   br label %loop
230 loop:
231   %indvar = phi i32 [%indvar.next, %loop], [0, %entry]
232   %b = add i32 %a, %indvar
233   %indvar.next = add i32 %indvar, 1
234   %cond = icmp slt i32 %indvar.next, %a
235   br i1 %cond, label %loop, label %exit
236 exit:
237   ret i32 %b
238 }
239 )IR");
240 
241   Function *F1 = M->getFunction("f1");
242   CallBase* CB = findCall(*F1, "b");
243   EXPECT_NE(CB, nullptr);
244 
245   FunctionPropertiesInfo ExpectedInitial;
246   ExpectedInitial.BasicBlockCount = 4;
247   ExpectedInitial.BlocksReachedFromConditionalInstruction = 2;
248   ExpectedInitial.TotalInstructionCount = 9;
249   ExpectedInitial.Uses = 1;
250   ExpectedInitial.DirectCallsToDefinedFunctions = 1;
251 
252   FunctionPropertiesInfo ExpectedFinal;
253   ExpectedFinal.BasicBlockCount = 6;
254   ExpectedFinal.BlocksReachedFromConditionalInstruction = 4;
255   ExpectedFinal.Uses = 1;
256   ExpectedFinal.MaxLoopDepth = 1;
257   ExpectedFinal.TopLevelLoopCount = 1;
258   ExpectedFinal.TotalInstructionCount = 14;
259 
260   auto FPI = buildFPI(*F1);
261   EXPECT_EQ(FPI, ExpectedInitial);
262   FunctionPropertiesUpdater FPU(FPI, *CB);
263   InlineFunctionInfo IFI;
264 
265   auto IR = llvm::InlineFunction(*CB, IFI);
266   EXPECT_TRUE(IR.isSuccess());
267   DominatorTree DTNew(*F1);
268   LoopInfo LINew(DTNew);
269   FPU.finish(LINew);
270   EXPECT_EQ(FPI, ExpectedFinal);
271 }
272 
273 TEST_F(FunctionPropertiesAnalysisTest, InvokeSimple) {
274   LLVMContext C;
275   std::unique_ptr<Module> M = makeLLVMModule(C,
276                                              R"IR(
277 target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
278 target triple = "x86_64-pc-linux-gnu"
279 declare void @might_throw()
280 
281 define internal void @callee() {
282 entry:
283   call void @might_throw()
284   ret void
285 }
286 
287 define i32 @caller() personality i32 (...)* @__gxx_personality_v0 {
288 entry:
289   invoke void @callee()
290       to label %cont unwind label %exc
291 
292 cont:
293   ret i32 0
294 
295 exc:
296   %exn = landingpad {i8*, i32}
297          cleanup
298   ret i32 1
299 }
300 
301 declare i32 @__gxx_personality_v0(...)
302 )IR");
303 
304   Function *F1 = M->getFunction("caller");
305   CallBase* CB = findCall(*F1);
306   EXPECT_NE(CB, nullptr);
307 
308   auto FPI = buildFPI(*F1);
309   FunctionPropertiesUpdater FPU(FPI, *CB);
310   InlineFunctionInfo IFI;
311   auto IR = llvm::InlineFunction(*CB, IFI);
312   EXPECT_TRUE(IR.isSuccess());
313   DominatorTree DTNew(*F1);
314   LoopInfo LINew(DTNew);
315   FPU.finish(LINew);
316   EXPECT_EQ(static_cast<size_t>(FPI.BasicBlockCount),
317             F1->getBasicBlockList().size());
318   EXPECT_EQ(static_cast<size_t>(FPI.TotalInstructionCount),
319             F1->getInstructionCount());
320 }
321 
322 TEST_F(FunctionPropertiesAnalysisTest, InvokeUnreachableHandler) {
323   LLVMContext C;
324   std::unique_ptr<Module> M = makeLLVMModule(C,
325                                              R"IR(
326 declare void @might_throw()
327 
328 define internal i32 @callee() personality i32 (...)* @__gxx_personality_v0 {
329 entry:
330   invoke void @might_throw()
331       to label %cont unwind label %exc
332 
333 cont:
334   ret i32 0
335 
336 exc:
337   %exn = landingpad {i8*, i32}
338          cleanup
339   resume { i8*, i32 } %exn
340 }
341 
342 define i32 @caller() personality i32 (...)* @__gxx_personality_v0 {
343 entry:
344   %X = invoke i32 @callee()
345            to label %cont unwind label %Handler
346 
347 cont:
348   ret i32 %X
349 
350 Handler:
351   %exn = landingpad {i8*, i32}
352          cleanup
353   ret i32 1
354 }
355 
356 declare i32 @__gxx_personality_v0(...)
357 )IR");
358 
359   Function *F1 = M->getFunction("caller");
360   CallBase* CB = findCall(*F1);
361   EXPECT_NE(CB, nullptr);
362 
363   auto FPI = buildFPI(*F1);
364   FunctionPropertiesUpdater FPU(FPI, *CB);
365   InlineFunctionInfo IFI;
366   auto IR = llvm::InlineFunction(*CB, IFI);
367   EXPECT_TRUE(IR.isSuccess());
368   DominatorTree DTNew(*F1);
369   LoopInfo LINew(DTNew);
370   FPU.finish(LINew);
371   EXPECT_EQ(static_cast<size_t>(FPI.BasicBlockCount),
372             F1->getBasicBlockList().size() - 1);
373   EXPECT_EQ(static_cast<size_t>(FPI.TotalInstructionCount),
374             F1->getInstructionCount() - 2);
375   EXPECT_EQ(FPI, FunctionPropertiesInfo::getFunctionPropertiesInfo(*F1, LINew));
376 }
377 
378 TEST_F(FunctionPropertiesAnalysisTest, Rethrow) {
379   LLVMContext C;
380   std::unique_ptr<Module> M = makeLLVMModule(C,
381                                              R"IR(
382 declare void @might_throw()
383 
384 define internal i32 @callee() personality i32 (...)* @__gxx_personality_v0 {
385 entry:
386   invoke void @might_throw()
387       to label %cont unwind label %exc
388 
389 cont:
390   ret i32 0
391 
392 exc:
393   %exn = landingpad {i8*, i32}
394          cleanup
395   resume { i8*, i32 } %exn
396 }
397 
398 define i32 @caller() personality i32 (...)* @__gxx_personality_v0 {
399 entry:
400   %X = invoke i32 @callee()
401            to label %cont unwind label %Handler
402 
403 cont:
404   ret i32 %X
405 
406 Handler:
407   %exn = landingpad {i8*, i32}
408          cleanup
409   ret i32 1
410 }
411 
412 declare i32 @__gxx_personality_v0(...)
413 )IR");
414 
415   Function *F1 = M->getFunction("caller");
416   CallBase* CB = findCall(*F1);
417   EXPECT_NE(CB, nullptr);
418 
419   auto FPI = buildFPI(*F1);
420   FunctionPropertiesUpdater FPU(FPI, *CB);
421   InlineFunctionInfo IFI;
422   auto IR = llvm::InlineFunction(*CB, IFI);
423   EXPECT_TRUE(IR.isSuccess());
424   DominatorTree DTNew(*F1);
425   LoopInfo LINew(DTNew);
426   FPU.finish(LINew);
427   EXPECT_EQ(static_cast<size_t>(FPI.BasicBlockCount),
428             F1->getBasicBlockList().size() - 1);
429   EXPECT_EQ(static_cast<size_t>(FPI.TotalInstructionCount),
430             F1->getInstructionCount() - 2);
431   EXPECT_EQ(FPI, FunctionPropertiesInfo::getFunctionPropertiesInfo(*F1, LINew));
432 }
433 
434 TEST_F(FunctionPropertiesAnalysisTest, LPadChanges) {
435   LLVMContext C;
436   std::unique_ptr<Module> M = makeLLVMModule(C,
437                                              R"IR(
438 declare void @external_func()
439 
440 @exception_type1 = external global i8
441 @exception_type2 = external global i8
442 
443 
444 define internal void @inner() personality i8* null {
445   invoke void @external_func()
446       to label %cont unwind label %lpad
447 cont:
448   ret void
449 lpad:
450   %lp = landingpad i32
451       catch i8* @exception_type1
452   resume i32 %lp
453 }
454 
455 define void @outer() personality i8* null {
456   invoke void @inner()
457       to label %cont unwind label %lpad
458 cont:
459   ret void
460 lpad:
461   %lp = landingpad i32
462       cleanup
463       catch i8* @exception_type2
464   resume i32 %lp
465 }
466 
467 )IR");
468 
469   Function *F1 = M->getFunction("outer");
470   CallBase* CB = findCall(*F1);
471   EXPECT_NE(CB, nullptr);
472 
473   auto FPI = buildFPI(*F1);
474   FunctionPropertiesUpdater FPU(FPI, *CB);
475   InlineFunctionInfo IFI;
476   auto IR = llvm::InlineFunction(*CB, IFI);
477   EXPECT_TRUE(IR.isSuccess());
478   DominatorTree DTNew(*F1);
479   LoopInfo LINew(DTNew);
480   FPU.finish(LINew);
481   EXPECT_EQ(static_cast<size_t>(FPI.BasicBlockCount),
482             F1->getBasicBlockList().size() - 1);
483   EXPECT_EQ(static_cast<size_t>(FPI.TotalInstructionCount),
484             F1->getInstructionCount() - 2);
485   EXPECT_EQ(FPI, FunctionPropertiesInfo::getFunctionPropertiesInfo(*F1, LINew));
486 }
487 
488 TEST_F(FunctionPropertiesAnalysisTest, LPadChangesConditional) {
489   LLVMContext C;
490   std::unique_ptr<Module> M = makeLLVMModule(C,
491                                              R"IR(
492 declare void @external_func()
493 
494 @exception_type1 = external global i8
495 @exception_type2 = external global i8
496 
497 
498 define internal void @inner() personality i8* null {
499   invoke void @external_func()
500       to label %cont unwind label %lpad
501 cont:
502   ret void
503 lpad:
504   %lp = landingpad i32
505       catch i8* @exception_type1
506   resume i32 %lp
507 }
508 
509 define void @outer(i32 %a) personality i8* null {
510 entry:
511   %i = icmp slt i32 %a, 0
512   br i1 %i, label %if.then, label %cont
513 if.then:
514   invoke void @inner()
515       to label %cont unwind label %lpad
516 cont:
517   ret void
518 lpad:
519   %lp = landingpad i32
520       cleanup
521       catch i8* @exception_type2
522   resume i32 %lp
523 }
524 
525 )IR");
526 
527   Function *F1 = M->getFunction("outer");
528   CallBase* CB = findCall(*F1);
529   EXPECT_NE(CB, nullptr);
530 
531   auto FPI = buildFPI(*F1);
532   FunctionPropertiesUpdater FPU(FPI, *CB);
533   InlineFunctionInfo IFI;
534   auto IR = llvm::InlineFunction(*CB, IFI);
535   EXPECT_TRUE(IR.isSuccess());
536   DominatorTree DTNew(*F1);
537   LoopInfo LINew(DTNew);
538   FPU.finish(LINew);
539   EXPECT_EQ(static_cast<size_t>(FPI.BasicBlockCount),
540             F1->getBasicBlockList().size() - 1);
541   EXPECT_EQ(static_cast<size_t>(FPI.TotalInstructionCount),
542             F1->getInstructionCount() - 2);
543   EXPECT_EQ(FPI, FunctionPropertiesInfo::getFunctionPropertiesInfo(*F1, LINew));
544 }
545 
546 TEST_F(FunctionPropertiesAnalysisTest, InlineSameLoopBB) {
547   LLVMContext C;
548   std::unique_ptr<Module> M = makeLLVMModule(C,
549                                              R"IR(
550 target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
551 target triple = "x86_64-pc-linux-gnu"
552 
553 declare i32 @a()
554 declare i32 @b()
555 
556 define i32 @f1(i32 %a) {
557 entry:
558   br label %loop
559 loop:
560   %i = call i32 @f2(i32 %a)
561   %c = icmp slt i32 %i, %a
562   br i1 %c, label %loop, label %end
563 end:
564   %r = phi i32 [%i, %loop], [%a, %entry]
565   ret i32 %r
566 }
567 
568 define i32 @f2(i32 %a) {
569   %cnd = icmp slt i32 %a, 0
570   br i1 %cnd, label %then, label %else
571 then:
572   %r1 = call i32 @a()
573   br label %end
574 else:
575   %r2 = call i32 @b()
576   br label %end
577 end:
578   %r = phi i32 [%r1, %then], [%r2, %else]
579   ret i32 %r
580 }
581 )IR");
582 
583   Function *F1 = M->getFunction("f1");
584   CallBase *CB = findCall(*F1);
585   EXPECT_NE(CB, nullptr);
586 
587   FunctionPropertiesInfo ExpectedInitial;
588   ExpectedInitial.BasicBlockCount = 3;
589   ExpectedInitial.TotalInstructionCount = 6;
590   ExpectedInitial.BlocksReachedFromConditionalInstruction = 2;
591   ExpectedInitial.Uses = 1;
592   ExpectedInitial.DirectCallsToDefinedFunctions = 1;
593   ExpectedInitial.MaxLoopDepth = 1;
594   ExpectedInitial.TopLevelLoopCount = 1;
595 
596   FunctionPropertiesInfo ExpectedFinal = ExpectedInitial;
597   ExpectedFinal.BasicBlockCount = 6;
598   ExpectedFinal.DirectCallsToDefinedFunctions = 0;
599   ExpectedFinal.BlocksReachedFromConditionalInstruction = 4;
600   ExpectedFinal.TotalInstructionCount = 12;
601 
602   auto FPI = buildFPI(*F1);
603   EXPECT_EQ(FPI, ExpectedInitial);
604 
605   FunctionPropertiesUpdater FPU(FPI, *CB);
606   InlineFunctionInfo IFI;
607   auto IR = llvm::InlineFunction(*CB, IFI);
608   EXPECT_TRUE(IR.isSuccess());
609   FPU.finish(*LI);
610   EXPECT_EQ(FPI, ExpectedFinal);
611 }
612 
613 } // end anonymous namespace
614