source: icGREP/icgrep-devel/icgrep/pablo/pablo_toolchain.cpp @ 5239

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

Multi-threading support for PabloAST / PabloCompiler?. Requires unique LLVM Context / Module for each thread.

File size: 12.9 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 <pablo/pablo_toolchain.h>
8#include <pablo/pablo_kernel.h>
9#include <pablo/pablo_compiler.h>
10#include <pablo/optimizers/pablo_simplifier.hpp>
11#include <pablo/optimizers/codemotionpass.h>
12#include <pablo/passes/flattenassociativedfg.h>
13#include <pablo/passes/flattenif.hpp>
14#include <pablo/passes/factorizedfg.h>
15#ifdef ENABLE_MULTIPLEXING
16#include <pablo/optimizers/pablo_automultiplexing.hpp>
17#include <pablo/optimizers/pablo_bddminimization.h>
18#include <pablo/optimizers/booleanreassociationpass.h>
19#include <pablo/optimizers/distributivepass.h>
20#include <pablo/optimizers/schedulingprepass.h>
21#endif
22#include <pablo/analysis/pabloverifier.hpp>
23#include <pablo/printer_pablos.h>
24#include <llvm/Support/CommandLine.h>
25#include <llvm/Support/FileSystem.h>
26#include <llvm/Support/raw_ostream.h>
27#ifdef PRINT_TIMING_INFORMATION
28#include <hrtime.h>
29#endif
30#include <string>
31#include <iostream>
32#include <fstream>
33#include <sstream>
34
35namespace pablo {
36
37
38static cl::OptionCategory PabloOptions("Pablo Options", "These options control printing, generation and instrumentation of Pablo intermediate code.");
39
40const cl::OptionCategory * pablo_toolchain_flags() {
41    return &PabloOptions;
42}
43   
44   
45static cl::bits<PabloDebugFlags> 
46DebugOptions(cl::values(clEnumVal(PrintOptimizedREcode, "print final optimized Pablo code"),
47                        clEnumVal(PrintCompiledCCcode, "print Pablo output from character class compiler"),
48                        clEnumVal(PrintCompiledREcode, "print Pablo output from the regular expression compiler"),
49                        clEnumVal(DumpTrace, "Generate dynamic traces of executed Pablo assignments."),
50                        clEnumVal(PrintUnloweredCode, "print Pablo output prior to lowering."),
51                        clEnumValEnd), cl::cat(PabloOptions));
52   
53static cl::opt<std::string> PabloOutputFilename("print-pablo-output", cl::init(""), cl::desc("output Pablo filename"), cl::cat(PabloOptions));
54static cl::opt<bool> Flatten("flatten-if", cl::init(false), cl::desc("Flatten all the Ifs in the Pablo AST"), cl::cat(PabloOptions));
55
56static cl::bits<PabloCompilationFlags> 
57    PabloOptimizationsOptions(cl::values(clEnumVal(DisableSimplification, "Disable Pablo Simplification pass (not recommended)"),
58                                         clEnumVal(EnableCodeMotion, "Moves statements into the innermost legal If-scope and moves invariants out of While-loops."),
59#ifdef ENABLE_MULTIPLEXING
60                                         clEnumVal(EnableMultiplexing, "combine Advances whose inputs are mutual exclusive into the fewest number of advances possible (expensive)."),
61                                         clEnumVal(EnableLowering, "coalesce associative functions prior to optimization passes."),
62                                         clEnumVal(EnablePreDistribution, "apply distribution law optimization prior to multiplexing."),
63                                         clEnumVal(EnablePostDistribution, "apply distribution law optimization after multiplexing."),
64                                         clEnumVal(EnablePrePassScheduling, "apply pre-pass scheduling prior to LLVM IR generation."),
65#endif                                         
66                            clEnumValEnd), cl::cat(PabloOptions));
67
68bool DebugOptionIsSet(PabloDebugFlags flag) {return DebugOptions.isSet(flag);}
69   
70   
71   
72#ifdef PRINT_TIMING_INFORMATION
73#define READ_CYCLE_COUNTER(name) name = read_cycle_counter();
74#else
75#define READ_CYCLE_COUNTER(name)
76#endif
77
78#ifdef PRINT_TIMING_INFORMATION
79unsigned COUNT_STATEMENTS(const PabloKernel * const entry) {
80    std::stack<const Statement *> scope;
81    unsigned statements = 0;
82    // Scan through and collect all the advances, calls, scanthrus and matchstars ...
83    for (const Statement * stmt = entry->getEntryBlock()->front(); ; ) {
84        while ( stmt ) {
85            ++statements;
86            if (LLVM_UNLIKELY(isa<If>(stmt) || isa<While>(stmt))) {
87                // Set the next statement to be the first statement of the inner scope and push the
88                // next statement of the current statement into the scope stack.
89                const PabloBlock * const nested = isa<If>(stmt) ? cast<If>(stmt)->getBody() : cast<While>(stmt)->getBody();
90                scope.push(stmt->getNextNode());
91                stmt = nested->front();
92                assert (stmt);
93                continue;
94            }
95            stmt = stmt->getNextNode();
96        }
97        if (scope.empty()) {
98            break;
99        }
100        stmt = scope.top();
101        scope.pop();
102    }
103    return statements;
104}
105
106unsigned COUNT_ADVANCES(const PabloKernel * const entry) {
107
108    std::stack<const Statement *> scope;
109    unsigned advances = 0;
110
111    // Scan through and collect all the advances, calls, scanthrus and matchstars ...
112    for (const Statement * stmt = entry->getEntryBlock()->front(); ; ) {
113        while ( stmt ) {
114            if (isa<Advance>(stmt)) {
115                ++advances;
116            }
117            else if (LLVM_UNLIKELY(isa<If>(stmt) || isa<While>(stmt))) {
118                // Set the next statement to be the first statement of the inner scope and push the
119                // next statement of the current statement into the scope stack.
120                const PabloBlock * const nested = isa<If>(stmt) ? cast<If>(stmt)->getBody() : cast<While>(stmt)->getBody();
121                scope.push(stmt->getNextNode());
122                stmt = nested->front();
123                assert (stmt);
124                continue;
125            }
126            stmt = stmt->getNextNode();
127        }
128        if (scope.empty()) {
129            break;
130        }
131        stmt = scope.top();
132        scope.pop();
133    }
134    return advances;
135}
136
137using DistributionMap = boost::container::flat_map<unsigned, unsigned>;
138
139DistributionMap SUMMARIZE_VARIADIC_DISTRIBUTION(const PabloKernel * const entry) {
140    std::stack<const Statement *> scope;
141    DistributionMap distribution;
142    // Scan through and collect all the advances, calls, scanthrus and matchstars ...
143    for (const Statement * stmt = entry->getEntryBlock()->front(); ; ) {
144        while ( stmt ) {
145            if (isa<Variadic>(stmt)) {
146                auto f = distribution.find(stmt->getNumOperands());
147                if (f == distribution.end()) {
148                    distribution.emplace(stmt->getNumOperands(), 1);
149                } else {
150                    f->second += 1;
151                }
152            }
153            else if (LLVM_UNLIKELY(isa<If>(stmt) || isa<While>(stmt))) {
154                // Set the next statement to be the first statement of the inner scope and push the
155                // next statement of the current statement into the scope stack.
156                const PabloBlock * const nested = isa<If>(stmt) ? cast<If>(stmt)->getBody() : cast<While>(stmt)->getBody();
157                scope.push(stmt->getNextNode());
158                stmt = nested->front();
159                assert (stmt);
160                continue;
161            }
162            stmt = stmt->getNextNode();
163        }
164        if (scope.empty()) {
165            break;
166        }
167        stmt = scope.top();
168        scope.pop();
169    }
170    return distribution;
171}
172#endif
173
174void pablo_function_passes(PabloKernel * kernel) {
175   
176    if (DebugOptions.isSet(PrintCompiledREcode)) {
177        //Print to the terminal the AST that was generated by the pararallel bit-stream compiler.
178        errs() << "Initial Pablo AST:\n";
179        PabloPrinter::print(kernel, errs());
180    }
181   
182    #ifndef NDEBUG
183    PabloVerifier::verify(kernel, "creation");
184    #endif
185
186    // Scan through the pablo code and perform DCE and CSE
187
188#ifdef PRINT_TIMING_INFORMATION
189    timestamp_t simplification_start = 0, simplification_end = 0;
190    timestamp_t flattenif_start = 0, flattenif_end = 0;
191    timestamp_t coalescing_start = 0, coalescing_end = 0;
192    timestamp_t sinking_start = 0, sinking_end = 0;
193    timestamp_t pre_distribution_start = 0, pre_distribution_end = 0;
194    timestamp_t multiplexing_start = 0, multiplexing_end = 0;
195    timestamp_t post_distribution_start = 0, post_distribution_end = 0;
196    timestamp_t lowering_start = 0, lowering_end = 0;
197    timestamp_t scheduling_start = 0, scheduling_end = 0;
198    DistributionMap distribution;
199    const timestamp_t optimization_start = read_cycle_counter();
200#endif
201    if (!PabloOptimizationsOptions.isSet(DisableSimplification)) {
202        READ_CYCLE_COUNTER(simplification_start);
203        Simplifier::optimize(kernel);
204        READ_CYCLE_COUNTER(simplification_end);
205    }
206    if (Flatten){
207        READ_CYCLE_COUNTER(flattenif_start);
208        FlattenIf::transform(kernel);
209        READ_CYCLE_COUNTER(flattenif_end);
210    }
211#ifdef ENABLE_MULTIPLEXING
212//    if (PabloOptimizationsOptions.isSet(EnableLowering) || PabloOptimizationsOptions.isSet(EnablePreDistribution) || PabloOptimizationsOptions.isSet(EnablePostDistribution)) {
213//        READ_CYCLE_COUNTER(coalescing_start);
214//        CanonicalizeDFG::transform(kernel);
215//        READ_CYCLE_COUNTER(coalescing_end);
216//    }
217    if (PabloOptimizationsOptions.isSet(EnablePreDistribution)) {
218        READ_CYCLE_COUNTER(pre_distribution_start);
219        BooleanReassociationPass::optimize(kernel);
220        READ_CYCLE_COUNTER(pre_distribution_end);
221    }
222    if (PabloOptimizationsOptions.isSet(EnableMultiplexing)) {
223        READ_CYCLE_COUNTER(multiplexing_start);
224        MultiplexingPass::optimize(kernel);
225        READ_CYCLE_COUNTER(multiplexing_end);
226//        if (PabloOptimizationsOptions.isSet(EnableLowering) || PabloOptimizationsOptions.isSet(EnablePreDistribution) || PabloOptimizationsOptions.isSet(EnablePostDistribution)) {
227//            CanonicalizeDFG::transform(kernel);
228//        }
229    }
230    if (PabloOptimizationsOptions.isSet(EnablePostDistribution)) {
231        READ_CYCLE_COUNTER(post_distribution_start);
232        BooleanReassociationPass::optimize(kernel);
233        READ_CYCLE_COUNTER(post_distribution_end);
234    }
235#endif
236    if (PabloOptimizationsOptions.isSet(EnableCodeMotion)) {
237        READ_CYCLE_COUNTER(sinking_start);
238        CodeMotionPass::optimize(kernel);
239        READ_CYCLE_COUNTER(sinking_end);
240    }
241#ifdef ENABLE_MULTIPLEXING
242    if (DebugOptions.isSet(PrintUnloweredCode)) {
243        //Print to the terminal the AST that was generated by the pararallel bit-stream compiler.
244        errs() << "Unlowered Pablo AST:\n";
245        PabloPrinter::print(kernel, errs());
246    }
247    #ifdef PRINT_TIMING_INFORMATION
248    distribution = SUMMARIZE_VARIADIC_DISTRIBUTION(function);
249    #endif
250//    if (PabloOptimizationsOptions.isSet(EnableLowering) || PabloOptimizationsOptions.isSet(EnablePreDistribution) || PabloOptimizationsOptions.isSet(EnablePostDistribution)) {
251//        READ_CYCLE_COUNTER(lowering_start);
252//        FactorizeDFG::transform(kernel);
253//        READ_CYCLE_COUNTER(lowering_end);
254//    }
255//    if (PabloOptimizationsOptions.isSet(EnablePrePassScheduling)) {
256//        READ_CYCLE_COUNTER(scheduling_start);
257//        SchedulingPrePass::optimize(kernel);
258//        READ_CYCLE_COUNTER(scheduling_end);
259//    }
260#endif
261#ifdef PRINT_TIMING_INFORMATION
262    const timestamp_t optimization_end = read_cycle_counter();
263#endif
264    if (DebugOptions.isSet(PrintOptimizedREcode)) {
265        if (PabloOutputFilename.empty()) {
266            //Print to the terminal the AST that was generated by the pararallel bit-stream compiler.
267            errs() << "Final Pablo AST:\n";
268            PabloPrinter::print(kernel, errs());
269        } else {
270            std::error_code error;
271            llvm::raw_fd_ostream out(PabloOutputFilename, error, sys::fs::OpenFlags::F_None);
272            PabloPrinter::print(kernel, out);
273        }
274    }
275#ifdef PRINT_TIMING_INFORMATION
276    errs() << "PABLO OPTIMIZATION TIME: " << (optimization_end - optimization_start) << "\n";
277    errs() << "  SIMPLIFICATION TIME: " << (simplification_end - simplification_start) << "\n";
278    errs() << "  COALESCING TIME: " << (coalescing_end - coalescing_start) << "\n";
279    errs() << "  SINKING TIME: " << (sinking_end - sinking_start) << "\n";
280    errs() << "  PRE-DISTRIBUTION TIME: " << (pre_distribution_end - pre_distribution_start) << "\n";
281    errs() << "  MULTIPLEXING TIME: " << (multiplexing_end - multiplexing_start) << "\n";
282    errs() << "  LOWERING TIME: " << (lowering_end - lowering_start) << "\n";
283    errs() << "  FLATTENIF TIME: " << (flattenif_end - flattenif_start) << "\n";
284    errs() << "  POST-DISTRIBUTION TIME: " << (post_distribution_end - post_distribution_start) << "\n";
285    errs() << "  SCHEDULING TIME: " << (scheduling_end - scheduling_start) << "\n";
286    errs() << "PABLO STATEMENTS: " << COUNT_STATEMENTS(function) << "\n";
287    errs() << "PABLO ADVANCES: " << COUNT_ADVANCES(function) << "\n";
288    errs() << "PRE-LOWERING VARIADIC DISTRIBUTION: ";
289    bool join = false;
290    for (auto dist : distribution) {
291        if (join) {
292            errs() << ';';
293        }
294        errs() << dist.first << '|' << dist.second;
295        join = true;
296    }
297    errs() << "\n";
298#endif
299}
300
301}
Note: See TracBrowser for help on using the repository browser.