source: icGREP/icgrep-devel/icgrep/generate_predefined_ucd_functions.cpp @ 4750

Last change on this file since 4750 was 4750, checked in by cameron, 4 years ago

Clean ups for compilation with gcc 4.8

File size: 22.2 KB
Line 
1/*
2 *  Copyright (c) 2015 International Characters.
3 *  This software is licensed to the public under the Open Software License 3.0.
4 *  icgrep is a trademark of International Characters.
5 */
6
7#include <cc/cc_compiler.h>
8#include <UCD/unicode_set.h>
9#include <UCD/PropertyObjectTable.h>
10#include <UCD/ucd_compiler.hpp>
11#include <pablo/pablo_compiler.h>
12#include <pablo/builder.hpp>
13#include <pablo/function.h>
14#include <llvm/Support/CommandLine.h>
15#include <utf_encoding.h>
16#include <pablo/optimizers/pablo_simplifier.hpp>
17#include <pablo/optimizers/pablo_codesinking.hpp>
18#ifdef ENABLE_MULTIPLEXING
19#include <pablo/optimizers/pablo_automultiplexing.hpp>
20#endif
21#include <llvm/IR/Verifier.h>
22#include <llvm/Support/Debug.h>
23#include <llvm/Support/TargetRegistry.h>
24#include <llvm/Support/TargetSelect.h>
25#include <llvm/Target/TargetLibraryInfo.h>
26#include <llvm/Target/TargetMachine.h>
27#include <llvm/Support/Host.h>
28#include <llvm/ADT/Triple.h>
29#include <llvm/Support/ToolOutputFile.h>
30#include <llvm/Pass.h>
31#include <llvm/PassManager.h>
32#include <llvm/ADT/STLExtras.h>
33#include <llvm/Target/TargetSubtargetInfo.h>
34#include <llvm/Support/FormattedStream.h>
35#include "llvm/Support/FileSystem.h"
36#include <llvm/Transforms/Scalar.h>
37#include <llvm/Support/raw_ostream.h>
38#include <llvm/Analysis/DependenceAnalysis.h>
39#include <boost/container/flat_map.hpp>
40#include <queue>
41#include <unordered_map>
42#include <pablo/printer_pablos.h>
43#include <llvm/Analysis/PostDominators.h>
44
45using namespace pablo;
46using namespace UCD;
47using namespace cc;
48using namespace llvm;
49using namespace boost::container;
50
51enum IfHierarchy {DefaultIfHierarchy, NoIfHierarchy};
52
53static cl::opt<std::string>
54ObjectFilename("o", cl::desc("Output object filename"), cl::value_desc("filename"), cl::Required);
55
56static cl::opt<std::string>
57UCDSourcePath("dir", cl::desc("UCD source code directory"), cl::value_desc("directory"), cl::Required);
58
59static cl::opt<std::string>
60PrintLongestDependenceChain("ldc", cl::desc("print longest dependency chain metrics."), cl::value_desc("filename"));
61
62static cl::opt<IfHierarchy> IfHierarchyStrategy(cl::desc("If Hierarchy strategy:"),
63                                                cl::values(clEnumVal(DefaultIfHierarchy, "Default"),
64                                                           clEnumVal(NoIfHierarchy, "None"),
65                                                           clEnumValEnd));
66
67
68
69
70static raw_fd_ostream * LongestDependenceChainFile = nullptr;
71
72#ifdef ENABLE_MULTIPLEXING
73static cl::opt<bool> EnableMultiplexing("multiplexing", cl::init(false),
74    cl::desc("combine Advances whose inputs are mutual exclusive into the fewest number of advances possible (expensive)."));
75
76static cl::opt<std::string>
77MultiplexingDistribution("multiplexing-dist",
78    cl::desc("Generate a CSV containing the # of Advances found in each UCD function before and after applying multiplexing."),
79    cl::value_desc("filename"));
80
81static raw_fd_ostream * MultiplexingDistributionFile = nullptr;
82#else
83const bool EnableMultiplexing = false;
84#endif
85
86using property_list = std::vector<std::string>;
87
88/** ------------------------------------------------------------------------------------------------------------- *
89 * @brief getNumOfAdvances
90 ** ------------------------------------------------------------------------------------------------------------- */
91unsigned getNumOfAdvances(const PabloBlock & entry) {
92    unsigned advances = 0;
93    for (const Statement * stmt : entry ) {
94        if (isa<Advance>(stmt)) {
95            ++advances;
96        }
97        else if (LLVM_UNLIKELY(isa<If>(stmt) || isa<While>(stmt))) {
98            advances += getNumOfAdvances(isa<If>(stmt) ? cast<If>(stmt)->getBody() : cast<While>(stmt)->getBody());
99        }
100    }
101    return advances;
102}
103
104/** ------------------------------------------------------------------------------------------------------------- *
105 * @brief computePabloDependencyMetrics
106 ** ------------------------------------------------------------------------------------------------------------- */
107unsigned computePabloDependencyChainMetrics(const PabloBlock & b, std::unordered_map<const PabloAST *, unsigned> & G) {
108    unsigned lpl = 0;
109    flat_map<const PabloAST *, unsigned> L;
110    for (const Statement * stmt : b) {
111        unsigned local_lpl = 0;
112        unsigned global_lpl = 0;
113        for (unsigned i = 0; i != stmt->getNumOperands(); ++i) {
114            const PabloAST * const op = stmt->getOperand(i);
115            if (isa<String>(op) || isa<Integer>(op)) {
116                continue;
117            }
118            const auto l = L.find(op);
119            if (l != L.end()) {
120                local_lpl = std::max<unsigned>(local_lpl, l->second);
121            }
122            const auto g = G.find(op);
123            if (LLVM_UNLIKELY(g == G.end())) {
124                throw std::runtime_error("Could not find dependency chain length for all operands!");
125            }
126            global_lpl = std::max<unsigned>(global_lpl, g->second);
127        }
128        L.emplace(stmt, local_lpl + 1);
129        G.insert(std::make_pair(stmt, global_lpl + 1));
130        if (LLVM_UNLIKELY(isa<If>(stmt) || isa<While>(stmt))) {
131            for (const auto & l : L) {
132                lpl = std::max(lpl, l.second);
133            }
134            L.clear();
135            lpl = std::max(lpl, computePabloDependencyChainMetrics(isa<If>(stmt) ? cast<If>(stmt)->getBody() : cast<While>(stmt)->getBody(), G));
136        }
137    }
138    return lpl;
139}
140
141/** ------------------------------------------------------------------------------------------------------------- *
142 * @brief computePabloDependencyMetrics
143 ** ------------------------------------------------------------------------------------------------------------- */
144std::pair<unsigned, unsigned> computePabloDependencyChainMetrics(const PabloFunction * f) {
145    std::unordered_map<const PabloAST *, unsigned> G;
146    G.insert(std::make_pair(f->getEntryBlock().createZeroes(), 0));
147    G.insert(std::make_pair(f->getEntryBlock().createOnes(), 0));
148    for (unsigned i = 0; i != f->getNumOfParameters(); ++i) {
149        G.insert(std::make_pair(f->getParameter(i), 0));
150    }
151    const unsigned local_lpl = computePabloDependencyChainMetrics(f->getEntryBlock(), G);
152    unsigned global_lpl = 0;
153    for (unsigned i = 0; i != f->getNumOfResults(); ++i) {
154        const auto e = G.find(f->getResult(i));
155        if (e == G.end()) {
156            throw std::runtime_error("No result computed!");
157        }
158        global_lpl = std::max<unsigned>(global_lpl, e->second);
159    }
160    return std::make_pair(global_lpl, local_lpl);
161}
162
163/** ------------------------------------------------------------------------------------------------------------- *
164 * @brief computeLLVMDependencyMetrics
165 ** ------------------------------------------------------------------------------------------------------------- */
166unsigned computeLLVMDependencyChainMetrics(const DomTreeNode * t, std::unordered_map<const Value *, unsigned> & G) {
167    unsigned lpl = 0;
168    if (true) {
169        flat_map<const Value *, unsigned> L;
170        const BasicBlock * b = t->getBlock();
171        for (auto itr = b->rbegin(); itr != b->rend(); ++itr) {
172            unsigned local_lpl = 0;
173            unsigned global_lpl = 0;
174            const Instruction & inst = *itr;
175            for (const Value * user : inst.users()) {
176                if (LLVM_LIKELY(isa<Instruction>(user))) {
177                    const auto l = L.find(user);
178                    if (l != L.end()) {
179                        local_lpl = std::max<unsigned>(local_lpl, l->second);
180                    }
181                    const auto g = G.find(user);
182                    if (LLVM_UNLIKELY(g == G.end())) {
183                        throw std::runtime_error("Could not find chain length for all users!");
184                    }
185                    global_lpl = std::max<unsigned>(global_lpl, g->second);
186                }
187            }
188            L.emplace(&inst, local_lpl + 1);
189            G.insert(std::make_pair(&inst, global_lpl + 1));
190            lpl = std::max(lpl, local_lpl + 1);
191        }
192    }
193    for (const DomTreeNode * pt : *t) {
194        lpl = std::max(lpl, computeLLVMDependencyChainMetrics(pt, G));
195    }
196    return lpl;
197}
198
199/** ------------------------------------------------------------------------------------------------------------- *
200 * @brief computeLLVMDependencyMetrics
201 ** ------------------------------------------------------------------------------------------------------------- */
202std::pair<unsigned, unsigned> computeLLVMDependencyChainMetrics(llvm::Function * f) {
203    std::unordered_map<const llvm::Value *, unsigned> G;
204
205    auto itr = f->getArgumentList().begin();
206    const Argument & input = *itr++;
207    const Argument & output = *itr;
208    for (const User * user : output.users()) {
209        G.insert(std::make_pair(user, 0));
210    }
211
212    PostDominatorTree dt;
213    dt.runOnFunction(*f);
214    const unsigned local_lpl = computeLLVMDependencyChainMetrics(dt.getRootNode(), G);
215    dt.releaseMemory();
216
217    unsigned global_lpl = 0;
218    for (const User * user : input.users()) {
219        const auto e = G.find(user);
220        if (e == G.end()) {
221            throw std::runtime_error("No result computed!");
222        }
223        global_lpl = std::max<unsigned>(global_lpl, e->second);
224    }
225    return std::make_pair(global_lpl, local_lpl);
226}
227
228/** ------------------------------------------------------------------------------------------------------------- *
229 * @brief compileUnicodeSet
230 ** ------------------------------------------------------------------------------------------------------------- */
231void compileUnicodeSet(std::string name, const UnicodeSet & set, PabloCompiler & pc, Module * module) {
232    #ifdef ENABLE_MULTIPLEXING
233    if (MultiplexingDistributionFile) {
234        (*MultiplexingDistributionFile) << name;
235    }
236    #endif
237    if (LongestDependenceChainFile) {
238        (*LongestDependenceChainFile) << name;
239    }
240    //std::cerr << name << std::endl;
241
242    PabloFunction * function = PabloFunction::Create(std::move(name), 8, 1);
243    Encoding encoding(Encoding::Type::UTF_8, 8);
244    CC_Compiler ccCompiler(*function, encoding);
245    UCDCompiler ucdCompiler(ccCompiler);
246    PabloBuilder builder(function->getEntryBlock());
247    // Build the unicode set function
248    PabloAST * result = nullptr;
249    if (IfHierarchyStrategy == IfHierarchy::DefaultIfHierarchy) {
250        result = ucdCompiler.generateWithDefaultIfHierarchy(set, builder);
251    } else if (IfHierarchyStrategy == IfHierarchy::NoIfHierarchy) {
252        result = ucdCompiler.generateWithoutIfHierarchy(set, builder);
253    } else {
254        throw std::runtime_error("Unknown if hierarchy strategy!");
255    }
256    function->setResult(0, builder.createAssign("matches", result));
257    // Optimize it at the pablo level
258    Simplifier::optimize(*function);
259    CodeSinking::optimize(*function);
260
261    #ifdef ENABLE_MULTIPLEXING
262    if (EnableMultiplexing) {
263        if (LongestDependenceChainFile) {
264            const auto pablo_metrix = computePabloDependencyChainMetrics(function);
265            (*LongestDependenceChainFile) << ',' << pablo_metrix.first << ',' << pablo_metrix.second;
266            Module module("tmp", getGlobalContext());
267            llvm::Function * func = pc.compile(function, &module);
268            const auto llvm_metrix = computeLLVMDependencyChainMetrics(func);
269            (*LongestDependenceChainFile) << ',' << llvm_metrix.first << ',' << llvm_metrix.second;
270        }
271
272        if (MultiplexingDistributionFile) {
273            (*MultiplexingDistributionFile) << ',' << getNumOfAdvances(function->getEntryBlock());
274        }
275        AutoMultiplexing::optimize(*function);
276        if (MultiplexingDistributionFile) {
277            (*MultiplexingDistributionFile) << ',' << getNumOfAdvances(function->getEntryBlock()) << '\n';
278        }
279    }
280    #endif
281    // Now compile the function ...
282    llvm::Function * func = pc.compile(function, module);
283    releaseSlabAllocatorMemory();
284
285    if (LongestDependenceChainFile) {
286        const auto pablo_metrix = computePabloDependencyChainMetrics(function);
287        (*LongestDependenceChainFile) << ',' << pablo_metrix.first << ',' << pablo_metrix.second;
288        const auto llvm_metrix = computeLLVMDependencyChainMetrics(func);
289        (*LongestDependenceChainFile) << ',' << llvm_metrix.first << ',' << llvm_metrix.second << '\n';
290    }
291
292}
293
294/** ------------------------------------------------------------------------------------------------------------- *
295 * @brief writePropertyInstaller
296 ** ------------------------------------------------------------------------------------------------------------- */
297
298void writePrecompiledProperties(property_list && properties) {
299
300    const std::string headerFilename = UCDSourcePath + "/precompiled_properties.h";
301    #ifdef USE_LLVM_3_5
302    std::string error;
303    raw_fd_ostream header(headerFilename.c_str(), error, sys::fs::F_None);
304    if (!error.empty()) {
305        throw std::runtime_error(error);
306    }
307    #else
308    std::error_code error;
309    raw_fd_ostream header(headerFilename, error, sys::fs::F_None);
310    if (error) {
311        throw std::runtime_error(error.message());
312    }
313    #endif
314
315    header << "#ifndef PRECOMPILED_PROPERTIES\n";
316    header << "#define PRECOMPILED_PROPERTIES\n\n";
317    header << "#include <string>\n\n";
318    header << "#include <tuple>\n";
319    header << "namespace UCD {\n\n";
320    header << "using ExternalProperty = std::tuple<void *, unsigned, unsigned>;\n\n";
321    header << "const ExternalProperty & resolveExternalProperty(const std::string & name);\n\n";
322    header << "}\n\n";
323    header << "#endif\n";
324    header.close();
325
326    const std::string cppFilename = UCDSourcePath + "/precompiled_properties.cpp";
327    #ifdef USE_LLVM_3_5
328    raw_fd_ostream cpp(cppFilename.c_str(), error, sys::fs::F_None);
329    if (!error.empty()) {
330        throw std::runtime_error(error);
331    }
332    #else
333    raw_fd_ostream cpp(cppFilename, error, sys::fs::F_None);
334    if (error) {
335        throw std::runtime_error(error.message());
336    }
337    #endif
338
339    cpp << "#include \"precompiled_properties.h\"\n";
340    cpp << "#include <include/simd-lib/bitblock.hpp>\n";
341    cpp << "#include <stdexcept>\n";
342    cpp << "#include <unordered_map>\n\n";
343    cpp << "namespace UCD {\nnamespace {\n\n";
344    cpp << "struct Input {\n    BitBlock bit[8];\n};\n\n";
345    cpp << "struct Output {\n    BitBlock bit[1];\n};\n\n";
346    for (auto prop : properties) {
347        cpp << "extern \"C\" void " + prop + "(const Input &, Output &);\n";
348    }
349
350    cpp << "\nconst static std::unordered_map<std::string, ExternalProperty> EXTERNAL_UCD_PROPERTY_MAP = {\n";
351    for (auto itr = properties.begin(); itr != properties.end(); ) {
352        cpp << "    {\"" + *itr + "\", std::make_tuple(reinterpret_cast<void *>(&" + *itr + "), 8, 1)}";
353        if (++itr != properties.end()) {
354            cpp << ",";
355        }
356        cpp << "\n";
357    }
358    cpp << "};\n\n} // end of anonymous namespace\n\n";
359
360    cpp << "const ExternalProperty & resolveExternalProperty(const std::string & name) {\n";
361    cpp << "    auto f = EXTERNAL_UCD_PROPERTY_MAP.find(name);\n";
362    cpp << "    if (f == EXTERNAL_UCD_PROPERTY_MAP.end())\n";
363    cpp << "        throw std::runtime_error(\"No external property named \\\"\" + name + \"\\\" found!\");\n";
364    cpp << "    return f->second;\n";
365    cpp << "}\n\n} // end of UCD namespace\n";
366
367    cpp.close();
368
369}
370
371/** ------------------------------------------------------------------------------------------------------------- *
372 * @brief generateUCDModule
373 ** ------------------------------------------------------------------------------------------------------------- */
374Module * generateUCDModule() {
375
376    property_list properties;
377
378    PabloCompiler pc;
379    Module * module = new Module("ucd", getGlobalContext());
380    for (PropertyObject * obj : property_object_table) {
381        if (EnumeratedPropertyObject * enumObj = dyn_cast<EnumeratedPropertyObject>(obj)) {
382            for (const std::string value : *enumObj) {
383                const UnicodeSet & set = enumObj->GetCodepointSet(canonicalize_value_name(value));
384                std::string name = "__get_" + property_enum_name[enumObj->getPropertyCode()] + "_" + value;
385                compileUnicodeSet(name, set, pc, module);
386                properties.emplace_back(name);
387            }
388        }
389        else if (ExtensionPropertyObject * extObj = dyn_cast<ExtensionPropertyObject>(obj)) {
390            for (const std::string value : *extObj) {
391                const UnicodeSet & set = extObj->GetCodepointSet(canonicalize_value_name(value));
392                std::string name = "__get_" + property_enum_name[extObj->getPropertyCode()] + "_" + value;
393                compileUnicodeSet(name, set, pc, module);
394                properties.emplace_back(name);
395            }
396        }
397        else if (BinaryPropertyObject * binObj = dyn_cast<BinaryPropertyObject>(obj)) {
398            const UnicodeSet & set = binObj->GetCodepointSet(Binary_ns::Y);
399            std::string name = "__get_" + property_enum_name[binObj->getPropertyCode()] + "_Y";
400            compileUnicodeSet(name, set, pc, module);
401            properties.emplace_back(name);
402        }
403    }
404
405    // Print an error message if our module is malformed in any way.
406    verifyModule(*module, &dbgs());
407
408    writePrecompiledProperties(std::move(properties));
409
410    return module;
411}
412
413/** ------------------------------------------------------------------------------------------------------------- *
414 * @brief compileUCDModule
415 ** ------------------------------------------------------------------------------------------------------------- */
416void compileUCDModule(Module * module) {
417    Triple TheTriple;
418
419    TheTriple.setTriple(sys::getDefaultTargetTriple());
420
421    // Get the target specific parser.
422    std::string msg;
423    const Target * TheTarget = TargetRegistry::lookupTarget(TheTriple.getTriple(), msg);
424    if (TheTarget == nullptr) {
425        throw std::runtime_error(msg);
426    }
427
428    TargetOptions Options;
429
430    std::unique_ptr<TargetMachine> Target(
431                TheTarget->createTargetMachine(TheTriple.getTriple(), sys::getHostCPUName(), "", Options,
432                                               Reloc::Default, CodeModel::Small, CodeGenOpt::Aggressive));
433
434    if (Target == nullptr) {
435        throw std::runtime_error("Could not allocate target machine!");
436    }
437
438    #ifdef USE_LLVM_3_5
439    std::string error;
440    std::unique_ptr<tool_output_file> out = make_unique<tool_output_file>(ObjectFilename.c_str(), error, sys::fs::F_None);
441    if (!error.empty()) {
442        throw std::runtime_error(error);
443    }
444    #else
445    std::error_code error;
446    std::unique_ptr<tool_output_file> out = make_unique<tool_output_file>(ObjectFilename, error, sys::fs::F_None);
447    if (error) {
448        throw std::runtime_error(error.message());
449    }
450    #endif
451
452    // Build up all of the passes that we want to do to the module.
453    PassManager PM;
454
455    // Add an appropriate TargetLibraryInfo pass for the module's triple.
456    PM.add(new TargetLibraryInfo(TheTriple));
457
458    // Add the target data from the target machine, if it exists, or the module.
459    #ifdef USE_LLVM_3_5
460    const DataLayout * DL = Target->getDataLayout();
461    #else
462    const DataLayout * DL = Target->getSubtargetImpl()->getDataLayout();
463    #endif
464    if (DL) {
465        module->setDataLayout(DL);
466    }
467    #ifdef USE_LLVM_3_5
468    PM.add(new DataLayoutPass(module));
469    #else
470    PM.add(new DataLayoutPass());
471    #endif   
472    PM.add(createReassociatePass());
473    PM.add(createInstructionCombiningPass());
474    PM.add(createSinkingPass());
475
476    formatted_raw_ostream outStream(out->os());
477    // Ask the target to add backend passes as necessary.
478    if (Target->addPassesToEmitFile(PM, outStream, TargetMachine::CGFT_ObjectFile)) {
479        throw std::runtime_error("Target does not support generation of object file type!\n");
480    }
481
482    PM.run(*module);
483
484
485    out->keep();
486}
487
488/** ------------------------------------------------------------------------------------------------------------- *
489 * @brief main
490 ** ------------------------------------------------------------------------------------------------------------- */
491int main(int argc, char *argv[]) {
492    // Initialize targets first, so that --version shows registered targets.
493    InitializeAllTargets();
494    InitializeAllTargetMCs();
495    InitializeAllAsmPrinters();
496    InitializeAllAsmParsers();
497    cl::ParseCommandLineOptions(argc, argv, "UCD Compiler\n");
498
499
500    #ifdef ENABLE_MULTIPLEXING
501    if (MultiplexingDistribution.length() > 0) {
502        #ifdef USE_LLVM_3_5
503        std::string error;
504        MultiplexingDistributionFile = new raw_fd_ostream(MultiplexingDistribution.c_str(), error, sys::fs::F_Text);
505        if (!error.empty()) {
506            throw std::runtime_error(error);
507        }
508        #else
509        std::error_code error;
510        MultiplexingDistributionFile = new raw_fd_ostream(MultiplexingDistribution, error, sys::fs::F_Text);
511        if (error) {
512            throw std::runtime_error(error.message());
513        }
514        #endif
515    }
516    #endif
517
518    if (PrintLongestDependenceChain.length() > 0) {
519        #ifdef USE_LLVM_3_5
520        std::string error;
521        LongestDependenceChainFile = new raw_fd_ostream(PrintLongestDependenceChain.c_str(), error, sys::fs::F_Text);
522        if (!error.empty()) {
523            throw std::runtime_error(error);
524        }
525        #else
526        std::error_code error;
527        LongestDependenceChainFile = new raw_fd_ostream(PrintLongestDependenceChain, error, sys::fs::F_Text);
528        if (error) {
529            throw std::runtime_error(error.message());
530        }
531        #endif
532
533        if (LongestDependenceChainFile) {
534            if (EnableMultiplexing) {
535                (*LongestDependenceChainFile) << ",Pre-Multiplexing,,,,Post-Multiplexing\n";
536            }
537            (*LongestDependenceChainFile) << ",Pablo,,LLVM,";
538            if (EnableMultiplexing) {
539                (*LongestDependenceChainFile) << ",Pablo,,LLVM,";
540            }
541            (*LongestDependenceChainFile) << "\nName,Global,Max Local,Global,Max Local";
542            if (EnableMultiplexing) {
543                (*LongestDependenceChainFile) << ",Global,Max Local,Global,Max Local";
544            }
545            (*LongestDependenceChainFile) << "\n";
546        }
547    }
548
549    Module * module = generateUCDModule();
550    #ifdef ENABLE_MULTIPLEXING
551    if (MultiplexingDistributionFile) {
552        MultiplexingDistributionFile->close();
553        delete MultiplexingDistributionFile;
554    }   
555    #endif
556    if (LongestDependenceChainFile) {
557        LongestDependenceChainFile->close();
558        delete LongestDependenceChainFile;
559    }
560    compileUCDModule(module);
561    return 0;
562}
Note: See TracBrowser for help on using the repository browser.