examples/Fibonacci/fibonacci.cpp

   1 //===--- examples/Fibonacci/fibonacci.cpp - An example use of the JIT -----===//
   2 //
   3 //                     The LLVM Compiler Infrastructure
   4 //
   5 // This file was developed by Valery A. Khamenya and is distributed under the
   6 // University of Illinois Open Source License. See LICENSE.TXT for details.
   7 //
   8 //===----------------------------------------------------------------------===//
   9 //
  10 // This small program provides an example of how to build quickly a small
  11 // module with function Fibonacci and execute it with the JIT.
  12 //
  13 // This simple example shows as well 30% speed up with LLVM 1.3
  14 // in comparison to gcc 3.3.3 at AMD Athlon XP 1500+ .
  15 //
  16 // (Modified from HowToUseJIT.cpp and Stacker/lib/compiler/StackerCompiler.cpp)
  17 //
  18 //===------------------------------------------------------------------------===
  19 // Goal:
  20 //  The goal of this snippet is to create in the memory
  21 //  the LLVM module consisting of one function as follow:
  22 //
  23 // int fib(int x) {
  24 //   if(x<=2) return 1;
  25 //   return fib(x-1)+fib(x-2);
  26 // }
  27 //
  28 // then compile the module via JIT, then execute the `fib'
  29 // function and return result to a driver, i.e. to a "host program".
  30 //
  31
  32 #include <iostream>
  33
  34 #include <llvm/Module.h>
  35 #include <llvm/DerivedTypes.h>
  36 #include <llvm/Constants.h>
  37 #include <llvm/Instructions.h>
  38 #include <llvm/ModuleProvider.h>
  39 #include <llvm/Analysis/Verifier.h>
  40 #include "llvm/ExecutionEngine/ExecutionEngine.h"
  41 #include "llvm/ExecutionEngine/GenericValue.h"
  42
  43
  44 using namespace llvm;
  45
  46 int main(int argc, char**argv) {
  47
  48   int n = argc > 1 ? atol(argv[1]) : 44;
  49
  50   // Create some module to put our function into it.
  51   Module *M = new Module("test");
  52
  53
  54   // We are about to create the "fib" function:
  55   Function *FibF;
  56
  57   {
  58     // first create type for the single argument of fib function:
  59     // the type is 'int ()'
  60     std::vector<const Type*> ArgT(1);
  61     ArgT[0] = Type::IntTy;
  62
  63     // now create full type of the "fib" function:
  64     FunctionType *FibT = FunctionType::get(Type::IntTy, // type of result
  65                                            ArgT,
  66                                            /*not vararg*/false);
  67
  68     // Now create the fib function entry and
  69     // insert this entry into module M
  70     // (By passing a module as the last parameter to the Function constructor,
  71     // it automatically gets appended to the Module.)
  72     FibF = new Function(FibT,
  73                         Function::ExternalLinkage, // maybe too much
  74                         "fib", M);
  75
  76     // Add a basic block to the function... (again, it automatically inserts
  77     // because of the last argument.)
  78     BasicBlock *BB = new BasicBlock("EntryBlock of fib function", FibF);
  79
  80     // Get pointers to the constants ...
  81     Value *One = ConstantSInt::get(Type::IntTy, 1);
  82     Value *Two = ConstantSInt::get(Type::IntTy, 2);
  83
  84     // Get pointers to the integer argument of the add1 function...
  85     assert(FibF->abegin() != FibF->aend()); // Make sure there's an arg
  86
  87     Argument &ArgX = FibF->afront();  // Get the arg
  88     ArgX.setName("AnArg");            // Give it a nice symbolic name for fun.
  89
  90     SetCondInst* CondInst
  91       = new SetCondInst( Instruction::SetLE,
  92                          &ArgX, Two );
  93
  94     BB->getInstList().push_back(CondInst);
  95
  96     // Create the true_block
  97     BasicBlock* true_bb = new BasicBlock("arg<=2");
  98
  99
 100     // Create the return instruction and add it
 101     // to the basic block for true case:
 102     true_bb->getInstList().push_back(new ReturnInst(One));
 103
 104     // Create an exit block
 105     BasicBlock* exit_bb = new BasicBlock("arg>2");
 106
 107     {
 108
 109       // create fib(x-1)
 110       CallInst* CallFibX1;
 111       {
 112         // Create the sub instruction... does not insert...
 113         Instruction *Sub
 114           = BinaryOperator::create(Instruction::Sub, &ArgX, One,
 115                                                 "arg");
 116
 117         exit_bb->getInstList().push_back(Sub);
 118
 119         CallFibX1 = new CallInst(FibF, Sub, "fib(x-1)");
 120         exit_bb->getInstList().push_back(CallFibX1);
 121
 122       }
 123
 124       // create fib(x-2)
 125       CallInst* CallFibX2;
 126       {
 127         // Create the sub instruction... does not insert...
 128         Instruction * Sub
 129           = BinaryOperator::create(Instruction::Sub, &ArgX, Two,
 130                                                 "arg");
 131
 132         exit_bb->getInstList().push_back(Sub);
 133         CallFibX2 = new CallInst(FibF, Sub, "fib(x-2)");
 134         exit_bb->getInstList().push_back(CallFibX2);
 135
 136       }
 137
 138       // Create the add instruction... does not insert...
 139       Instruction *Add =
 140         BinaryOperator::create(Instruction::Add,
 141                                CallFibX1, CallFibX2, "addresult");
 142
 143       // explicitly insert it into the basic block...
 144       exit_bb->getInstList().push_back(Add);
 145
 146       // Create the return instruction and add it to the basic block
 147       exit_bb->getInstList().push_back(new ReturnInst(Add));
 148     }
 149
 150     // Create a branch on the SetCond
 151     BranchInst* br_inst =
 152       new BranchInst( true_bb, exit_bb, CondInst );
 153
 154     BB->getInstList().push_back( br_inst );
 155     FibF->getBasicBlockList().push_back(true_bb);
 156     FibF->getBasicBlockList().push_back(exit_bb);
 157   }
 158
 159   // Now we going to create JIT
 160   ExistingModuleProvider* MP = new ExistingModuleProvider(M);
 161   ExecutionEngine* EE = ExecutionEngine::create( MP, false );
 162
 163   // Call the `foo' function with argument n:
 164   std::vector<GenericValue> args(1);
 165   args[0].IntVal = n;
 166
 167
 168   std::clog << "verifying... ";
 169   if (verifyModule(*M)) {
 170     std::cerr << argv[0]
 171               << ": assembly parsed, but does not verify as correct!\n";
 172     return 1;
 173   }
 174   else
 175     std::clog << "OK\n";
 176
 177
 178   std::clog << "We just constructed this LLVM module:\n\n---------\n" << *M;
 179   std::clog << "---------\nstarting fibonacci("
 180             << n << ") with JIT...\n" << std::flush;
 181
 182   GenericValue gv = EE->runFunction(FibF, args);
 183
 184   // import result of execution:
 185   std::cout << "Result: " << gv.IntVal << std:: endl;
 186
 187   return 0;
 188 }