fibonacci.cpp revision 8b477ed579794ba6d76915d56b3f448a7dd20120
166e7cd0eea6f116f3ed79acb8948c6d8db50833cReid Spencer//===--- examples/Fibonacci/fibonacci.cpp - An example use of the JIT -----===// 2237cef4b0b94b17ca065efad484f386f42579b61Misha Brukman// 3e784fa40c5808bfb88480f0ab3746ed378a939dfReid Spencer// The LLVM Compiler Infrastructure 4e784fa40c5808bfb88480f0ab3746ed378a939dfReid Spencer// 5fc001bbfc360ab828e5a4b0cbe4bb7db87361b85Chris Lattner// This file is distributed under the University of Illinois Open Source 6fc001bbfc360ab828e5a4b0cbe4bb7db87361b85Chris Lattner// License. See LICENSE.TXT for details. 7237cef4b0b94b17ca065efad484f386f42579b61Misha Brukman// 8e784fa40c5808bfb88480f0ab3746ed378a939dfReid Spencer//===----------------------------------------------------------------------===// 9e784fa40c5808bfb88480f0ab3746ed378a939dfReid Spencer// 1038f024daea1f27b6a8b610e3f8d21596f3e928d8Chris Lattner// This small program provides an example of how to build quickly a small module 1138f024daea1f27b6a8b610e3f8d21596f3e928d8Chris Lattner// with function Fibonacci and execute it with the JIT. 12e784fa40c5808bfb88480f0ab3746ed378a939dfReid Spencer// 1338f024daea1f27b6a8b610e3f8d21596f3e928d8Chris Lattner// The goal of this snippet is to create in the memory the LLVM module 1438f024daea1f27b6a8b610e3f8d21596f3e928d8Chris Lattner// consisting of one function as follow: 15e784fa40c5808bfb88480f0ab3746ed378a939dfReid Spencer// 1638f024daea1f27b6a8b610e3f8d21596f3e928d8Chris Lattner// int fib(int x) { 1738f024daea1f27b6a8b610e3f8d21596f3e928d8Chris Lattner// if(x<=2) return 1; 1838f024daea1f27b6a8b610e3f8d21596f3e928d8Chris Lattner// return fib(x-1)+fib(x-2); 1938f024daea1f27b6a8b610e3f8d21596f3e928d8Chris Lattner// } 20237cef4b0b94b17ca065efad484f386f42579b61Misha Brukman// 2138f024daea1f27b6a8b610e3f8d21596f3e928d8Chris Lattner// Once we have this, we compile the module via JIT, then execute the `fib' 22e784fa40c5808bfb88480f0ab3746ed378a939dfReid Spencer// function and return result to a driver, i.e. to a "host program". 23e784fa40c5808bfb88480f0ab3746ed378a939dfReid Spencer// 2438f024daea1f27b6a8b610e3f8d21596f3e928d8Chris Lattner//===----------------------------------------------------------------------===// 25e784fa40c5808bfb88480f0ab3746ed378a939dfReid Spencer 268b477ed579794ba6d76915d56b3f448a7dd20120Owen Anderson#include "llvm/LLVMContext.h" 2738f024daea1f27b6a8b610e3f8d21596f3e928d8Chris Lattner#include "llvm/Module.h" 2838f024daea1f27b6a8b610e3f8d21596f3e928d8Chris Lattner#include "llvm/DerivedTypes.h" 2938f024daea1f27b6a8b610e3f8d21596f3e928d8Chris Lattner#include "llvm/Constants.h" 3038f024daea1f27b6a8b610e3f8d21596f3e928d8Chris Lattner#include "llvm/Instructions.h" 3138f024daea1f27b6a8b610e3f8d21596f3e928d8Chris Lattner#include "llvm/ModuleProvider.h" 3238f024daea1f27b6a8b610e3f8d21596f3e928d8Chris Lattner#include "llvm/Analysis/Verifier.h" 33afebb449283ada1b44f423e698b30672606fdc54Jeff Cohen#include "llvm/ExecutionEngine/JIT.h" 34afebb449283ada1b44f423e698b30672606fdc54Jeff Cohen#include "llvm/ExecutionEngine/Interpreter.h" 35e784fa40c5808bfb88480f0ab3746ed378a939dfReid Spencer#include "llvm/ExecutionEngine/GenericValue.h" 36944fac71e082cc2664cc71b4d3f6c72bab7143fbChris Lattner#include "llvm/Support/raw_ostream.h" 37e784fa40c5808bfb88480f0ab3746ed378a939dfReid Spencerusing namespace llvm; 38e784fa40c5808bfb88480f0ab3746ed378a939dfReid Spencer 3938f024daea1f27b6a8b610e3f8d21596f3e928d8Chris Lattnerstatic Function *CreateFibFunction(Module *M) { 4038f024daea1f27b6a8b610e3f8d21596f3e928d8Chris Lattner // Create the fib function and insert it into module M. This function is said 4138f024daea1f27b6a8b610e3f8d21596f3e928d8Chris Lattner // to return an int and take an int parameter. 426a98754ebbc211958297b0d20a77e8c3261c3708Chris Lattner Function *FibF = 436a98754ebbc211958297b0d20a77e8c3261c3708Chris Lattner cast<Function>(M->getOrInsertFunction("fib", Type::Int32Ty, Type::Int32Ty, 446a98754ebbc211958297b0d20a77e8c3261c3708Chris Lattner (Type *)0)); 45237cef4b0b94b17ca065efad484f386f42579b61Misha Brukman 4638f024daea1f27b6a8b610e3f8d21596f3e928d8Chris Lattner // Add a basic block to the function. 47051a950000e21935165db56695e35bade668193bGabor Greif BasicBlock *BB = BasicBlock::Create("EntryBlock", FibF); 48237cef4b0b94b17ca065efad484f386f42579b61Misha Brukman 4938f024daea1f27b6a8b610e3f8d21596f3e928d8Chris Lattner // Get pointers to the constants. 50db8d2bed6a0ef890b81fabb014bfcb678e891695Reid Spencer Value *One = ConstantInt::get(Type::Int32Ty, 1); 51db8d2bed6a0ef890b81fabb014bfcb678e891695Reid Spencer Value *Two = ConstantInt::get(Type::Int32Ty, 2); 52e784fa40c5808bfb88480f0ab3746ed378a939dfReid Spencer 5338f024daea1f27b6a8b610e3f8d21596f3e928d8Chris Lattner // Get pointer to the integer argument of the add1 function... 54dadf88123f7abce7afe0db12beccc24c87e004a5Alkis Evlogimenos Argument *ArgX = FibF->arg_begin(); // Get the arg. 5538f024daea1f27b6a8b610e3f8d21596f3e928d8Chris Lattner ArgX->setName("AnArg"); // Give it a nice symbolic name for fun. 56e784fa40c5808bfb88480f0ab3746ed378a939dfReid Spencer 5738f024daea1f27b6a8b610e3f8d21596f3e928d8Chris Lattner // Create the true_block. 58051a950000e21935165db56695e35bade668193bGabor Greif BasicBlock *RetBB = BasicBlock::Create("return", FibF); 5938f024daea1f27b6a8b610e3f8d21596f3e928d8Chris Lattner // Create an exit block. 60051a950000e21935165db56695e35bade668193bGabor Greif BasicBlock* RecurseBB = BasicBlock::Create("recurse", FibF); 61e784fa40c5808bfb88480f0ab3746ed378a939dfReid Spencer 627520fcd7a5e4c17011588aab105dea9afa2ba3ecChris Lattner // Create the "if (arg <= 2) goto exitbb" 63e4d87aa2de6e52952dca73716386db09aad5a8fdReid Spencer Value *CondInst = new ICmpInst(ICmpInst::ICMP_SLE, ArgX, Two, "cond", BB); 64051a950000e21935165db56695e35bade668193bGabor Greif BranchInst::Create(RetBB, RecurseBB, CondInst, BB); 65e784fa40c5808bfb88480f0ab3746ed378a939dfReid Spencer 6638f024daea1f27b6a8b610e3f8d21596f3e928d8Chris Lattner // Create: ret int 1 67051a950000e21935165db56695e35bade668193bGabor Greif ReturnInst::Create(One, RetBB); 68237cef4b0b94b17ca065efad484f386f42579b61Misha Brukman 6938f024daea1f27b6a8b610e3f8d21596f3e928d8Chris Lattner // create fib(x-1) 707cbd8a3e92221437048b484d5ef9c0a22d0f8c58Gabor Greif Value *Sub = BinaryOperator::CreateSub(ArgX, One, "arg", RecurseBB); 71051a950000e21935165db56695e35bade668193bGabor Greif CallInst *CallFibX1 = CallInst::Create(FibF, Sub, "fibx1", RecurseBB); 72f6b5c1abce89dbd7e8e12407aa8e4a04f805fdf2Chris Lattner CallFibX1->setTailCall(); 73237cef4b0b94b17ca065efad484f386f42579b61Misha Brukman 7438f024daea1f27b6a8b610e3f8d21596f3e928d8Chris Lattner // create fib(x-2) 757cbd8a3e92221437048b484d5ef9c0a22d0f8c58Gabor Greif Sub = BinaryOperator::CreateSub(ArgX, Two, "arg", RecurseBB); 76051a950000e21935165db56695e35bade668193bGabor Greif CallInst *CallFibX2 = CallInst::Create(FibF, Sub, "fibx2", RecurseBB); 77f6b5c1abce89dbd7e8e12407aa8e4a04f805fdf2Chris Lattner CallFibX2->setTailCall(); 7847968e4dfd849b83a7eb958611c994e6b500998cChris Lattner 7938f024daea1f27b6a8b610e3f8d21596f3e928d8Chris Lattner 8038f024daea1f27b6a8b610e3f8d21596f3e928d8Chris Lattner // fib(x-1)+fib(x-2) 817cbd8a3e92221437048b484d5ef9c0a22d0f8c58Gabor Greif Value *Sum = BinaryOperator::CreateAdd(CallFibX1, CallFibX2, 8238f024daea1f27b6a8b610e3f8d21596f3e928d8Chris Lattner "addresult", RecurseBB); 83237cef4b0b94b17ca065efad484f386f42579b61Misha Brukman 8438f024daea1f27b6a8b610e3f8d21596f3e928d8Chris Lattner // Create the return instruction and add it to the basic block 85051a950000e21935165db56695e35bade668193bGabor Greif ReturnInst::Create(Sum, RecurseBB); 86e784fa40c5808bfb88480f0ab3746ed378a939dfReid Spencer 8738f024daea1f27b6a8b610e3f8d21596f3e928d8Chris Lattner return FibF; 8838f024daea1f27b6a8b610e3f8d21596f3e928d8Chris Lattner} 89e784fa40c5808bfb88480f0ab3746ed378a939dfReid Spencer 90e784fa40c5808bfb88480f0ab3746ed378a939dfReid Spencer 9138f024daea1f27b6a8b610e3f8d21596f3e928d8Chris Lattnerint main(int argc, char **argv) { 9238f024daea1f27b6a8b610e3f8d21596f3e928d8Chris Lattner int n = argc > 1 ? atol(argv[1]) : 24; 93e784fa40c5808bfb88480f0ab3746ed378a939dfReid Spencer 948b477ed579794ba6d76915d56b3f448a7dd20120Owen Anderson LLVMContext Context; 958b477ed579794ba6d76915d56b3f448a7dd20120Owen Anderson 9638f024daea1f27b6a8b610e3f8d21596f3e928d8Chris Lattner // Create some module to put our function into it. 978b477ed579794ba6d76915d56b3f448a7dd20120Owen Anderson Module *M = new Module("test", &Context); 9838f024daea1f27b6a8b610e3f8d21596f3e928d8Chris Lattner 9938f024daea1f27b6a8b610e3f8d21596f3e928d8Chris Lattner // We are about to create the "fib" function: 10038f024daea1f27b6a8b610e3f8d21596f3e928d8Chris Lattner Function *FibF = CreateFibFunction(M); 101e784fa40c5808bfb88480f0ab3746ed378a939dfReid Spencer 102237cef4b0b94b17ca065efad484f386f42579b61Misha Brukman // Now we going to create JIT 10338f024daea1f27b6a8b610e3f8d21596f3e928d8Chris Lattner ExistingModuleProvider *MP = new ExistingModuleProvider(M); 10438f024daea1f27b6a8b610e3f8d21596f3e928d8Chris Lattner ExecutionEngine *EE = ExecutionEngine::create(MP, false); 105e784fa40c5808bfb88480f0ab3746ed378a939dfReid Spencer 106944fac71e082cc2664cc71b4d3f6c72bab7143fbChris Lattner errs() << "verifying... "; 107e784fa40c5808bfb88480f0ab3746ed378a939dfReid Spencer if (verifyModule(*M)) { 108944fac71e082cc2664cc71b4d3f6c72bab7143fbChris Lattner errs() << argv[0] << ": Error constructing function!\n"; 109e784fa40c5808bfb88480f0ab3746ed378a939dfReid Spencer return 1; 110e784fa40c5808bfb88480f0ab3746ed378a939dfReid Spencer } 111e784fa40c5808bfb88480f0ab3746ed378a939dfReid Spencer 112944fac71e082cc2664cc71b4d3f6c72bab7143fbChris Lattner errs() << "OK\n"; 113944fac71e082cc2664cc71b4d3f6c72bab7143fbChris Lattner errs() << "We just constructed this LLVM module:\n\n---------\n" << *M; 114944fac71e082cc2664cc71b4d3f6c72bab7143fbChris Lattner errs() << "---------\nstarting fibonacci(" << n << ") with JIT...\n"; 115e784fa40c5808bfb88480f0ab3746ed378a939dfReid Spencer 1167cf540bba0b262681a14058d01ad41a87ac870dfMisha Brukman // Call the Fibonacci function with argument n: 11738f024daea1f27b6a8b610e3f8d21596f3e928d8Chris Lattner std::vector<GenericValue> Args(1); 11834bd70de3c344034b82dc9a964a6b6893efa3e82Reid Spencer Args[0].IntVal = APInt(32, n); 11938f024daea1f27b6a8b610e3f8d21596f3e928d8Chris Lattner GenericValue GV = EE->runFunction(FibF, Args); 120e784fa40c5808bfb88480f0ab3746ed378a939dfReid Spencer 12138f024daea1f27b6a8b610e3f8d21596f3e928d8Chris Lattner // import result of execution 122944fac71e082cc2664cc71b4d3f6c72bab7143fbChris Lattner outs() << "Result: " << GV.IntVal << "\n"; 123e784fa40c5808bfb88480f0ab3746ed378a939dfReid Spencer return 0; 124e784fa40c5808bfb88480f0ab3746ed378a939dfReid Spencer} 125