Changeset 4594 for icGREP


Ignore:
Timestamp:
Jun 4, 2015, 4:28:10 PM (4 years ago)
Author:
nmedfort
Message:

Added ability to infer mutual exclusivity / subset relationships based on already proven relationships. Simplifer can now eliminate If nodes whenever all of the defined vars are Zeroes.

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

Legend:

Unmodified
Added
Removed
  • icGREP/icgrep-devel/icgrep/CMakeLists.txt

    r4587 r4594  
    279279SET(CMAKE_CXX_FLAGS_RELEASE "${CMAKE_CXX_FLAGS} -O3 -DNDEBUG")
    280280IF (${CMAKE_SYSTEM} MATCHES "Linux")
    281     SET(CMAKE_CXX_FLAGS_DEBUG "${CMAKE_CXX_FLAGS} -g -fsanitize=alignment")
     281    SET(CMAKE_CXX_FLAGS_DEBUG "${CMAKE_CXX_FLAGS} -g -fsanitize=address")
    282282ENDIF()
    283283
  • icGREP/icgrep-devel/icgrep/compiler.cpp

    r4592 r4594  
    6363                                      cl::cat(cPabloOptimizationsOptions));
    6464#ifdef ENABLE_MULTIPLEXING
    65 static cl::opt<bool> PabloMutualExclusionPass("mutual-exclusion", cl::init(false),
     65static cl::opt<bool> PabloMutualExclusionPass("csme", cl::init(true),
    6666                                      cl::desc("Multiplex Advances whose inputs are mutual exclusive and replace any contradictory stream with Zero."),
    6767                                      cl::cat(cPabloOptimizationsOptions));
     
    168168        CodeSinking::optimize(main);
    169169    }
    170 
    171170    #ifdef ENABLE_MULTIPLEXING
    172171    if (PabloMutualExclusionPass) {
    173         AutoMultiplexing::optimize(basisBits, main);
     172        if (AutoMultiplexing::optimize(basisBits, main) && !DisablePabloCSE) {
     173            Simplifier::optimize(main);
     174        }
    174175    }
    175176    #endif
  • icGREP/icgrep-devel/icgrep/pablo/optimizers/pablo_automultiplexing.cpp

    r4592 r4594  
    2323namespace pablo {
    2424
    25 void AutoMultiplexing::optimize(const std::vector<Var *> & input, PabloBlock & entry) {
     25bool AutoMultiplexing::optimize(const std::vector<Var *> & input, PabloBlock & entry) {
    2626    AutoMultiplexing am;
    2727    am.initialize(input, entry);
     
    3636        am.multiplexSelectedIndependentSets();
    3737        am.topologicalSort(entry);
    38     }
     38        return true;
     39    }
     40    return false;
    3941}
    4042
     
    175177    // edges as we're writing them to obtain the transposed graph.
    176178    mConstraintGraph = ConstraintGraph(m);
     179    mSubsetGraph = SubsetGraph(m);
    177180    for (unsigned j = 0; j != m; ++j) {
    178181        for (unsigned i = 0; i != m; ++i) {
     
    185188    // Initialize the BDD engine ...
    186189    mManager = Cudd_Init((complex.size() + vars.size()), 0, CUDD_UNIQUE_SLOTS, CUDD_CACHE_SLOTS, 0);
     190    Cudd_AutodynDisable(mManager);
    187191
    188192    // Map the predefined 0/1 entries
     
    211215    std::vector<std::pair<DdNode *, DdNode *>> advances; // the input BDD and the BDD variable of the i-th Advance
    212216    std::stack<Statement *> scope;
     217    std::vector<bool> unconstrained(mAdvance.size());
     218    advances.reserve(mAdvance.size());
     219
     220    // TODO: What if we did some minterm analysis in here? We'd need to be careful to keep the Advances properly indexed.
    213221
    214222    // Scan through and collect all the advances, calls, scanthrus and matchstars ...
     
    267275                    break;
    268276                case PabloAST::ClassTypeId::ScanThru:
    269                     // It may be possible use "mEngine.applyNot(input[1])" for ScanThrus if we rule out the
    270                     // possibility of a contradition being erroneously calculated later. An example of this
    271                     // would be ¬(ScanThru(c,m) √ m) but are there others that would be harder to predict?
     277                    // It may be possible use "Not(input[1])" for ScanThrus if we rule out the possibility
     278                    // of a contradition being erroneously calculated later. An example of this
     279                    // would be ¬(ScanThru(c,m) √ m)
    272280                case PabloAST::ClassTypeId::MatchStar:
    273281                    if (LLVM_UNLIKELY(isZero(input[0]) || isZero(input[1]))) {
     
    292300                        assert (mCharacterizationMap.count(stmt));
    293301                        DdNode * const Ik = input[0];
    294                         DdNode * const Vk = bdd = mCharacterizationMap[stmt];
     302                        DdNode * Ck = mCharacterizationMap[stmt];
     303                        DdNode * const Nk = Not(Ck);
     304
    295305                        const unsigned k = advances.size();
    296306
     307                        std::fill(unconstrained.begin(), unconstrained.end(), false);
     308
     309                        // Instead of processing these sequentially, look at the existing subset relationships incase we can infer
     310                        // more things sooner?
    297311                        for (unsigned i = 0; i != k; ++i) {
    298312
    299313                            Advance * adv = mAdvance[i];
    300                             DdNode * Ii = std::get<0>(advances[i]);
    301                             DdNode * Vi = std::get<1>(advances[i]);
    302 
    303                             // We could probably avoid some tests by infering that if X ⊂ Y and Y ⊂ Z then X ⊂ Z too. Will need a
    304                             // more complex graph structure for storing subset edges. Similarly if X ∩ Y = âˆ
    305  and Z ⊂ X, Z ∩ Y = âˆ
    306 
    307314
    308315                            // Only test pairs if they are in the same scope or one has a user in the a scope that is reachable by
    309316                            // the other?
    310317
    311                             bool constrained = true;
     318                            bool constrained = !unconstrained[i];
    312319
    313320                            // If these advances are "shifting" their values by the same amount and aren't transitively dependant ...
    314                             if ((stmt->getOperand(1) == adv->getOperand(1)) && (!edge(k, i, mPathGraph).second)) {
    315                                 // Test this with Cudd_And, Cudd_bddIntersect (and maybe Cudd_bddLeq?) to see which is faster ...
    316                                 DdNode * const tmp = Cudd_bddIntersect(mManager, Ik, Ii);
    317                                 Cudd_Ref(tmp);
     321                            if (constrained && (stmt->getOperand(1) == adv->getOperand(1)) && (notTransitivelyDependant(k, i))) {
     322                                DdNode * Ii = std::get<0>(advances[i]);
     323                                DdNode * Ni = std::get<1>(advances[i]);
     324                                // TODO: test both Cudd_And and Cudd_bddIntersect to see which is faster
     325                                DdNode * const IiIk = Cudd_bddIntersect(mManager, Ik, Ii); Cudd_Ref(IiIk);
    318326                                // Is there any satisfying truth assignment? If not, these streams are mutually exclusive.
    319                                 if (noSatisfyingAssignment(tmp)) {
     327                                if (noSatisfyingAssignment(IiIk)) {
    320328                                    assert (mCharacterizationMap.count(adv));
    321 
    322                                     DdNode *& other = mCharacterizationMap[adv];
     329                                    DdNode *& Ci = mCharacterizationMap[adv];
    323330                                    // mark the i-th and k-th Advances as being mutually exclusive
    324                                     bdd = And(bdd, Not(Vi));
    325                                     other = And(other, Not(Vk));
     331                                    Ck = And(Ck, Ni);
     332                                    Ci = And(Ci, Nk);
     333                                    // If Ai ∩ Ak = âˆ
     334 and Aj ⊂ Ai, Aj ∩ Ak = âˆ
     335.
     336                                    graph_traits<SubsetGraph>::in_edge_iterator ei, ei_end;
     337                                    for (std::tie(ei, ei_end) = in_edges(i, mSubsetGraph); ei != ei_end; ++ei) {
     338                                        const auto j = source(*ei, mSubsetGraph);
     339                                        if (j > i && notTransitivelyDependant(k, j)) {
     340                                            assert (mCharacterizationMap.count(mAdvance[j]));
     341                                            DdNode *& Cj = mCharacterizationMap[mAdvance[j]];
     342                                            DdNode * Nj = std::get<1>(advances[j]);
     343                                            // Mark the i-th and j-th Advances as being mutually exclusive
     344                                            Ck = And(Ck, Nj);
     345                                            Cj = And(Cj, Nk);
     346                                            unconstrained[j] = true;
     347                                        }
     348                                    }
    326349                                    constrained = false;
    327350                                }
    328                                 else if (Ik == tmp) {
    329                                     // If Ik = Ii ∩ Ik then Ik (the input to the k-th advance) is a *subset* of Ii (the input of the
    330                                     // i-th advance). Record this in the subset graph with the arc (k,i). These edges will be moved into the
    331                                     // multiplex set graph if Advance_i and Advance_k happen to be in the same mutually exclusive set.
    332                                     mSubsetGraph.emplace_back(k, i);
     351                                else if (Ik == IiIk) {
     352                                    // If Ik = Ii ∩ Ik then Ik ⊂ Ii. Record this in the subset graph with the arc (k,i).
     353                                    // These edges will be moved into the multiplex set graph if Ai and Ak happen to be
     354                                    // in the same mutually exclusive set.
     355                                    add_edge(k, i, mSubsetGraph);
     356                                    // If Ak ⊂ Ai and Ai ⊂ Aj, Ak ⊂ Aj.
     357                                    graph_traits<SubsetGraph>::out_edge_iterator ei, ei_end;
     358                                    for (std::tie(ei, ei_end) = out_edges(i, mSubsetGraph); ei != ei_end; ++ei) {
     359                                        const auto j = target(*ei, mSubsetGraph);
     360                                        if (j > i) {
     361                                            add_edge(k, j, mSubsetGraph);
     362                                            unconstrained[j] = true;
     363                                        }
     364                                    }
    333365                                    constrained = false;
    334366                                }
    335                                 else if (Ii == tmp) {
    336                                     mSubsetGraph.emplace_back(i, k);
     367                                else if (Ii == IiIk) {
     368                                    // If Ii = Ii ∩ Ik then Ii ⊂ Ik. Record this in the subset graph with the arc (i,k).
     369                                    add_edge(i, k, mSubsetGraph);
     370                                    // If Ai ⊂ Ak and Aj ⊂ Ai, Aj ⊂ Ak.
     371                                    graph_traits<SubsetGraph>::in_edge_iterator ei, ei_end;
     372                                    for (std::tie(ei, ei_end) = in_edges(i, mSubsetGraph); ei != ei_end; ++ei) {
     373                                        const auto j = source(*ei, mSubsetGraph);
     374                                        if (j > i) {
     375                                            add_edge(j, k, mSubsetGraph);
     376                                            unconstrained[j] = true;
     377                                        }
     378                                    }
    337379                                    constrained = false;
    338380                                }
    339                                 Cudd_RecursiveDeref(mManager, tmp);
     381                                Cudd_RecursiveDeref(mManager, IiIk);
    340382                            }
    341383
     
    350392                        // Append this advance to the list of known advances. Both its input BDD and the Advance variable are stored in
    351393                        // the list to eliminate the need for searching for it.
    352                         advances.emplace_back(Ik, Vk);
     394                        advances.emplace_back(Ik, Nk);
    353395                        testContradiction = false;
     396                        bdd = Ck;
    354397                    }
    355398                    break;
     
    362405            }
    363406            if (LLVM_UNLIKELY(testContradiction && noSatisfyingAssignment(bdd))) {               
    364                 if (!isa<Assign>(stmt) || cast<Assign>(stmt)->superfluous()) {
     407                if (!isa<Assign>(stmt)) {
    365408                    Cudd_RecursiveDeref(mManager, bdd);
    366409                    stmt = stmt->replaceWith(entry.createZeroes());
     
    380423
    381424/** ------------------------------------------------------------------------------------------------------------- *
     425 * @brief notTransitivelyDependant
     426 ** ------------------------------------------------------------------------------------------------------------- */
     427inline bool AutoMultiplexing::notTransitivelyDependant(const PathGraph::vertex_descriptor i, const PathGraph::vertex_descriptor j) const {
     428    return (mPathGraph.get_edge(i, j) == 0);
     429}
     430
     431/** ------------------------------------------------------------------------------------------------------------- *
    382432 * @brief CUDD wrappers
    383433 ** ------------------------------------------------------------------------------------------------------------- */
    384434
    385435inline DdNode * AutoMultiplexing::Zero() const {
    386     DdNode * r = Cudd_ReadLogicZero(mManager);
    387     Cudd_Ref(r);
    388     return r;
     436    return Cudd_ReadLogicZero(mManager);
    389437}
    390438
    391439inline DdNode * AutoMultiplexing::One() const {
    392     DdNode * r = Cudd_ReadOne(mManager);
    393     Cudd_Ref(r);
    394     return r;
    395 }
    396 
    397 inline bool AutoMultiplexing::isZero(DdNode * x) const {
    398     return x == Cudd_ReadLogicZero(mManager);
    399 }
    400 
    401 inline DdNode * AutoMultiplexing::And(DdNode * x, DdNode * y) {
     440    return Cudd_ReadOne(mManager);
     441}
     442
     443inline bool AutoMultiplexing::isZero(DdNode * const x) const {
     444    return x == Zero();
     445}
     446
     447inline DdNode * AutoMultiplexing::And(DdNode * const x, DdNode * const y) {
    402448    DdNode * r = Cudd_bddAnd(mManager, x, y);
    403449    Cudd_Ref(r);
     
    405451}
    406452
    407 inline DdNode * AutoMultiplexing::Or(DdNode * x, DdNode * y) {
     453inline DdNode * AutoMultiplexing::Or(DdNode * const x, DdNode * const y) {
    408454    DdNode * r = Cudd_bddOr(mManager, x, y);
    409455    Cudd_Ref(r);
     
    411457}
    412458
    413 inline DdNode * AutoMultiplexing::Xor(DdNode * x, DdNode * y) {
     459inline DdNode * AutoMultiplexing::Xor(DdNode * const x, DdNode * const y) {
    414460    DdNode * r = Cudd_bddXor(mManager, x, y);
    415461    Cudd_Ref(r);
     
    417463}
    418464
    419 inline DdNode * AutoMultiplexing::Not(DdNode * x) {
     465inline DdNode * AutoMultiplexing::Not(DdNode * const x) const {
    420466    return Cudd_Not(x);
    421467}
    422468
    423 inline DdNode * AutoMultiplexing::Ite(DdNode * x, DdNode * y, DdNode * z) {
     469inline DdNode * AutoMultiplexing::Ite(DdNode * const x, DdNode * const y, DdNode * const z) {
    424470    DdNode * r = Cudd_bddIte(mManager, x, y, z);
    425471    Cudd_Ref(r);
     
    427473}
    428474
    429 inline bool AutoMultiplexing::noSatisfyingAssignment(DdNode * x) {
    430     return Cudd_bddLeq(mManager, x, Cudd_ReadLogicZero(mManager));
     475inline bool AutoMultiplexing::noSatisfyingAssignment(DdNode * const x) {
     476    return Cudd_bddLeq(mManager, x, Zero());
    431477}
    432478
     
    622668    // Add in any edges from our subset constraints to M that are within the same set.
    623669    bool hasSubsetConstraint = false;
    624     for (const auto & ei : mSubsetGraph) {
    625         const auto u = ei.first;
    626         const auto v = ei.second;
     670
     671    graph_traits<SubsetGraph>::edge_iterator ei, ei_end;
     672    for (std::tie(ei, ei_end) = edges(mSubsetGraph); ei != ei_end; ++ei) {
     673        const auto u = source(*ei, mSubsetGraph);
     674        const auto v = target(*ei, mSubsetGraph);
    627675        graph_traits<MultiplexSetGraph>::in_edge_iterator ej, ej_end;
    628676        // If both the source and target of ei are adjacent to the same vertex, that vertex must be the
     
    744792}
    745793
    746 struct CreateOr {
    747     CreateOr(PabloBlock * pb) : mPb(pb) {}
    748     PabloAST * operator() (PabloAST * x, PabloAST * y) { return mPb->createOr(x, y); }
    749     PabloBlock * mPb;
    750 };
    751 
    752 struct CreateAnd {
    753     CreateAnd(PabloBlock * pb) : mPb(pb) {}
    754     PabloAST * operator() (PabloAST * x, PabloAST * y) { return mPb->createAnd(x, y); }
    755     PabloBlock * mPb;
    756 };
    757 
    758794/** ------------------------------------------------------------------------------------------------------------- *
    759795 * @brief multiplexSelectedIndependentSets
     
    808844            }
    809845            #endif
    810 
    811             ExpressionMap<PabloAST *, PabloAST *> expMap(nullptr);
    812846
    813847            /// Perform n-to-m Multiplexing
     
    839873                    assert (!Q.full());
    840874                    pb->setInsertPoint(choose(a2, a1, adv));
    841                     CreateOr createOr(pb);
    842                     PabloAST * tmp = expMap.findOrCall(createOr, PabloAST::ClassTypeId::Or, a1, a2); assert (tmp);
    843                     Q.push_back(tmp);
     875                    Q.push_back(pb->createOr(a1, a2));
    844876                }
    845877                assert (Q.size() == 1);
     
    872904                        PabloAST * a2 = Q.front(); Q.pop_front(); assert (a2);
    873905                        assert (!Q.full());
    874                         CreateOr createOr(pb);
    875                         PabloAST * tmp = expMap.findOrCall(createOr, PabloAST::ClassTypeId::Or, a1, a2); assert (tmp);
    876                         Q.push_back(tmp);
     906                        Q.push_back(pb->createOr(a1, a2));
    877907                    }
    878908                    assert (Q.size() == 1);
     
    895925                    PabloAST * a2 = Q.front(); Q.pop_front(); assert (a2);
    896926                    assert (!Q.full());
    897                     CreateAnd createAnd(pb);
    898                     PabloAST * tmp = expMap.findOrCall(createAnd, PabloAST::ClassTypeId::And, a1, a2); assert (tmp);
    899                     Q.push_back(tmp);
     927                    Q.push_back(pb->createAnd(a1, a2));
    900928                }
    901929
     
    904932                PabloAST * demux = Q.front(); Q.pop_front(); assert (demux);
    905933                if (LLVM_LIKELY(neg != nullptr)) {
    906                     CreateAnd createAnd(pb);
    907                     demux = expMap.findOrCall(createAnd, PabloAST::ClassTypeId::And, demux, neg); assert (demux);
     934                    demux = pb->createAnd(demux, neg);
    908935                }
    909936                V[i - 1]->replaceWith(demux, true, true);
  • icGREP/icgrep-devel/icgrep/pablo/optimizers/pablo_automultiplexing.hpp

    r4592 r4594  
    2626    using IndependentSetGraph = boost::adjacency_list<boost::hash_setS, boost::listS, boost::undirectedS, std::pair<unsigned, MultiplexSetGraph::vertex_descriptor>>;
    2727    using ChosenSets = std::vector<MultiplexSetGraph::vertex_descriptor>;
    28     using SubsetGraph = std::vector<std::pair<MultiplexSetGraph::vertex_descriptor, MultiplexSetGraph::vertex_descriptor>>;
     28    using SubsetGraph = boost::adjacency_list<boost::hash_setS, boost::vecS, boost::bidirectionalS>;
    2929    using Advances = std::vector<Advance *>;
    30     using TopologicalSortGraph = boost::adjacency_list<boost::hash_setS, boost::vecS, boost::bidirectionalS, Statement *>;
    31     using TopologicalSortQueue = std::queue<TopologicalSortGraph::vertex_descriptor>;
    32     using TopologicalSortMap = boost::container::flat_map<PabloAST *, TopologicalSortGraph::vertex_descriptor>;
    3330
    3431    using RNG = std::mt19937;
     
    4037
    4138public:
    42     static void optimize(const std::vector<Var *> & input, PabloBlock & entry);
     39    static bool optimize(const std::vector<Var *> & input, PabloBlock & entry);
    4340protected:
    4441    void initialize(const std::vector<Var *> & vars, const PabloBlock & entry);
    45     void characterize(PabloBlock & entry);   
     42    void characterize(PabloBlock & entry);
     43    bool notTransitivelyDependant(const PathGraph::vertex_descriptor i, const PathGraph::vertex_descriptor j) const;
    4644    void createMultiplexSetGraph();
    4745    bool generateMultiplexSets(RNG & rng);   
     
    5755    DdNode * Zero() const;
    5856    DdNode * One() const;
    59     bool isZero(DdNode * x) const;
    60     DdNode * And(DdNode * x, DdNode * y);
    61     DdNode * Or(DdNode * x, DdNode * y);
    62     DdNode * Xor(DdNode * x, DdNode * y);
    63     DdNode * Not(DdNode * x);
    64     DdNode * Ite(DdNode * x, DdNode * y, DdNode * z);
    65     bool noSatisfyingAssignment(DdNode * x);
     57    bool isZero(DdNode * const x) const;
     58    DdNode * And(DdNode * const x, DdNode * const y);
     59    DdNode * Or(DdNode * const x, DdNode * const y);
     60    DdNode * Xor(DdNode * const x, DdNode * const y);
     61    DdNode * Not(DdNode * x) const;
     62    DdNode * Ite(DdNode * const x, DdNode * const y, DdNode * const z);
     63    bool noSatisfyingAssignment(DdNode * const x);
    6664    void shutdown();
    6765private:
  • icGREP/icgrep-devel/icgrep/pablo/optimizers/pablo_simplifier.cpp

    r4569 r4594  
    6464            }
    6565        }
    66         else if (isa<If>(stmt)) {
     66        else if (If * ifNode = dyn_cast<If>(stmt)) {
     67            // Check to see if the Cond is Zero and delete the loop.
     68            if (LLVM_UNLIKELY(isa<Zeroes>(ifNode->getCondition()))) {
     69                for (PabloAST * defVar : ifNode->getDefined()) {
     70                    cast<Assign>(defVar)->replaceWith(block.createZeroes(), false, true);
     71                }
     72                stmt = stmt->eraseFromParent(true);
     73                continue;
     74            }
     75            // Process the If body
    6776            eliminateRedundantCode(cast<If>(stmt)->getBody(), &encountered);
     77            // Scan through and replace any defined variable that is assigned Zero with a Zero object
     78            // and remove it from the defined variable list.
     79            If::DefinedVars & defVars = ifNode->getDefined();
     80            for (auto i = defVars.begin(); i != defVars.end(); ) {
     81                Assign * defVar = cast<Assign>(*i);
     82                if (LLVM_UNLIKELY(isa<Zeroes>(defVar->getExpr()))) {
     83                    i = defVars.erase(i);
     84                    defVar->replaceWith(block.createZeroes(), false, true);
     85                    continue;
     86                }
     87                ++i;
     88            }
     89            // If we ended up Zero-ing out all of the defined variables, delete the If node.
     90            if (LLVM_UNLIKELY(defVars.empty())) {
     91                stmt = stmt->eraseFromParent(true);
     92                continue;
     93            }
    6894        }
    6995        else if (isa<While>(stmt)) {
  • icGREP/icgrep-devel/icgrep/pablo/pabloAST.cpp

    r4592 r4594  
    185185        mOperand[i]->removeUser(this);
    186186    }
     187    // If this is an If or While statement, we'll have to remove the statements within the
     188    // body or we'll lose track of them.
     189    if (LLVM_UNLIKELY(isa<If>(this) || isa<While>(this))) {
     190        if (isa<If>(this)) {
     191            // Eliminate the relationship between the If node and its defined vars ...
     192            for (PabloAST * var : cast<If>(this)->getDefined()) {
     193                var->removeUser(this);
     194                this->removeUser(var);
     195                var->replaceAllUsesWith(mParent->createZeroes());
     196            }
     197        }
     198        PabloBlock & body = isa<If>(this) ? cast<If>(this)->getBody() : cast<While>(this)->getBody();
     199        Statement * stmt = body.front();
     200        while (stmt) {
     201            stmt = stmt->eraseFromParent(recursively);
     202        }
     203    }
     204
    187205    if (recursively) {
    188206        for (auto i = 0; i != mOperands; ++i) {
  • icGREP/icgrep-devel/icgrep/pablo/ps_if.h

    r4541 r4594  
    1717class If : public Statement {
    1818    friend class PabloBlock;
     19    friend class Statement;
     20    friend class Simplifier;
    1921public:
    2022    using DefinedVars = std::vector<PabloAST *, VectorAllocator>;
     
    4244    }
    4345protected:
     46    inline DefinedVars & getDefined() {
     47        return mDefined;
     48    }
    4449    If(PabloAST * expr, const std::initializer_list<Assign *> definedVars, PabloBlock & body, PabloBlock * parent);
    4550
Note: See TracChangeset for help on using the changeset viewer.