Changeset 4752 for icGREP/icgrep-devel


Ignore:
Timestamp:
Aug 30, 2015, 4:34:44 PM (4 years ago)
Author:
nmedfort
Message:

More work on the reassociation pass + few additional Simplification tests

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

Legend:

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

    r4751 r4752  
    114114static inline bool inCurrentBlock(const PabloAST * expr, const PabloBlock & block) {
    115115    return isa<Statement>(expr) && inCurrentBlock(cast<Statement>(expr), block);
     116}
     117
     118/** ------------------------------------------------------------------------------------------------------------- *
     119 * @brief isAnyUserNotInCurrentBlock
     120 ** ------------------------------------------------------------------------------------------------------------- */
     121static inline bool isAnyUserNotInCurrentBlock(const PabloAST * expr, const PabloBlock & block) {
     122    for (PabloAST * user : expr->users()) {
     123        if (!inCurrentBlock(cast<Statement>(user), block)) {
     124            return true;
     125        }
     126    }
     127    return false;
    116128}
    117129
     
    289301    for (auto u : make_iterator_range(vertices(G))) {
    290302        out << "v" << u << " [label=\"";
    291         if (in_degree(u, G) > 0) {
    292             PabloPrinter::print(cast<Statement>(G[u]), "", out);
     303        PabloAST * expr = G[u];
     304        if (isa<Statement>(expr)) {
     305            if (LLVM_UNLIKELY(isa<If>(expr))) {
     306                out << "if ";
     307                PabloPrinter::print(cast<If>(expr)->getOperand(0), out);
     308                out << ":";
     309            } else if (LLVM_UNLIKELY(isa<While>(expr))) {
     310                out << "while ";
     311                PabloPrinter::print(cast<While>(expr)->getOperand(0), out);
     312                out << ":";
     313            } else {
     314                PabloPrinter::print(cast<Statement>(expr), "", out);
     315            }
    293316        } else {
    294             PabloPrinter::print(G[u], out);
    295         }
    296         out << "\"];\n";
     317            PabloPrinter::print(expr, out);
     318        }
     319        out << "\"";
     320        if (!inCurrentBlock(expr, block)) {
     321            out << " style=dashed";
     322        }
     323        out << "];\n";
    297324    }
    298325    for (auto e : make_iterator_range(edges(G))) {
    299326        out << "v" << source(e, G) << " -> v" << target(e, G) << ";\n";
    300327    }
     328
     329    out << "{ rank=same;";
     330    for (auto u : make_iterator_range(vertices(G))) {
     331        if (in_degree(u, G) == 0 && out_degree(u, G) != 0) {
     332            out << " v" << u;
     333        }
     334    }
     335    out << "}\n";
     336
     337    out << "{ rank=same;";
     338    for (auto u : make_iterator_range(vertices(G))) {
     339        if (out_degree(u, G) == 0 && in_degree(u, G) != 0) {
     340            out << " v" << u;
     341        }
     342    }
     343    out << "}\n";
     344
    301345    out << "}\n\n";
    302346    out.flush();
     
    334378                // add or find this terminal in our global graph
    335379                Vertex x = getVertex(term, G, M);
    336 
    337                 if (isOptimizable(term)) {
    338                     const Vertex u = add_vertex(term, Gk);
    339                     Mk.insert(std::make_pair(term, u));
    340                     push(u, Q);
    341                     continue;
    342                 } else if ((isa<Assign>(term) || isa<Next>(term)) && !inCurrentBlock(term->getOperand(0), block)) {
     380                if (inCurrentBlock(term, block)) {
     381                    if (isOptimizable(term)) {
     382                        const Vertex u = add_vertex(term, Gk);
     383                        Mk.insert(std::make_pair(term, u));
     384                        push(u, Q);
     385                        continue;
     386                    }
     387                } else if (isa<Assign>(term) || isa<Next>(term)) {
    343388                    // If this is an Assign (Next) node whose operand does not originate from the current block
    344389                    // then check to see if there is an If (While) node that does.
     
    348393                            if (isa<If>(user)) {
    349394                                const If * ifNode = cast<If>(user);
    350                                 const auto & defs = ifNode->getDefined();
    351                                 if (LLVM_LIKELY(std::find(defs.begin(), defs.end(), cast<Assign>(term)) != defs.end())) {
    352                                     if (inCurrentBlock(ifNode, block)) {
     395                                if (inCurrentBlock(ifNode, block)) {
     396                                    const auto & defs = ifNode->getDefined();
     397                                    if (LLVM_LIKELY(std::find(defs.begin(), defs.end(), cast<Assign>(term)) != defs.end())) {
    353398                                        branch = cast<Statement>(user);
     399                                        break;
    354400                                    }
    355                                     break;
    356401                                }
    357402                            }
     
    361406                            if (isa<While>(user)) {
    362407                                const While * whileNode = cast<While>(user);
    363                                 const auto & vars = whileNode->getVariants();
    364                                 if (LLVM_LIKELY(std::find(vars.begin(), vars.end(), cast<Next>(term)) != vars.end())) {
    365                                     if (inCurrentBlock(whileNode, block)) {
     408                                if (inCurrentBlock(whileNode, block)) {
     409                                    const auto & vars = whileNode->getVariants();
     410                                    if (LLVM_LIKELY(std::find(vars.begin(), vars.end(), cast<Next>(term)) != vars.end())) {
    366411                                        branch = cast<Statement>(user);
     412                                        break;
    367413                                    }
    368                                     break;
    369414                                }
    370415                            }
     
    380425                    // Otherwise add the branch to G and test its operands rather than the original terminal
    381426                    const Vertex z = getVertex(branch, G, M);
    382                     add_edge(x, z, G);
     427                    add_edge(z, x, G);
    383428                    x = z;
    384429                    term = branch;
     
    387432                for (unsigned i = 0; i != term->getNumOperands(); ++i) {
    388433                    PabloAST * const op = term->getOperand(i);
    389                     const Vertex y = getVertex(op, G, M);
    390                     add_edge(x, y, G);
    391                     if (LLVM_LIKELY(in_degree(y, G) == 0 && Mk.count(op) == 0 && isa<Statement>(op))) {
    392                         const Vertex v = add_vertex(op, Gk);
    393                         Mk.insert(std::make_pair(op, v));
    394                         push(v, Q);
    395                     }
    396                 }
    397 
    398             }
    399         }
    400 
    401         if (Q.empty()) {
     434                    if (LLVM_LIKELY(inCurrentBlock(op, block))) {
     435                        const Vertex y = getVertex(op, G, M);
     436                        add_edge(y, x, G);
     437                        if (LLVM_LIKELY(Mk.count(op) == 0)) {
     438                            const Vertex v = add_vertex(op, Gk);
     439                            Mk.insert(std::make_pair(op, v));
     440                            push(v, Q);
     441                        }
     442                    }
     443                }
     444            }
     445        }
     446
     447        if (LLVM_UNLIKELY(Q.empty())) {
    402448            break;
    403449        }
     
    406452            const Vertex u = pop(Q);
    407453            if (isOptimizable(Gk[u])) {
     454                Statement * stmt = cast<Statement>(Gk[u]);
     455                if (isAnyUserNotInCurrentBlock(stmt, block)) {
     456                    const Vertex v = add_vertex(block.createZeroes(), Gk);
     457                    add_edge(u, v, Gk);
     458                }
    408459                // Scan through the use-def chains to locate any chains of rearrangable expressions and their inputs
    409                 Statement * stmt = cast<Statement>(Gk[u]);
    410460                for (unsigned i = 0; i != 2; ++i) {
    411461                    PabloAST * op = stmt->getOperand(i);
     
    414464                        const Vertex v = add_vertex(op, Gk);
    415465                        f = Mk.insert(std::make_pair(op, v)).first;
    416                         if (op->getClassTypeId() == stmt->getClassTypeId() && cast<Statement>(op)->getParent() == &block) {
     466                        if (op->getClassTypeId() == stmt->getClassTypeId() && inCurrentBlock(cast<Statement>(op), block)) {
    417467                            push(v, Q);
    418468                        }
     
    509559        for (const Vertex u : ordering) {
    510560            if (LLVM_UNLIKELY(out_degree(u, Gk) == 0)) {
     561                if (LLVM_UNLIKELY(isa<Zeroes>(Gk[u]))) {
     562                    continue;
     563                }
    511564                const Vertex x = getVertex(Gk[u], G, M);
    512                 if (LLVM_LIKELY(in_degree(u, Gk) != 0)) {
     565                if (LLVM_LIKELY(in_degree(u, Gk) > 0)) {
    513566                    flat_set<PabloAST *> vars;
    514567                    flat_set<Vertex> visited;
     
    530583                    }
    531584                    for (PabloAST * var : vars) {
    532                         add_edge(x, getVertex(var, G, M), G);
     585                        add_edge(getVertex(var, G, M), x, G);
    533586                    }
    534587                }
     
    539592        flat_set<Statement *> nextSet;
    540593        for (auto u : ordering) {
    541             if (in_degree(u, Gk) == 0) {
    542                 PabloAST * const var = Gk[u];
    543                 if (LLVM_LIKELY(inCurrentBlock(var, block))) {
    544                     nextSet.insert(cast<Statement>(var));
    545                 }
    546             } else if (out_degree(u, Gk) == 0) { // an input may also be the output of a subgraph of G. We don't need to reevaluate it.
    547                 PabloAST * const var = Gk[u];
    548                 if (LLVM_LIKELY(inCurrentBlock(var, block))) {
    549                     nextSet.erase(cast<Statement>(var));
    550                 }
    551             }
    552         }
    553 
    554         if (nextSet.empty()) {
     594            if (LLVM_UNLIKELY(in_degree(u, Gk) == 0 && isa<Statement>(Gk[u]))) {
     595                nextSet.insert(cast<Statement>(Gk[u]));
     596            } else if (LLVM_UNLIKELY(out_degree(u, Gk) == 0 && isa<Statement>(Gk[u]))) { // an input may also be the output of a subgraph of G. We don't need to reevaluate it.
     597                nextSet.erase(cast<Statement>(Gk[u]));
     598            }
     599        }
     600
     601        if (LLVM_UNLIKELY(nextSet.empty())) {
    555602            break;
    556603        }
     
    558605        terminals.assign(nextSet.begin(), nextSet.end());
    559606    }
     607
    560608}
    561609
  • icGREP/icgrep-devel/icgrep/pablo/optimizers/pablo_simplifier.cpp

    r4736 r4752  
    9898            }
    9999            // Process the If body
    100             eliminateRedundantCode(cast<If>(stmt)->getBody(), &encountered);
    101             // Scan through and replace any defined variable that is assigned Zero with a Zero object
    102             // and remove it from the defined variable list.
    103             If::DefinedVars & defVars = ifNode->getDefined();
    104             for (auto i = defVars.begin(); i != defVars.end(); ) {
    105                 Assign * defVar = cast<Assign>(*i);
    106                 if (LLVM_UNLIKELY(isa<Zeroes>(defVar->getExpression()))) {
    107                     i = defVars.erase(i);
    108                     defVar->replaceWith(block.createZeroes(), false, true);
     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.
     104            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);
    109110                    continue;
    110111                }
    111                 ++i;
    112             }
    113             // If we ended up Zero-ing out all of the defined variables, delete the If node.
    114             if (LLVM_UNLIKELY(defVars.empty())) {
     112                ++itr;
     113            }
     114            // If we ended up removing all of the defined variables, delete the If node.
     115            if (LLVM_UNLIKELY(defs.empty())) {
    115116                stmt = stmt->eraseFromParent(true);
    116117                continue;
     118            }
     119            // Otherwise check if we any Assign reports the same value as another. If so, replace all uses of the
     120            // second with the first. This will simplify future analysis.
     121            for (auto i = defs.begin(); i != defs.end(); ++i) {
     122                PabloAST * expr = (*i)->getExpression();
     123                for (auto j = i + 1; j != defs.end(); ) {
     124                    Assign * def = (*j);
     125                    if (LLVM_UNLIKELY(def->getExpression() == expr)) {
     126                        j = defs.erase(j);
     127                        def->replaceWith(*i, false, true);
     128                        continue;
     129                    }
     130                    ++j;
     131                }
    117132            }
    118133        }
Note: See TracChangeset for help on using the changeset viewer.