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

Last change on this file since 4724 was 4724, checked in by nmedfort, 4 years ago

Temporary check in

File size: 21.6 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::pair<std::string, size_t>>;
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 ** ------------------------------------------------------------------------------------------------------------- */
221size_t 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    return func.second;
276}
277
278/** ------------------------------------------------------------------------------------------------------------- *
279 * @brief writePropertyInstaller
280 ** ------------------------------------------------------------------------------------------------------------- */
281
282void writePrecompiledProperties(property_list && properties) {
283
284    const std::string headerFilename = UCDSourcePath + "/precompiled_properties.h";
285    #ifdef USE_LLVM_3_5
286    std::string error;
287    raw_fd_ostream header(headerFilename.c_str(), error, sys::fs::F_None);
288    if (!error.empty()) {
289        throw std::runtime_error(error);
290    }
291    #else
292    std::error_code error;
293    raw_fd_ostream header(headerFilename, error, sys::fs::F_None);
294    if (error) {
295        throw std::runtime_error(error.message());
296    }
297    #endif
298
299    header << "#ifndef PRECOMPILED_PROPERTIES\n";
300    header << "#define PRECOMPILED_PROPERTIES\n\n";
301    header << "#include <string>\n\n";
302    header << "#include <tuple>\n";
303    header << "namespace UCD {\n\n";
304    header << "using ExternalProperty = std::tuple<void *, unsigned, unsigned, size_t>;\n\n";
305    header << "const ExternalProperty & resolveExternalProperty(const std::string & name);\n\n";
306    header << "}\n\n";
307    header << "#endif\n";
308    header.close();
309
310    const std::string cppFilename = UCDSourcePath + "/precompiled_properties.cpp";
311    #ifdef USE_LLVM_3_5
312    raw_fd_ostream cpp(cppFilename.c_str(), error, sys::fs::F_None);
313    if (!error.empty()) {
314        throw std::runtime_error(error);
315    }
316    #else
317    raw_fd_ostream cpp(cppFilename, error, sys::fs::F_None);
318    if (error) {
319        throw std::runtime_error(error.message());
320    }
321    #endif
322
323    cpp << "#include \"precompiled_properties.h\"\n";
324    cpp << "#include <include/simd-lib/bitblock.hpp>\n";
325    cpp << "#include <stdexcept>\n";
326    cpp << "#include <unordered_map>\n\n";
327    cpp << "namespace UCD {\nnamespace {\n\n";
328    cpp << "struct Input {\n    BitBlock bit[8];\n};\n\n";
329    cpp << "struct Output {\n    BitBlock bit[1];\n};\n\n";
330    for (auto prop : properties) {
331        cpp << "extern \"C\" void " + prop.first + "(const Input &, BitBlock *, Output &);\n";
332    }
333
334    cpp << "\nconst static std::unordered_map<std::string, ExternalProperty> EXTERNAL_UCD_PROPERTY_MAP = {\n";
335    for (auto itr = properties.begin(); itr != properties.end(); ) {
336        cpp << "    {\"" + itr->first + "\", std::make_tuple(reinterpret_cast<void *>(&" + itr->first + "), 8, 1, " + std::to_string(itr->second) + ")}";
337        if (++itr != properties.end()) {
338            cpp << ",";
339        }
340        cpp << "\n";
341    }
342    cpp << "};\n\n} // end of anonymous namespace\n\n";
343
344    cpp << "const ExternalProperty & resolveExternalProperty(const std::string & name) {\n";
345    cpp << "    auto f = EXTERNAL_UCD_PROPERTY_MAP.find(name);\n";
346    cpp << "    if (f == EXTERNAL_UCD_PROPERTY_MAP.end())\n";
347    cpp << "        throw std::runtime_error(\"No external property named \\\"\" + name + \"\\\" found!\");\n";
348    cpp << "    return f->second;\n";
349    cpp << "}\n\n} // end of UCD namespace\n";
350
351    cpp.close();
352
353}
354
355/** ------------------------------------------------------------------------------------------------------------- *
356 * @brief generateUCDModule
357 ** ------------------------------------------------------------------------------------------------------------- */
358Module * generateUCDModule() {
359
360    property_list properties;
361
362    PabloCompiler pc;
363    Module * module = new Module("ucd", getGlobalContext());
364    for (PropertyObject * obj : property_object_table) {
365        if (EnumeratedPropertyObject * enumObj = dyn_cast<EnumeratedPropertyObject>(obj)) {
366            for (const std::string value : *enumObj) {
367                const UnicodeSet & set = enumObj->GetCodepointSet(canonicalize_value_name(value));
368                std::string name = "__get_" + property_enum_name[enumObj->getPropertyCode()] + "_" + value;
369                properties.emplace_back(name, compileUnicodeSet(name, set, pc, module));
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                properties.emplace_back(name, compileUnicodeSet(name, set, pc, module));
377            }
378        }
379        else if (BinaryPropertyObject * binObj = dyn_cast<BinaryPropertyObject>(obj)) {
380            const UnicodeSet & set = binObj->GetCodepointSet(Binary_ns::Y);
381            std::string name = "__get_" + property_enum_name[binObj->getPropertyCode()] + "_Y";
382            properties.emplace_back(name, compileUnicodeSet(name, set, pc, module));
383        }
384    }
385
386    // Print an error message if our module is malformed in any way.
387    verifyModule(*module, &dbgs());
388
389    writePrecompiledProperties(std::move(properties));
390
391    return module;
392}
393
394/** ------------------------------------------------------------------------------------------------------------- *
395 * @brief compileUCDModule
396 ** ------------------------------------------------------------------------------------------------------------- */
397void compileUCDModule(Module * module) {
398    Triple TheTriple;
399
400    TheTriple.setTriple(sys::getDefaultTargetTriple());
401
402    // Get the target specific parser.
403    std::string msg;
404    const Target * TheTarget = TargetRegistry::lookupTarget(TheTriple.getTriple(), msg);
405    if (TheTarget == nullptr) {
406        throw std::runtime_error(msg);
407    }
408
409    TargetOptions Options;
410
411    std::unique_ptr<TargetMachine> Target(
412                TheTarget->createTargetMachine(TheTriple.getTriple(), sys::getHostCPUName(), "", Options,
413                                               Reloc::Default, CodeModel::Small, CodeGenOpt::Aggressive));
414
415    if (Target == nullptr) {
416        throw std::runtime_error("Could not allocate target machine!");
417    }
418
419    #ifdef USE_LLVM_3_5
420    std::string error;
421    std::unique_ptr<tool_output_file> out = make_unique<tool_output_file>(ObjectFilename.c_str(), error, sys::fs::F_None);
422    if (!error.empty()) {
423        throw std::runtime_error(error);
424    }
425    #else
426    std::error_code error;
427    std::unique_ptr<tool_output_file> out = make_unique<tool_output_file>(ObjectFilename, error, sys::fs::F_None);
428    if (error) {
429        throw std::runtime_error(error.message());
430    }
431    #endif
432
433    // Build up all of the passes that we want to do to the module.
434    PassManager PM;
435
436    // Add an appropriate TargetLibraryInfo pass for the module's triple.
437    PM.add(new TargetLibraryInfo(TheTriple));
438
439    // Add the target data from the target machine, if it exists, or the module.
440    #ifdef USE_LLVM_3_5
441    const DataLayout * DL = Target->getDataLayout();
442    #else
443    const DataLayout * DL = Target->getSubtargetImpl()->getDataLayout();
444    #endif
445    if (DL) {
446        module->setDataLayout(DL);
447    }
448    #ifdef USE_LLVM_3_5
449    PM.add(new DataLayoutPass(module));
450    #else
451    PM.add(new DataLayoutPass());
452    #endif   
453    PM.add(createReassociatePass());
454    PM.add(createInstructionCombiningPass());
455    PM.add(createSinkingPass());
456
457    formatted_raw_ostream outStream(out->os());
458    // Ask the target to add backend passes as necessary.
459    if (Target->addPassesToEmitFile(PM, outStream, TargetMachine::CGFT_ObjectFile)) {
460        throw std::runtime_error("Target does not support generation of object file type!\n");
461    }
462
463    PM.run(*module);
464
465
466    out->keep();
467}
468
469/** ------------------------------------------------------------------------------------------------------------- *
470 * @brief main
471 ** ------------------------------------------------------------------------------------------------------------- */
472int main(int argc, char *argv[]) {
473    // Initialize targets first, so that --version shows registered targets.
474    InitializeAllTargets();
475    InitializeAllTargetMCs();
476    InitializeAllAsmPrinters();
477    InitializeAllAsmParsers();
478    cl::ParseCommandLineOptions(argc, argv, "UCD Compiler\n");
479
480
481    #ifdef ENABLE_MULTIPLEXING
482    if (MultiplexingDistribution.length() > 0) {
483        #ifdef USE_LLVM_3_5
484        std::string error;
485        MultiplexingDistributionFile = new raw_fd_ostream(MultiplexingDistribution.c_str(), error, sys::fs::F_Text);
486        if (!error.empty()) {
487            throw std::runtime_error(error);
488        }
489        #else
490        std::error_code error;
491        MultiplexingDistributionFile = new raw_fd_ostream(MultiplexingDistribution, error, sys::fs::F_Text);
492        if (error) {
493            throw std::runtime_error(error.message());
494        }
495        #endif
496    }
497    #endif
498
499    if (PrintLongestDependenceChain.length() > 0) {
500        #ifdef USE_LLVM_3_5
501        std::string error;
502        LongestDependenceChainFile = new raw_fd_ostream(PrintLongestDependenceChain.c_str(), error, sys::fs::F_Text);
503        if (!error.empty()) {
504            throw std::runtime_error(error);
505        }
506        #else
507        std::error_code error;
508        LongestDependenceChainFile = new raw_fd_ostream(PrintLongestDependenceChain, error, sys::fs::F_Text);
509        if (error) {
510            throw std::runtime_error(error.message());
511        }
512        #endif
513
514        if (LongestDependenceChainFile) {
515            if (EnableMultiplexing) {
516                (*LongestDependenceChainFile) << ",Pre-Multiplexing,,,,Post-Multiplexing\n";
517            }
518            (*LongestDependenceChainFile) << ",Pablo,,LLVM,";
519            if (EnableMultiplexing) {
520                (*LongestDependenceChainFile) << ",Pablo,,LLVM,";
521            }
522            (*LongestDependenceChainFile) << "\nName,Global,Max Local,Global,Max Local";
523            if (EnableMultiplexing) {
524                (*LongestDependenceChainFile) << ",Global,Max Local,Global,Max Local";
525            }
526            (*LongestDependenceChainFile) << "\n";
527        }
528    }
529
530    Module * module = generateUCDModule();
531    #ifdef ENABLE_MULTIPLEXING
532    if (MultiplexingDistributionFile) {
533        MultiplexingDistributionFile->close();
534        delete MultiplexingDistributionFile;
535    }   
536    #endif
537    if (LongestDependenceChainFile) {
538        LongestDependenceChainFile->close();
539        delete LongestDependenceChainFile;
540    }
541    compileUCDModule(module);
542    return 0;
543}
Note: See TracBrowser for help on using the repository browser.