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

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

Work on multiplexing and distribution passes + a few AST modification bug fixes.

File size: 13.2 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/booleanreassociationpass.h>
22#include <pablo/optimizers/distributivepass.h>
23#include <pablo/optimizers/schedulingprepass.h>
24#endif
25#include <pablo/function.h>
26#include <pablo/analysis/pabloverifier.hpp>
27#include <pablo/printer_pablos.h>
28#include <sstream>
29#include <llvm/Support/CommandLine.h>
30#include <llvm/Support/FileSystem.h>
31#ifdef PRINT_TIMING_INFORMATION
32#include <hrtime.h>
33#endif
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(PabloSinkingPass, "Moves all instructions into the innermost legal If-scope so that they are only executed when needed."),
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 PabloFunction * 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 PabloFunction * 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 PabloFunction * 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(PabloFunction * function) {
175   
176    if (DebugOptions.isSet(PrintCompiledREcode)) {
177        //Print to the terminal the AST that was generated by the pararallel bit-stream compiler.
178        llvm::raw_os_ostream cerr(std::cerr);
179        cerr << "Initial Pablo AST:\n";
180        PabloPrinter::print(*function, cerr);
181    }
182   
183#ifndef NDEBUG
184    PabloVerifier::verify(*function, "creation");
185#endif
186   
187    // Scan through the pablo code and perform DCE and CSE
188
189#ifdef PRINT_TIMING_INFORMATION
190    timestamp_t simplification_start = 0, simplification_end = 0;
191    timestamp_t flattenif_start = 0, flattenif_end = 0;
192    timestamp_t coalescing_start = 0, coalescing_end = 0;
193    timestamp_t sinking_start = 0, sinking_end = 0;
194    timestamp_t pre_distribution_start = 0, pre_distribution_end = 0;
195    timestamp_t multiplexing_start = 0, multiplexing_end = 0;
196    timestamp_t post_distribution_start = 0, post_distribution_end = 0;
197    timestamp_t lowering_start = 0, lowering_end = 0;
198    timestamp_t scheduling_start = 0, scheduling_end = 0;
199    DistributionMap distribution;
200    const timestamp_t optimization_start = read_cycle_counter();
201#endif
202    if (!PabloOptimizationsOptions.isSet(DisableSimplification)) {
203        READ_CYCLE_COUNTER(simplification_start);
204        Simplifier::optimize(*function);
205        READ_CYCLE_COUNTER(simplification_end);
206    }
207    if (Flatten){
208        READ_CYCLE_COUNTER(flattenif_start);
209        FlattenIf::transform(*function);
210        READ_CYCLE_COUNTER(flattenif_end);
211    }
212#ifdef ENABLE_MULTIPLEXING
213//    if (PabloOptimizationsOptions.isSet(EnableLowering) || PabloOptimizationsOptions.isSet(EnablePreDistribution) || PabloOptimizationsOptions.isSet(EnablePostDistribution)) {
214//        READ_CYCLE_COUNTER(coalescing_start);
215//        CanonicalizeDFG::transform(*function);
216//        READ_CYCLE_COUNTER(coalescing_end);
217//    }
218    if (PabloOptimizationsOptions.isSet(EnablePreDistribution)) {
219        READ_CYCLE_COUNTER(pre_distribution_start);
220        BooleanReassociationPass::optimize(*function);
221        READ_CYCLE_COUNTER(pre_distribution_end);
222    }
223    if (PabloOptimizationsOptions.isSet(EnableMultiplexing)) {
224        READ_CYCLE_COUNTER(multiplexing_start);
225        MultiplexingPass::optimize(*function);
226        READ_CYCLE_COUNTER(multiplexing_end);
227//        if (PabloOptimizationsOptions.isSet(EnableLowering) || PabloOptimizationsOptions.isSet(EnablePreDistribution) || PabloOptimizationsOptions.isSet(EnablePostDistribution)) {
228//            CanonicalizeDFG::transform(*function);
229//        }
230    }
231    if (PabloOptimizationsOptions.isSet(EnablePostDistribution)) {
232        READ_CYCLE_COUNTER(post_distribution_start);
233        BooleanReassociationPass::optimize(*function);
234        READ_CYCLE_COUNTER(post_distribution_end);
235    }
236#endif
237    if (PabloOptimizationsOptions.isSet(PabloSinkingPass)) {
238        READ_CYCLE_COUNTER(sinking_start);
239        CodeMotionPass::optimize(*function);
240        READ_CYCLE_COUNTER(sinking_end);
241    }
242#ifdef ENABLE_MULTIPLEXING
243    if (DebugOptions.isSet(PrintUnloweredCode)) {
244        //Print to the terminal the AST that was generated by the pararallel bit-stream compiler.
245        llvm::raw_os_ostream cerr(std::cerr);
246        cerr << "Unlowered Pablo AST:\n";
247        PabloPrinter::print(*function, cerr);
248    }
249    #ifdef PRINT_TIMING_INFORMATION
250    distribution = SUMMARIZE_VARIADIC_DISTRIBUTION(function);
251    #endif
252//    if (PabloOptimizationsOptions.isSet(EnableLowering) || PabloOptimizationsOptions.isSet(EnablePreDistribution) || PabloOptimizationsOptions.isSet(EnablePostDistribution)) {
253//        READ_CYCLE_COUNTER(lowering_start);
254//        FactorizeDFG::transform(*function);
255//        READ_CYCLE_COUNTER(lowering_end);
256//    }
257//    if (PabloOptimizationsOptions.isSet(EnablePrePassScheduling)) {
258//        READ_CYCLE_COUNTER(scheduling_start);
259//        SchedulingPrePass::optimize(*function);
260//        READ_CYCLE_COUNTER(scheduling_end);
261//    }
262#endif
263#ifdef PRINT_TIMING_INFORMATION
264    const timestamp_t optimization_end = read_cycle_counter();
265#endif
266    if (DebugOptions.isSet(PrintOptimizedREcode)) {
267        if (PabloOutputFilename.empty()) {
268            //Print to the terminal the AST that was generated by the pararallel bit-stream compiler.
269            llvm::raw_os_ostream cerr(std::cerr);
270            cerr << "Final Pablo AST:\n";
271            PabloPrinter::print(*function, cerr);
272        } else {
273            std::error_code error;
274            llvm::raw_fd_ostream out(PabloOutputFilename, error, sys::fs::OpenFlags::F_None);
275            PabloPrinter::print(*function, out);
276        }
277    }
278#ifdef PRINT_TIMING_INFORMATION
279    std::cerr << "PABLO OPTIMIZATION TIME: " << (optimization_end - optimization_start) << std::endl;
280    std::cerr << "  SIMPLIFICATION TIME: " << (simplification_end - simplification_start) << std::endl;
281    std::cerr << "  COALESCING TIME: " << (coalescing_end - coalescing_start) << std::endl;
282    std::cerr << "  SINKING TIME: " << (sinking_end - sinking_start) << std::endl;
283    std::cerr << "  PRE-DISTRIBUTION TIME: " << (pre_distribution_end - pre_distribution_start) << std::endl;
284    std::cerr << "  MULTIPLEXING TIME: " << (multiplexing_end - multiplexing_start) << std::endl;
285    std::cerr << "  LOWERING TIME: " << (lowering_end - lowering_start) << std::endl;
286    std::cerr << "  FLATTENIF TIME: " << (flattenif_end - flattenif_start) << std::endl;
287    std::cerr << "  POST-DISTRIBUTION TIME: " << (post_distribution_end - post_distribution_start) << std::endl;
288    std::cerr << "  SCHEDULING TIME: " << (scheduling_end - scheduling_start) << std::endl;
289    std::cerr << "PABLO STATEMENTS: " << COUNT_STATEMENTS(function) << std::endl;
290    std::cerr << "PABLO ADVANCES: " << COUNT_ADVANCES(function) << std::endl;
291    std::cerr << "PRE-LOWERING VARIADIC DISTRIBUTION: ";
292    bool join = false;
293    for (auto dist : distribution) {
294        if (join) {
295            std::cerr << ';';
296        }
297        std::cerr << dist.first << '|' << dist.second;
298        join = true;
299    }
300    std::cerr << std::endl;
301#endif
302}
303
304}
Note: See TracBrowser for help on using the repository browser.