1//===- llvm/unittest/VMCore/PassManager.cpp - Constants unit tests ------===//
2//
3//                     The LLVM Compiler Infrastructure
4//
5// This file is distributed under the University of Illinois Open Source
6// License. See LICENSE.TXT for details.
7//
8//===----------------------------------------------------------------------===//
9
10#include "llvm/Module.h"
11#include "llvm/LLVMContext.h"
12#include "llvm/PassManager.h"
13#include "llvm/Analysis/LoopInfo.h"
14#include "llvm/Pass.h"
15#include "llvm/Analysis/LoopPass.h"
16#include "llvm/CallGraphSCCPass.h"
17#include "llvm/Target/TargetData.h"
18#include "llvm/Support/raw_ostream.h"
19#include "llvm/DerivedTypes.h"
20#include "llvm/Constants.h"
21#include "llvm/GlobalVariable.h"
22#include "llvm/Function.h"
23#include "llvm/CallingConv.h"
24#include "llvm/BasicBlock.h"
25#include "llvm/Instructions.h"
26#include "llvm/InlineAsm.h"
27#include "llvm/Support/MathExtras.h"
28#include "llvm/Support/raw_ostream.h"
29#include "llvm/PassManager.h"
30#include "llvm/ADT/SmallVector.h"
31#include "llvm/Analysis/Verifier.h"
32#include "llvm/Assembly/PrintModulePass.h"
33#include "gtest/gtest.h"
34
35using namespace llvm;
36
37namespace llvm {
38  void initializeModuleNDMPass(PassRegistry&);
39  void initializeFPassPass(PassRegistry&);
40  void initializeCGPassPass(PassRegistry&);
41  void initializeLPassPass(PassRegistry&);
42  void initializeBPassPass(PassRegistry&);
43
44  namespace {
45    // ND = no deps
46    // NM = no modifications
47    struct ModuleNDNM: public ModulePass {
48    public:
49      static char run;
50      static char ID;
51      ModuleNDNM() : ModulePass(ID) { }
52      virtual bool runOnModule(Module &M) {
53        run++;
54        return false;
55      }
56      virtual void getAnalysisUsage(AnalysisUsage &AU) const {
57        AU.setPreservesAll();
58      }
59    };
60    char ModuleNDNM::ID=0;
61    char ModuleNDNM::run=0;
62
63    struct ModuleNDM : public ModulePass {
64    public:
65      static char run;
66      static char ID;
67      ModuleNDM() : ModulePass(ID) {}
68      virtual bool runOnModule(Module &M) {
69        run++;
70        return true;
71      }
72    };
73    char ModuleNDM::ID=0;
74    char ModuleNDM::run=0;
75
76    struct ModuleNDM2 : public ModulePass {
77    public:
78      static char run;
79      static char ID;
80      ModuleNDM2() : ModulePass(ID) {}
81      virtual bool runOnModule(Module &M) {
82        run++;
83        return true;
84      }
85    };
86    char ModuleNDM2::ID=0;
87    char ModuleNDM2::run=0;
88
89    struct ModuleDNM : public ModulePass {
90    public:
91      static char run;
92      static char ID;
93      ModuleDNM() : ModulePass(ID) {
94        initializeModuleNDMPass(*PassRegistry::getPassRegistry());
95      }
96      virtual bool runOnModule(Module &M) {
97        EXPECT_TRUE(getAnalysisIfAvailable<TargetData>());
98        run++;
99        return false;
100      }
101      virtual void getAnalysisUsage(AnalysisUsage &AU) const {
102        AU.addRequired<ModuleNDM>();
103        AU.setPreservesAll();
104      }
105    };
106    char ModuleDNM::ID=0;
107    char ModuleDNM::run=0;
108
109    template<typename P>
110    struct PassTestBase : public P {
111    protected:
112      static int runc;
113      static bool initialized;
114      static bool finalized;
115      int allocated;
116      void run() {
117        EXPECT_TRUE(initialized);
118        EXPECT_FALSE(finalized);
119        EXPECT_EQ(0, allocated);
120        allocated++;
121        runc++;
122      }
123    public:
124      static char ID;
125      static void finishedOK(int run) {
126        EXPECT_GT(runc, 0);
127        EXPECT_TRUE(initialized);
128        EXPECT_TRUE(finalized);
129        EXPECT_EQ(run, runc);
130      }
131      PassTestBase() : P(ID), allocated(0) {
132        initialized = false;
133        finalized = false;
134        runc = 0;
135      }
136
137      virtual void releaseMemory() {
138        EXPECT_GT(runc, 0);
139        EXPECT_GT(allocated, 0);
140        allocated--;
141      }
142    };
143    template<typename P> char PassTestBase<P>::ID;
144    template<typename P> int PassTestBase<P>::runc;
145    template<typename P> bool PassTestBase<P>::initialized;
146    template<typename P> bool PassTestBase<P>::finalized;
147
148    template<typename T, typename P>
149    struct PassTest : public PassTestBase<P> {
150    public:
151      virtual bool doInitialization(T &t) {
152        EXPECT_FALSE(PassTestBase<P>::initialized);
153        PassTestBase<P>::initialized = true;
154        return false;
155      }
156      virtual bool doFinalization(T &t) {
157        EXPECT_FALSE(PassTestBase<P>::finalized);
158        PassTestBase<P>::finalized = true;
159        EXPECT_EQ(0, PassTestBase<P>::allocated);
160        return false;
161      }
162    };
163
164    struct CGPass : public PassTest<CallGraph, CallGraphSCCPass> {
165    public:
166      CGPass() {
167        initializeCGPassPass(*PassRegistry::getPassRegistry());
168      }
169      virtual bool runOnSCC(CallGraphSCC &SCMM) {
170        EXPECT_TRUE(getAnalysisIfAvailable<TargetData>());
171        run();
172        return false;
173      }
174    };
175
176    struct FPass : public PassTest<Module, FunctionPass> {
177    public:
178      virtual bool runOnFunction(Function &F) {
179        // FIXME: PR4112
180        // EXPECT_TRUE(getAnalysisIfAvailable<TargetData>());
181        run();
182        return false;
183      }
184    };
185
186    struct LPass : public PassTestBase<LoopPass> {
187    private:
188      static int initcount;
189      static int fincount;
190    public:
191      LPass() {
192        initializeLPassPass(*PassRegistry::getPassRegistry());
193        initcount = 0; fincount=0;
194        EXPECT_FALSE(initialized);
195      }
196      static void finishedOK(int run, int finalized) {
197        PassTestBase<LoopPass>::finishedOK(run);
198        EXPECT_EQ(run, initcount);
199        EXPECT_EQ(finalized, fincount);
200      }
201      virtual bool doInitialization(Loop* L, LPPassManager &LPM) {
202        initialized = true;
203        initcount++;
204        return false;
205      }
206      virtual bool runOnLoop(Loop *L, LPPassManager &LPM) {
207        EXPECT_TRUE(getAnalysisIfAvailable<TargetData>());
208        run();
209        return false;
210      }
211      virtual bool doFinalization() {
212        fincount++;
213        finalized = true;
214        return false;
215      }
216    };
217    int LPass::initcount=0;
218    int LPass::fincount=0;
219
220    struct BPass : public PassTestBase<BasicBlockPass> {
221    private:
222      static int inited;
223      static int fin;
224    public:
225      static void finishedOK(int run, int N) {
226        PassTestBase<BasicBlockPass>::finishedOK(run);
227        EXPECT_EQ(inited, N);
228        EXPECT_EQ(fin, N);
229      }
230      BPass() {
231        inited = 0;
232        fin = 0;
233      }
234      virtual bool doInitialization(Module &M) {
235        EXPECT_FALSE(initialized);
236        initialized = true;
237        return false;
238      }
239      virtual bool doInitialization(Function &F) {
240        inited++;
241        return false;
242      }
243      virtual bool runOnBasicBlock(BasicBlock &BB) {
244        EXPECT_TRUE(getAnalysisIfAvailable<TargetData>());
245        run();
246        return false;
247      }
248      virtual bool doFinalization(Function &F) {
249        fin++;
250        return false;
251      }
252      virtual bool doFinalization(Module &M) {
253        EXPECT_FALSE(finalized);
254        finalized = true;
255        EXPECT_EQ(0, allocated);
256        return false;
257      }
258    };
259    int BPass::inited=0;
260    int BPass::fin=0;
261
262    struct OnTheFlyTest: public ModulePass {
263    public:
264      static char ID;
265      OnTheFlyTest() : ModulePass(ID) {
266        initializeFPassPass(*PassRegistry::getPassRegistry());
267      }
268      virtual bool runOnModule(Module &M) {
269        EXPECT_TRUE(getAnalysisIfAvailable<TargetData>());
270        for (Module::iterator I=M.begin(),E=M.end(); I != E; ++I) {
271          Function &F = *I;
272          {
273            SCOPED_TRACE("Running on the fly function pass");
274            getAnalysis<FPass>(F);
275          }
276        }
277        return false;
278      }
279      virtual void getAnalysisUsage(AnalysisUsage &AU) const {
280        AU.addRequired<FPass>();
281      }
282    };
283    char OnTheFlyTest::ID=0;
284
285    TEST(PassManager, RunOnce) {
286      Module M("test-once", getGlobalContext());
287      struct ModuleNDNM *mNDNM = new ModuleNDNM();
288      struct ModuleDNM *mDNM = new ModuleDNM();
289      struct ModuleNDM *mNDM = new ModuleNDM();
290      struct ModuleNDM2 *mNDM2 = new ModuleNDM2();
291
292      mNDM->run = mNDNM->run = mDNM->run = mNDM2->run = 0;
293
294      PassManager Passes;
295      Passes.add(new TargetData(&M));
296      Passes.add(mNDM2);
297      Passes.add(mNDM);
298      Passes.add(mNDNM);
299      Passes.add(mDNM);
300
301      Passes.run(M);
302      // each pass must be run exactly once, since nothing invalidates them
303      EXPECT_EQ(1, mNDM->run);
304      EXPECT_EQ(1, mNDNM->run);
305      EXPECT_EQ(1, mDNM->run);
306      EXPECT_EQ(1, mNDM2->run);
307    }
308
309    TEST(PassManager, ReRun) {
310      Module M("test-rerun", getGlobalContext());
311      struct ModuleNDNM *mNDNM = new ModuleNDNM();
312      struct ModuleDNM *mDNM = new ModuleDNM();
313      struct ModuleNDM *mNDM = new ModuleNDM();
314      struct ModuleNDM2 *mNDM2 = new ModuleNDM2();
315
316      mNDM->run = mNDNM->run = mDNM->run = mNDM2->run = 0;
317
318      PassManager Passes;
319      Passes.add(new TargetData(&M));
320      Passes.add(mNDM);
321      Passes.add(mNDNM);
322      Passes.add(mNDM2);// invalidates mNDM needed by mDNM
323      Passes.add(mDNM);
324
325      Passes.run(M);
326      // Some passes must be rerun because a pass that modified the
327      // module/function was run in between
328      EXPECT_EQ(2, mNDM->run);
329      EXPECT_EQ(1, mNDNM->run);
330      EXPECT_EQ(1, mNDM2->run);
331      EXPECT_EQ(1, mDNM->run);
332    }
333
334    Module* makeLLVMModule();
335
336    template<typename T>
337    void MemoryTestHelper(int run) {
338      OwningPtr<Module> M(makeLLVMModule());
339      T *P = new T();
340      PassManager Passes;
341      Passes.add(new TargetData(M.get()));
342      Passes.add(P);
343      Passes.run(*M);
344      T::finishedOK(run);
345    }
346
347    template<typename T>
348    void MemoryTestHelper(int run, int N) {
349      Module *M = makeLLVMModule();
350      T *P = new T();
351      PassManager Passes;
352      Passes.add(new TargetData(M));
353      Passes.add(P);
354      Passes.run(*M);
355      T::finishedOK(run, N);
356      delete M;
357    }
358
359    TEST(PassManager, Memory) {
360      // SCC#1: test1->test2->test3->test1
361      // SCC#2: test4
362      // SCC#3: indirect call node
363      {
364        SCOPED_TRACE("Callgraph pass");
365        MemoryTestHelper<CGPass>(3);
366      }
367
368      {
369        SCOPED_TRACE("Function pass");
370        MemoryTestHelper<FPass>(4);// 4 functions
371      }
372
373      {
374        SCOPED_TRACE("Loop pass");
375        MemoryTestHelper<LPass>(2, 1); //2 loops, 1 function
376      }
377      {
378        SCOPED_TRACE("Basic block pass");
379        MemoryTestHelper<BPass>(7, 4); //9 basic blocks
380      }
381
382    }
383
384    TEST(PassManager, MemoryOnTheFly) {
385      Module *M = makeLLVMModule();
386      {
387        SCOPED_TRACE("Running OnTheFlyTest");
388        struct OnTheFlyTest *O = new OnTheFlyTest();
389        PassManager Passes;
390        Passes.add(new TargetData(M));
391        Passes.add(O);
392        Passes.run(*M);
393
394        FPass::finishedOK(4);
395      }
396      delete M;
397    }
398
399    Module* makeLLVMModule() {
400      // Module Construction
401      Module* mod = new Module("test-mem", getGlobalContext());
402      mod->setDataLayout("e-p:64:64:64-i1:8:8-i8:8:8-i16:16:16-i32:32:32-"
403                         "i64:64:64-f32:32:32-f64:64:64-v64:64:64-v128:128:128-"
404                         "a0:0:64-s0:64:64-f80:128:128");
405      mod->setTargetTriple("x86_64-unknown-linux-gnu");
406
407      // Type Definitions
408      std::vector<Type*>FuncTy_0_args;
409      FunctionType* FuncTy_0 = FunctionType::get(
410        /*Result=*/IntegerType::get(getGlobalContext(), 32),
411        /*Params=*/FuncTy_0_args,
412        /*isVarArg=*/false);
413
414      std::vector<Type*>FuncTy_2_args;
415      FuncTy_2_args.push_back(IntegerType::get(getGlobalContext(), 1));
416      FunctionType* FuncTy_2 = FunctionType::get(
417        /*Result=*/Type::getVoidTy(getGlobalContext()),
418        /*Params=*/FuncTy_2_args,
419        /*isVarArg=*/false);
420
421
422      // Function Declarations
423
424      Function* func_test1 = Function::Create(
425        /*Type=*/FuncTy_0,
426        /*Linkage=*/GlobalValue::ExternalLinkage,
427        /*Name=*/"test1", mod);
428      func_test1->setCallingConv(CallingConv::C);
429      AttrListPtr func_test1_PAL;
430      func_test1->setAttributes(func_test1_PAL);
431
432      Function* func_test2 = Function::Create(
433        /*Type=*/FuncTy_0,
434        /*Linkage=*/GlobalValue::ExternalLinkage,
435        /*Name=*/"test2", mod);
436      func_test2->setCallingConv(CallingConv::C);
437      AttrListPtr func_test2_PAL;
438      func_test2->setAttributes(func_test2_PAL);
439
440      Function* func_test3 = Function::Create(
441        /*Type=*/FuncTy_0,
442        /*Linkage=*/GlobalValue::ExternalLinkage,
443        /*Name=*/"test3", mod);
444      func_test3->setCallingConv(CallingConv::C);
445      AttrListPtr func_test3_PAL;
446      func_test3->setAttributes(func_test3_PAL);
447
448      Function* func_test4 = Function::Create(
449        /*Type=*/FuncTy_2,
450        /*Linkage=*/GlobalValue::ExternalLinkage,
451        /*Name=*/"test4", mod);
452      func_test4->setCallingConv(CallingConv::C);
453      AttrListPtr func_test4_PAL;
454      func_test4->setAttributes(func_test4_PAL);
455
456      // Global Variable Declarations
457
458
459      // Constant Definitions
460
461      // Global Variable Definitions
462
463      // Function Definitions
464
465      // Function: test1 (func_test1)
466      {
467
468        BasicBlock* label_entry = BasicBlock::Create(getGlobalContext(), "entry",func_test1,0);
469
470        // Block entry (label_entry)
471        CallInst* int32_3 = CallInst::Create(func_test2, "", label_entry);
472        int32_3->setCallingConv(CallingConv::C);
473        int32_3->setTailCall(false);AttrListPtr int32_3_PAL;
474        int32_3->setAttributes(int32_3_PAL);
475
476        ReturnInst::Create(getGlobalContext(), int32_3, label_entry);
477
478      }
479
480      // Function: test2 (func_test2)
481      {
482
483        BasicBlock* label_entry_5 = BasicBlock::Create(getGlobalContext(), "entry",func_test2,0);
484
485        // Block entry (label_entry_5)
486        CallInst* int32_6 = CallInst::Create(func_test3, "", label_entry_5);
487        int32_6->setCallingConv(CallingConv::C);
488        int32_6->setTailCall(false);AttrListPtr int32_6_PAL;
489        int32_6->setAttributes(int32_6_PAL);
490
491        ReturnInst::Create(getGlobalContext(), int32_6, label_entry_5);
492
493      }
494
495      // Function: test3 (func_test3)
496      {
497
498        BasicBlock* label_entry_8 = BasicBlock::Create(getGlobalContext(), "entry",func_test3,0);
499
500        // Block entry (label_entry_8)
501        CallInst* int32_9 = CallInst::Create(func_test1, "", label_entry_8);
502        int32_9->setCallingConv(CallingConv::C);
503        int32_9->setTailCall(false);AttrListPtr int32_9_PAL;
504        int32_9->setAttributes(int32_9_PAL);
505
506        ReturnInst::Create(getGlobalContext(), int32_9, label_entry_8);
507
508      }
509
510      // Function: test4 (func_test4)
511      {
512        Function::arg_iterator args = func_test4->arg_begin();
513        Value* int1_f = args++;
514        int1_f->setName("f");
515
516        BasicBlock* label_entry_11 = BasicBlock::Create(getGlobalContext(), "entry",func_test4,0);
517        BasicBlock* label_bb = BasicBlock::Create(getGlobalContext(), "bb",func_test4,0);
518        BasicBlock* label_bb1 = BasicBlock::Create(getGlobalContext(), "bb1",func_test4,0);
519        BasicBlock* label_return = BasicBlock::Create(getGlobalContext(), "return",func_test4,0);
520
521        // Block entry (label_entry_11)
522        BranchInst::Create(label_bb, label_entry_11);
523
524        // Block bb (label_bb)
525        BranchInst::Create(label_bb, label_bb1, int1_f, label_bb);
526
527        // Block bb1 (label_bb1)
528        BranchInst::Create(label_bb1, label_return, int1_f, label_bb1);
529
530        // Block return (label_return)
531        ReturnInst::Create(getGlobalContext(), label_return);
532
533      }
534      return mod;
535    }
536
537  }
538}
539
540INITIALIZE_PASS(ModuleNDM, "mndm", "mndm", false, false)
541INITIALIZE_PASS_BEGIN(CGPass, "cgp","cgp", false, false)
542INITIALIZE_AG_DEPENDENCY(CallGraph)
543INITIALIZE_PASS_END(CGPass, "cgp","cgp", false, false)
544INITIALIZE_PASS(FPass, "fp","fp", false, false)
545INITIALIZE_PASS_BEGIN(LPass, "lp","lp", false, false)
546INITIALIZE_PASS_DEPENDENCY(LoopInfo)
547INITIALIZE_PASS_END(LPass, "lp","lp", false, false)
548INITIALIZE_PASS(BPass, "bp","bp", false, false)
549