source: icGREP/icgrep-devel/icgrep/pablo/passes/flattenassociativedfg.cpp @ 4878

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

More work on n-ary operations.

File size: 7.5 KB
Line 
1#include "flattenassociativedfg.h"
2
3#include <pablo/codegenstate.h>
4#include <pablo/optimizers/pablo_simplifier.hpp>
5#include <boost/container/flat_map.hpp>
6#include <boost/graph/adjacency_list.hpp>
7#include <pablo/analysis/pabloverifier.hpp>
8
9#include <boost/graph/strong_components.hpp>
10#include <pablo/printer_pablos.h>
11#include <iostream>
12
13using namespace boost;
14using namespace boost::container;
15
16namespace pablo {
17
18using TypeId = PabloAST::ClassTypeId;
19using Graph = adjacency_list<hash_setS, vecS, bidirectionalS, PabloAST *>;
20using Map = flat_map<PabloAST *, Graph::vertex_descriptor>;
21
22/** ------------------------------------------------------------------------------------------------------------- *
23 * @brief flatten
24 ** ------------------------------------------------------------------------------------------------------------- */
25inline void FlattenAssociativeDFG::flatten(Variadic * const var) {
26    const TypeId typeId = var->getClassTypeId();
27    for (unsigned i = 0; i < var->getNumOperands(); ) {
28        PabloAST * const op = var->getOperand(i);
29        if (op->getClassTypeId() == typeId) {
30            var->removeOperand(i);
31            for (unsigned j = 0; j != cast<Variadic>(op)->getNumOperands(); ++j) {
32                var->addOperand(cast<Variadic>(op)->getOperand(j));
33            }
34            continue;
35        }
36        ++i;
37    }
38}
39
40/** ------------------------------------------------------------------------------------------------------------- *
41 * @brief applyNegationInwards
42 *
43 * Apply the De Morgans' law to any negated And or Or statement with the intent of further flattening its operands
44 * and creating a bigger clause for the Simplifier to analyze.
45 ** ------------------------------------------------------------------------------------------------------------- */
46inline void FlattenAssociativeDFG::applyNegationInwards(Not * const var, PabloBlock * const block) {
47    PabloAST * negatedVar = var->getOperand(0);
48    if (isa<And>(negatedVar) || isa<Or>(negatedVar)) {
49        Variadic * src = cast<Variadic>(negatedVar);
50        const unsigned operands = src->getNumOperands();
51        Variadic * replacement = nullptr;
52        block->setInsertPoint(var->getPrevNode());
53        if (isa<And>(negatedVar)) {
54            replacement = block->createOr(operands, PabloBlock::createZeroes());
55        } else {
56            replacement = block->createAnd(operands, PabloBlock::createOnes());
57        }
58        block->setInsertPoint(replacement->getPrevNode());
59        for (unsigned i = 0; i != operands; ++i) {
60            replacement->setOperand(i, block->createNot(src->getOperand(i)));
61        }
62        flatten(replacement);
63        var->replaceWith(replacement, true, true);
64    }
65}
66
67/** ------------------------------------------------------------------------------------------------------------- *
68 * @brief flatten
69 ** ------------------------------------------------------------------------------------------------------------- */
70void FlattenAssociativeDFG::flatten(PabloBlock * const block) {
71    Statement * stmt = block->front();
72    while (stmt) {
73        Statement * next = stmt->getNextNode();
74        if (isa<If>(stmt) || isa<While>(stmt)) {
75            flatten(isa<If>(stmt) ? cast<If>(stmt)->getBody() : cast<While>(stmt)->getBody());
76        } else if (isa<And>(stmt) || isa<Or>(stmt) || isa<Xor>(stmt)) {
77            flatten(cast<Variadic>(stmt));
78        } else if (isa<Not>(stmt)) {
79            applyNegationInwards(cast<Not>(stmt), block);
80        }
81        stmt = next;
82    }
83}
84
85/** ------------------------------------------------------------------------------------------------------------- *
86 * @brief extractNegationsOutwards
87 ** ------------------------------------------------------------------------------------------------------------- */
88inline void FlattenAssociativeDFG::extractNegationsOutwards(Variadic * const var, PabloBlock * const block) {
89    PabloAST * negated[var->getNumOperands()];
90    unsigned operands = 0;
91    for (unsigned i = 0; i != var->getNumOperands(); ) {
92        if (isa<Not>(var->getOperand(i))) {
93            negated[operands++] = cast<Not>(var->removeOperand(i))->getOperand(0);
94            continue;
95        }
96        ++i;
97    }
98    if (operands) {
99        block->setInsertPoint(var->getPrevNode());
100        Variadic * extractedVar = nullptr;
101        if (isa<And>(var)) {
102            extractedVar = block->createOr(operands, PabloBlock::createZeroes());
103        } else {
104            extractedVar = block->createAnd(operands, PabloBlock::createOnes());
105        }
106        for (unsigned i = 0; i != operands; ++i) {
107            extractedVar->setOperand(i, negated[i]);
108        }
109        std::sort(extractedVar->begin(), extractedVar->end());
110        var->addOperand(block->createNot(extractedVar));
111        std::sort(var->begin(), var->end());
112    }
113}
114
115/** ------------------------------------------------------------------------------------------------------------- *
116 * @brief removeCommonCalculation
117 ** ------------------------------------------------------------------------------------------------------------- */
118inline void FlattenAssociativeDFG::removeCommonCalculation(Assign * const def) {
119    PabloAST * op = def->getOperand(0);
120    if (isa<And>(op) || isa<Or>(op) || isa<Xor>(op)) {
121        Variadic * const var = cast<Variadic>(op);
122        std::vector<PabloAST *> common(var->begin(), var->end());
123        std::vector<PabloAST *> temp;
124        temp.reserve(common.size());
125        for (PabloAST * user : def->users()) {
126            if (user->getClassTypeId() != var->getClassTypeId()) {
127                if (isa<If>(user)) {
128                    continue;
129                }
130                return;
131            }
132            std::set_intersection(common.begin(), common.end(), cast<Variadic>(user)->begin(), cast<Variadic>(user)->end(), std::back_inserter(temp));
133            common.swap(temp);
134            temp.clear();
135        }
136        for (PabloAST * op : common) {
137            for (unsigned i = 0; i != var->getNumOperands(); ++i) {
138                if (var->getOperand(i) == op) {
139                    var->removeOperand(i);
140                    break;
141                }
142            }
143        }
144    }
145}
146
147/** ------------------------------------------------------------------------------------------------------------- *
148 * @brief extract
149 ** ------------------------------------------------------------------------------------------------------------- */
150void FlattenAssociativeDFG::extract(PabloBlock * const block) {
151    Statement * stmt = block->front();
152    while (stmt) {
153        if (isa<If>(stmt) || isa<While>(stmt)) {
154            extract(isa<If>(stmt) ? cast<If>(stmt)->getBody() : cast<While>(stmt)->getBody());
155        } else if (isa<And>(stmt) || isa<Or>(stmt)) {
156            extractNegationsOutwards(cast<Variadic>(stmt), block);
157        } else if (isa<Assign>(stmt)) {
158            removeCommonCalculation(cast<Assign>(stmt));
159        }
160        stmt = stmt->getNextNode();
161    }
162}
163
164/** ------------------------------------------------------------------------------------------------------------- *
165 * @brief process
166 ** ------------------------------------------------------------------------------------------------------------- */
167void FlattenAssociativeDFG::transform(PabloFunction & function) {
168
169    FlattenAssociativeDFG::flatten(function.getEntryBlock());
170    #ifndef NDEBUG
171    PabloVerifier::verify(function, "post-flatten");
172    #endif
173    Simplifier::optimize(function);
174
175    FlattenAssociativeDFG::extract(function.getEntryBlock());
176    #ifndef NDEBUG
177    PabloVerifier::verify(function, "post-extract");
178    #endif
179    Simplifier::optimize(function);
180
181}
182
183}
Note: See TracBrowser for help on using the repository browser.