Ignore:
Timestamp:
Sep 14, 2015, 3:57:02 PM (4 years ago)
Author:
nmedfort
Message:

More bug-fixing work on reassociation pass.

File:
1 edited

Legend:

Unmodified
Added
Removed
  • icGREP/icgrep-devel/icgrep/pablo/optimizers/pablo_bddminimization.cpp

    r4751 r4770  
    1414#include <boost/container/flat_map.hpp>
    1515#include <boost/graph/adjacency_list.hpp>
     16#include <boost/graph/topological_sort.hpp>
    1617
    1718using namespace llvm;
     
    2122namespace pablo {
    2223
     24using TypeId = PabloAST::ClassTypeId;
     25
    2326bool BDDMinimizationPass::optimize(PabloFunction & function) {
    2427    BDDMinimizationPass am;
    2528    am.eliminateLogicallyEquivalentStatements(function);
     29
     30    am.shutdown();
    2631    return Simplifier::optimize(function);
    2732}
     
    5257            }
    5358            switch (stmt->getClassTypeId()) {
    54                 case PabloAST::ClassTypeId::Assign:
    55                 case PabloAST::ClassTypeId::Next:
    56                 case PabloAST::ClassTypeId::Advance:
    57                 case PabloAST::ClassTypeId::Call:
    58                 case PabloAST::ClassTypeId::MatchStar:
    59                 case PabloAST::ClassTypeId::ScanThru:
     59                case TypeId::Assign:
     60                case TypeId::Next:
     61                case TypeId::Advance:
     62                case TypeId::Call:
     63                case TypeId::MatchStar:
     64                case TypeId::ScanThru:
    6065                    variableCount++;
    6166                    break;                                   
     
    9398
    9499    eliminateLogicallyEquivalentStatements(function.getEntryBlock(), baseMap);
    95 
    96     Cudd_Quit(mManager);
    97100}
    98101
     
    135138        stmt = stmt->getNextNode();
    136139    }   
    137     Cudd_ReduceHeap(mManager, CUDD_REORDER_SIFT, 1);
     140    // Cudd_ReduceHeap(mManager, CUDD_REORDER_SIFT, 1);
    138141}
    139142
     
    166169
    167170    switch (stmt->getClassTypeId()) {
    168         case PabloAST::ClassTypeId::Assign:
    169         case PabloAST::ClassTypeId::Next:
     171        case TypeId::Assign:
     172        case TypeId::Next:
    170173            return std::make_pair(input[0], false);
    171         case PabloAST::ClassTypeId::And:
     174        case TypeId::And:
    172175            bdd = And(input[0], input[1]);
    173176            break;
    174         case PabloAST::ClassTypeId::Or:
     177        case TypeId::Or:
    175178            bdd = Or(input[0], input[1]);
    176179            break;
    177         case PabloAST::ClassTypeId::Xor:
     180        case TypeId::Xor:
    178181            bdd = Xor(input[0], input[1]);
    179182            break;
    180         case PabloAST::ClassTypeId::Not:
     183        case TypeId::Not:
    181184            bdd = Not(input[0]);
    182185            break;
    183         case PabloAST::ClassTypeId::Sel:
     186        case TypeId::Sel:
    184187            bdd = Ite(input[0], input[1], input[2]);
    185188            break;
    186         case PabloAST::ClassTypeId::MatchStar:
    187         case PabloAST::ClassTypeId::ScanThru:
     189        case TypeId::MatchStar:
     190        case TypeId::ScanThru:
    188191            if (LLVM_UNLIKELY(input[1] == Zero())) {
    189192                return std::make_pair(Zero(), true);
    190193            }
    191         case PabloAST::ClassTypeId::Advance:
     194        case TypeId::Advance:
    192195            if (LLVM_UNLIKELY(input[0] == Zero())) {
    193196                return std::make_pair(Zero(), true);
    194197            }
    195         case PabloAST::ClassTypeId::Call:
     198        case TypeId::Call:
    196199            // TODO: we may have more than one output. Need to fix call class to allow for it.
    197200            return std::make_pair(NewVar(stmt), false);
     
    208211
    209212/** ------------------------------------------------------------------------------------------------------------- *
     213 * @brief identifyHiddenContradicionsAndTautologies
     214 *
     215 * This function attempts to scan through the AST and identify statements such as (A op2 B) op1 (¬A op3 C), where
     216 * op1, op2 and op3 are And, Or or Xor operations.
     217 ** ------------------------------------------------------------------------------------------------------------- */
     218void BDDMinimizationPass::identifyHiddenContradicionsAndTautologies(PabloBlock & block) {
     219
     220    using Graph = adjacency_list<hash_setS, vecS, bidirectionalS, PabloAST *>;
     221    using Vertex = Graph::vertex_descriptor;
     222    using Map = std::unordered_map<const PabloAST *, Vertex>;
     223
     224    Graph G;
     225    Map M;
     226    for (Statement * stmt : block) {
     227        const TypeId typeId = stmt->getClassTypeId();
     228        if (typeId == TypeId::And || typeId == TypeId::Or || typeId == TypeId::Xor) {
     229            const auto u = add_vertex(stmt, G);
     230            M.insert(std::make_pair(stmt, u));
     231            for (unsigned i = 0; i != stmt->getNumOperands(); ++i) {
     232                const auto f = M.find(stmt->getOperand(i));
     233                if (f != M.end()) {
     234                    add_edge(f->second, u, G);
     235                }
     236            }
     237        }
     238    }
     239
     240    if (num_edges(G) == 0) {
     241        return;
     242    }
     243
     244    std::vector<Vertex> ordering;
     245    ordering.reserve(num_vertices(G));
     246    topological_sort(G, std::back_inserter(ordering));
     247
     248    std::vector<unsigned> component(num_vertices(G));
     249    unsigned components = 0;
     250    for (auto u : ordering) {
     251        if (out_degree(u, G) != G[u]->users().size()) {
     252            assert (out_degree(u, G) > G[u]->users().size());
     253            component[u] = ++components;
     254        }
     255    }
     256
     257    // ....
     258
     259
     260}
     261
     262/** ------------------------------------------------------------------------------------------------------------- *
    210263 * @brief CUDD wrappers
    211264 ** ------------------------------------------------------------------------------------------------------------- */
Note: See TracChangeset for help on using the changeset viewer.