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

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

More work on the dependency chain metrics.

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