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

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

Incorporated n-ary coalescing into DistributivePass?.

File size: 6.3 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
9using namespace boost;
10using namespace boost::container;
11
12namespace pablo {
13
14using TypeId = PabloAST::ClassTypeId;
15using Graph = adjacency_list<hash_setS, vecS, bidirectionalS, PabloAST *>;
16using Map = flat_map<PabloAST *, Graph::vertex_descriptor>;
17
18/** ------------------------------------------------------------------------------------------------------------- *
19 * @brief coalesce
20 ** ------------------------------------------------------------------------------------------------------------- */
21inline void FlattenAssociativeDFG::coalesce(Variadic * const var) {
22    const TypeId typeId = var->getClassTypeId();
23    for (unsigned i = 0; i < var->getNumOperands(); ) {
24        PabloAST * const op = var->getOperand(i);
25        if (op->getClassTypeId() == typeId) {
26            Variadic * removedVar = cast<Variadic>(var->removeOperand(i));
27            for (unsigned j = 0; j != cast<Variadic>(op)->getNumOperands(); ++j) {
28                var->addOperand(cast<Variadic>(op)->getOperand(j));
29            }
30            if (removedVar->getNumOperands() == 1) {
31                removedVar->replaceWith(removedVar->getOperand(0));
32            } else if (removedVar->getNumUsers() == 0) {
33                removedVar->eraseFromParent(true);
34            }
35            continue;
36        }
37        ++i;
38    }
39}
40
41/** ------------------------------------------------------------------------------------------------------------- *
42 * @brief coalesce
43 ** ------------------------------------------------------------------------------------------------------------- */
44void FlattenAssociativeDFG::coalesce(PabloBlock * const block, const bool traverse) {
45    Statement * stmt = block->front();
46    while (stmt) {
47        Statement * next = stmt->getNextNode();
48        if (traverse && (isa<If>(stmt) || isa<While>(stmt))) {
49            coalesce(isa<If>(stmt) ? cast<If>(stmt)->getBody() : cast<While>(stmt)->getBody(), true);
50        } else if (isa<And>(stmt) || isa<Or>(stmt) || isa<Xor>(stmt)) {
51            coalesce(cast<Variadic>(stmt));
52        } else if (isa<Not>(stmt)) {
53            deMorgansExpansion(cast<Not>(stmt), block);
54        }
55        stmt = next;
56    }
57}
58
59/** ------------------------------------------------------------------------------------------------------------- *
60 * @brief deMorgansExpansion
61 *
62 * Apply the De Morgans' law to any negated And or Or statement with the intent of further coalescing its operands
63 * thereby allowing the Simplifier to check for tautologies and contradictions.
64 ** ------------------------------------------------------------------------------------------------------------- */
65inline void FlattenAssociativeDFG::deMorgansExpansion(Not * const var, PabloBlock * const block) {
66    PabloAST * const negatedVar = var->getOperand(0);
67    if (isa<And>(negatedVar) || isa<Or>(negatedVar)) {
68        Variadic * src = cast<Variadic>(negatedVar);
69        const unsigned operands = src->getNumOperands();
70        Variadic * replacement = nullptr;
71        block->setInsertPoint(var->getPrevNode());
72        if (isa<And>(negatedVar)) {
73            replacement = block->createOr(operands);
74        } else {
75            replacement = block->createAnd(operands);
76        }
77        block->setInsertPoint(replacement->getPrevNode());
78        for (unsigned i = 0; i != operands; ++i) {
79            replacement->addOperand(block->createNot(src->getOperand(i)));
80        }
81        coalesce(replacement);
82        var->replaceWith(replacement, true, true);
83    }
84}
85
86/** ------------------------------------------------------------------------------------------------------------- *
87 * @brief deMorgansReduction
88 ** ------------------------------------------------------------------------------------------------------------- */
89inline void FlattenAssociativeDFG::deMorgansReduction(Variadic * const var, PabloBlock * const block) {
90    unsigned negations = 0;
91    for (unsigned i = 0; i < var->getNumOperands(); ++i) {
92        if (isa<Not>(var->getOperand(i))) {
93            ++negations;
94        }
95    }
96    if (negations > 1) {
97        PabloAST * negated[negations];
98        for (unsigned i = var->getNumOperands(), j = negations; i && j; ) {
99            if (isa<Not>(var->getOperand(--i))) {
100                negated[--j] = cast<Not>(var->removeOperand(i))->getOperand(0);
101            }
102        }
103        block->setInsertPoint(var->getPrevNode());
104        Variadic * extractedVar = nullptr;
105        if (isa<And>(var)) {
106            extractedVar = block->createOr(negations);
107        } else { // if (isa<Or>(var)) {
108            extractedVar = block->createAnd(negations);
109        }
110        for (unsigned i = 0; i != negations; ++i) {
111            extractedVar->addOperand(negated[i]);
112        }
113        var->addOperand(block->createNot(extractedVar));
114    }
115}
116
117/** ------------------------------------------------------------------------------------------------------------- *
118 * @brief extractNegationsOutwards
119 ** ------------------------------------------------------------------------------------------------------------- */
120inline void FlattenAssociativeDFG::deMorgansReduction(PabloBlock * const block) {
121    for (Statement * stmt : *block) {
122        if (isa<If>(stmt) || isa<While>(stmt)) {
123            deMorgansReduction(isa<If>(stmt) ? cast<If>(stmt)->getBody() : cast<While>(stmt)->getBody());
124        } else if (isa<And>(stmt) || isa<Or>(stmt)) {
125            deMorgansReduction(cast<Variadic>(stmt), block);
126        }
127    }
128}
129
130/** ------------------------------------------------------------------------------------------------------------- *
131 * @brief transform
132 ** ------------------------------------------------------------------------------------------------------------- */
133void FlattenAssociativeDFG::transform(PabloFunction & function) {
134
135    FlattenAssociativeDFG::coalesce(function.getEntryBlock(), true);
136    #ifndef NDEBUG
137    PabloVerifier::verify(function, "post-coalescence");
138    #endif
139
140    Simplifier::optimize(function);
141
142    FlattenAssociativeDFG::deMorgansReduction(function.getEntryBlock());
143    #ifndef NDEBUG
144    PabloVerifier::verify(function, "post-demorgans-reduction");
145    #endif
146
147    Simplifier::optimize(function);
148}
149
150}
Note: See TracBrowser for help on using the repository browser.