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

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

Removed dummy nodes from the reassociation pass and have edges pointing to the if/while node instead to allow for proper topological ordering.

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