Changeset 4286


Ignore:
Timestamp:
Nov 2, 2014, 12:09:11 PM (4 years ago)
Author:
nmedfort
Message:

Temporary check-in for CC constraint metadata.

Location:
icGREP/icgrep-devel/icgrep
Files:
6 edited

Legend:

Unmodified
Added
Removed
  • icGREP/icgrep-devel/icgrep/cc/cc_compiler.cpp

    r4285 r4286  
    3131using namespace re;
    3232using namespace pablo;
     33using namespace boost;
    3334
    3435namespace cc {
     
    4849    for (Name * name : nameMap) {
    4950        compile_re(name);
     51    }
     52    if (mAnnotateVariableConstraints) {
     53        computeVariableConstraints();
    5054    }
    5155    return std::move(mBasisBit);
     
    8589                throw std::runtime_error("Unexpected CC node given to CC_Compiler: " + Printer_RE::PrintRE(name) + " : " + Printer_RE::PrintRE(cc));
    8690            }
    87             var = mCG.createVar(mCG.createAssign(name->getName(), value));
     91            Assign * assign = mCG.createAssign(name->getName(), value);
     92            if (mAnnotateVariableConstraints && isa<CC>(cc)) {
     93                mVariableVector.push_back(std::make_pair(cast<CC>(cc), assign));
     94            }
     95            var = mCG.createVar(assign);
    8896        }
    8997        else {
     
    159167                    bit0 = mCG.createNot(bit0);
    160168                }
    161                 return tempify(mCG.createAnd(expr, bit0));
     169                return mCG.createAnd(expr, bit0);
    162170            }
    163171        }
     
    166174    for (const CharSetItem & item : *cc) {
    167175        PabloAST * temp = char_or_range_expr(item.lo_codepoint, item.hi_codepoint);
    168         expr = (expr == nullptr) ? temp : tempify(mCG.createOr(expr, temp));
     176        expr = (expr == nullptr) ? temp : mCG.createOr(expr, temp);
    169177    }
    170178    return expr;
     
    208216        for (auto i = 0; i < (bit_terms.size()/2); i++)
    209217        {
    210             new_terms.push_back(tempify(mCG.createAnd(bit_terms[(2 * i) + 1], bit_terms[2 * i])));
     218            new_terms.push_back(mCG.createAnd(bit_terms[(2 * i) + 1], bit_terms[2 * i]));
    211219        }
    212220        if (bit_terms.size() % 2 == 1)
     
    232240    if ((n2 < n1) || (diff_count > mEncoding.getBits()))
    233241    {
    234         throw std::runtime_error(std::string("Bad Range: [") + std::to_string(n1) + "," + std::to_string(n2) + "]");
     242        throw std::runtime_error("Bad Range: [" + std::to_string(n1) + "," + std::to_string(n2) + "]");
    235243    }
    236244
     
    246254    PabloAST* hi_test = LE_Range(diff_count - 1, n2 & mask1);
    247255
    248     return tempify(mCG.createAnd(common, mCG.createSel(getBasisVar(diff_count - 1), hi_test, lo_test)));
     256    return mCG.createAnd(common, mCG.createSel(getBasisVar(diff_count - 1), hi_test, lo_test));
    249257}
    250258
     
    254262    }
    255263    else if (((N % 2) == 0) && ((n >> (N - 2)) == 0)) {
    256         return tempify(mCG.createOr(tempify(mCG.createOr(getBasisVar(N - 1), getBasisVar(N - 2))), GE_Range(N - 2, n)));
     264        return mCG.createOr(mCG.createOr(getBasisVar(N - 1), getBasisVar(N - 2)), GE_Range(N - 2, n));
    257265    }
    258266    else if (((N % 2) == 0) && ((n >> (N - 2)) == 3)) {
    259         return tempify(mCG.createAnd(tempify(mCG.createAnd(getBasisVar(N - 1), getBasisVar(N - 2))), GE_Range(N - 2, n - (3 << (N - 2)))));
     267        return mCG.createAnd(mCG.createAnd(getBasisVar(N - 1), getBasisVar(N - 2)), GE_Range(N - 2, n - (3 << (N - 2))));
    260268    }
    261269    else if (N >= 1)
     
    271279              the value of GE_range(N-1), lo_range) is required.
    272280            */
    273             return tempify(mCG.createOr(getBasisVar(N - 1), lo_range));
     281            return mCG.createOr(getBasisVar(N - 1), lo_range);
    274282        }
    275283        else
     
    279287              in the target for >= and GE_range(N-1, lo_bits) must also be true.
    280288            */
    281             return tempify(mCG.createAnd(getBasisVar(N - 1), lo_range));
     289            return mCG.createAnd(getBasisVar(N - 1), lo_range);
    282290        }
    283291    }
     
    295303    }
    296304    else {
    297         return tempify(mCG.createNot(GE_Range(N, n + 1)));
     305        return mCG.createNot(GE_Range(N, n + 1));
    298306    }
    299307}
     
    313321}
    314322
    315 inline PabloAST * CC_Compiler::tempify(PabloAST * value) {
    316 //    if (isa<Var>(value)) {
    317 //        return cast<Var>(value);
    318 //    }
    319 //    return mCG.createVar(mCG.createAssign("t", value));
    320     return value;
     323void CC_Compiler::computeVariableConstraints() {
     324    typedef adjacency_list<vecS, vecS, directedS> ConstraintGraph;
     325    typedef adjacency_list<vecS, vecS, directedS> SubsetGraph;
     326
     327    typedef graph_traits<ConstraintGraph>::out_edge_iterator ConstraintEdgeIterator;
     328    typedef graph_traits<SubsetGraph>::out_edge_iterator SubsetEdgeIterator;
     329
     330    const auto n = mVariableVector.size();
     331
     332    if (n == 0) {
     333        return;
     334    }
     335
     336    // Compute the constraint and subset graphs.
     337
     338    ConstraintGraph C(n);
     339    SubsetGraph S(n);
     340
     341    for (auto i = 0; i != n; ++i) {
     342        const CC * const cc1 = mVariableVector[i].first;
     343        for (auto j = i + 1; j != n; ++j) {
     344            const CC * const cc2 = mVariableVector[i].first;
     345            switch(cc1->compare(cc2)) {
     346                case CC::Relationship::OVERLAPPING:
     347                    add_edge(i, j, C);
     348                    add_edge(j, i, C);
     349                    break;
     350                case CC::Relationship::SUBSET:
     351                    add_edge(i, j, S);
     352                    break;
     353                case CC::Relationship::SUPERSET:
     354                    add_edge(j, i, S);
     355                    break;
     356                default:
     357                    /* do nothing */
     358                    break;
     359            }
     360        }
     361    }
     362
     363    // Write out the constraints and subset relationships as metadata
     364
     365    for (auto i = 0; i != n; ++i) {
     366        std::vector<PabloAST *> constraints;
     367        ConstraintEdgeIterator ci, ci_end;
     368        for (std::tie(ci, ci_end) = out_edges(i, C); ci != ci_end; ++ci) {
     369            constraints.push_back(mVariableVector[target(*ci, C)].second);
     370        }
     371
     372        std::vector<PabloAST *> subsets;
     373        SubsetEdgeIterator si, si_end;
     374        for (std::tie(si, si_end) = out_edges(i, S); si != si_end; ++si) {
     375            subsets.push_back(mVariableVector[target(*si, S)].second);
     376        }
     377
     378        Assign * assign = mVariableVector[i].second;
     379        if (!constraints.empty()) {
     380            assign->setMetadata("constraints", PMDVector::get(std::move(constraints)));
     381        }
     382        if (!subsets.empty()) {
     383            assign->setMetadata("subsets", PMDVector::get(std::move(subsets)));
     384        }
     385    }
     386
     387
     388
    321389}
    322390
  • icGREP/icgrep-devel/icgrep/cc/cc_compiler.h

    r4284 r4286  
    1414#include <unordered_map>
    1515#include <string>
     16#include <boost/graph/adjacency_list.hpp>
    1617
    1718namespace cc {
     
    2021
    2122class CC_Compiler{
     23    typedef std::vector<std::pair<const re::CC*, pablo::Assign*>> ConstraintVector;
    2224public:
    2325
     
    2729
    2830private:
     31
    2932
    3033    pablo::PabloAST * compile_re(re::RE * re);
     
    4144    pablo::PabloAST * char_or_range_expr(const re::CodePointType lo, const re::CodePointType hi);
    4245    pablo::PabloAST * charset_expr(const re::CC *cc);
    43     pablo::PabloAST * tempify(pablo::PabloAST * value);
     46
     47    void computeVariableConstraints();
    4448
    4549private:
     
    4852    std::vector<pablo::Var *>   mBasisBit;
    4953    const Encoding              mEncoding;
     54    ConstraintVector            mVariableVector;
    5055};
    5156
  • icGREP/icgrep-devel/icgrep/pablo/analysis/useanalysis.cpp

    r4284 r4286  
    11#include "useanalysis.h"
    22#include <queue>
     3#include <iostream>
    34
    45using namespace boost;
     
    1617void UseAnalysis::cse(PabloBlock & block) {
    1718    VertexIterator vi, vi_end;
    18     auto mGraphMap = get(vertex_name, mUseDefGraph);
     19    const auto nodeOf = get(vertex_name, mUseDefGraph);
    1920    for (std::tie(vi, vi_end) = vertices(mUseDefGraph); vi != vi_end; ++vi) {
    2021        const Vertex u = *vi;
    21         const auto count = out_degree(u, mUseDefGraph) ;
     22        const auto count = out_degree(u, mUseDefGraph);
    2223        if (count > 1) {
    23             PabloAST * expr = mGraphMap[u];
     24            PabloAST * expr = nodeOf[u];
    2425            if (isa<Statement>(expr) || isa<Var>(expr)) {
    2526                continue;
     
    3536                const Vertex t = target(*ei, mUseDefGraph);
    3637                add_edge(v, t, mUseDefGraph);
    37                 PabloAST * user = mGraphMap[t];
     38                PabloAST * user = nodeOf[t];
    3839                user->replaceUsesOfWith(expr, var);
    3940            }
     
    5455inline Statement * UseAnalysis::findInsertionPointFor(const Vertex v, PabloBlock & block) {
    5556    // We want to find a predecessor of v that is the last statement in the AST.
    56     auto mGraphMap = get(vertex_name, mUseDefGraph);
     57    const auto nodeOf = get(vertex_name, mUseDefGraph);
    5758    PredecessorSet predecessors;
    5859    std::queue<Vertex> Q;
     
    6061    for (std::tie(ei, ei_end) = in_edges(v, mUseDefGraph); ei != ei_end; ++ei) {
    6162        const Vertex u = source(*ei, mUseDefGraph);
    62         PabloAST * n = mGraphMap[u];
     63        PabloAST * n = nodeOf[u];
    6364        if (isa<Statement>(n)) {
    6465            predecessors.insert(cast<Statement>(n));
     
    7273        const Vertex u = Q.front();
    7374        Q.pop();
    74         PabloAST * n = mGraphMap[u];
     75        PabloAST * n = nodeOf[u];
    7576
    7677        if (isa<Statement>(n)) {
     
    116117
    117118void UseAnalysis::dce() {
    118     auto mGraphMap = get(vertex_name, mUseDefGraph);
     119    const auto nodeOf = get(vertex_name, mUseDefGraph);
    119120    std::queue<Vertex> Q;
    120121    // gather up all of the nodes that aren't output assignments and have no users
     
    123124        const Vertex v = *vi;
    124125        if (out_degree(v, mUseDefGraph) == 0) {
    125             PabloAST * n = mGraphMap[v];
     126            PabloAST * n = nodeOf[v];
    126127            if (!isa<Assign>(n) || (cast<Assign>(n)->isOutputAssignment())) {
    127128                continue;
     
    133134        const Vertex v = Q.front();
    134135        Q.pop();
    135         PabloAST * n = mGraphMap[v];
     136        PabloAST * n = nodeOf[v];
    136137        if (isa<Assign>(n)) {
    137138            cast<Assign>(n)->removeFromParent();
     
    154155            gatherUseDefInformation(v, assign->getExpr());
    155156        }
    156         if (const Next * next = dyn_cast<Next>(stmt)) {
    157             gatherUseDefInformation(v, next->getExpr());
    158         }
    159157        else if (const If * ifStatement = dyn_cast<If>(stmt)) {
    160158            gatherUseDefInformation(v, ifStatement->getCondition());
     
    164162            gatherUseDefInformation(v, whileStatement->getCondition());
    165163            gatherUseDefInformation(v, whileStatement->getBody());
     164        }
     165        else if (isa<Next>(stmt)) {
     166            throw std::runtime_error("Next node is illegal in main block!");
    166167        }
    167168    }
     
    176177        }
    177178        else if (const Next * next = dyn_cast<Next>(stmt)) {
    178             add_edge(u, find(next->getInitial()), mUseDefGraph);
     179            add_edge(find(next->getInitial()), u, mUseDefGraph);
    179180            gatherUseDefInformation(u, next->getExpr());
    180181        }
  • icGREP/icgrep-devel/icgrep/pablo/pe_metadata.h

    r4285 r4286  
    3030class PMDVector : public PMDNode, public std::vector<PabloAST*> {
    3131public:
    32     PMDVector * get(std::vector<PabloAST*> && vec) {
     32    inline static PMDVector * get(std::vector<PabloAST*> && vec) {
    3333        return new PMDVector(std::move(vec));
    3434    }
  • icGREP/icgrep-devel/icgrep/re/re_cc.cpp

    r4285 r4286  
    66
    77#include "re_cc.h"
     8#include <llvm/Support/Compiler.h>
    89
    910namespace re {
     
    8384}
    8485
    85 CC::Relationship CC::compare(const CC * a, const CC * b) {
     86CC::Relationship CC::compare(const CC * other) const {
    8687
    87     auto ai = a->cbegin();
    88     const auto ai_end = a->cend();
    89     auto bi = b->cbegin();
    90     const auto bi_end = b->cend();
     88    if (LLVM_UNLIKELY(other == this)) {
     89        return Relationship::EQUIVALENT;
     90    }
    9191
    92     bool A_cannot_be_a_subset_of_B = false;
    93     bool B_cannot_be_a_subset_of_A = false;
     92    auto ai = cbegin();
     93    const auto ai_end = cend();
     94    auto bi = other->cbegin();
     95    const auto bi_end = other->cend();
     96
     97    bool nonSubset = false;
     98    bool nonSuperset = false;
    9499    bool disjoint = true;
    95 
    96100
    97101    while (ai != ai_end && bi != bi_end) {
     
    101105        if (ra.hi_codepoint < rb.lo_codepoint) {
    102106            ++ai;
    103             B_cannot_be_a_subset_of_A = true;
     107            nonSuperset = true;
    104108            continue;
    105109        }
    106110        if (rb.hi_codepoint < ra.lo_codepoint) {
    107111            ++bi;
    108             A_cannot_be_a_subset_of_B = true;
     112            nonSubset = true;
    109113            continue;
    110114        }
     
    113117
    114118        if (ra.lo_codepoint < rb.lo_codepoint) {
    115             A_cannot_be_a_subset_of_B = true;
     119            nonSubset = true;
    116120        }
    117121
    118122        if (rb.lo_codepoint < ra.lo_codepoint) {
    119             B_cannot_be_a_subset_of_A = true;
     123            nonSuperset = true;
    120124        }
    121125
     
    133137
    134138    if (ai == ai_end && bi != bi_end) {
    135         B_cannot_be_a_subset_of_A = true;
     139        nonSuperset = true;
    136140    }
    137     if (bi == bi_end && ai != ai_end) {
    138         A_cannot_be_a_subset_of_B = true;
     141    else if (bi == bi_end && ai != ai_end) {
     142        nonSubset = true;
    139143    }
    140144
    141     if (A_cannot_be_a_subset_of_B && B_cannot_be_a_subset_of_A) {
     145    if (nonSubset && nonSuperset) {
    142146        return Relationship::OVERLAPPING;
    143147    }
    144     else if (A_cannot_be_a_subset_of_B) {
    145         return Relationship::B_SUBSET_A;
     148    else if (nonSubset) {
     149        return Relationship::SUPERSET;
    146150    }
    147     else {
    148         return Relationship::A_SUBSET_B;
     151    else if (nonSuperset) {
     152        return Relationship::SUBSET;
    149153    }
     154    return Relationship::EQUIVALENT;
    150155}
    151156
  • icGREP/icgrep-devel/icgrep/re/re_cc.h

    r4285 r4286  
    3737
    3838    enum class Relationship {
    39         A_SUBSET_B
    40         , B_SUBSET_A
     39        SUBSET
     40        , SUPERSET
    4141        , DISJOINT
    4242        , OVERLAPPING
     43        , EQUIVALENT
    4344    };
    44 
    45     static Relationship compare(const CC * a, const CC * b);
    4645
    4746    typedef CharSetVector::iterator                 iterator;
     
    114113        return mSparseCharSet.empty();
    115114    }
     115
     116    Relationship compare(const CC * other) const;
    116117
    117118    virtual ~CC() {}
Note: See TracChangeset for help on using the changeset viewer.