1/*
2 * Copyright (C) 2015 Apple Inc. All rights reserved.
3 *
4 * Redistribution and use in source and binary forms, with or without
5 * modification, are permitted provided that the following conditions
6 * are met:
7 * 1. Redistributions of source code must retain the above copyright
8 * notice, this list of conditions and the following disclaimer.
9 * 2. Redistributions in binary form must reproduce the above copyright
10 * notice, this list of conditions and the following disclaimer in the
11 * documentation and/or other materials provided with the distribution.
12 *
13 * THIS SOFTWARE IS PROVIDED BY APPLE INC. ``AS IS'' AND ANY
14 * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
15 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
16 * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL APPLE INC. OR
17 * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
18 * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
19 * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
20 * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY
21 * OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
22 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
23 * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
24 */
25
26// Compile like so:
27// clang++ -O3 -o ComplexTest ComplexTest.cpp -std=c++14 `~/Downloads/clang+llvm-3.7.0-x86_64-apple-darwin/bin/llvm-config --cppflags --cxxflags --ldflags --libs` -lcurses -g -lz
28
29#include <vector>
30#include <memory>
31#include <chrono>
32
33#include <sys/time.h>
34
35#include <llvm/Support/raw_ostream.h>
36#include <llvm/IR/LLVMContext.h>
37#include <llvm/IR/DataLayout.h>
38#include <llvm/IR/IRBuilder.h>
39#include <llvm/IR/Constants.h>
40#include <llvm/IR/Function.h>
41#include <llvm/IR/Instructions.h>
42#include <llvm/IR/Module.h>
43#include <llvm/IR/Verifier.h>
44#include <llvm/ExecutionEngine/ExecutionEngine.h>
45#include <llvm/Transforms/Utils/BasicBlockUtils.h>
46#include <llvm/Pass.h>
47#include <llvm/IR/LegacyPassManager.h>
48#include <llvm/Support/Host.h>
49#include <llvm/Analysis/Passes.h>
50#include <llvm/Transforms/Scalar.h>
51#include <llvm/Transforms/IPO.h>
52#include <llvm/Transforms/IPO/PassManagerBuilder.h>
53#include <llvm/ExecutionEngine/MCJIT.h>
54#include <llvm/Support/ErrorHandling.h>
55#include <llvm/Support/TargetSelect.h>
56
57using namespace llvm;
58using namespace std;
59
60namespace {
61
62template<typename ToType, typename FromType>
63inline ToType bitwise_cast(FromType from)
64{
65 static_assert(sizeof(FromType) == sizeof(ToType), "bitwise_cast size of FromType and ToType must be equal!");
66 union {
67 FromType from;
68 ToType to;
69 } u;
70 u.from = from;
71 return u.to;
72}
73
74double monotonicallyIncreasingTimeMS()
75{
76 return chrono::duration_cast<chrono::microseconds>(
77 chrono::steady_clock::now().time_since_epoch()).count() / 1000.;
78}
79
80void run(unsigned numVars, unsigned numConstructs)
81{
82 LLVMContext context;
83 Type* int32Ty = Type::getInt32Ty(context);
84 Module* module = new Module("complexModule", context);
85 Function* function = Function::Create(
86 FunctionType::get(int32Ty, false), GlobalValue::ExternalLinkage, "complexFunction", module);
87
88 vector<int32_t> varSlots;
89 for (unsigned i = numVars; i--;)
90 varSlots.push_back(i);
91
92 BasicBlock* current = BasicBlock::Create(context, "", function);
93 unique_ptr<IRBuilder<>> builder = make_unique<IRBuilder<>>(current);
94
95 vector<Value*> vars;
96 for (int32_t& varSlot : varSlots) {
97 Value* ptr = builder->CreateIntToPtr(builder->getInt64(bitwise_cast<intptr_t>(&varSlot)),
98 int32Ty->getPointerTo());
99 vars.push_back(builder->CreateLoad(ptr));
100 }
101
102 for (unsigned i = 0; i < numConstructs; ++i) {
103 if (i & 1) {
104 // Control flow diamond.
105 unsigned predicateVarIndex = (i >> 1) % numVars;
106 unsigned thenIncVarIndex = ((i >> 1) + 1) % numVars;
107 unsigned elseIncVarIndex = ((i >> 1) + 2) % numVars;
108
109 BasicBlock* thenBlock = BasicBlock::Create(context, "", function);
110 BasicBlock* elseBlock = BasicBlock::Create(context, "", function);
111 BasicBlock* continuation = BasicBlock::Create(context, "", function);
112
113 builder->CreateCondBr(
114 builder->CreateICmpNE(vars[predicateVarIndex], builder->getInt32(0)),
115 thenBlock, elseBlock);
116
117 builder = make_unique<IRBuilder<>>(thenBlock);
118 Value* thenValue = builder->CreateAdd(vars[thenIncVarIndex], builder->getInt32(1));
119 builder->CreateBr(continuation);
120
121 builder = make_unique<IRBuilder<>>(elseBlock);
122 Value* elseValue = builder->CreateAdd(vars[elseIncVarIndex], builder->getInt32(1));
123 builder->CreateBr(continuation);
124
125 builder = make_unique<IRBuilder<>>(current = continuation);
126 PHINode* thenPhi = builder->CreatePHI(int32Ty, 2);
127 thenPhi->addIncoming(thenValue, thenBlock);
128 thenPhi->addIncoming(vars[thenIncVarIndex], elseBlock);
129 PHINode* elsePhi = builder->CreatePHI(int32Ty, 2);
130 elsePhi->addIncoming(elseValue, elseBlock);
131 elsePhi->addIncoming(vars[elseIncVarIndex], thenBlock);
132
133 vars[thenIncVarIndex] = thenPhi;
134 vars[elseIncVarIndex] = elsePhi;
135 } else {
136 // Loop.
137
138 BasicBlock* loopBody = BasicBlock::Create(context, "", function);
139 BasicBlock* continuation = BasicBlock::Create(context, "", function);
140
141 Value* startIndex = vars[(i >> 1) % numVars];
142 Value* startSum = builder->getInt32(0);
143 builder->CreateCondBr(
144 builder->CreateICmpNE(startIndex, builder->getInt32(0)),
145 loopBody, continuation);
146
147 builder = make_unique<IRBuilder<>>(loopBody);
148 PHINode* bodyIndex = builder->CreatePHI(int32Ty, 2);
149 PHINode* bodySum = builder->CreatePHI(int32Ty, 2);
150 bodyIndex->addIncoming(startIndex, current);
151 bodySum->addIncoming(startSum, current);
152
153 Value* newBodyIndex = builder->CreateSub(bodyIndex, builder->getInt32(1));
154 Value* newBodySum = builder->CreateAdd(
155 bodySum,
156 builder->CreateLoad(
157 builder->CreateIntToPtr(
158 builder->CreateAdd(
159 builder->getInt64(bitwise_cast<intptr_t>(&varSlots[0])),
160 builder->CreateShl(
161 builder->CreateZExt(
162 builder->CreateAnd(
163 newBodyIndex,
164 builder->getInt32(numVars - 1)),
165 Type::getInt64Ty(context)),
166 builder->getInt64(2))),
167 int32Ty->getPointerTo())));
168 bodyIndex->addIncoming(newBodyIndex, loopBody);
169 bodySum->addIncoming(newBodySum, loopBody);
170 builder->CreateCondBr(
171 builder->CreateICmpNE(newBodyIndex, builder->getInt32(0)),
172 loopBody, continuation);
173
174 builder = make_unique<IRBuilder<>>(continuation);
175 PHINode* finalSum = builder->CreatePHI(int32Ty, 2);
176 finalSum->addIncoming(startSum, current);
177 finalSum->addIncoming(newBodySum, loopBody);
178 current = continuation;
179 }
180 }
181
182 builder->CreateRet(vars[0]);
183 builder = nullptr;
184
185 unique_ptr<ExecutionEngine> EE;
186 {
187 std::string errorMessage;
188 EngineBuilder builder((std::unique_ptr<Module>(module)));
189 builder.setMArch("");
190 builder.setMCPU(sys::getHostCPUName());
191 builder.setMAttrs(std::vector<std::string>());
192 builder.setRelocationModel(Reloc::Default);
193 builder.setCodeModel(CodeModel::JITDefault);
194 builder.setErrorStr(&errorMessage);
195 builder.setEngineKind(EngineKind::JIT);
196
197 builder.setOptLevel(CodeGenOpt::Default);
198
199 {
200 TargetOptions Options;
201 Options.FloatABIType = FloatABI::Default;
202
203 builder.setTargetOptions(Options);
204 }
205
206 EE = unique_ptr<ExecutionEngine>(builder.create());
207 }
208
209 legacy::PassManager passManager;
210 //passManager.add(new DataLayout(*EE->getDataLayout()));
211 passManager.add(createPromoteMemoryToRegisterPass());
212 passManager.add(createConstantPropagationPass());
213 passManager.add(createInstructionCombiningPass());
214 passManager.add(createBasicAliasAnalysisPass());
215 passManager.add(createTypeBasedAliasAnalysisPass());
216 passManager.add(createGVNPass());
217 passManager.add(createCFGSimplificationPass());
218 passManager.run(*module);
219
220 EE->getFunctionAddress(function->getName());
221}
222
223} // anonymous namespace
224
225int main(int c, char** v)
226{
227 InitializeAllTargets();
228 InitializeAllTargetMCs();
229 InitializeAllAsmPrinters();
230 InitializeAllAsmParsers();
231 for (unsigned i = 1; i <= 3; ++i) {
232 printf("Doing: run(64, %u)\n", i * 128);
233 double before = monotonicallyIncreasingTimeMS();
234 run(64, 128 * i);
235 double after = monotonicallyIncreasingTimeMS();
236 printf("That took %lf ms.\n", after - before);
237 }
238 return 0;
239}
240