Ignore:
Timestamp:
Aug 28, 2017, 4:00:17 PM (22 months ago)
Author:
nmedfort
Message:

Bug fixes for multigrep mode. Optional PabloKernel? branch hit counter added. Minor optimizations.

Location:
icGREP/icgrep-devel/icgrep/pablo
Files:
8 edited

Legend:

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

    r5566 r5620  
    99#include <pablo/analysis/pabloverifier.hpp>
    1010#endif
     11
     12#include <llvm/Support/raw_ostream.h>
     13#include <pablo/printer_pablos.h>
    1114
    1215using namespace llvm;
     
    183186        for (Var * variant : loop->getEscaped()) {
    184187            mLoopVariants.insert(variant);
    185         }
     188            mLoopInvariants.insert(variant);
     189        }
     190        mLoopInvariants.erase(loop->getCondition());
     191
    186192        Statement * outerNode = loop->getPrevNode();
    187193        Statement * stmt = loop->getBody()->front();
     
    190196                for (Var * var : cast<Branch>(stmt)->getEscaped()) {
    191197                    mLoopVariants.insert(var);
     198                    mLoopInvariants.erase(var);
    192199                }
    193200                stmt = stmt->getNextNode();
    194201            } else {
    195202                bool invariant = true;
    196                 for (unsigned i = 0; i != stmt->getNumOperands(); ++i) {
    197                     if (mLoopVariants.count(stmt->getOperand(i)) != 0) {
     203                if (LLVM_UNLIKELY(isa<Assign>(stmt))) {
     204                    if (mLoopVariants.count(cast<Assign>(stmt)->getValue()) != 0) {
    198205                        invariant = false;
    199                         break;
    200206                    }
    201                 }
    202                 if (LLVM_UNLIKELY(invariant)) {
    203                     Statement * next = stmt->getNextNode();
     207                } else {
     208                    for (unsigned i = 0; i != stmt->getNumOperands(); ++i) {
     209                        const PabloAST * const op = stmt->getOperand(i);
     210                        if (mLoopVariants.count(op) != 0) {
     211                            if (isa<Var>(op)) {
     212                                mLoopInvariants.erase(op);
     213                            }
     214                            invariant = false;
     215                        }
     216                    }
     217                }
     218
     219                Statement * const next = stmt->getNextNode();
     220                if (LLVM_UNLIKELY(invariant)) {                   
    204221                    stmt->insertAfter(outerNode);
    205                     outerNode = stmt;
    206                     stmt = next;
     222                    outerNode = stmt;                   
    207223                } else {
    208224                    mLoopVariants.insert(stmt);
    209                     stmt = stmt->getNextNode();
    210                 }
     225                }
     226                stmt = next;
    211227            }
    212228        }
    213229        mLoopVariants.clear();
     230        assert (mLoopInvariants.empty());
    214231    }
    215232
     
    249266    UserSet         mUsers;
    250267    LoopVariants    mLoopVariants;
     268    LoopVariants    mLoopInvariants;
    251269};
    252270
  • icGREP/icgrep-devel/icgrep/pablo/optimizers/distributivepass.cpp

    r5608 r5620  
    205205            entry->setInsertPoint(stmt->getPrevNode());
    206206            for (const auto e : make_iterator_range(in_edges(u, G))) {
    207                 stmt->setOperand(G[e], regenerateIfNecessary(stmt, entry, source(e, G), count));
     207                const auto v = source(e, G);
     208                stmt->setOperand(G[e], regenerateIfNecessary(stmt, entry, v, count));
     209                setLastUsageTime(v, ++count);
    208210            }
    209211            setValue(u, stmt);
    210212            setLastUsageTime(u, ++count);
    211 
    212             if (isa<Branch>(stmt)) {
     213            if (LLVM_UNLIKELY(isa<Branch>(stmt))) {
    213214                count = rewriteAST(cast<Branch>(stmt)->getBody(), count);
    214215            }
     
    299300            assert (value);
    300301            setUnmodified(u);
    301             setValue(u, value);
    302             setLastUsageTime(u, ++count);
    303         }
     302            setValue(u, value);           
     303        }       
    304304        return value;
    305305    }
     
    325325
    326326    /** ------------------------------------------------------------------------------------------------------------- *
     327     * @brief printGraph
     328     ** ------------------------------------------------------------------------------------------------------------- */
     329    void printGraph(const std::string & name, llvm::raw_ostream & out, std::vector<Vertex> restricted = {}) {
     330
     331        const auto n = num_vertices(G);
     332        std::vector<unsigned> c(n);
     333        const auto components = strong_components(G, make_iterator_property_map(c.begin(), get(vertex_index, G), c[0]));
     334
     335        std::vector<bool> show(n, false);
     336        if (LLVM_LIKELY(restricted.empty() && n == components)) {
     337            for (const auto u : make_iterator_range(vertices(G))) {
     338                show[u] = isLive(u);
     339            }
     340        } else {
     341            std::queue<Vertex> Q;
     342            for (const auto m : restricted) {
     343                if (m < n && isLive(m)) {
     344                    show[m] = true;
     345                    assert (Q.empty());
     346                    Q.push(m);
     347                    for (;;) {
     348                        const auto u = Q.front();
     349                        Q.pop();
     350                        for (auto e : make_iterator_range(in_edges(u, G))) {
     351                            const auto v = source(e, G);
     352                            if (show[v] || !isLive(v)) {
     353                                continue;
     354                            }
     355                            show[v] = true;
     356                            Q.push(v);
     357                        }
     358                        if (Q.empty()) {
     359                            break;
     360                        }
     361                    }
     362                    for (auto e : make_iterator_range(out_edges(m, G))) {
     363                        const auto v = target(e, G);
     364                        show[v] = isLive(v) ? true : show[v];
     365                    }
     366                }
     367            }
     368        }
     369
     370        out << "digraph " << name << " {\n";
     371        for (auto u : make_iterator_range(vertices(G))) {
     372
     373            if (show[u]) {
     374
     375                out << "v" << u << " [label=\"" << u << ": ";
     376                TypeId typeId;
     377                PabloAST * expr;
     378                State state;
     379
     380                std::tie(expr, typeId, state, std::ignore) = G[u];
     381
     382                bool space = true;
     383
     384                switch (typeId) {
     385                    case TypeId::And:
     386                        out << "(∧)";
     387                        break;
     388                    case TypeId::Or:
     389                        out << "(√)";
     390                        break;
     391                    case TypeId::Xor:
     392                        out << "(⊕)";
     393                        break;
     394                    case TypeId::Not:
     395                        out << "(¬)";
     396                        break;
     397                    case TypeId::Zeroes:
     398                        out << "(⊥)";
     399                        break;
     400                    case TypeId::Ones:
     401                        out << "(⊀)";
     402                    default:
     403                        space = false;
     404                        break;
     405                }
     406                if (expr) {
     407                    if (space) {
     408                        out << ' ';
     409                    }
     410                    expr->print(out);
     411                }
     412
     413                out << "\"";
     414                if (!hasValidOperandIndicies(u, false)) {
     415                    out << " color=red style=bold";
     416                } else if (!(isImmutable(typeId) || out_degree(u, G) > 0)) {
     417                    out << " color=orange style=bold";
     418                } else if (isRegenerable(typeId)) {
     419                    out << " color=blue";
     420                    if (state == State::Modified) {
     421                        out << " style=dashed";
     422                    }
     423                }
     424                out << "];\n";
     425            }
     426        }
     427        for (auto e : make_iterator_range(edges(G))) {
     428            const auto s = source(e, G);
     429            const auto t = target(e, G);
     430            if (show[s] && show[t]) {
     431                const auto cyclic = (c[s] == c[t]);
     432                const auto nonAssoc = !isAssociative(getType(t));
     433                out << "v" << s << " -> v" << t;
     434                if (cyclic || nonAssoc) {
     435                    out << " [";
     436                    if (nonAssoc) {
     437                        out << " label=\"" << G[e] << "\"";
     438                    }
     439                    if (cyclic) {
     440                        out << " color=red";
     441                    }
     442                    out << "]";
     443                }
     444                out << ";\n";
     445            }
     446        }
     447
     448        out << "}\n\n";
     449        out.flush();
     450    }
     451
     452    /** ------------------------------------------------------------------------------------------------------------- *
    327453     * @brief getReverseTopologicalOrdering
    328454     ** ------------------------------------------------------------------------------------------------------------- */
     
    332458            PrePassInserter & operator=(const Vertex u) {
    333459                if (LLVM_LIKELY(self.isLive(u))) {
    334                     assert(self.hasValidOperandIndicies(u));
     460                    assert (self.hasValidOperandIndicies(u));
    335461                    if (LLVM_UNLIKELY(isImmutable(self.getType(u)))) {
    336462                        /* do nothing */
     
    353479        };
    354480
    355 
    356481        ordering.clear();
    357482        ordering.reserve(num_vertices(G));
     
    370495
    371496            const auto typeId = getType(u);
    372 
    373497            assert (isLive(u));
    374498            assert (!isImmutable(typeId));
  • icGREP/icgrep-devel/icgrep/pablo/optimizers/pablo_simplifier.cpp

    r5607 r5620  
    1313#include <pablo/pe_matchstar.h>
    1414#include <pablo/pe_var.h>
    15 #include <boost/container/flat_set.hpp>
    1615#ifndef NDEBUG
    1716#include <pablo/analysis/pabloverifier.hpp>
    1817#endif
    19 #include <llvm/Support/raw_ostream.h>
    20 
     18#include <boost/container/flat_set.hpp>
    2119
    2220using namespace boost;
     
    2826using TypeId = PabloAST::ClassTypeId;
    2927
     28using ScopeMap = flat_map<PabloBlock *, unsigned>;
     29
     30/** ------------------------------------------------------------------------------------------------------------- *
     31 * @brief VariableTable
     32 ** ------------------------------------------------------------------------------------------------------------- */
     33struct VariableTable {
     34
     35    VariableTable(VariableTable * predecessor = nullptr)
     36    : mPredecessor(predecessor) {
     37
     38    }
     39
     40    PabloAST * get(PabloAST * const var) const {
     41        const auto f = mMap.find(var);
     42        if (f == mMap.end()) {
     43            return (mPredecessor) ? mPredecessor->get(var) : nullptr;
     44        }
     45        return f->second;
     46    }
     47
     48    void put(PabloAST * const var, PabloAST * value) {
     49        const auto f = mMap.find(var);
     50        if (LLVM_LIKELY(f == mMap.end())) {
     51            mMap.emplace(var, value);
     52        } else {
     53            f->second = value;
     54        }
     55        assert (get(var) == value);
     56    }
     57
     58private:
     59    VariableTable * const mPredecessor;
     60    flat_map<PabloAST *, PabloAST *> mMap;
     61};
     62
     63struct PassContainer {
     64
     65/** ------------------------------------------------------------------------------------------------------------- *
     66 * @brief run
     67 ** ------------------------------------------------------------------------------------------------------------- */
     68void run(PabloKernel * const kernel) {
     69    redundancyElimination(kernel->getEntryBlock(), nullptr, nullptr);
     70    strengthReduction(kernel->getEntryBlock());
     71    deadCodeElimination(kernel->getEntryBlock());
     72}
     73
     74protected:
     75
     76/** ------------------------------------------------------------------------------------------------------------- *
     77 * @brief redundancyElimination
     78 *
     79 * Note: Do not recursively delete statements in this function. The ExpressionTable could use deleted statements
     80 * as replacements. Let the DCE remove the unnecessary statements with the finalized Def-Use information.
     81 ** ------------------------------------------------------------------------------------------------------------- */
     82void redundancyElimination(PabloBlock * const block, ExpressionTable * const et, VariableTable * const vt) {
     83    ExpressionTable expressions(et);
     84    VariableTable variables(vt);
     85
     86    if (Branch * br = block->getBranch()) {
     87        assert ("block has a branch but the expression and variable tables were not supplied" && et && vt);
     88        for (Var * var : br->getEscaped()) {
     89            variables.put(var, var);
     90        }
     91    }
     92
     93    mInScope.push_back(block);
     94
     95    const auto baseNonZeroEntries = mNonZero.size();
     96    Statement * stmt = block->front();
     97    while (stmt) {
     98
     99        if (LLVM_UNLIKELY(isa<Assign>(stmt))) {
     100            Assign * const assign = cast<Assign>(stmt);
     101            PabloAST * const var = assign->getVariable();
     102            PabloAST * value = assign->getValue();
     103            if (LLVM_UNLIKELY(var == value)) {
     104                stmt = stmt->eraseFromParent();
     105                continue;
     106            }
     107            while (LLVM_UNLIKELY(isa<Var>(value))) {
     108                PabloAST * next = variables.get(cast<Var>(value));
     109                if (LLVM_LIKELY(next == nullptr || next == value)) {
     110                    break;
     111                }
     112                value = next;
     113                assign->setValue(value);
     114            }
     115            if (LLVM_UNLIKELY(variables.get(var) == value)) {
     116                stmt = stmt->eraseFromParent();
     117                continue;
     118            }
     119            variables.put(var, value);
     120
     121        } else if (LLVM_UNLIKELY(isa<Branch>(stmt))) {
     122
     123            Branch * const br = cast<Branch>(stmt);
     124            PabloAST * cond = br->getCondition();
     125            if (isa<Var>(cond)) {
     126                PabloAST * const value = variables.get(cast<Var>(cond));
     127                if (value) {
     128                    cond = value;
     129                    if (isa<If>(br)) {
     130                        br->setCondition(cond);
     131                    }
     132                }
     133            }
     134
     135            // Test whether we can ever take this branch
     136            if (LLVM_UNLIKELY(isa<Zeroes>(cond))) {
     137                stmt = stmt->eraseFromParent();
     138                continue;
     139            }
     140
     141            // If we're guaranteed to take this branch, flatten it.
     142            if (LLVM_LIKELY(isa<If>(br)) && LLVM_UNLIKELY(isNonZero(cond))) {
     143                stmt = flatten(br);
     144                continue;
     145            }
     146
     147            // Mark the cond as non-zero prior to processing the inner scope.
     148            mNonZero.push_back(cond);
     149            // Process the Branch body
     150            redundancyElimination(br->getBody(), &expressions, &variables);
     151            assert (mNonZero.back() == cond);
     152            mNonZero.pop_back();
     153
     154            if (LLVM_LIKELY(isa<If>(br))) {
     155                // Check whether the cost of testing the condition and taking the branch with
     156                // 100% correct prediction rate exceeds the cost of the body itself
     157                if (LLVM_UNLIKELY(isTrivial(br->getBody()))) {
     158                    stmt = flatten(br);
     159                    continue;
     160                }
     161            }
     162
     163        } else {
     164
     165            // demote any uses of any Var whose value is in scope
     166            for (unsigned i = 0; i < stmt->getNumOperands(); ++i) {
     167                PabloAST * op = stmt->getOperand(i);
     168                if (LLVM_UNLIKELY(isa<Var>(op))) {
     169                    PabloAST * const value = variables.get(cast<Var>(op));
     170                    if (value && value != op) {
     171                        stmt->setOperand(i, value);
     172                    }
     173                }
     174            }
     175
     176            PabloAST * const folded = triviallyFold(stmt, block);
     177            if (folded) {
     178                Statement * const prior = stmt->getPrevNode();
     179                stmt->replaceWith(folded);
     180                stmt = prior ? prior->getNextNode() : block->front();
     181                continue;
     182            }
     183
     184            // By recording which statements have already been seen, we can detect the redundant statements
     185            // as any having the same type and operands. If so, we can replace its users with the prior statement.
     186            // and erase this statement from the AST
     187            const auto f = expressions.findOrAdd(stmt);
     188            if (!f.second) {
     189                stmt = stmt->replaceWith(f.first);
     190                continue;
     191            }
     192
     193            // Attempt to extend our set of trivially non-zero statements.
     194            if (isa<Or>(stmt)) {
     195                for (unsigned i = 0; i < stmt->getNumOperands(); ++i) {
     196                    if (LLVM_UNLIKELY(isNonZero(stmt->getOperand(i)))) {
     197                        mNonZero.push_back(stmt);
     198                        break;
     199                    }
     200                }
     201            } else if (isa<Advance>(stmt)) {
     202                const Advance * const adv = cast<Advance>(stmt);
     203                if (LLVM_LIKELY(adv->getAmount() < (adv->getType()->getPrimitiveSizeInBits() / 2))) {
     204                    if (LLVM_UNLIKELY(isNonZero(adv->getExpression()))) {
     205                        mNonZero.push_back(adv);
     206                    }
     207                }
     208            }
     209        }
     210
     211        stmt = stmt->getNextNode();
     212    }
     213
     214    // Erase any local non-zero entries that were discovered while processing this scope
     215    mNonZero.erase(mNonZero.begin() + baseNonZeroEntries, mNonZero.end());
     216
     217    assert (mInScope.back() == block);
     218    mInScope.pop_back();
     219
     220    // If this block has a branch statement leading into it, we can verify whether an escaped value
     221    // was updated within this block and update the preceeding block's variable state appropriately.
     222
     223    Branch * const br = block->getBranch();
     224    if (LLVM_LIKELY(br != nullptr)) {
     225
     226        // When removing identical escaped values, we have to consider that the identical Vars could
     227        // be assigned new differing values later in the outer body. Thus instead of replacing them
     228        // directly, we map future uses of the duplicate Var to the initial one. The DCE pass will
     229        // later mark any Assign statement as dead if the Var is never read.
     230
     231        const auto escaped = br->getEscaped();
     232        const auto n = escaped.size();
     233        PabloAST * variable[n];
     234        PabloAST * incoming[n];
     235        PabloAST * outgoing[n];
     236        for (unsigned i = 0; i < n; ++i) {
     237            variable[i] = escaped[i];
     238            incoming[i] = vt->get(variable[i]);
     239            outgoing[i] = variables.get(variable[i]);
     240            if (LLVM_UNLIKELY(incoming[i] == outgoing[i])) {
     241                variable[i] = incoming[i];
     242            } else {
     243                for (unsigned j = 0; j < i; ++j) {
     244                    if (LLVM_UNLIKELY((outgoing[j] == outgoing[i]) && (incoming[j] == incoming[i]))) {
     245                        variable[i] = variable[j];
     246                        break;
     247                    }
     248                }
     249            }
     250            vt->put(escaped[i], variable[i]);
     251        }
     252
     253    }
     254
     255}
     256
     257
    30258/** ------------------------------------------------------------------------------------------------------------- *
    31259 * @brief fold
    32260 ** ------------------------------------------------------------------------------------------------------------- */
    33 PabloAST * triviallyFold(Statement * stmt, PabloBlock * const block) {
     261static PabloAST * triviallyFold(Statement * stmt, PabloBlock * const block) {
    34262    if (isa<Not>(stmt)) {
    35263        PabloAST * value = stmt->getOperand(0);
     
    41269            return block->createZeroes(stmt->getType()); // ¬1 ⇔ 0
    42270        }
    43     } else if (isa<Advance>(stmt)) {
    44         if (LLVM_UNLIKELY(isa<Zeroes>(stmt->getOperand(0)))) {
    45             return block->createZeroes(stmt->getType());
    46         }
    47     } else if (isa<Add>(stmt) || isa<Subtract>(stmt)) {
     271    } else if (LLVM_UNLIKELY(isa<Add>(stmt) || isa<Subtract>(stmt))) {
    48272       if (LLVM_UNLIKELY(isa<Integer>(stmt->getOperand(0)) && isa<Integer>(stmt->getOperand(1)))) {
    49273           const Integer * const int0 = cast<Integer>(stmt->getOperand(0));
     
    57281           return block->getInteger(result);
    58282       }
     283    } else if (LLVM_UNLIKELY(isa<Variadic>(stmt))) {
     284
     285        std::sort(cast<Variadic>(stmt)->begin(), cast<Variadic>(stmt)->end());
     286
     287        for (unsigned i = 1; i < stmt->getNumOperands(); ) {
     288            if (LLVM_UNLIKELY(stmt->getOperand(i - 1) == stmt->getOperand(i))) {
     289                if (LLVM_UNLIKELY(isa<Xor>(stmt))) {
     290                    if (LLVM_LIKELY(stmt->getNumOperands() == 2)) {
     291                        return block->createZeroes(stmt->getType());
     292                    } else {
     293                        cast<Variadic>(stmt)->removeOperand(i);
     294                        cast<Variadic>(stmt)->removeOperand(i - 1);
     295                        continue;
     296                    }
     297                } else {
     298                    if (LLVM_LIKELY(stmt->getNumOperands() == 2)) {
     299                        return stmt->getOperand(1 - i);
     300                    } else {
     301                        cast<Variadic>(stmt)->removeOperand(i);
     302                        continue;
     303                    }
     304                }
     305            }
     306            ++i;
     307        }
     308
     309        if (LLVM_UNLIKELY(stmt->getNumOperands() < 2)) {
     310            if (LLVM_LIKELY(stmt->getNumOperands() == 1)) {
     311                return stmt->getOperand(0);
     312            } else {
     313                return block->createZeroes(stmt->getType());
     314            }
     315        }
     316
     317        if (LLVM_UNLIKELY(isa<Xor>(stmt))) {
     318            bool negated = false;
     319            PabloAST * expr = nullptr;
     320            for (unsigned i = 0; i < stmt->getNumOperands(); ) {
     321                const PabloAST * const op = stmt->getOperand(i);
     322                if (isa<Not>(op)) {
     323                    negated ^= true;
     324                    stmt->setOperand(i, cast<Not>(op)->getExpr());
     325                } else if (LLVM_UNLIKELY(isa<Zeroes>(op) || isa<Ones>(op))) {
     326                    negated ^= isa<Ones>(op);
     327                    if (LLVM_LIKELY(stmt->getNumOperands() == 2)) {
     328                        expr = stmt->getOperand(1 - i);
     329                        break;
     330                    } else {
     331                        cast<Variadic>(stmt)->removeOperand(i);
     332                        continue;
     333                    }
     334                }
     335                ++i;
     336            }
     337            if (LLVM_UNLIKELY(negated)) {
     338                block->setInsertPoint(stmt);
     339                expr = block->createNot(expr ? expr : stmt);
     340            }
     341            return expr;
     342        } else { // if (isa<And>(stmt) || isa<Or>(stmt))
     343            for (unsigned i = 0; i < stmt->getNumOperands(); ++i) {
     344                const PabloAST * const op = stmt->getOperand(i);
     345                if (LLVM_UNLIKELY(isa<Zeroes>(op) || isa<Ones>(op))) {
     346                    if (isa<And>(stmt) ^ isa<Zeroes>(op)) {
     347                        if (LLVM_LIKELY(stmt->getNumOperands() == 2)) {
     348                            return stmt->getOperand(1 - i);
     349                        } else {
     350                            cast<Variadic>(stmt)->removeOperand(i);
     351                            continue;
     352                        }
     353                    } else {
     354                        return stmt->getOperand(i);
     355                    }
     356                }
     357                ++i;
     358            }
     359        }
    59360    } else {
    60361        for (unsigned i = 0; i != stmt->getNumOperands(); ++i) {
     
    68369                            case 2: return block->createAnd(stmt->getOperand(0), stmt->getOperand(1));
    69370                        }
     371                    case TypeId::Advance:
    70372                    case TypeId::ScanThru:
    71373                    case TypeId::MatchStar:
     
    101403
    102404/** ------------------------------------------------------------------------------------------------------------- *
    103  * @brief VariableTable
    104  ** ------------------------------------------------------------------------------------------------------------- */
    105 struct VariableTable {
    106 
    107     VariableTable(VariableTable * predecessor = nullptr)
    108     : mPredecessor(predecessor) {
    109 
    110     }
    111 
    112     PabloAST * get(PabloAST * const var) const {
    113         const auto f = mMap.find(var);
    114         if (f == mMap.end()) {
    115             return (mPredecessor) ? mPredecessor->get(var) : nullptr;
    116         }
    117         return f->second;
    118     }
    119 
    120     void put(PabloAST * const var, PabloAST * value) {
    121         const auto f = mMap.find(var);
    122         if (LLVM_LIKELY(f == mMap.end())) {
    123             mMap.emplace(var, value);
    124         } else {
    125             f->second = value;
    126         }
    127         assert (get(var) == value);
    128     }
    129 
    130     bool isNonZero(const PabloAST * const var) const {
    131         if (mNonZero.count(var) != 0) {
    132             return true;
    133         } else if (mPredecessor) {
    134             return mPredecessor->isNonZero(var);
    135         }
    136         return false;
    137     }
    138 
    139     void addNonZero(const PabloAST * const var) {
    140         mNonZero.insert(var);
    141     }
    142 
    143 private:
    144     VariableTable * const mPredecessor;
    145     flat_map<PabloAST *, PabloAST *> mMap;
    146     flat_set<const PabloAST *> mNonZero;
    147 };
    148 
    149 /** ------------------------------------------------------------------------------------------------------------- *
    150405 * @brief isTrivial
    151406 *
     
    153408 * statements, just add the statements in the inner block to the current block
    154409 ** ------------------------------------------------------------------------------------------------------------- */
    155 inline bool isTrivial(const PabloBlock * const block) {
     410static bool isTrivial(const PabloBlock * const block) {
    156411    unsigned computations = 0;
    157412    for (const Statement * stmt : *block) {
     
    176431 * @brief flatten
    177432 ** ------------------------------------------------------------------------------------------------------------- */
    178 Statement * flatten(Branch * const br) {
     433static Statement * flatten(Branch * const br) {
    179434    Statement * stmt = br;
    180435    Statement * nested = br->getBody()->front();
     
    189444
    190445/** ------------------------------------------------------------------------------------------------------------- *
    191  * @brief redundancyElimination
    192  *
    193  * Note: Do not recursively delete statements in this function. The ExpressionTable could use deleted statements
    194  * as replacements. Let the DCE remove the unnecessary statements with the finalized Def-Use information.
    195  ** ------------------------------------------------------------------------------------------------------------- */
    196 void redundancyElimination(PabloBlock * const block, ExpressionTable * const et, VariableTable * const vt) {
    197     VariableTable variables(vt);
    198 
    199     // When processing a While body, we cannot use its initial value from the outer
    200     // body since the Var will likely be assigned a different value in the current
    201     // body that should be used on the subsequent iteration of the loop.
    202     if (Branch * br = block->getBranch()) {
    203         assert ("block has a branch but the expression and variable tables were not supplied" && et && vt);
    204         variables.addNonZero(br->getCondition());
    205         for (Var * var : br->getEscaped()) {
    206             variables.put(var, var);
    207         }
    208     }
    209 
    210     ExpressionTable expressions(et);
    211 
    212     Statement * stmt = block->front();
    213     while (stmt) {
    214 
    215         if (LLVM_UNLIKELY(isa<Assign>(stmt))) {
    216             Assign * const assign = cast<Assign>(stmt);
    217             PabloAST * const var = assign->getVariable();
    218             PabloAST * value = assign->getValue();
    219             while (LLVM_UNLIKELY(isa<Var>(value))) {
    220                 PabloAST * next = variables.get(cast<Var>(value));
    221                 if (LLVM_LIKELY(next == nullptr || next == value)) {
    222                     break;
    223                 }
    224                 value = next;
    225                 assign->setValue(value);
    226             }
    227             if (LLVM_UNLIKELY(variables.get(var) == value)) {
    228                 stmt = stmt->eraseFromParent();
    229                 continue;
    230             }
    231             variables.put(var, value);
    232         } else if (LLVM_UNLIKELY(isa<Branch>(stmt))) {
    233 
    234             Branch * const br = cast<Branch>(stmt);
    235 
    236             // Test whether we can ever take this branch
    237             PabloAST * cond = br->getCondition();
    238             if (isa<Var>(cond)) {
    239                 PabloAST * const value = variables.get(cast<Var>(cond));
    240                 if (value) {
    241                     cond = value;
    242                     // TODO: verify this works for a nested If node within a While body.
    243                     if (isa<If>(br)) {
    244                         br->setCondition(cond);
    245                     }
    246                 }
    247             }
    248 
    249             if (LLVM_UNLIKELY(isa<Zeroes>(cond))) {
    250                 stmt = stmt->eraseFromParent();
    251                 continue;
    252             }
    253 
    254             if (LLVM_LIKELY(isa<If>(br))) {
    255                 if (LLVM_UNLIKELY(variables.isNonZero(cond))) {
    256                     stmt = flatten(br);
    257                     continue;
    258                 }
    259             }
    260 
    261             // Process the Branch body
    262             redundancyElimination(br->getBody(), &expressions, &variables);
    263 
    264             if (LLVM_LIKELY(isa<If>(br))) {
    265                 // Check whether the cost of testing the condition and taking the branch with
    266                 // 100% correct prediction rate exceeds the cost of the body itself
    267                 if (LLVM_UNLIKELY(isTrivial(br->getBody()))) {
    268                     stmt = flatten(br);
    269                     continue;
    270                 }
    271             }
    272 
    273         } else {
    274 
    275             // demote any uses of a Var whose value is in scope
    276             for (unsigned i = 0; i < stmt->getNumOperands(); ++i) {
    277                 PabloAST * op = stmt->getOperand(i);
    278                 if (LLVM_UNLIKELY(isa<Var>(op))) {
    279                     PabloAST * const value = variables.get(cast<Var>(op));
    280                     if (value && value != op) {
    281                         stmt->setOperand(i, value);
    282                     }
    283                 }
    284             }
    285 
    286             PabloAST * const folded = triviallyFold(stmt, block);
    287             if (folded) {
    288                 stmt = stmt->replaceWith(folded);
    289                 continue;
    290             }
    291 
    292             // By recording which statements have already been seen, we can detect the redundant statements
    293             // as any having the same type and operands. If so, we can replace its users with the prior statement.
    294             // and erase this statement from the AST
    295             const auto f = expressions.findOrAdd(stmt);
    296             if (!f.second) {
    297                 stmt = stmt->replaceWith(f.first);
    298                 continue;
    299             }
    300 
    301             // Check whether this statement is trivially non-zero and if so, add it to our set of non-zero variables.
    302             // This will allow us to flatten an If scope if its branch is always taken.
    303             if (isa<Or>(stmt)) {
    304                 for (unsigned i = 0; i < stmt->getNumOperands(); ++i) {
    305                     if (LLVM_UNLIKELY(variables.isNonZero(stmt->getOperand(i)))) {
    306                         variables.addNonZero(stmt);
    307                         break;
    308                     }
    309                 }
    310             } else if (isa<Advance>(stmt)) {
    311                 const Advance * const adv = cast<Advance>(stmt);
    312                 if (LLVM_LIKELY(adv->getAmount() < 32)) {
    313                     if (LLVM_UNLIKELY(variables.isNonZero(adv->getExpression()))) {
    314                         variables.addNonZero(adv);
    315                     }
    316                 }
    317             }
    318         }
    319 
    320         stmt = stmt->getNextNode();
    321     }
    322 
    323     // If this block has a branch statement leading into it, we can verify whether an escaped value
    324     // was updated within this block and update the preceeding block's variable state appropriately.
    325 
    326     if (Branch * const br = block->getBranch()) {
    327 
    328         // When removing identical escaped values, we have to consider that the identical Vars could
    329         // be assigned new differing values later in the outer body. Thus instead of replacing them
    330         // directly, we map future uses of the duplicate Var to the initial one. The DCE pass will
    331         // later mark any Assign statement as dead if the Var is never read.
    332 
    333         /// TODO: this doesn't properly optimize the loop control variable(s) yet.
    334 
    335         const auto escaped = br->getEscaped();
    336         const auto n = escaped.size();
    337         PabloAST * variable[n];
    338         PabloAST * incoming[n];
    339         PabloAST * outgoing[n];
    340 
    341         for (unsigned i = 0; i < escaped.size(); ++i) {
    342             PabloAST * var = escaped[i];
    343             incoming[i] = vt->get(var);
    344             outgoing[i] = variables.get(var);
    345             if (LLVM_UNLIKELY(incoming[i] == outgoing[i])) {
    346                 var = incoming[i];
    347             } else {
    348                 for (size_t j = 0; j != i; ++j) {
    349                     if ((outgoing[j] == outgoing[i]) && (incoming[j] == incoming[i])) {
    350                         var = variable[j];
    351                         break;
    352                     }
    353                 }
    354             }
    355             variable[i] = var;
    356             vt->put(escaped[i], var);
    357         }
    358     }
    359 }
    360 
    361 /** ------------------------------------------------------------------------------------------------------------- *
    362  * @brief deadCodeElimination
    363  ** ------------------------------------------------------------------------------------------------------------- */
    364 void deadCodeElimination(PabloBlock * const block) {
    365 
    366     flat_map<PabloAST *, Assign *> unread;
    367 
    368     Statement * stmt = block->front();
    369     while (stmt) {
    370         if (unread.size() != 0) {
    371             for (unsigned i = 0; i < stmt->getNumOperands(); ++i) {
    372                 PabloAST * const op = stmt->getOperand(i);
    373                 if (LLVM_UNLIKELY(isa<Var>(op))) {
    374                     unread.erase(op);
    375                 }
    376             }
    377         }
    378         if (LLVM_UNLIKELY(isa<Branch>(stmt))) {
    379             Branch * const br = cast<Branch>(stmt);
    380             deadCodeElimination(br->getBody());
    381             if (LLVM_UNLIKELY(br->getEscaped().empty())) {
    382                 stmt = stmt->eraseFromParent(true);
    383                 continue;
    384             }
    385         } else if (LLVM_UNLIKELY(isa<Assign>(stmt))) {
    386             // An Assign statement is locally dead whenever its variable is not read
    387             // before being reassigned a value.
    388             PabloAST * var = cast<Assign>(stmt)->getVariable();
    389             auto f = unread.find(var);
    390             if (f != unread.end()) {
    391                 auto prior = f->second;
    392                 prior->eraseFromParent(true);
    393                 f->second = cast<Assign>(stmt);
    394             } else {
    395                 unread.emplace(var, cast<Assign>(stmt));
    396             }
    397         } else if (LLVM_UNLIKELY(stmt->getNumUses() == 0)) {
    398             stmt = stmt->eraseFromParent(true);
    399             continue;
    400         }
    401         stmt = stmt->getNextNode();
    402     }
    403 }
    404 
    405 /** ------------------------------------------------------------------------------------------------------------- *
    406  * @brief deadCodeElimination
    407  ** ------------------------------------------------------------------------------------------------------------- */
    408 void deadCodeElimination(PabloKernel * kernel) {
    409 
    410     deadCodeElimination(kernel->getEntryBlock());
    411 
    412     for (unsigned i = 0; i < kernel->getNumOfVariables(); ++i) {
    413         Var * var = kernel->getVariable(i);
    414         bool unused = true;
    415         for (PabloAST * user : var->users()) {
    416             if (isa<Assign>(user)) {
    417                 if (cast<Assign>(user)->getValue() == var) {
    418                     unused = false;
    419                     break;
    420                 }
    421             } else {
    422                 unused = false;
    423                 break;
    424             }
    425         }
    426         if (LLVM_UNLIKELY(unused)) {
    427             for (PabloAST * user : var->users()) {
    428                 cast<Assign>(user)->eraseFromParent(true);
    429             }
    430         }
    431     }
    432 
     446 * @brief isNonZero
     447 ** ------------------------------------------------------------------------------------------------------------- */
     448bool isNonZero(const PabloAST * const expr) const {
     449    return isa<Ones>(expr) || std::find(mNonZero.begin(), mNonZero.end(), expr) != mNonZero.end();
    433450}
    434451
     
    503520
    504521/** ------------------------------------------------------------------------------------------------------------- *
     522 * @brief deadCodeElimination
     523 ** ------------------------------------------------------------------------------------------------------------- */
     524void deadCodeElimination(PabloBlock * const block) {
     525
     526    flat_set<PabloAST *> written;
     527
     528    for (Statement * stmt = block->back(), * prior; stmt; stmt = prior) {
     529        prior = stmt->getPrevNode();
     530        if (LLVM_UNLIKELY(stmt->getNumUses() == 0)) {
     531            if (LLVM_UNLIKELY(isa<Branch>(stmt))) {
     532                written.clear();
     533                deadCodeElimination(cast<Branch>(stmt)->getBody());
     534            } else if (LLVM_UNLIKELY(isa<Assign>(stmt))) {
     535                // An Assign statement is locally dead whenever its variable is not read
     536                // before being reassigned a value.
     537                PabloAST * var = cast<Assign>(stmt)->getVariable();
     538                if (LLVM_UNLIKELY(!written.insert(var).second)) {
     539                    stmt->eraseFromParent();
     540                }
     541            } else {
     542                stmt->eraseFromParent();
     543            }
     544        }
     545    }
     546}
     547
     548std::vector<const PabloAST *>       mNonZero;
     549std::vector<const PabloBlock *>     mInScope;
     550
     551};
     552
     553/** ------------------------------------------------------------------------------------------------------------- *
    505554 * @brief optimize
    506555 ** ------------------------------------------------------------------------------------------------------------- */
    507556bool Simplifier::optimize(PabloKernel * kernel) {
    508     redundancyElimination(kernel->getEntryBlock(), nullptr, nullptr);
    509     strengthReduction(kernel->getEntryBlock());
    510     deadCodeElimination(kernel);
     557    PassContainer pc;
     558    pc.run(kernel);
    511559    #ifndef NDEBUG
    512560    PabloVerifier::verify(kernel, "post-simplification");
  • icGREP/icgrep-devel/icgrep/pablo/pablo_compiler.cpp

    r5510 r5620  
    4040using TypeId = PabloAST::ClassTypeId;
    4141
    42 inline static unsigned getAlignment(const Value * const ptr) {
    43     return ptr->getType()->getPrimitiveSizeInBits() / 8;
     42inline static unsigned getAlignment(const Value * const type) {
     43    return type->getType()->getPrimitiveSizeInBits() / 8;
    4444}
    4545
     
    4848}
    4949
    50 void PabloCompiler::initializeKernelData(const std::unique_ptr<kernel::KernelBuilder> &  iBuilder) {
     50void PabloCompiler::initializeKernelData(const std::unique_ptr<kernel::KernelBuilder> & iBuilder) {
    5151    assert ("PabloCompiler does not have a IDISA iBuilder" && iBuilder);
     52    mBranchCount = 0;
    5253    examineBlock(iBuilder, mKernel->getEntryBlock());
    5354    mCarryManager->initializeCarryData(iBuilder, mKernel);
    54 }
    55 
    56 void PabloCompiler::releaseKernelData(const std::unique_ptr<kernel::KernelBuilder> &  iBuilder) {
     55    if (CompileOptionIsSet(PabloCompilationFlags::EnableProfiling)) {
     56        const auto count = (mBranchCount * 2) + 1;
     57        mKernel->addScalar(ArrayType::get(mKernel->getSizeTy(), count), "profile");
     58        mBasicBlock.reserve(count);
     59    }
     60}
     61
     62void PabloCompiler::releaseKernelData(const std::unique_ptr<kernel::KernelBuilder> & iBuilder) {
    5763    assert ("PabloCompiler does not have a IDISA iBuilder" && iBuilder);
    5864    mCarryManager->releaseCarryData(iBuilder);
    5965}
    6066
    61 void PabloCompiler::compile(const std::unique_ptr<kernel::KernelBuilder> &  iBuilder) {
     67void PabloCompiler::compile(const std::unique_ptr<kernel::KernelBuilder> & iBuilder) {
    6268    assert ("PabloCompiler does not have a IDISA iBuilder" && iBuilder);
    6369    mCarryManager->initializeCodeGen(iBuilder);
     
    6571    mMarker.emplace(entryBlock->createZeroes(), iBuilder->allZeroes());
    6672    mMarker.emplace(entryBlock->createOnes(), iBuilder->allOnes());
     73    mBranchCount = 0;
     74    addBranchCounter(iBuilder);
    6775    compileBlock(iBuilder, entryBlock);
    6876    mCarryManager->finalizeCodeGen(iBuilder);
    6977}
    7078
    71 void PabloCompiler::examineBlock(const std::unique_ptr<kernel::KernelBuilder> &  iBuilder, const PabloBlock * const block) {
     79void PabloCompiler::examineBlock(const std::unique_ptr<kernel::KernelBuilder> & iBuilder, const PabloBlock * const block) {
    7280    for (const Statement * stmt : *block) {
    7381        if (LLVM_UNLIKELY(isa<Lookahead>(stmt))) {
     
    7886            }
    7987        } else if (LLVM_UNLIKELY(isa<Branch>(stmt))) {
     88            ++mBranchCount;
    8089            examineBlock(iBuilder, cast<Branch>(stmt)->getBody());
    8190        } else if (LLVM_UNLIKELY(isa<Count>(stmt))) {
     
    8594}
    8695
    87 inline void PabloCompiler::compileBlock(const std::unique_ptr<kernel::KernelBuilder> &  iBuilder, const PabloBlock * const block) {
     96void PabloCompiler::addBranchCounter(const std::unique_ptr<kernel::KernelBuilder> & iBuilder) {
     97    if (CompileOptionIsSet(PabloCompilationFlags::EnableProfiling)) {       
     98        Value * ptr = iBuilder->getScalarFieldPtr("profile");
     99        assert (mBasicBlock.size() < ptr->getType()->getPointerElementType()->getArrayNumElements());
     100        ptr = iBuilder->CreateGEP(ptr, {iBuilder->getInt32(0), iBuilder->getInt32(mBasicBlock.size())});
     101        const auto alignment = getPointerElementAlignment(ptr);
     102        Value * value = iBuilder->CreateAlignedLoad(ptr, alignment, false, "branchCounter");
     103        value = iBuilder->CreateAdd(value, ConstantInt::get(cast<IntegerType>(value->getType()), 1));
     104        iBuilder->CreateAlignedStore(value, ptr, alignment);
     105        mBasicBlock.push_back(iBuilder->GetInsertBlock());
     106    }
     107}
     108
     109inline void PabloCompiler::compileBlock(const std::unique_ptr<kernel::KernelBuilder> & iBuilder, const PabloBlock * const block) {
    88110    for (const Statement * statement : *block) {
    89111        compileStatement(iBuilder, statement);
     
    91113}
    92114
    93 void PabloCompiler::compileIf(const std::unique_ptr<kernel::KernelBuilder> &  iBuilder, const If * const ifStatement) {
     115void PabloCompiler::compileIf(const std::unique_ptr<kernel::KernelBuilder> & iBuilder, const If * const ifStatement) {
    94116    //
    95117    //  The If-ElseZero stmt:
     
    111133
    112134    BasicBlock * const ifEntryBlock = iBuilder->GetInsertBlock();
    113     BasicBlock * const ifBodyBlock = iBuilder->CreateBasicBlock("if.body");
    114     BasicBlock * const ifEndBlock = iBuilder->CreateBasicBlock("if.end");
     135    ++mBranchCount;
     136    BasicBlock * const ifBodyBlock = iBuilder->CreateBasicBlock("if.body_" + std::to_string(mBranchCount));
     137    BasicBlock * const ifEndBlock = iBuilder->CreateBasicBlock("if.end_" + std::to_string(mBranchCount));
    115138   
    116139    std::vector<std::pair<const Var *, Value *>> incoming;
     
    156179
    157180    mCarryManager->enterIfBody(iBuilder, ifEntryBlock);
     181
     182    addBranchCounter(iBuilder);
    158183
    159184    compileBlock(iBuilder, ifBody);
     
    209234        phi->addIncoming(outgoing, ifExitBlock);
    210235        f->second = phi;
    211     }   
    212 }
    213 
    214 void PabloCompiler::compileWhile(const std::unique_ptr<kernel::KernelBuilder> &  iBuilder, const While * const whileStatement) {
     236    }
     237
     238    addBranchCounter(iBuilder);
     239}
     240
     241void PabloCompiler::compileWhile(const std::unique_ptr<kernel::KernelBuilder> & iBuilder, const While * const whileStatement) {
    215242
    216243    const PabloBlock * const whileBody = whileStatement->getBody();
     
    243270    mCarryManager->enterLoopScope(iBuilder, whileBody);
    244271
    245     BasicBlock * whileBodyBlock = iBuilder->CreateBasicBlock("while.body");
     272    BasicBlock * whileBodyBlock = iBuilder->CreateBasicBlock("while.body_" + std::to_string(mBranchCount));
     273    BasicBlock * whileEndBlock = iBuilder->CreateBasicBlock("while.end_" + std::to_string(mBranchCount));
     274    ++mBranchCount;
    246275
    247276    iBuilder->CreateBr(whileBodyBlock);
     
    287316
    288317    mCarryManager->enterLoopBody(iBuilder, whileEntryBlock);
     318
     319    addBranchCounter(iBuilder);
    289320
    290321    compileBlock(iBuilder, whileBody);
     
    338369    }
    339370
    340     BasicBlock * whileEndBlock = iBuilder->CreateBasicBlock("while.end");
    341 
    342371    // Terminate the while loop body with a conditional branch back.
    343372    Value * condition = compileExpression(iBuilder, whileStatement->getCondition());
     
    348377    iBuilder->CreateCondBr(condition, whileBodyBlock, whileEndBlock);
    349378
     379    whileEndBlock->moveAfter(whileExitBlock);
     380
    350381    iBuilder->SetInsertPoint(whileEndBlock);
    351382
    352383    mCarryManager->leaveLoopScope(iBuilder, whileEntryBlock, whileExitBlock);
    353384
    354 }
    355 
    356 void PabloCompiler::compileStatement(const std::unique_ptr<kernel::KernelBuilder> &  iBuilder, const Statement * const stmt) {
     385    addBranchCounter(iBuilder);
     386}
     387
     388void PabloCompiler::compileStatement(const std::unique_ptr<kernel::KernelBuilder> & iBuilder, const Statement * const stmt) {
    357389
    358390    if (LLVM_UNLIKELY(isa<If>(stmt))) {
     
    587619}
    588620
    589 Value * PabloCompiler::compileExpression(const std::unique_ptr<kernel::KernelBuilder> &  iBuilder, const PabloAST * expr, const bool ensureLoaded) const {
     621Value * PabloCompiler::compileExpression(const std::unique_ptr<kernel::KernelBuilder> & iBuilder, const PabloAST * expr, const bool ensureLoaded) const {
    590622    if (LLVM_UNLIKELY(isa<Ones>(expr))) {
    591623        return iBuilder->allOnes();
     
    654686PabloCompiler::PabloCompiler(PabloKernel * const kernel)
    655687: mKernel(kernel)
    656 , mCarryManager(new CarryManager) {
     688, mCarryManager(new CarryManager)
     689, mBranchCount(0) {
    657690    assert ("PabloKernel cannot be null!" && kernel);
    658691}
  • icGREP/icgrep-devel/icgrep/pablo/pablo_compiler.h

    r5486 r5620  
    99
    1010#include <unordered_map>
     11#include <vector>
    1112#include <memory>
    1213namespace IDISA { class IDISA_Builder; }
     14namespace llvm { class BasicBlock; }
    1315namespace llvm { class Function; }
    1416namespace llvm { class Value; }
     
    3840protected:
    3941
    40     void initializeKernelData(const std::unique_ptr<kernel::KernelBuilder> &  iBuilder);
     42    void initializeKernelData(const std::unique_ptr<kernel::KernelBuilder> & iBuilder);
    4143
    42     void compile(const std::unique_ptr<kernel::KernelBuilder> &  iBuilder);
     44    void compile(const std::unique_ptr<kernel::KernelBuilder> & iBuilder);
    4345
    44     void releaseKernelData(const std::unique_ptr<kernel::KernelBuilder> &  iBuilder);
     46    void releaseKernelData(const std::unique_ptr<kernel::KernelBuilder> & iBuilder);
    4547
    4648private:
    4749
    48     void examineBlock(const std::unique_ptr<kernel::KernelBuilder> &  iBuilder, const PabloBlock * const block);
     50    void examineBlock(const std::unique_ptr<kernel::KernelBuilder> & iBuilder, const PabloBlock * const block);
    4951
    50     void compileBlock(const std::unique_ptr<kernel::KernelBuilder> &  iBuilder, const PabloBlock * const block);
     52    void compileBlock(const std::unique_ptr<kernel::KernelBuilder> & iBuilder, const PabloBlock * const block);
    5153
    52     void compileStatement(const std::unique_ptr<kernel::KernelBuilder> &  iBuilder, const Statement * stmt);
     54    void compileStatement(const std::unique_ptr<kernel::KernelBuilder> & iBuilder, const Statement * stmt);
    5355
    54     void compileIf(const std::unique_ptr<kernel::KernelBuilder> &  iBuilder, const If * ifStmt);
     56    void compileIf(const std::unique_ptr<kernel::KernelBuilder> & iBuilder, const If * ifStmt);
    5557
    56     void compileWhile(const std::unique_ptr<kernel::KernelBuilder> &  iBuilder, const While * whileStmt);
     58    void compileWhile(const std::unique_ptr<kernel::KernelBuilder> & iBuilder, const While * whileStmt);
    5759
    58     llvm::Value * compileExpression(const std::unique_ptr<kernel::KernelBuilder> &  iBuilder, const PabloAST * expr, const bool ensureLoaded = true) const;
     60    void addBranchCounter(const std::unique_ptr<kernel::KernelBuilder> & iBuilder);
     61
     62    llvm::Value * compileExpression(const std::unique_ptr<kernel::KernelBuilder> & iBuilder, const PabloAST * expr, const bool ensureLoaded = true) const;
    5963
    6064private:
     
    6468    TranslationMap                  mMarker;
    6569    TranslationMap                  mAccumulator;
    66 
     70    unsigned                        mBranchCount;
     71    std::vector<llvm::BasicBlock *> mBasicBlock;
    6772};
    6873
  • icGREP/icgrep-devel/icgrep/pablo/pablo_kernel.cpp

    r5493 r5620  
    1313#include <kernels/kernel_builder.h>
    1414#include <llvm/IR/Module.h>
     15
     16#include <pablo/branch.h>
     17#include <sys/stat.h>
     18#include <fcntl.h>
     19#include <llvm/Support/raw_ostream.h>
    1520
    1621using namespace kernel;
     
    149154void PabloKernel::generateFinalizeMethod(const std::unique_ptr<kernel::KernelBuilder> & iBuilder) {
    150155    mPabloCompiler->releaseKernelData(iBuilder);
     156
     157    if (CompileOptionIsSet(PabloCompilationFlags::EnableProfiling)) {
     158
     159
     160        Value * fd = iBuilder->CreateOpenCall(iBuilder->GetString("./" + getName() + ".profile"),
     161                                              iBuilder->getInt32(O_WRONLY | O_CREAT | O_TRUNC),
     162                                              iBuilder->getInt32(S_IRUSR | S_IWUSR | S_IRGRP | S_IWGRP | S_IROTH));
     163
     164        Function * dprintf = iBuilder->GetDprintf();
     165
     166
     167
     168        Value * profile = iBuilder->getScalarFieldPtr("profile");
     169
     170
     171        unsigned branchCount = 0;
     172
     173        for (const auto bb : mPabloCompiler->mBasicBlock) {
     174
     175            std::string tmp;
     176            raw_string_ostream str(tmp);
     177            str << "%lu\t";
     178            str << bb->getName();
     179            str << "\n";
     180
     181            Value * taken = iBuilder->CreateLoad(iBuilder->CreateGEP(profile, {iBuilder->getInt32(0), iBuilder->getInt32(branchCount++)}));
     182            iBuilder->CreateCall(dprintf, {fd, iBuilder->GetString(str.str()), taken});
     183
     184        }
     185
     186//        Value * base = iBuilder->CreateLoad(iBuilder->CreateGEP(profile, {iBuilder->getInt32(0), iBuilder->getInt32(0)}));
     187//        base = iBuilder->CreateUIToFP(base, iBuilder->getDoubleTy());
     188
     189//        unsigned branchCount = 0;
     190//        std::function<void (const PabloBlock *)> writeProfile = [&](const PabloBlock * const scope) {
     191//            for (const Statement * stmt : *scope) {
     192//                if (isa<Branch>(stmt)) {
     193
     194//                    ++branchCount;
     195
     196//                    std::string tmp;
     197//                    raw_string_ostream str(tmp);
     198//                    str << "%3.3f\t";
     199//                    str << mPabloCompiler->getBranchEntry(branchCount)->getName();
     200//                    str << "\n";
     201
     202//                    Value * branches = iBuilder->CreateLoad(iBuilder->CreateGEP(profile, {iBuilder->getInt32(0), iBuilder->getInt32(branchCount)}));
     203//                    branches = iBuilder->CreateUIToFP(branches, iBuilder->getDoubleTy());
     204//                    Value * prob = iBuilder->CreateFDiv(branches, base);
     205//                    iBuilder->CreateCall(dprintf, {fd, iBuilder->GetString(str.str()), prob});
     206
     207//                    writeProfile(cast<Branch>(stmt)->getBody());
     208
     209//                }
     210//            }
     211//        };
     212
     213//        writeProfile(getEntryBlock());
     214        iBuilder->CreateCloseCall(fd);
     215    }
     216
    151217}
    152218
     
    163229}
    164230
    165 static inline std::string annotateKernelNameWithDebugFlags(std::string && name) {
     231static inline std::string && annotateKernelNameWithDebugFlags(std::string && name) {
    166232    if (DebugOptionIsSet(DumpTrace)) {
    167233        name += "_DumpTrace";
    168234    }
    169     return name;
     235    if (CompileOptionIsSet(EnableProfiling)) {
     236        name += "_BranchProfiling";
     237    }
     238    return std::move(name);
    170239}
    171240
  • icGREP/icgrep-devel/icgrep/pablo/pablo_toolchain.cpp

    r5562 r5620  
    3333                        clEnumVal(ShowOptimizedPablo, "Print optimizeed Pablo code"),
    3434                        clEnumVal(VerifyPablo, "Run the Pablo verifier"),
    35                         clEnumVal(DumpTrace, "Generate dynamic traces of executed Pablo assignments."),
     35                        clEnumVal(DumpTrace, "Generate dynamic traces of executed Pablo assignments."),                       
    3636                        clEnumValEnd), cl::cat(PabloOptions));
    3737   
     
    4242    PabloOptimizationsOptions(cl::values(clEnumVal(DisableSimplification, "Disable Pablo Simplification pass (not recommended)"),
    4343                                         clEnumVal(DisableCodeMotion, "Moves statements into the innermost legal If-scope and moves invariants out of While-loops."),
    44                                          clEnumVal(EnableDistribution, "Apply distribution law optimization."),
    45 
     44                                         clEnumVal(EnableDistribution, "Apply distribution law optimization."),                                         
    4645                                         clEnumVal(EnableSchedulingPrePass, "Pablo Statement Scheduling Pre-Pass"),
     46                                         clEnumVal(EnableProfiling, "Profile branch statistics."),
    4747                                         clEnumValEnd), cl::cat(PabloOptions));
    4848
    49 bool DebugOptionIsSet(PabloDebugFlags flag) {return DebugOptions.isSet(flag);}
     49bool DebugOptionIsSet(const PabloDebugFlags flag) {return DebugOptions.isSet(flag);}
    5050   
     51bool CompileOptionIsSet(const PabloCompilationFlags flag) {return PabloOptimizationsOptions.isSet(flag);}
    5152
    5253void pablo_function_passes(PabloKernel * kernel) {
     
    6768
    6869    // Scan through the pablo code and perform DCE and CSE
     70    if (Flatten){
     71        FlattenIf::transform(kernel);
     72    }
    6973    if (LLVM_LIKELY(!PabloOptimizationsOptions.isSet(DisableSimplification))) {
    7074        Simplifier::optimize(kernel);
    7175    }
    72     if (Flatten){
    73         FlattenIf::transform(kernel);
     76    if (PabloOptimizationsOptions.isSet(EnableDistribution)) {
     77        DistributivePass::optimize(kernel);
    7478    }
    7579    if (LLVM_LIKELY(!PabloOptimizationsOptions.isSet(DisableCodeMotion))) {
    7680        CodeMotionPass::optimize(kernel);
    77     }
    78     if (PabloOptimizationsOptions.isSet(EnableDistribution)) {
    79         DistributivePass::optimize(kernel);
    8081    }
    8182    if (PabloOptimizationsOptions.isSet(EnableSchedulingPrePass)) {
  • icGREP/icgrep-devel/icgrep/pablo/pablo_toolchain.h

    r5562 r5620  
    1818
    1919enum PabloCompilationFlags {
    20     DisableSimplification, DisableCodeMotion, EnableDistribution, EnableSchedulingPrePass
     20    DisableSimplification, DisableCodeMotion, EnableDistribution, EnableSchedulingPrePass, EnableProfiling
    2121};
    2222   
    2323const llvm::cl::OptionCategory * pablo_toolchain_flags();
    2424
    25 bool DebugOptionIsSet(PabloDebugFlags flag);
     25bool DebugOptionIsSet(const PabloDebugFlags flag);
     26
     27bool CompileOptionIsSet(const PabloCompilationFlags flag);
    2628
    2729void pablo_function_passes(PabloKernel * kernel);
Note: See TracChangeset for help on using the changeset viewer.