B3::reduceStrength's DCE should be more agro and less wrong
[WebKit-https.git] / Tools / ReducedFTL / ComplexTest.cpp
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
57 using namespace llvm;
58 using namespace std;
59
60 namespace {
61
62 template<typename ToType, typename FromType>
63 inline 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
74 double monotonicallyIncreasingTimeMS()
75 {
76     return chrono::duration_cast<chrono::microseconds>(
77         chrono::steady_clock::now().time_since_epoch()).count() / 1000.;
78 }
79
80 void 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
225 int 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(4, %u)\n", i * 128);
233         double before = monotonicallyIncreasingTimeMS();
234         run(4, 128 * i);
235         double after = monotonicallyIncreasingTimeMS();
236         printf("That took %lf ms.\n", after - before);
237     }
238     for (unsigned i = 1; i <= 3; ++i) {
239         printf("Doing: run(64, %u)\n", i * 128);
240         double before = monotonicallyIncreasingTimeMS();
241         run(64, 128 * i);
242         double after = monotonicallyIncreasingTimeMS();
243         printf("That took %lf ms.\n", after - before);
244     }
245     return 0;
246 }
247