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

Last change on this file since 5124 was 5032, checked in by xuedongx, 3 years ago

Add a Pablo option to flatten all the Ifs in the Pablo AST.

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