Ignore:
Timestamp:
Nov 22, 2015, 3:17:10 PM (4 years ago)
Author:
nmedfort
Message:

More work on n-ary operations.

Location:
icGREP/icgrep-devel/icgrep/pablo/passes
Files:
2 edited

Legend:

Unmodified
Added
Removed
  • icGREP/icgrep-devel/icgrep/pablo/passes/flattenassociativedfg.cpp

    r4876 r4878  
    33#include <pablo/codegenstate.h>
    44#include <pablo/optimizers/pablo_simplifier.hpp>
     5#include <boost/container/flat_map.hpp>
     6#include <boost/graph/adjacency_list.hpp>
    57#include <pablo/analysis/pabloverifier.hpp>
    68
     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
    716namespace pablo {
     17
     18using TypeId = PabloAST::ClassTypeId;
     19using Graph = adjacency_list<hash_setS, vecS, bidirectionalS, PabloAST *>;
     20using Map = flat_map<PabloAST *, Graph::vertex_descriptor>;
    821
    922/** ------------------------------------------------------------------------------------------------------------- *
    1023 * @brief flatten
    1124 ** ------------------------------------------------------------------------------------------------------------- */
    12 inline bool FlattenAssociativeDFG::flatten(Variadic * const var, PabloBlock * const block) {
    13     bool modified = false;
    14     for (;;) {
    15         bool unmodified = true;
    16         for (unsigned i = 0; i < var->getNumOperands(); ) {
    17             PabloAST * const op = var->getOperand(i);
    18             if ((op->getNumUses() == 1) && (op->getClassTypeId() == var->getClassTypeId()) && (cast<Variadic>(op)->getParent() == block)) {
    19                 var->removeOperand(i);
    20                 for (unsigned j = 0; j != cast<Variadic>(op)->getNumOperands(); ++j) {
    21                     var->addOperand(cast<Variadic>(op)->getOperand(j));
    22                 }
    23                 assert (op->getNumUses() == 0);
    24                 cast<Variadic>(op)->eraseFromParent(true);
    25                 unmodified = false;
    26                 modified = true;
    27                 continue;
     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));
    2833            }
    29             ++i;
     34            continue;
    3035        }
    31         if (unmodified) {
    32             break;
     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());
    3357        }
     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);
    3464    }
    35     return modified;
    3665}
    3766
     
    3968 * @brief flatten
    4069 ** ------------------------------------------------------------------------------------------------------------- */
    41 inline bool FlattenAssociativeDFG::flatten(PabloBlock * const block) {
    42     bool modified = false;
     70void FlattenAssociativeDFG::flatten(PabloBlock * const block) {
    4371    Statement * stmt = block->front();
    4472    while (stmt) {
    45         if (isa<And>(stmt) || isa<Or>(stmt) || isa<Xor>(stmt)) {
    46             Variadic * var = cast<Variadic>(stmt);
    47             if (flatten(var, block)) {
    48                 modified = true;
    49                 if (PabloAST * replacement = Simplifier::foldReassociativeFunction(var, block)) {
    50                     stmt = stmt->replaceWith(replacement);
     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)) {
    51128                    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;
    52141                }
    53142            }
    54143        }
    55         stmt = stmt->getNextNode();
    56144    }
    57     return modified;
    58145}
    59146
    60147/** ------------------------------------------------------------------------------------------------------------- *
    61  * @brief factorize
     148 * @brief extract
    62149 ** ------------------------------------------------------------------------------------------------------------- */
    63 inline bool FlattenAssociativeDFG::factorize(PabloBlock * const block) {
    64     bool modified = false;
     150void FlattenAssociativeDFG::extract(PabloBlock * const block) {
    65151    Statement * stmt = block->front();
    66152    while (stmt) {
    67         if (isa<And>(stmt) || isa<Or>(stmt) || isa<Xor>(stmt)) {
    68             // Does this function share two operands with another function of the same type?
    69             // If so, pull them out of both functions.
    70             Variadic * var = cast<Variadic>(stmt);
    71             for (unsigned i = 1; i < var->getNumOperands(); ++i) {
    72                 for (unsigned j = 0; j != i; ++j) {
    73 
    74                 }
    75             }
     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));
    76159        }
    77160        stmt = stmt->getNextNode();
    78161    }
    79     return modified;
    80 }
    81 
    82 
    83 /** ------------------------------------------------------------------------------------------------------------- *
    84  * @brief traverse
    85  ** ------------------------------------------------------------------------------------------------------------- */
    86 void FlattenAssociativeDFG::traverse(PabloBlock * const block) {
    87     for (Statement * stmt : *block) {
    88         if (isa<If>(stmt) || isa<While>(stmt)) {
    89             traverse(isa<If>(stmt) ? cast<If>(stmt)->getBody() : cast<While>(stmt)->getBody());
    90         }
    91     }
    92     flatten(block);
    93162}
    94163
     
    96165 * @brief process
    97166 ** ------------------------------------------------------------------------------------------------------------- */
    98 void FlattenAssociativeDFG::process(PabloFunction & function) {
    99     FlattenAssociativeDFG::traverse(function.getEntryBlock());
    100 //    #ifndef NDEBUG
    101     PabloVerifier::verify(function, "post-flatten-associative-dfg");
    102 //    #endif
     167void FlattenAssociativeDFG::transform(PabloFunction & function) {
     168
     169    FlattenAssociativeDFG::flatten(function.getEntryBlock());
     170    #ifndef NDEBUG
     171    PabloVerifier::verify(function, "post-flatten");
     172    #endif
    103173    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
    104181}
    105182
  • icGREP/icgrep-devel/icgrep/pablo/passes/flattenassociativedfg.h

    r4876 r4878  
    11#ifndef FLATTENASSOCIATIVEDFG_H
    22#define FLATTENASSOCIATIVEDFG_H
    3 
    43
    54namespace pablo {
     
    87class PabloBlock;
    98class Variadic;
     9class Not;
     10class Assign;
     11
    1012
    1113class FlattenAssociativeDFG {
    1214public:
    13     static void process(PabloFunction & function);
     15    static void transform(PabloFunction & function);
    1416protected:
    15     static void traverse(PabloBlock * const block);
    16     static bool flatten(PabloBlock * const block);
    17     static bool factorize(PabloBlock * const block);
    18     static bool flatten(Variadic * const var, PabloBlock * const block);
     17
     18    static void flatten(PabloBlock * const block);
     19    static void flatten(Variadic * const var);
     20    static void applyNegationInwards(Not * const var, PabloBlock * const block);
     21
     22    static void extract(PabloBlock * const block);
     23    static void extractNegationsOutwards(Variadic * const var, PabloBlock * const block);
     24    static void removeCommonCalculation(Assign * const def);
     25
    1926    FlattenAssociativeDFG() = default;
    2027};
Note: See TracChangeset for help on using the changeset viewer.