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

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

Embed carry data in compiled LLVM module; eliminate passing of carry data pointers/size

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