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

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

Misc. changes and start of dependency chain analysis in ucd generator.

File size: 15.8 KB
RevLine 
[4657]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
[4661]7#include <cc/cc_compiler.h>
[4657]8#include <UCD/unicode_set.h>
[4661]9#include <UCD/PropertyObjectTable.h>
[4657]10#include <UCD/ucd_compiler.hpp>
11#include <pablo/pablo_compiler.h>
[4661]12#include <pablo/builder.hpp>
[4657]13#include <pablo/function.h>
14#include <llvm/Support/CommandLine.h>
[4661]15#include <utf_encoding.h>
16#include <pablo/optimizers/pablo_simplifier.hpp>
17#include <pablo/optimizers/pablo_codesinking.hpp>
[4665]18#ifdef ENABLE_MULTIPLEXING
[4661]19#include <pablo/optimizers/pablo_automultiplexing.hpp>
[4665]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"
[4666]36#include <llvm/Transforms/Scalar.h>
[4686]37#include <llvm/Support/raw_ostream.h>
38#include <llvm/Analysis/DependenceAnalysis.h>
[4661]39
[4722]40#include <queue>
41#include <unordered_map>
42
[4657]43using namespace pablo;
[4661]44using namespace UCD;
45using namespace cc;
[4665]46using namespace llvm;
[4657]47
[4684]48static cl::opt<std::string>
49ObjectFilename("o", cl::desc("Output object filename"), cl::value_desc("filename"), cl::Required);
[4657]50
[4665]51static cl::opt<std::string>
[4684]52UCDSourcePath("dir", cl::desc("UCD source code directory"), cl::value_desc("directory"), cl::Required);
[4657]53
[4722]54static cl::opt<bool> PrintDependenceAnalysis("pablo-ldc", cl::init(false), cl::desc("print Pablo longest dependency chain metrics."));
[4686]55
56
[4667]57#ifdef ENABLE_MULTIPLEXING
58static cl::opt<bool> EnableMultiplexing("multiplexing", cl::init(false),
[4722]59    cl::desc("combine Advances whose inputs are mutual exclusive into the fewest number of advances possible (expensive)."));
[4686]60
61static cl::opt<std::string>
[4722]62MultiplexingDistribution("multiplexing-dist",
63    cl::desc("Generate a CSV containing the # of Advances found in each UCD function before and after applying multiplexing."), cl::value_desc("filename"));
[4686]64
65static raw_fd_ostream * MultiplexingDistributionFile = nullptr;
[4667]66#endif
67
[4671]68using property_list = std::vector<std::pair<std::string, size_t>>;
69
[4665]70/** ------------------------------------------------------------------------------------------------------------- *
[4686]71 * @brief getNumOfAdvances
72 ** ------------------------------------------------------------------------------------------------------------- */
73unsigned getNumOfAdvances(const PabloBlock & entry) {
74    unsigned advances = 0;
75    for (const Statement * stmt : entry ) {
76        if (isa<Advance>(stmt)) {
77            ++advances;
78        }
79        else if (LLVM_UNLIKELY(isa<If>(stmt) || isa<While>(stmt))) {
80            advances += getNumOfAdvances(isa<If>(stmt) ? cast<If>(stmt)->getBody() : cast<While>(stmt)->getBody());
81        }
82    }
83    return advances;
84}
85
86/** ------------------------------------------------------------------------------------------------------------- *
[4722]87 * @brief computePabloDependencyMetrics
88 ** ------------------------------------------------------------------------------------------------------------- */
89void computePabloDependencyChainMetrics(const PabloFunction & f) {
90
91    std::queue<const PabloAST *> Q;
92    std::unordered_map<const PabloAST *, unsigned> V;
93
94    for (unsigned i = 0; i != f.getNumOfResults(); ++i) {
95        V.insert(std::make_pair(f.getResult(i), 0));
96        const PabloAST * expr = f.getResult(i)->getExpression();
97        if (expr->getNumUses() == 1 && V.count(expr) == 0) {
98            V.insert(std::make_pair(expr, 1));
99            if (LLVM_LIKELY(isa<Statement>(expr))) {
100                Q.push(cast<Statement>(expr));
101            }
102        }
103    }
104
105    while (!Q.empty()) {
106        const PabloAST * expr = Q.front(); Q.pop();
107        unsigned lpl = 0; // longest path length
108        for (const PabloAST * user : expr->users()) {
109            lpl = std::max<unsigned>(lpl, V[user]);
110        }
111        V.insert(std::make_pair(expr, lpl + 1));
112        if (const Statement * stmt = dyn_cast<Statement>(expr)) {
113            for (unsigned i = 0; i != stmt->getNumOperands(); ++i) {
114                assert (V.count(stmt->getOperand(i)) == 0);
115                bool everyUserOfThisOperandWasProcessed = true;
116                for (const PabloAST * user : stmt->getOperand(i)->users()) {
117                    if (V.count(user) == 0) {
118                        everyUserOfThisOperandWasProcessed = false;
119                        break;
120                    }
121                }
122                if (everyUserOfThisOperandWasProcessed) {
123                    Q.push(stmt->getOperand(i));
124                }
125            }
126        }
127    }
128
129    unsigned lpl = 0;
130    for (unsigned i = 0; i != f.getNumOfParameters(); ++i) {
131        assert (V.count(f.getParameter(i)));
132        lpl = std::max<unsigned>(lpl, V[f.getParameter(i)]);
133    }
134
135
136
137}
138
139/** ------------------------------------------------------------------------------------------------------------- *
140 * @brief computeLLVMDependencyMetrics
141 ** ------------------------------------------------------------------------------------------------------------- */
142void computeLLVMDependencyChainMetrics(const llvm::Function & f) {
143
144
145
146}
147
148/** ------------------------------------------------------------------------------------------------------------- *
[4665]149 * @brief compileUnicodeSet
150 ** ------------------------------------------------------------------------------------------------------------- */
[4671]151size_t compileUnicodeSet(std::string name, const UnicodeSet & set, PabloCompiler & pc, Module * module) {
[4686]152    #ifdef ENABLE_MULTIPLEXING
153    if (MultiplexingDistributionFile) {
154        (*MultiplexingDistributionFile) << name;
155    }
156    #endif
[4680]157    PabloFunction function = PabloFunction::Create(std::move(name), 8, 1);
[4661]158    Encoding encoding(Encoding::Type::UTF_8, 8);
159    CC_Compiler ccCompiler(function, encoding);
160    UCDCompiler ucdCompiler(ccCompiler);
161    PabloBuilder builder(function.getEntryBlock());
162    // Build the unicode set function
[4686]163    function.setResult(0, builder.createAssign("matches", ucdCompiler.generateWithDefaultIfHierarchy(set, builder)));
[4661]164    // Optimize it at the pablo level
165    Simplifier::optimize(function);
166    CodeSinking::optimize(function);
[4665]167    #ifdef ENABLE_MULTIPLEXING
[4667]168    if (EnableMultiplexing) {
[4686]169        if (MultiplexingDistributionFile) {
170            (*MultiplexingDistributionFile) << ',' << getNumOfAdvances(function.getEntryBlock());
171        }
[4667]172        AutoMultiplexing::optimize(function);
[4685]173        Simplifier::optimize(function);
[4686]174        if (MultiplexingDistributionFile) {
175            (*MultiplexingDistributionFile) << ',' << getNumOfAdvances(function.getEntryBlock()) << '\n';
176        }
[4667]177    }
[4665]178    #endif
[4661]179    // Now compile the function ...
[4668]180    auto func = pc.compile(function, module);
[4665]181    releaseSlabAllocatorMemory();
[4671]182
183    return func.second;
[4661]184}
[4657]185
[4665]186/** ------------------------------------------------------------------------------------------------------------- *
[4671]187 * @brief writePropertyInstaller
[4665]188 ** ------------------------------------------------------------------------------------------------------------- */
[4668]189
[4684]190void writePrecompiledProperties(property_list && properties) {
[4671]191
[4684]192    const std::string headerFilename = UCDSourcePath + "/precompiled_properties.h";
[4668]193    #ifdef USE_LLVM_3_5
194    std::string error;
[4684]195    raw_fd_ostream header(headerFilename.c_str(), error, sys::fs::F_None);
[4668]196    if (!error.empty()) {
197        throw std::runtime_error(error);
198    }
199    #else
200    std::error_code error;
[4684]201    raw_fd_ostream header(headerFilename, error, sys::fs::F_None);
[4668]202    if (error) {
203        throw std::runtime_error(error.message());
204    }
205    #endif
206
[4684]207    header << "#ifndef PRECOMPILED_PROPERTIES\n";
208    header << "#define PRECOMPILED_PROPERTIES\n\n";
209    header << "#include <string>\n\n";
210    header << "#include <tuple>\n";
211    header << "namespace UCD {\n\n";
212    header << "using ExternalProperty = std::tuple<void *, unsigned, unsigned, size_t>;\n\n";
213    header << "const ExternalProperty & resolveExternalProperty(const std::string & name);\n\n";
214    header << "}\n\n";
215    header << "#endif\n";
216    header.close();
217
218    const std::string cppFilename = UCDSourcePath + "/precompiled_properties.cpp";
219    #ifdef USE_LLVM_3_5
220    raw_fd_ostream cpp(cppFilename.c_str(), error, sys::fs::F_None);
221    if (!error.empty()) {
222        throw std::runtime_error(error);
[4671]223    }
[4684]224    #else
225    raw_fd_ostream cpp(cppFilename, error, sys::fs::F_None);
226    if (error) {
227        throw std::runtime_error(error.message());
228    }
229    #endif
230
231    cpp << "#include \"precompiled_properties.h\"\n";
232    cpp << "#include <include/simd-lib/bitblock.hpp>\n";
233    cpp << "#include <stdexcept>\n";
234    cpp << "#include <unordered_map>\n\n";
[4686]235    cpp << "namespace UCD {\nnamespace {\n\n";
[4684]236    cpp << "struct Input {\n    BitBlock bit[8];\n};\n\n";
237    cpp << "struct Output {\n    BitBlock bit[1];\n};\n\n";
[4671]238    for (auto prop : properties) {
[4684]239        cpp << "extern \"C\" void " + prop.first + "(const Input &, BitBlock *, Output &);\n";
[4671]240    }
[4684]241
[4686]242    cpp << "\nconst static std::unordered_map<std::string, ExternalProperty> EXTERNAL_UCD_PROPERTY_MAP = {\n";
[4684]243    for (auto itr = properties.begin(); itr != properties.end(); ) {
244        cpp << "    {\"" + itr->first + "\", std::make_tuple(reinterpret_cast<void *>(&" + itr->first + "), 8, 1, " + std::to_string(itr->second) + ")}";
245        if (++itr != properties.end()) {
246            cpp << ",";
247        }
248        cpp << "\n";
249    }
[4686]250    cpp << "};\n\n} // end of anonymous namespace\n\n";
[4684]251
252    cpp << "const ExternalProperty & resolveExternalProperty(const std::string & name) {\n";
[4686]253    cpp << "    auto f = EXTERNAL_UCD_PROPERTY_MAP.find(name);\n";
254    cpp << "    if (f == EXTERNAL_UCD_PROPERTY_MAP.end())\n";
[4684]255    cpp << "        throw std::runtime_error(\"No external property named \\\"\" + name + \"\\\" found!\");\n";
256    cpp << "    return f->second;\n";
[4686]257    cpp << "}\n\n} // end of UCD namespace\n";
[4684]258
259    cpp.close();
260
[4671]261}
[4668]262
[4671]263/** ------------------------------------------------------------------------------------------------------------- *
264 * @brief generateUCDModule
265 ** ------------------------------------------------------------------------------------------------------------- */
266Module * generateUCDModule() {
267
268    property_list properties;
269
[4661]270    PabloCompiler pc;
[4665]271    Module * module = new Module("ucd", getGlobalContext());
[4661]272    for (PropertyObject * obj : property_object_table) {
[4667]273        if (EnumeratedPropertyObject * enumObj = dyn_cast<EnumeratedPropertyObject>(obj)) {
[4661]274            for (const std::string value : *enumObj) {
275                const UnicodeSet & set = enumObj->GetCodepointSet(canonicalize_value_name(value));
[4667]276                std::string name = "__get_" + property_enum_name[enumObj->getPropertyCode()] + "_" + value;
[4671]277                properties.emplace_back(name, compileUnicodeSet(name, set, pc, module));
[4661]278            }
279        }
[4667]280        else if (ExtensionPropertyObject * extObj = dyn_cast<ExtensionPropertyObject>(obj)) {
[4665]281            for (const std::string value : *extObj) {
282                const UnicodeSet & set = extObj->GetCodepointSet(canonicalize_value_name(value));
[4667]283                std::string name = "__get_" + property_enum_name[extObj->getPropertyCode()] + "_" + value;
[4671]284                properties.emplace_back(name, compileUnicodeSet(name, set, pc, module));
[4665]285            }
286        }
[4667]287        else if (BinaryPropertyObject * binObj = dyn_cast<BinaryPropertyObject>(obj)) {
[4665]288            const UnicodeSet & set = binObj->GetCodepointSet(Binary_ns::Y);
[4667]289            std::string name = "__get_" + property_enum_name[binObj->getPropertyCode()] + "_Y";
[4671]290            properties.emplace_back(name, compileUnicodeSet(name, set, pc, module));
[4665]291        }
292    }
[4657]293
[4665]294    // Print an error message if our module is malformed in any way.
295    verifyModule(*module, &dbgs());
[4657]296
[4684]297    writePrecompiledProperties(std::move(properties));
[4671]298
[4665]299    return module;
300}
301
302/** ------------------------------------------------------------------------------------------------------------- *
303 * @brief compileUCDModule
304 ** ------------------------------------------------------------------------------------------------------------- */
305void compileUCDModule(Module * module) {
306    Triple TheTriple;
307
[4666]308    TheTriple.setTriple(sys::getDefaultTargetTriple());
309
[4665]310    // Get the target specific parser.
311    std::string msg;
312    const Target * TheTarget = TargetRegistry::lookupTarget(TheTriple.getTriple(), msg);
313    if (TheTarget == nullptr) {
314        throw std::runtime_error(msg);
315    }
316
317    TargetOptions Options;
318
319    std::unique_ptr<TargetMachine> Target(
[4685]320                TheTarget->createTargetMachine(TheTriple.getTriple(), sys::getHostCPUName(), "", Options,
[4665]321                                               Reloc::Default, CodeModel::Small, CodeGenOpt::Aggressive));
322
323    if (Target == nullptr) {
324        throw std::runtime_error("Could not allocate target machine!");
325    }
326
327    #ifdef USE_LLVM_3_5
328    std::string error;
[4685]329    std::unique_ptr<tool_output_file> out = make_unique<tool_output_file>(ObjectFilename.c_str(), error, sys::fs::F_None);
[4665]330    if (!error.empty()) {
331        throw std::runtime_error(error);
332    }
333    #else
334    std::error_code error;
[4685]335    std::unique_ptr<tool_output_file> out = make_unique<tool_output_file>(ObjectFilename, error, sys::fs::F_None);
[4665]336    if (error) {
337        throw std::runtime_error(error.message());
338    }
339    #endif
340
341    // Build up all of the passes that we want to do to the module.
342    PassManager PM;
343
344    // Add an appropriate TargetLibraryInfo pass for the module's triple.
[4669]345    PM.add(new TargetLibraryInfo(TheTriple));
[4665]346
347    // Add the target data from the target machine, if it exists, or the module.
348    #ifdef USE_LLVM_3_5
349    const DataLayout * DL = Target->getDataLayout();
350    #else
351    const DataLayout * DL = Target->getSubtargetImpl()->getDataLayout();
352    #endif
353    if (DL) {
354        module->setDataLayout(DL);
355    }
[4669]356    #ifdef USE_LLVM_3_5
357    PM.add(new DataLayoutPass(module));
358    #else
[4665]359    PM.add(new DataLayoutPass());
[4692]360    #endif   
[4666]361    PM.add(createReassociatePass());
362    PM.add(createInstructionCombiningPass());
363    PM.add(createSinkingPass());
[4665]364
[4686]365    formatted_raw_ostream outStream(out->os());
[4665]366    // Ask the target to add backend passes as necessary.
[4686]367    if (Target->addPassesToEmitFile(PM, outStream, TargetMachine::CGFT_ObjectFile)) {
[4671]368        throw std::runtime_error("Target does not support generation of object file type!\n");
[4665]369    }
370
371    PM.run(*module);
372
[4692]373
[4685]374    out->keep();
[4665]375}
376
377/** ------------------------------------------------------------------------------------------------------------- *
378 * @brief main
379 ** ------------------------------------------------------------------------------------------------------------- */
380int main(int argc, char *argv[]) {
[4686]381    // Initialize targets first, so that --version shows registered targets.
382    InitializeAllTargets();
383    InitializeAllTargetMCs();
384    InitializeAllAsmPrinters();
385    InitializeAllAsmParsers();
[4665]386    cl::ParseCommandLineOptions(argc, argv, "UCD Compiler\n");
[4692]387
388
389
390
[4686]391    #ifdef ENABLE_MULTIPLEXING
392    if (MultiplexingDistribution.length() > 0) {
393        #ifdef USE_LLVM_3_5
394        std::string error;
395        MultiplexingDistributionFile = new raw_fd_ostream(MultiplexingDistribution.c_str(), error, sys::fs::F_Text);
396        if (!error.empty()) {
397            throw std::runtime_error(error);
398        }
399        #else
400        std::error_code error;
401        MultiplexingDistributionFile = new raw_fd_ostream(MultiplexingDistribution, error, sys::fs::F_Text);
402        if (error) {
403            throw std::runtime_error(error.message());
404        }
405        #endif
406    }
407    #endif
[4665]408    Module * module = generateUCDModule();
[4686]409    #ifdef ENABLE_MULTIPLEXING
410    if (MultiplexingDistributionFile) {
411        MultiplexingDistributionFile->close();
412        delete MultiplexingDistributionFile;
413    }
414    #endif
[4665]415    compileUCDModule(module);
[4661]416    return 0;
[4657]417}
Note: See TracBrowser for help on using the repository browser.