source: icGREP/icgrep-devel/icgrep/toolchain.cpp @ 4937

Last change on this file since 4937 was 4937, checked in by nmedfort, 3 years ago

Check in of misc changes prior to symbol table work.

File size: 20.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 <string>
8#include <iostream>
9#include <fstream>
10
11#include "basis_bits.h"
12#include "utf_encoding.h"
13#include "pablo/pablo_compiler.h"
14#include <llvm/IR/Function.h>
15#include <llvm/IR/Module.h>
16#include <llvm/ExecutionEngine/ExecutionEngine.h>
17#include <llvm/ExecutionEngine/MCJIT.h>
18#include <llvm/IRReader/IRReader.h>
19#include <llvm/Support/CommandLine.h>
20#include <llvm/CodeGen/CommandFlags.h>
21#include <llvm/Support/SourceMgr.h>
22#include <llvm/Support/TargetSelect.h>
23#include <llvm/Support/Host.h>
24#include <llvm/Support/FileSystem.h>
25
26
27#include <IDISA/idisa_avx_builder.h>
28#include <IDISA/idisa_sse_builder.h>
29#ifndef DISABLE_PREGENERATED_UCD_FUNCTIONS
30#include <UCD/precompiled_properties.h>
31#endif
32#include <re/re_cc.h>
33#include <re/re_nullable.h>
34#include <re/re_simplifier.h>
35#include <re/re_alt.h>
36#include <re/parsefailure.h>
37#include <re/re_parser.h>
38#include <re/re_compiler.h>
39#include <utf8_encoder.h>
40#include <cc/cc_compiler.h>
41#include <pablo/pablo_compiler.h>
42#include <pablo/optimizers/pablo_simplifier.hpp>
43#include <pablo/optimizers/codemotionpass.h>
44#ifdef ENABLE_MULTIPLEXING
45#include <pablo/passes/flattenassociativedfg.h>
46#include <pablo/passes/factorizedfg.h>
47#include <pablo/optimizers/pablo_automultiplexing.hpp>
48#include <pablo/optimizers/pablo_bddminimization.h>
49#include <pablo/optimizers/distributivepass.h>
50#include <pablo/optimizers/schedulingprepass.h>
51#endif
52#include <pablo/function.h>
53#include <pablo/analysis/pabloverifier.hpp>
54#include <re/printer_re.h>
55#include <pablo/printer_pablos.h>
56
57#include <hrtime.h>
58#include <do_grep.h>
59
60using namespace pablo;
61
62static cl::OptionCategory cRegexOutputOptions("Regex Dump Options",
63                                              "These options control printing of intermediate regular expression structures.");
64static cl::opt<bool> PrintAllREs("print-REs", cl::init(false), cl::desc("print regular expression passes"), cl::cat(cRegexOutputOptions));
65static cl::opt<bool> PrintParsedREs("print-parsed-REs", cl::init(false), cl::desc("print out parsed regular expressions"), cl::cat(cRegexOutputOptions));
66static cl::opt<bool> PrintStrippedREs("print-stripped-REs", cl::init(false), cl::desc("print out REs with nullable prefixes/suffixes removed"), cl::cat(cRegexOutputOptions));
67static cl::opt<bool> PrintNamedREs("print-named-REs", cl::init(false), cl::desc("print out named REs"), cl::cat(cRegexOutputOptions));
68static cl::opt<bool> PrintUTF8REs("print-utf8-REs", cl::init(false), cl::desc("print out UTF-8 REs"), cl::cat(cRegexOutputOptions));
69static cl::opt<bool> PrintSimplifiedREs("print-simplified-REs", cl::init(false), cl::desc("print out final simplified REs"), cl::cat(cRegexOutputOptions));
70static cl::OptionCategory dPabloDumpOptions("Pablo Dump Options", "These options control printing of intermediate Pablo code.");
71
72static cl::opt<bool> PrintOptimizedREcode("print-pablo", cl::init(false), cl::desc("print final optimized Pablo code"), cl::cat(dPabloDumpOptions));
73static cl::opt<bool> PrintCompiledCCcode("print-CC-pablo", cl::init(false), cl::desc("print Pablo output from character class compiler"), cl::cat(dPabloDumpOptions));
74static cl::opt<bool> PrintCompiledREcode("print-RE-pablo", cl::init(false), cl::desc("print Pablo output from the regular expression compiler"), cl::cat(dPabloDumpOptions));
75static cl::opt<std::string> PabloOutputFilename("print-pablo-output", cl::init(""), cl::desc("output Pablo filename"), cl::cat(dPabloDumpOptions));
76
77static cl::OptionCategory cPabloOptimizationsOptions("Pablo Optimizations", "These options control Pablo optimization passes.");
78
79static cl::opt<bool> DisableSimplification("disable-simplification", cl::init(false),
80                                     cl::desc("Disable Pablo Simplification pass (not recommended)"),
81                                     cl::cat(cPabloOptimizationsOptions));
82
83static cl::opt<bool> PabloSinkingPass("sinking", cl::init(false),
84                                      cl::desc("Moves all instructions into the innermost legal If-scope so that they are only executed when needed."),
85                                      cl::cat(cPabloOptimizationsOptions));
86
87static cl::OptionCategory cMachineCodeOptimization("Machine Code Optimizations", "These options control back-end compilier optimization levels.");
88
89
90static cl::opt<char> OptLevel("O", cl::desc("Optimization level. [-O0, -O1, -O2, or -O3] (default = '-O0')"),
91                              cl::cat(cMachineCodeOptimization), cl::Prefix, cl::ZeroOrMore, cl::init('0'));
92
93#ifdef ENABLE_MULTIPLEXING
94static cl::opt<bool> PrintUnloweredCode("print-unlowered-pablo", cl::init(false), cl::desc("print Pablo output prior to lowering. "), cl::cat(dPabloDumpOptions));
95
96static cl::opt<bool> EnableMultiplexing("multiplexing", cl::init(false),
97                                        cl::desc("combine Advances whose inputs are mutual exclusive into the fewest number of advances possible (expensive)."),
98                                        cl::cat(cPabloOptimizationsOptions));
99
100static cl::opt<bool> EnableLowering("lowering", cl::init(false),
101                                         cl::desc("coalesce associative functions prior to optimization passes."),
102                                         cl::cat(cPabloOptimizationsOptions));
103
104static cl::opt<bool> EnablePreDistribution("pre-dist", cl::init(false),
105                                         cl::desc("apply distribution law optimization prior to multiplexing."),
106                                         cl::cat(cPabloOptimizationsOptions));
107
108static cl::opt<bool> EnablePostDistribution("post-dist", cl::init(false),
109                                         cl::desc("apply distribution law optimization after multiplexing."),
110                                         cl::cat(cPabloOptimizationsOptions));
111
112static cl::opt<bool> EnablePrePassScheduling("pre-pass-scheduling", cl::init(false),
113                                         cl::desc("apply pre-pass scheduling prior to LLVM IR generation."),
114                                         cl::cat(cPabloOptimizationsOptions));
115#endif
116
117static cl::opt<bool> DisableAVX2("disable-AVX2", cl::init(false), cl::desc("disable AVX2 instruction set."), cl::cat(cPabloOptimizationsOptions));
118
119re::RE * regular_expression_passes(const Encoding encoding, re::RE * re_ast)  {
120    if (PrintAllREs || PrintParsedREs) {
121        std::cerr << "Parser:" << std::endl << Printer_RE::PrintRE(re_ast) << std::endl;
122    }
123
124    //Optimization passes to simplify the AST.
125    re_ast = re::RE_Nullable::removeNullablePrefix(re_ast);
126    if (PrintAllREs || PrintStrippedREs) {
127        std::cerr << "RemoveNullablePrefix:" << std::endl << Printer_RE::PrintRE(re_ast) << std::endl;
128    }
129    re_ast = re::RE_Nullable::removeNullableSuffix(re_ast);
130    if (PrintAllREs || PrintStrippedREs) {
131        std::cerr << "RemoveNullableSuffix:" << std::endl << Printer_RE::PrintRE(re_ast) << std::endl;
132    }
133
134    re_ast = re::RE_Simplifier::simplify(re_ast);
135    if (PrintAllREs || PrintSimplifiedREs) {
136        //Print to the terminal the AST that was generated by the simplifier.
137        std::cerr << "Simplifier:" << std::endl << Printer_RE::PrintRE(re_ast) << std::endl;
138    }
139    return re_ast;
140}
141   
142PabloFunction * re2pablo_compiler(const Encoding encoding, re::RE * re_ast) {
143    PabloFunction * function = PabloFunction::Create("process_block", 8, 2);
144    cc::CC_Compiler cc_compiler(*function, encoding);
145    re::RE_Compiler re_compiler(*function, cc_compiler);
146    re_compiler.initializeRequiredStreams();
147    re_compiler.compileUnicodeNames(re_ast);
148    re_compiler.finalizeMatchResult(re_compiler.compile(re_ast));
149
150    if (PrintCompiledREcode) {
151        //Print to the terminal the AST that was generated by the pararallel bit-stream compiler.
152        llvm::raw_os_ostream cerr(std::cerr);
153        cerr << "Initial Pablo AST:\n";
154        PabloPrinter::print(*function, cerr);
155    }
156    #ifndef NDEBUG
157    PabloVerifier::verify(*function, "creation");
158    #endif
159    return function;
160}
161
162#ifdef PRINT_TIMING_INFORMATION
163#define READ_CYCLE_COUNTER(name) name = read_cycle_counter();
164#else
165#define READ_CYCLE_COUNTER(name)
166#endif
167
168#ifdef PRINT_TIMING_INFORMATION
169unsigned COUNT_STATEMENTS(const PabloFunction * const entry) {
170    std::stack<const Statement *> scope;
171    unsigned statements = 0;
172    // Scan through and collect all the advances, calls, scanthrus and matchstars ...
173    for (const Statement * stmt = entry->getEntryBlock()->front(); ; ) {
174        while ( stmt ) {
175            ++statements;
176            if (LLVM_UNLIKELY(isa<If>(stmt) || isa<While>(stmt))) {
177                // Set the next statement to be the first statement of the inner scope and push the
178                // next statement of the current statement into the scope stack.
179                const PabloBlock * const nested = isa<If>(stmt) ? cast<If>(stmt)->getBody() : cast<While>(stmt)->getBody();
180                scope.push(stmt->getNextNode());
181                stmt = nested->front();
182                assert (stmt);
183                continue;
184            }
185            stmt = stmt->getNextNode();
186        }
187        if (scope.empty()) {
188            break;
189        }
190        stmt = scope.top();
191        scope.pop();
192    }
193    return statements;
194}
195
196unsigned COUNT_ADVANCES(const PabloFunction * const entry) {
197
198    std::stack<const Statement *> scope;
199    unsigned advances = 0;
200
201    // Scan through and collect all the advances, calls, scanthrus and matchstars ...
202    for (const Statement * stmt = entry->getEntryBlock()->front(); ; ) {
203        while ( stmt ) {
204            if (isa<Advance>(stmt)) {
205                ++advances;
206            }
207            else if (LLVM_UNLIKELY(isa<If>(stmt) || isa<While>(stmt))) {
208                // Set the next statement to be the first statement of the inner scope and push the
209                // next statement of the current statement into the scope stack.
210                const PabloBlock * const nested = isa<If>(stmt) ? cast<If>(stmt)->getBody() : cast<While>(stmt)->getBody();
211                scope.push(stmt->getNextNode());
212                stmt = nested->front();
213                assert (stmt);
214                continue;
215            }
216            stmt = stmt->getNextNode();
217        }
218        if (scope.empty()) {
219            break;
220        }
221        stmt = scope.top();
222        scope.pop();
223    }
224    return advances;
225}
226
227using DistributionMap = boost::container::flat_map<unsigned, unsigned>;
228
229DistributionMap SUMMARIZE_VARIADIC_DISTRIBUTION(const PabloFunction * const entry) {
230    std::stack<const Statement *> scope;
231    DistributionMap distribution;
232    // Scan through and collect all the advances, calls, scanthrus and matchstars ...
233    for (const Statement * stmt = entry->getEntryBlock()->front(); ; ) {
234        while ( stmt ) {
235            if (isa<Variadic>(stmt)) {
236                auto f = distribution.find(stmt->getNumOperands());
237                if (f == distribution.end()) {
238                    distribution.emplace(stmt->getNumOperands(), 1);
239                } else {
240                    f->second += 1;
241                }
242            }
243            else if (LLVM_UNLIKELY(isa<If>(stmt) || isa<While>(stmt))) {
244                // Set the next statement to be the first statement of the inner scope and push the
245                // next statement of the current statement into the scope stack.
246                const PabloBlock * const nested = isa<If>(stmt) ? cast<If>(stmt)->getBody() : cast<While>(stmt)->getBody();
247                scope.push(stmt->getNextNode());
248                stmt = nested->front();
249                assert (stmt);
250                continue;
251            }
252            stmt = stmt->getNextNode();
253        }
254        if (scope.empty()) {
255            break;
256        }
257        stmt = scope.top();
258        scope.pop();
259    }
260    return distribution;
261}
262#endif
263
264void pablo_function_passes(PabloFunction * function) {   
265    // Scan through the pablo code and perform DCE and CSE
266
267#ifdef PRINT_TIMING_INFORMATION
268    timestamp_t simplification_start = 0, simplification_end = 0;
269    timestamp_t coalescing_start = 0, coalescing_end = 0;
270    timestamp_t sinking_start = 0, sinking_end = 0;
271    timestamp_t pre_distribution_start = 0, pre_distribution_end = 0;
272    timestamp_t multiplexing_start = 0, multiplexing_end = 0;
273    timestamp_t post_distribution_start = 0, post_distribution_end = 0;
274    timestamp_t lowering_start = 0, lowering_end = 0;
275    timestamp_t scheduling_start = 0, scheduling_end = 0;
276    DistributionMap distribution;
277    const timestamp_t optimization_start = read_cycle_counter();
278#endif
279    if (!DisableSimplification) {
280        READ_CYCLE_COUNTER(simplification_start);
281        Simplifier::optimize(*function);
282        READ_CYCLE_COUNTER(simplification_end);
283    }
284#ifdef ENABLE_MULTIPLEXING
285    if (EnableLowering || EnablePreDistribution || EnablePostDistribution) {
286        READ_CYCLE_COUNTER(coalescing_start);
287        CanonicalizeDFG::transform(*function);
288        READ_CYCLE_COUNTER(coalescing_end);
289    }
290    if (EnablePreDistribution) {
291        READ_CYCLE_COUNTER(pre_distribution_start);
292        DistributivePass::optimize(*function);
293        READ_CYCLE_COUNTER(pre_distribution_end);
294    }
295    if (EnableMultiplexing) {
296        READ_CYCLE_COUNTER(multiplexing_start);
297        MultiplexingPass::optimize(*function);
298        READ_CYCLE_COUNTER(multiplexing_end);
299        if (EnableLowering || EnablePreDistribution || EnablePostDistribution) {
300            CanonicalizeDFG::transform(*function);
301        }
302    }
303    if (EnablePostDistribution) {
304        READ_CYCLE_COUNTER(post_distribution_start);
305        DistributivePass::optimize(*function);
306        READ_CYCLE_COUNTER(post_distribution_end);
307    }
308#endif
309    if (PabloSinkingPass) {
310        READ_CYCLE_COUNTER(sinking_start);
311        CodeMotionPass::optimize(*function);
312        READ_CYCLE_COUNTER(sinking_end);
313    }
314#ifdef ENABLE_MULTIPLEXING
315    if (PrintUnloweredCode) {
316        //Print to the terminal the AST that was generated by the pararallel bit-stream compiler.
317        llvm::raw_os_ostream cerr(std::cerr);
318        cerr << "Unlowered Pablo AST:\n";
319        PabloPrinter::print(*function, cerr);
320    }   
321    #ifdef PRINT_TIMING_INFORMATION
322    distribution = SUMMARIZE_VARIADIC_DISTRIBUTION(function);
323    #endif
324    if (EnableLowering || EnablePreDistribution || EnablePostDistribution) {
325        READ_CYCLE_COUNTER(lowering_start);
326        FactorizeDFG::transform(*function);
327        READ_CYCLE_COUNTER(lowering_end);
328    }
329    if (EnablePrePassScheduling) {
330        READ_CYCLE_COUNTER(scheduling_start);
331        SchedulingPrePass::optimize(*function);
332        READ_CYCLE_COUNTER(scheduling_end);
333    }
334#endif
335#ifdef PRINT_TIMING_INFORMATION
336    const timestamp_t optimization_end = read_cycle_counter();
337#endif
338    if (PrintOptimizedREcode) {
339        if (PabloOutputFilename.empty()) {
340            //Print to the terminal the AST that was generated by the pararallel bit-stream compiler.
341            llvm::raw_os_ostream cerr(std::cerr);
342            cerr << "Final Pablo AST:\n";
343            PabloPrinter::print(*function, cerr);
344        } else {
345            std::error_code error;
346            llvm::raw_fd_ostream out(PabloOutputFilename, error, sys::fs::OpenFlags::F_None);
347            PabloPrinter::print(*function, out);
348        }
349    }
350#ifdef PRINT_TIMING_INFORMATION
351    std::cerr << "PABLO OPTIMIZATION TIME: " << (optimization_end - optimization_start) << std::endl;
352    std::cerr << "  SIMPLIFICATION TIME: " << (simplification_end - simplification_start) << std::endl;
353    std::cerr << "  COALESCING TIME: " << (coalescing_end - coalescing_start) << std::endl;
354    std::cerr << "  SINKING TIME: " << (sinking_end - sinking_start) << std::endl;
355    std::cerr << "  PRE-DISTRIBUTION TIME: " << (pre_distribution_end - pre_distribution_start) << std::endl;
356    std::cerr << "  MULTIPLEXING TIME: " << (multiplexing_end - multiplexing_start) << std::endl;
357    std::cerr << "  MULTIPLEXING SEED: " << MultiplexingPass::SEED << std::endl;
358    std::cerr << "  MULTIPLEXING NODES USED: " << MultiplexingPass::NODES_USED << std::endl;
359    std::cerr << "  MULTIPLEXING NODES ALLOCATED: " << MultiplexingPass::NODES_ALLOCATED << std::endl;
360    std::cerr << "  LOWERING TIME: " << (lowering_end - lowering_start) << std::endl;
361    std::cerr << "  POST-DISTRIBUTION TIME: " << (post_distribution_end - post_distribution_start) << std::endl;
362    std::cerr << "  SCHEDULING TIME: " << (scheduling_end - scheduling_start) << std::endl;
363    std::cerr << "PABLO STATEMENTS: " << COUNT_STATEMENTS(function) << std::endl;
364    std::cerr << "PABLO ADVANCES: " << COUNT_ADVANCES(function) << std::endl;
365    std::cerr << "PRE-LOWERING VARIADIC DISTRIBUTION: ";
366    bool join = false;
367    for (auto dist : distribution) {
368        if (join) {
369            std::cerr << ';';
370        }
371        std::cerr << dist.first << '|' << dist.second;
372        join = true;
373    }
374    std::cerr << std::endl;
375#endif
376}
377
378// Dynamic AVX2 confirmation
379#if (BLOCK_SIZE == 256)
380#define ISPC_LLVM_VERSION ISPC_LLVM_3_6
381#include "ispc.cpp"
382#endif
383
384
385IDISA::IDISA_Builder * GetNativeIDISA_Builder(Module * mod, Type * bitBlockType) {
386
387#if (BLOCK_SIZE == 256)
388    if ((strncmp(lGetSystemISA(), "avx2", 4) == 0)) {
389        return new IDISA::IDISA_AVX2_Builder(mod, bitBlockType);
390        //std::cerr << "IDISA_AVX2_Builder selected\n";
391    }
392    else{
393        return new IDISA::IDISA_SSE2_Builder(mod, bitBlockType);
394        //std::cerr << "Generic IDISA_Builder selected\n";
395    }
396#else   
397    return new IDISA::IDISA_SSE2_Builder(mod, bitBlockType);
398#endif
399}
400
401
402
403ExecutionEngine * JIT_to_ExecutionEngine (Module * m) {
404
405    InitializeNativeTarget();
406    InitializeNativeTargetAsmPrinter();
407    InitializeNativeTargetAsmParser();
408
409    std::string errMessage;
410    EngineBuilder builder(std::move(std::unique_ptr<Module>(m)));
411    builder.setErrorStr(&errMessage);
412    builder.setMCPU(sys::getHostCPUName());
413    CodeGenOpt::Level optLevel = CodeGenOpt::Level::None;
414    switch (OptLevel) {
415        case '0': optLevel = CodeGenOpt::None; break;
416        case '1': optLevel = CodeGenOpt::Less; break;
417        case '2': optLevel = CodeGenOpt::Default; break;
418        case '3': optLevel = CodeGenOpt::Aggressive; break;
419        default: errs() << OptLevel << " is an invalid optimization level.\n";
420    }
421    builder.setOptLevel(optLevel);
422
423#if (BLOCK_SIZE == 256)
424    if (!DisableAVX2 && (strncmp(lGetSystemISA(), "avx2", 4) == 0)) {
425            std::vector<std::string> attrs;
426            attrs.push_back("avx2");
427            builder.setMAttrs(attrs);
428    //std::cerr << "+avx2 set" << std::endl;
429    }
430#endif
431    //builder.setOptLevel(mMaxWhileDepth ? CodeGenOpt::Level::Less : CodeGenOpt::Level::None);
432    ExecutionEngine * engine = builder.create();
433    if (engine == nullptr) {
434        throw std::runtime_error("Could not create ExecutionEngine: " + errMessage);
435    }
436
437    return engine;
438}
439
440extern "C" {
441    void wrapped_report_match(uint64_t recordNum, uint64_t recordStart, uint64_t recordEnd) {
442        printf("line %lu: (%lu, %lu)\n", recordNum, recordStart, recordEnd);
443    }
444}
445
446
447extern "C" {
448  void wrapped_print_register(char * regName, BitBlock bit_block) {
449      print_register<BitBlock>(regName, bit_block);
450  }
451}
452
453void icgrep_Linking(Module * m, ExecutionEngine * e) {
454    Module::FunctionListType & fns = m->getFunctionList();
455    for (Module::FunctionListType::iterator it = fns.begin(), it_end = fns.end(); it != it_end; ++it) {
456        std::string fnName = it->getName().str();
457        if (fnName == "s2p_block") continue;
458        if (fnName == "process_block") continue;
459        if (fnName == "process_block_initialize_carries") continue;
460       
461        if (fnName == "wrapped_print_register") {
462            e->addGlobalMapping(cast<GlobalValue>(it), (void *)&wrapped_print_register);
463        }
464        if (fnName == "wrapped_report_match") {
465            e->addGlobalMapping(cast<GlobalValue>(it), (void *)&wrapped_report_match);
466        }
467#ifndef DISABLE_PREGENERATED_UCD_FUNCTIONS
468        else {
469            const UCD::ExternalProperty & ep = UCD::resolveExternalProperty(fnName);
470            e->addGlobalMapping(cast<GlobalValue>(it), std::get<0>(ep));
471        }
472#endif
473    }
474}
475
Note: See TracBrowser for help on using the repository browser.