Changeset 4763


Ignore:
Timestamp:
Sep 7, 2015, 3:31:05 PM (3 years ago)
Author:
nmedfort
Message:

Temporary check in

Location:
icGREP/icgrep-devel/icgrep/pablo/optimizers
Files:
3 edited

Legend:

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

    r4762 r4763  
    3131bool BooleanReassociationPass::optimize(PabloFunction & function) {
    3232    BooleanReassociationPass brp;
     33
    3334    brp.resolveScopes(function);
    3435    brp.processScopes(function);
    35 
    36     raw_os_ostream out(std::cerr);
    37     PabloPrinter::print(function.getEntryBlock().statements(), out);
    38 
    3936    Simplifier::optimize(function);
     37
    4038    return true;
    4139}
     
    4543 ** ------------------------------------------------------------------------------------------------------------- */
    4644inline void BooleanReassociationPass::resolveScopes(PabloFunction &function) {
     45    mResolvedScopes.emplace(&function.getEntryBlock(), nullptr);
    4746    resolveScopes(function.getEntryBlock());
    4847}
     
    217216    out << "digraph " << name << " {\n";
    218217    for (auto u : make_iterator_range(vertices(G))) {
    219         if (in_degree(u, G) == 0 && out_degree(u, G) == 0) {
    220             continue;
    221         }
     218//        if (in_degree(u, G) == 0 && out_degree(u, G) == 0) {
     219//            continue;
     220//        }
    222221        out << "v" << u << " [label=\"";
    223222        PabloAST * expr = G[u];
     
    338337inline void BooleanReassociationPass::processScope(PabloBlock & block, std::vector<Statement *> && terminals) {
    339338    Graph G;
     339
    340340    summarizeAST(block, G);
    341     redistributeAST(block, G);
    342     printGraph(block, G, "G");
    343 
    344 
    345 
     341//    redistributeAST(block, G);
     342
     343
     344    raw_os_ostream out(std::cerr);
     345
     346    out << "BEFORE:\n";
     347    PabloPrinter::print(block.statements(), out);
     348    out << "----------------------------------------------------------\n";
     349    out.flush();
    346350
    347351
    348352    circular_buffer<Vertex> Q(num_vertices(G));
    349353    topological_sort(G, std::front_inserter(Q));
     354    assert (Q.size() == num_vertices(G));
    350355
    351356    circular_buffer<PabloAST *> nodes;
    352     block.setInsertPoint(nullptr);
     357    block.setInsertPoint(block.back());
    353358
    354359    while (!Q.empty()) {
    355         const Vertex u = Q.front();
    356         Q.pop_front();
    357         if (LLVM_LIKELY(in_degree(u, G) != 0 || out_degree(u, G) != 0)) {
    358             PabloAST * expr = G[u];
    359             if (LLVM_LIKELY(inCurrentBlock(expr, block))) {
    360                 switch (expr->getClassTypeId()) {
    361                     case TypeId::And:
    362                     case TypeId::Or:
    363                 case TypeId::Xor: {
    364                             nodes.set_capacity(in_degree(u, G));
    365                             for (auto e : make_iterator_range(in_edges(u, G))) {
    366                                 nodes.push_back(G[source(e, G)]);
    367                             }
    368                             PabloAST * replacement = createTree(block, expr->getClassTypeId(), nodes);
    369                             cast<Statement>(expr)->replaceWith(replacement, true, true);
    370                             expr = replacement;
    371                         }
    372                     default:
    373                         block.insert(cast<Statement>(expr));
    374                 }
    375             }
    376         }
    377     }
    378 
    379 
     360        const Vertex u = Q.front(); Q.pop_front();
     361        PabloAST * expr = G[u];
     362        if (LLVM_LIKELY(inCurrentBlock(expr, block))) {
     363            if (isOptimizable(expr)) {
     364                if (in_degree(u, G) == 0) {
     365                    PabloPrinter::print(cast<Statement>(expr), " erasing ", out); out << '\n';
     366                    cast<Statement>(expr)->eraseFromParent(true);
     367                    continue;
     368                } else {
     369                    if (LLVM_UNLIKELY(nodes.capacity() < in_degree(u, G))) {
     370                        nodes.set_capacity(in_degree(u, G));
     371                    }
     372                    for (auto e : make_iterator_range(in_edges(u, G))) {
     373                        nodes.push_back(G[source(e, G)]);
     374                    }
     375                    assert (nodes.size() == in_degree(u, G));
     376                    PabloAST * replacement = createTree(block, expr->getClassTypeId(), nodes);
     377
     378                    PabloPrinter::print(cast<Statement>(expr), " replacing ", out);
     379                    PabloPrinter::print(cast<Statement>(replacement), " with ", out);
     380                    out << '\n';
     381
     382                    cast<Statement>(expr)->replaceWith(replacement, true, true);
     383                    expr = replacement;
     384                }
     385            }
     386
     387            PabloPrinter::print(cast<Statement>(expr), "    -> ", out);
     388            out << '\n';
     389
     390            block.insert(cast<Statement>(expr));
     391        }
     392    }
     393
     394    out << "----------------------------------------------------------\n";
     395    out << "AFTER:\n";
     396    PabloPrinter::print(block.statements(), out);
     397    out.flush();
     398    out << "==========================================================\n";
    380399}
    381400
     
    403422        if (isa<If>(stmt)) {
    404423            for (Assign * def : cast<const If>(stmt)->getDefined()) {
    405                 add_edge(u, getVertex(def, G, M), G);
     424                const Vertex v = getVertex(def, G, M);
     425                add_edge(u, v, G);
     426                annotateUseDefs(v, def, block, G, M);
    406427            }
    407428        } else if (isa<While>(stmt)) {
    408429            for (Next * var : cast<const While>(stmt)->getVariants()) {
    409                 add_edge(u, getVertex(var, G, M), G);
    410             }
    411         } else if (isOptimizable(stmt)) {
    412             for (PabloAST * user : stmt->users()) {
    413                 if (LLVM_LIKELY(isa<Statement>(user))) {
    414                     PabloBlock * parent = cast<Statement>(user)->getParent();
    415                     if (LLVM_UNLIKELY(parent != &block)) {
    416                         while (parent->getParent() != &block) {
    417                             parent = parent->getParent();
    418                         }
    419                         if (LLVM_UNLIKELY(parent == nullptr)) {
    420                             throw std::runtime_error("Could not locate nested scope block!");
    421                         }
    422                         const auto f = mResolvedScopes.find(parent);
    423                         if (LLVM_UNLIKELY(f == mResolvedScopes.end())) {
    424                             throw std::runtime_error("Failed to resolve scope block!");
    425                         }
    426                         add_edge(u, getVertex(f->second, G, M), G);
    427                     }
    428                 }
    429             }
     430                const Vertex v = getVertex(var, G, M);
     431                add_edge(u, v, G);
     432                annotateUseDefs(v, var, block, G, M);
     433            }
     434        } else {
     435            annotateUseDefs(u, stmt, block, G, M);
    430436        }
    431437    }
     
    454460    }
    455461
    456 }
    457 
    458 
    459 ///** ------------------------------------------------------------------------------------------------------------- *
    460 // * @brief summarizeAST
    461 // *
    462 // * This function scans through a basic block (starting by its terminals) and computes a DAG in which any sequences
    463 // * of AND, OR or XOR functions are "flattened" (i.e., allowed to have any number of inputs.) This allows us to
    464 // * reassociate them in the most efficient way possible.
    465 // ** ------------------------------------------------------------------------------------------------------------- */
    466 //void BooleanReassociationPass::summarizeAST(PabloBlock & block, std::vector<Statement *> terminals, Graph & G) const {
    467 
    468 //    VertexQueue Q(128);
    469 //    EdgeQueue E;
    470 //    Map M;
    471 
    472 
    473 
    474 //    raw_os_ostream out(std::cerr);
    475 
    476 //    out << "================================================================\n";
    477 
    478 //    for (;;) {
    479 
    480 
    481 //        Graph Gk;
    482 //        Map Mk;
    483 
    484 //        // Generate a graph depicting the relationships between the terminals. If the original terminals
    485 //        // cannot be optimized with this algorithm bypass them in favour of their operands. If those cannot
    486 //        // be optimized, they'll be left as the initial terminals for the next "layer" of the AST.
    487 
    488 //        for (Statement * term : terminals) {
    489 //            if (LLVM_LIKELY(Mk.count(term) == 0)) {
    490 //                // add or find this terminal in our global graph
    491 //                Vertex x = getVertex(term, G, M);
    492 
    493 //                PabloPrinter::print(term, "term: ", out);
    494 //                out << '\n';
    495 
    496 
    497 //                if (inCurrentBlock(term, block)) {
    498 //                    if (isOptimizable(term)) {
    499 //                        const Vertex u = add_vertex(term, Gk);
    500 //                        Mk.insert(std::make_pair(term, u));
    501 //                        push(u, Q);
    502 //                        continue;
    503 //                    }
    504 //                } else if (isa<Assign>(term) || isa<Next>(term)) {
    505 //                    // If this is an Assign (Next) node whose operand does not originate from the current block
    506 //                    // then check to see if there is an If (While) node that does.
    507 //                    Statement * branch = nullptr;
    508 //                    if (isa<Assign>(term)) {
    509 //                        for (PabloAST * user : term->users()) {
    510 //                            if (isa<If>(user)) {
    511 //                                const If * ifNode = cast<If>(user);
    512 //                                if (inCurrentBlock(ifNode, block)) {
    513 //                                    const auto & defs = ifNode->getDefined();
    514 //                                    if (LLVM_LIKELY(std::find(defs.begin(), defs.end(), cast<Assign>(term)) != defs.end())) {
    515 //                                        branch = cast<Statement>(user);
    516 //                                        break;
    517 //                                    }
    518 //                                }
    519 //                            }
    520 //                        }
    521 //                    } else { // if (isa<Next>(term))
    522 //                        for (PabloAST * user : term->users()) {
    523 //                            if (isa<While>(user)) {
    524 //                                const While * whileNode = cast<While>(user);
    525 //                                if (inCurrentBlock(whileNode, block)) {
    526 //                                    const auto & vars = whileNode->getVariants();
    527 //                                    if (LLVM_LIKELY(std::find(vars.begin(), vars.end(), cast<Next>(term)) != vars.end())) {
    528 //                                        branch = cast<Statement>(user);
    529 //                                        break;
    530 //                                    }
    531 //                                }
    532 //                            }
    533 //                        }
    534 //                    }
    535 
    536 //                    // If we didn't find a branch, then the Assign (Next) node must have come from a preceeding
    537 //                    // block. Just skip it for now.
    538 //                    if (branch == nullptr) {
    539 //                        continue;
    540 //                    }
    541 
    542 //                    // Otherwise add the branch to G and test its operands rather than the original terminal
    543 //                    const Vertex z = getVertex(branch, G, M);
    544 //                    add_edge(z, x, G);
    545 //                    x = z;
    546 //                    term = branch;
    547 
    548 //                }
    549 
    550 //                for (unsigned i = 0; i != term->getNumOperands(); ++i) {
    551 //                    PabloAST * const op = term->getOperand(i);
    552 //                    if (LLVM_LIKELY(inCurrentBlock(op, block))) {
    553 //                        const Vertex y = getVertex(op, G, M);
    554 //                        add_edge(y, x, G);
    555 
    556 //                        if (LLVM_LIKELY(Mk.count(op) == 0)) {
    557 //                            const Vertex v = add_vertex(op, Gk);
    558 //                            Mk.insert(std::make_pair(op, v));
    559 //                            push(v, Q);
    560 //                        }
    561 //                    }
    562 //                }
    563 //            }
    564 //        }
    565 
    566 //        out << "----------------------------------------------------------------\n";
    567 //        out.flush();
    568 
    569 //        if (LLVM_UNLIKELY(Q.empty())) {
    570 //            break;
    571 //        }
    572 
    573 //        for (;;) {
    574 //            const Vertex u = pop(Q);
    575 //            if (isOptimizable(Gk[u])) {
    576 //                Statement * stmt = cast<Statement>(Gk[u]);
    577 //                // If any user of this statement is not in the current block, determine the outermost If/While node
    578 //                // that contains this statement within and add an edge from this statement to it to denote both the
    579 //                // topological ordering necessary and that this statement must be computed.
    580 //                for (PabloAST * user : stmt->users()) {
    581 //                    if (LLVM_LIKELY(isa<Statement>(user))) {
    582 //                        PabloBlock * parent = cast<Statement>(user)->getParent();
    583 //                        if (LLVM_UNLIKELY(parent != &block)) {
    584 //                            while (parent->getParent() != &block) {
    585 //                                parent = parent->getParent();
    586 //                            }
    587 //                            if (LLVM_UNLIKELY(parent == nullptr)) {
    588 //                                throw std::runtime_error("Could not locate nested scope block!");
    589 //                            }
    590 //                            const auto f = mResolvedScopes.find(parent);
    591 //                            if (LLVM_UNLIKELY(f == mResolvedScopes.end())) {
    592 //                                throw std::runtime_error("Failed to resolve scope block!");
    593 //                            }
    594 //                            add_edge(u, getVertex(f->second, Gk, Mk), Gk);
    595 //                        }
    596 //                    }
    597 //                }
    598 //                // Scan through the use-def chains to locate any chains of rearrangable expressions and their inputs
    599 //                for (unsigned i = 0; i != 2; ++i) {
    600 //                    PabloAST * op = stmt->getOperand(i);
    601 //                    auto f = Mk.find(op);
    602 //                    if (f == Mk.end()) {
    603 //                        const Vertex v = add_vertex(op, Gk);
    604 //                        f = Mk.insert(std::make_pair(op, v)).first;
    605 //                        if (op->getClassTypeId() == stmt->getClassTypeId() && inCurrentBlock(cast<Statement>(op), block)) {
    606 //                            push(v, Q);
    607 //                        }
    608 //                    }
    609 //                    add_edge(f->second, u, Gk);
    610 //                }
    611 //            }
    612 //            if (Q.empty()) {
    613 //                break;
    614 //            }
    615 //        }
    616 
    617 //        printGraph(block, Gk, "Gk1");
    618 
    619 //        // Generate a topological ordering for G; if one of our terminals happens to also be a partial computation of
    620 //        // another terminal, we need to make sure we compute it as an independent subexpression.
    621 //        std::vector<unsigned> ordering;
    622 //        ordering.reserve(num_vertices(Gk));
    623 //        topological_sort(Gk, std::back_inserter(ordering));
    624 //        std::vector<unsigned> component(num_vertices(Gk), 0);
    625 
    626 //        // Mark which computation component each terminal is in based on their topological (occurence) order.
    627 //        unsigned components = 0;
    628 //        std::sort(terminals.begin(), terminals.end());
    629 //        for (auto u : ordering) {
    630 //            unsigned id = 0;
    631 //            // If this is a sink in G, it is the root of a new component.
    632 //            if (out_degree(u, Gk) == 0 || std::binary_search(terminals.begin(), terminals.end(), Gk[u])) {
    633 //                id = ++components;
    634 //            } else { // otherwise it belongs to the outermost component.
    635 //                for (auto e : make_iterator_range(out_edges(u, Gk))) {
    636 //                    assert (component[target(e, Gk)] != 0);
    637 //                    id = std::max(id, component[target(e, Gk)]);
    638 //                }
    639 //            }
    640 //            assert (id && "Topological ordering failed!");
    641 //            component[u] = id;
    642 //        }
    643 
    644 //        for (;;) {
    645 
    646 //            // Cut the graph wherever a computation crosses a component or whenever we need to cut the graph because
    647 //            // the instructions corresponding to the pair of nodes differs.
    648 //            graph_traits<Graph>::edge_iterator ei, ei_end;
    649 //            for (std::tie(ei, ei_end) = edges(Gk); ei != ei_end; ) {
    650 //                const Graph::edge_descriptor e = *ei++;
    651 //                const Vertex u = source(e, Gk);
    652 //                const Vertex v = target(e, Gk);
    653 //                if (LLVM_UNLIKELY(isCutNecessary(u, v, Gk, component))) {
    654 //                    E.push(std::make_pair(u, v));
    655 //                    remove_edge(u, v, Gk);
    656 //                }
    657 //            }
    658 
    659 //            // If no cuts are necessary, we're done.
    660 //            if (E.empty()) {
    661 //                break;
    662 //            }
    663 
    664 //            for (;;) {
    665 
    666 //                Vertex u, v;
    667 //                std::tie(u, v) = E.front(); E.pop();
    668 
    669 //                // The vertex belonging to a component with a greater number must come "earlier"
    670 //                // in the program. By replicating it, this ensures it's computed as an output of
    671 //                // one component and used as an input of another.
    672 //                if (component[u] < component[v]) {
    673 //                    std::swap(u, v);
    674 //                }
    675 
    676 //                // Replicate u and fix the ordering and component vectors to reflect the change in Gk.
    677 //                const Vertex w = add_vertex(Gk[u], Gk);
    678 //                ordering.insert(std::find(ordering.begin(), ordering.end(), u), w);
    679 //                assert (component.size() == w);
    680 //                component.push_back(component[v]);
    681 //                add_edge(w, v, Gk);
    682 
    683 //                // However, after we do so, we need to make sure the original source vertex will be a
    684 //                // sink in Gk unless it is also an input variable (in which case we'd simply end up with
    685 //                // extraneous isolated vertex. Otherwise, we need to make further cuts and replications.
    686 //                if (in_degree(u, Gk) != 0) {
    687 //                    for (auto e : make_iterator_range(out_edges(u, Gk))) {
    688 //                        E.push(std::make_pair(source(e, Gk), target(e, Gk)));
    689 //                    }
    690 //                    clear_out_edges(u, Gk);
    691 //                }
    692 
    693 //                if (E.empty()) {
    694 //                    break;
    695 //                }
    696 //            }
    697 
    698 //            // Mark which computation component each sink is in based on their topological (occurence) order.
    699 //            unsigned components = 0;
    700 //            #ifndef NDEBUG
    701 //            std::fill(component.begin(), component.end(), 0);
    702 //            #endif
    703 //            for (auto u : ordering) {
    704 //                unsigned id = 0;
    705 //                // If this is a sink in G, it is the root of a new component.
    706 //                if (out_degree(u, Gk) == 0) {
    707 //                    id = ++components;
    708 //                } else { // otherwise it belongs to the outermost component.
    709 //                    for (auto e : make_iterator_range(out_edges(u, Gk))) {
    710 //                        assert (component[target(e, Gk)] != 0);
    711 //                        id = std::max(id, component[target(e, Gk)]);
    712 //                    }
    713 //                }
    714 //                assert (id && "Topological ordering failed!");
    715 //                component[u] = id;
    716 //            }
    717 //        }
    718 
    719 //        printGraph(block, Gk, "Gk2");
    720 
    721 //        // Scan through the graph so that we process the outermost expressions first
    722 //        for (const Vertex u : ordering) {
    723 //            if (LLVM_UNLIKELY(out_degree(u, Gk) == 0)) {
    724 //                // Create a vertex marking the output statement we may end up replacing
    725 //                // and collect the set of source variables in the component
    726 //                const Vertex x = getVertex(Gk[u], G, M);
    727 //                if (LLVM_LIKELY(in_degree(u, Gk) > 0)) {
    728 //                    flat_set<PabloAST *> vars;
    729 //                    flat_set<Vertex> visited;
    730 //                    for (Vertex v = u;;) {
    731 //                        if (in_degree(v, Gk) == 0) {
    732 //                            vars.insert(Gk[v]);
    733 //                        } else {
    734 //                            for (auto e : make_iterator_range(in_edges(v, Gk))) {
    735 //                                const Vertex w = source(e, Gk);
    736 //                                if (LLVM_LIKELY(visited.insert(w).second)) {
    737 //                                    push(w, Q);
    738 //                                }
    739 //                            }
    740 //                        }
    741 //                        if (Q.empty()) {
    742 //                            break;
    743 //                        }
    744 //                        v = pop(Q);
    745 //                    }
    746 //                    for (PabloAST * var : vars) {
    747 //                        add_edge(getVertex(var, G, M), x, G);
    748 //                    }
    749 //                }
    750 //            }
    751 //        }
    752 
    753 //        // Determine the source variables of the next "layer" of the AST
    754 //        flat_set<Statement *> nextSet;
    755 //        for (auto u : ordering) {
    756 //            if (LLVM_UNLIKELY(in_degree(u, Gk) == 0 && isa<Statement>(Gk[u]))) {
    757 //                nextSet.insert(cast<Statement>(Gk[u]));
    758 //            } else if (LLVM_UNLIKELY(out_degree(u, Gk) == 0 && isa<Statement>(Gk[u]))) {
    759 //                // some input will also be the output of some subgraph of Gk whenever we cut and
    760 //                // replicated a vertex. We don't need to reevaluate it as part of the next layer.
    761 //                nextSet.erase(cast<Statement>(Gk[u]));
    762 //            }
    763 //        }
    764 
    765 //        if (LLVM_UNLIKELY(nextSet.empty())) {
    766 //            break;
    767 //        }
    768 
    769 //        out << "----------------------------------------------------------------\n";
    770 
    771 //        terminals.assign(nextSet.begin(), nextSet.end());
    772 //    }
    773 
    774 
    775 
    776 //}
     462    printGraph(block, G, "G");
     463
     464}
     465
     466/** ------------------------------------------------------------------------------------------------------------- *
     467 * @brief annotateUseDefs
     468 ** ------------------------------------------------------------------------------------------------------------- */
     469void BooleanReassociationPass::annotateUseDefs(const Vertex u, PabloAST * expr, PabloBlock & block, Graph & G, Map & M) const {
     470    for (PabloAST * user : expr->users()) {
     471        assert (user);
     472        if (LLVM_UNLIKELY(user == expr)) {
     473            continue;
     474        }
     475        if (LLVM_LIKELY(isa<Statement>(user))) {
     476            PabloBlock * parent = cast<Statement>(user)->getParent();
     477            assert (parent);
     478            if (LLVM_UNLIKELY(parent != &block)) {
     479                #ifndef NDEBUG
     480                bool found = false;
     481                for (Statement * test : *parent) {
     482                    if (test == user) {
     483                        found = true;
     484                        break;
     485                    }
     486                }
     487                assert ("Could not locate user in its recorded scope block!" && found);
     488                #endif
     489                for (;;) {
     490                    if (LLVM_UNLIKELY(parent == nullptr)) {
     491                        assert (isa<Assign>(expr) || isa<Next>(expr));
     492                        break;
     493                    } else if (parent->getParent() == &block) {
     494                        const auto f = mResolvedScopes.find(parent);
     495                        if (LLVM_UNLIKELY(f == mResolvedScopes.end())) {
     496                            throw std::runtime_error("Failed to resolve scope block!");
     497                        }
     498                        add_edge(u, getVertex(f->second, G, M), G);
     499                        break;
     500                    }
     501                    parent = parent->getParent();
     502                }
     503            }
     504        }
     505    }
     506}
    777507
    778508using VertexSet = std::vector<Vertex>;
  • icGREP/icgrep-devel/icgrep/pablo/optimizers/booleanreassociationpass.h

    r4762 r4763  
    2323    void processScope(PabloBlock & block, std::vector<Statement *> && terminals);
    2424    void summarizeAST(PabloBlock & block, Graph & G) const;
     25    void annotateUseDefs(const Vertex u, PabloAST * expr, PabloBlock & block, Graph & G, Map & M) const;
    2526    bool redistributeAST(PabloBlock & block, Graph & G) const;
    2627private:
  • icGREP/icgrep-devel/icgrep/pablo/optimizers/pablo_simplifier.cpp

    r4752 r4763  
    44#include <pablo/function.h>
    55#include <pablo/printer_pablos.h>
    6 
     6#include <iostream>
    77
    88
     
    9797                continue;
    9898            }
    99             // Process the If body
    100             eliminateRedundantCode(cast<If>(stmt)->getBody(), &encountered);           
    101             // If the defined variable is actually equivalent to the condition, promote the assignment out of If
    102             // scope and remove it from the list of defined variables. Otherwise, replace any defined variable that
    103             // is assigned Zero with a Zero object and remove it from the defined variable list.
     99
     100            bool evaluate = true;
    104101            If::DefinedVars & defs = ifNode->getDefined();
    105             for (auto itr = defs.begin(); itr != defs.end(); ) {
    106                 Assign * def = *itr;
    107                 if (LLVM_UNLIKELY((ifNode->getCondition() == def->getExpression()) || isa<Zeroes>(def->getExpression()))) {
    108                     itr = defs.erase(itr);
    109                     def->replaceWith(def->getExpression(), false, true);
    110                     continue;
    111                 }
    112                 ++itr;
    113             }
     102            while (evaluate) {
     103                evaluate = false;
     104                // Process the If body
     105                eliminateRedundantCode(cast<If>(stmt)->getBody(), &encountered);
     106                // Now test whether all of the defined variables are necessary
     107                for (auto itr = defs.begin(); itr != defs.end(); ) {
     108                    Assign * def = *itr;
     109                    // If this value isn't used outside of this scope then there is no reason to allow it to escape it.
     110                    bool unusedOutsideOfNestedScope = true;
     111                    for (PabloAST * user : def->users()) {
     112                        if (user != ifNode) {
     113                            PabloBlock * parent = cast<Statement>(user)->getParent();
     114                            while (parent && parent != def->getParent()) {
     115                                parent = parent->getParent();
     116                            }
     117                            if (parent == nullptr) {
     118                                unusedOutsideOfNestedScope = false;
     119                                break;
     120                            }
     121                        }
     122                    }
     123                    // If the defined variable is actually equivalent to the condition, promote the assignment out of If
     124                    // scope and remove it from the list of defined variables. Additionally, replace any defined variable
     125                    // assigned Zero or One with the appropriate constant and remove it from the defined variable list.
     126                    if (LLVM_UNLIKELY(unusedOutsideOfNestedScope || (ifNode->getCondition() == def->getExpression()) || isa<Zeroes>(def->getExpression()) || isa<Ones>(def->getExpression()))) {
     127                        itr = defs.erase(itr);
     128                        def->replaceWith(def->getExpression(), unusedOutsideOfNestedScope, true);
     129                        evaluate = true;
     130                        continue;
     131                    }
     132                    ++itr;
     133                }
     134            }
     135
    114136            // If we ended up removing all of the defined variables, delete the If node.
    115137            if (LLVM_UNLIKELY(defs.empty())) {
Note: See TracChangeset for help on using the changeset viewer.