Ignore:
Timestamp:
Aug 24, 2015, 4:14:48 PM (4 years ago)
Author:
nmedfort
Message:

First (hopefully) working version of the boolean reassociation pass + some bug fixes.

File:
1 edited

Legend:

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

    r4747 r4748  
    6262using Graph = adjacency_list<hash_setS, vecS, bidirectionalS, PabloAST *>;
    6363using Vertex = Graph::vertex_descriptor;
     64using VertexQueue = circular_buffer<Vertex>;
    6465
    6566/** ------------------------------------------------------------------------------------------------------------- *
     
    7879
    7980/** ------------------------------------------------------------------------------------------------------------- *
     81 * @brief push
     82 ** ------------------------------------------------------------------------------------------------------------- */
     83static inline void push(const Vertex u, VertexQueue & Q) {
     84    if (LLVM_UNLIKELY(Q.full())) {
     85        Q.set_capacity(Q.capacity() * 2);
     86    }
     87    Q.push_back(u);
     88    assert (Q.back() == u);
     89}
     90
     91/** ------------------------------------------------------------------------------------------------------------- *
     92 * @brief pop
     93 ** ------------------------------------------------------------------------------------------------------------- */
     94static inline Vertex pop(VertexQueue & Q) {
     95    assert (!Q.empty() && "Popping an empty vertex queue");
     96    const Vertex u = Q.front();
     97    Q.pop_front();
     98    return u;
     99}
     100
     101/** ------------------------------------------------------------------------------------------------------------- *
    80102 * @brief scan
    81103 ** ------------------------------------------------------------------------------------------------------------- */
     
    83105
    84106    using Map = std::unordered_map<PabloAST *, Vertex>;
    85     using VertexQueue = std::queue<Vertex>;
    86107    using EdgeQueue = std::queue<std::pair<Vertex, Vertex>>;
    87 
    88     PabloBuilder builder(block);
    89108
    90109    for (Statement * stmt : block) {
     
    97116            Terminals terminals(vars.begin(), vars.end());
    98117            scan(cast<While>(stmt)->getBody(), std::move(terminals));
    99         } else {
    100             builder.record(stmt);
    101         }
    102 
     118        }
    103119    }
    104120
     
    106122    // safely rearrange expressions such as "((((a √ b) √ c) √ d) √ e) √ f" into "((a √ b) √ (c √ d)) √ (e √ f)".
    107123
    108     bool modifiedAST = false;
     124    VertexQueue Q(128);
    109125
    110126    for (;;) {
     
    114130
    115131        // Generate a graph depicting the relationships between the terminals. If the original terminals
    116         // cannot be optimized with this algorithm bypass them in favour of their operands.
    117 
    118         VertexQueue Q;
    119         unsigned count = 0;
     132        // cannot be optimized with this algorithm bypass them in favour of their operands. If those cannot
     133        // be optimized, they'll be left as the initial terminals for the next "layer" of the AST.
     134
    120135        for (Statement * const term : terminals) {
    121136            assert (term);
    122             assert (Q.size() == count);
    123137            if (isaBooleanOperation(term)) {
    124138                if (LLVM_LIKELY(M.count(term) == 0)) {                   
    125                     const auto v = add_vertex(term, G);
     139                    const Vertex v = add_vertex(term, G);
    126140                    assert (v < num_vertices(G));
    127141                    M.insert(std::make_pair(term, v));
    128                     Q.push(v);
    129                     ++count;
     142                    push(v, Q);
    130143                }
    131144            } else {
     
    134147                    assert (op);
    135148                    if (LLVM_LIKELY(isa<Statement>(op) && M.count(op) == 0)) {
    136                         const auto v = add_vertex(op, G);
     149                        const Vertex v = add_vertex(op, G);
    137150                        assert (v < num_vertices(G));
    138151                        M.insert(std::make_pair(op, v));
    139                         Q.push(v);
    140                         ++count;
     152                        push(v, Q);
    141153                    }
    142154                }
     
    144156        }
    145157
     158        if (Q.empty()) {
     159            break;
     160        }
     161
    146162        for (;;) {
    147             assert (Q.size() == count);
    148             const Vertex u = Q.front(); Q.pop();
    149             --count;
     163            const Vertex u = pop(Q);
    150164            assert (u < num_vertices(G));
    151165            if (isaBooleanOperation(G[u])) {
     
    156170                    auto f = M.find(op);
    157171                    if (f == M.end()) {
    158                         const auto v = add_vertex(op, G);
     172                        const Vertex v = add_vertex(op, G);
    159173                        assert (v < num_vertices(G));
    160174                        f = M.insert(std::make_pair(op, v)).first;
    161175                        if (op->getClassTypeId() == stmt->getClassTypeId() && cast<Statement>(op)->getParent() == &block) {
    162                             Q.push(v);
    163                             ++count;
     176                            push(v, Q);
    164177                        }
    165178                    }
     
    199212            // Cut the graph wherever a computation crosses a component or whenever we need to cut the graph because
    200213            // the instructions corresponding to the pair of nodes differs.
    201             EdgeQueue Q;
     214            EdgeQueue E;
    202215            graph_traits<Graph>::edge_iterator ei, ei_end;
    203216            for (std::tie(ei, ei_end) = edges(G); ei != ei_end; ) {
     
    206219                const Vertex v = target(e, G);
    207220                if (LLVM_UNLIKELY(isCutNecessary(u, v, G, component))) {
    208                     Q.push(std::make_pair(u, v));
     221                    E.push(std::make_pair(u, v));
    209222                    remove_edge(u, v, G);
    210223                }
     
    212225
    213226            // If no cuts are necessary, we're done.
    214             if (Q.empty()) {
     227            if (E.empty()) {
    215228                break;
    216229            }
     
    219232
    220233                Vertex u, v;
    221                 std::tie(u, v) = Q.front(); Q.pop();
     234                std::tie(u, v) = E.front(); E.pop();
    222235
    223236                // The vertex belonging to a component with a greater number must come "earlier"
     
    242255                if (in_degree(u, G) != 0) {
    243256                    for (auto e : make_iterator_range(out_edges(u, G))) {
    244                         Q.push(std::make_pair(source(e, G), target(e, G)));
     257                        E.push(std::make_pair(source(e, G), target(e, G)));
    245258                    }
    246259                    clear_out_edges(u, G);
    247260                }
    248261
    249                 if (Q.empty()) {
     262                if (E.empty()) {
    250263                    break;
    251264                }
     
    263276                flat_map<Vertex, unsigned> L;
    264277                flat_set<PabloAST *> V;
    265                 VertexQueue Q;
    266278
    267279                Vertex v = u;
     
    282294                                f->second = std::max(f->second, l);
    283295                            }
    284                             Q.push(w);
     296                            push(w, Q);
    285297                        }
    286298                    }
     
    288300                        break;
    289301                    }
    290                     v = Q.front();
    291                     Q.pop();
     302                    v = pop(Q);
    292303                }
    293304
     
    307318                            PabloAST * e1 = Q.front(); Q.pop_front();
    308319                            PabloAST * e2 = Q.front(); Q.pop_front();
    309                             Q.push_back(builder.createAnd(e1, e2));
     320                            Q.push_back(block.createAnd(e1, e2));
    310321                        }
    311322                    } else if (isa<Or>(stmt)) {
     
    313324                            PabloAST * e1 = Q.front(); Q.pop_front();
    314325                            PabloAST * e2 = Q.front(); Q.pop_front();
    315                             Q.push_back(builder.createOr(e1, e2));
     326                            Q.push_back(block.createOr(e1, e2));
    316327                        }
    317328                    } else { assert(isa<Xor>(stmt));
     
    319330                            PabloAST * e1 = Q.front(); Q.pop_front();
    320331                            PabloAST * e2 = Q.front(); Q.pop_front();
    321                             Q.push_back(builder.createXor(e1, e2));
    322                         }
    323                     }
    324                     stmt->replaceWith(Q.front(), true, false);
    325                     modifiedAST = true;
     332                            Q.push_back(block.createXor(e1, e2));
     333                        }
     334                    }
     335                    stmt->replaceWith(Q.front(), true, true);
    326336                }
    327337            }
     
    350360        terminals.assign(nextSet.begin(), nextSet.end());
    351361    }
    352 
    353     // If we modified the AST, we likely left dead code in it. Go through and remove any from this block.
    354     if (modifiedAST) {
    355         Statement * stmt = block.front();
    356         while (stmt) {
    357             if (stmt->getNumUses() == 0 && !(isa<If>(stmt) || isa<While>(stmt))){
    358                 stmt = stmt->eraseFromParent(true);
    359             } else {
    360                 stmt = stmt->getNextNode();
    361             }
    362         }
    363     }
    364362}
    365363
Note: See TracChangeset for help on using the changeset viewer.