Changeset 4521 for icGREP


Ignore:
Timestamp:
Feb 26, 2015, 3:35:19 PM (4 years ago)
Author:
nmedfort
Message:

added code sinking module; disabled by default as it hurts performance unless if-insertions occur.

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

Legend:

Unmodified
Added
Removed
  • icGREP/icgrep-devel/icgrep/compiler.cpp

    r4516 r4521  
    1818#include <pablo/pablo_compiler.h>
    1919#include <pablo/optimizers/pablo_simplifier.hpp>
     20#include <pablo/optimizers/pablo_codesinking.hpp>
    2021#include "UCD/precompiled_gc.h"
    2122#include "UCD/precompiled_sc.h"
     
    4849static cl::opt<bool> PrintOptimizedREcode("print-pablo", cl::init(false), cl::desc("print final optimized Pablo code"), cl::cat(dPabloDumpOptions));
    4950
     51
     52cl::OptionCategory cPabloOptimizationsOptions("Pablo Optimizations",
     53                                              "These options enable optional Pablo optimization passes. (Disabled by default.)");
     54
     55static cl::opt<bool> PabloSinkingPass("sinking", cl::init(false),
     56                                      cl::desc("Moves all instructions into the innermost legal If-scope so that they are only executed when needed."),
     57                                      cl::cat(cPabloOptimizationsOptions));
    5058
    5159using namespace re;
     
    141149    // Scan through the pablo code and perform DCE and CSE
    142150    Simplifier::optimize(main);
    143 
     151    if (PabloSinkingPass) {
     152        CodeSinking::optimize(main);
     153    }
    144154    if (PrintOptimizedREcode) {
    145155      //Print to the terminal the AST that was generated by the pararallel bit-stream compiler.
  • icGREP/icgrep-devel/icgrep/icgrep-devel.files

    r4511 r4521  
    288288pablo/symbol_generator.h
    289289pablo/builder.cpp
     290pablo/optimizers/pablo_codesinking.cpp
     291pablo/optimizers/pablo_codesinking.hpp
  • icGREP/icgrep-devel/icgrep/pablo/codegenstate.cpp

    r4518 r4521  
    405405, mOnes(new Ones())
    406406, mSymbolGenerator(symbolGenerator)
    407 , mPredecessor(nullptr)
     407, mParent(nullptr)
    408408{
    409409
     
    415415, mOnes(predecessor->mOnes) // inherit the original "Ones" variable for simplicity
    416416, mSymbolGenerator(predecessor->mSymbolGenerator)
    417 , mPredecessor(predecessor)
     417, mParent(predecessor)
    418418{
    419419
  • icGREP/icgrep-devel/icgrep/pablo/codegenstate.h

    r4511 r4521  
    7474    }
    7575
    76     inline static PabloBlock & Create(PabloBlock & predecessor) {
    77         return *(new PabloBlock(&predecessor));
     76    inline static PabloBlock & Create(PabloBlock & parent) {
     77        return *(new PabloBlock(&parent));
    7878    }
    7979
     
    168168    inline Integer * getInteger(Integer::integer_t value) {
    169169        return mSymbolGenerator.getInteger(value);
     170    }
     171
     172    inline PabloBlock * getParent() const {
     173        return mParent;
    170174    }
    171175
     
    191195    Ones * const                                        mOnes;
    192196    SymbolGenerator &                                   mSymbolGenerator;
    193     PabloBlock *                                        mPredecessor;
     197    PabloBlock *                                        mParent;
    194198};
    195199
  • icGREP/icgrep-devel/icgrep/pablo/optimizers/pablo_automultiplexing.cpp

    r4287 r4521  
    11#include "pablo_automultiplexing.hpp"
    2 #include <pablo/pe_metadata.h>
    3 #include <pablo/pe_advance.h>
    4 
     2#include <pablo/codegenstate.h>
    53#include <llvm/ADT/SmallVector.h>
    64#include <llvm/ADT/DenseMap.h>
    75#include <llvm/ADT/DenseSet.h>
    8 #include <boost/pool/object_pool.hpp>
    96
    107
     
    2320    // identifySuffixConstraints
    2421
     22
     23
     24}
     25
     26struct AnnotatedStatement {
     27    Statement * mNode;
     28    PabloAST *  mOutput;
     29    bool        mNegated;
     30};
     31
     32void AutoMultiplexing::identifyInputVariables(const PabloBlock & block) {
     33
     34    for (const Statement * stmt : block) {
     35
     36
     37
     38        if (isa<If>(stmt) || isa<While>(stmt)) {
     39            // Process any statements we found to determine their constraints. Purge the statement list afterwards.
     40
     41            if (isa<If>(stmt)) {
     42                identifyInputVariables(cast<If>(stmt)->getBody());
     43            }
     44            else {
     45                identifyInputVariables(cast<While>(stmt)->getBody());
     46            }
     47            continue;
     48        }
     49
     50
     51
     52        if (isa<Advance>(stmt)) {
     53            // The result of an Advance(expr,n) is the input expr advanced by n.
     54
     55        }
     56        else if (isa<ScanThru>(stmt)) {
     57            // The result of a ScanThru(from, thru) is anything starting from the "from" and cannot be something in "thru"
     58
     59        }
     60        else if (isa<MatchStar>(stmt)) {
     61            // The result of a MatchStar(marker, charclass) is anything starting from the "marker" and cannot be something in "charclass"
     62
     63            // Logically this is similar to ScanThru but only one "marker" can preceed each "charclass" in that case.
     64            // Could we prove whether ScanThru can be used in place of MatchStar and generalize the concept?
     65
     66
     67
     68        }
     69
     70
     71    }
    2572
    2673
  • icGREP/icgrep-devel/icgrep/pablo/optimizers/pablo_codesinking.cpp

    r4516 r4521  
    11#include "pablo_codesinking.hpp"
    2 #include <pablo/printer_pablos.h>
    3 #include <iostream>
    42
    53namespace pablo {
     
    75bool CodeSinking::optimize(PabloBlock & block)
    86{
    9     // determine the block dominator "tree"
    10     sink(block);
     7    CodeSinking lcf;
     8    lcf.sink(block);
    119    return true;
    1210}
     
    1917}
    2018
    21 //void CodeSinking::buildDominatorTree(PabloBlock & block) {
    22 //    Statement * stmt = block.front();
    23 //    while (stmt) {
    24 //        if (isa<If>(stmt)) {
    25 //            buildDominatorTree(cast<If>(stmt)->getBody());
    26 //        }
    27 //        else if (isa<While>(stmt)) {
    28 //            buildDominatorTree(cast<While>(stmt)->getBody());
    29 //        }
     19void CodeSinking::sink(PabloBlock & block) {
    3020
    31 //        stmt = stmt->getNextNode();
    32 //    }
    33 //}
    34 
    35 void CodeSinking::sink(PabloBlock & block) {
    3621    Statement * stmt = block.back();
    3722    while (stmt) {
     
    3924        if (isa<If>(stmt)) {
    4025            If * ifNode = cast<If>(stmt);
     26            assert (ifNode->getParent() == &block);
    4127            sink(ifNode->getBody());
    4228        }
    4329        else if (isa<While>(stmt)) {
    44             sink(cast<While>(stmt)->getBody());
     30            While * whileNode = cast<While>(stmt);
     31            assert (whileNode->getParent() == &block);
     32            sink(whileNode->getBody());
    4533        }
    4634        else if (isSafeToMove(stmt)) {
    47             const PabloBlock * usedInBlock = nullptr;
    48             bool usedInOnlyOneBlock = true;
     35
     36            BlockSetVector ancestors;
     37            bool canSinkInstruction = false;
    4938            for (const PabloAST * u : stmt->users()) {
    50                 const Statement * use = dyn_cast<Statement>(u);
    51                 if (use) {
    52                     if (usedInBlock == nullptr || usedInBlock == use->getParent()) {
    53                         usedInBlock = use->getParent();
     39                if (const Statement * use = dyn_cast<Statement>(u)) {
     40                    if (mProcessed.count(use->getParent())) {
     41                        canSinkInstruction = true;
     42                        ancestors.insert(use->getParent());
    5443                        continue;
    5544                    }
    56                     usedInOnlyOneBlock = false;
     45                    canSinkInstruction = false;
    5746                    break;
    5847                }
    5948            }
    60             assert (usedInBlock);
    61             if (usedInOnlyOneBlock && usedInBlock != &block) {
    62 //                PabloPrinter::print(stmt, " moving ", std::cerr);
    63 //                PabloPrinter::print(usedInBlock->front(), " before ", std::cerr);
    64 //                std::cerr << std::endl;
    65                 stmt->insertBefore(usedInBlock->front());
     49            if (canSinkInstruction) {
     50
     51                assert (ancestors.size() >= 1);
     52
     53                if (ancestors.size() > 1) {
     54                    BlockSetVector P1, P2;
     55                    while (ancestors.size() > 1) {
     56
     57                        PabloBlock * u = ancestors.back();
     58                        while (u != &block) {
     59                            P1.push_back(u);
     60                            u = u->getParent();
     61                        }
     62                        ancestors.pop_back();
     63
     64                        PabloBlock * v = ancestors.back();
     65                        while (v != &block) {
     66                            P2.push_back(v);
     67                            v = v->getParent();
     68                        }
     69                        ancestors.pop_back();
     70
     71                        // P1 and P2 now contain the paths from the 'sink' to the 'source'. Scan backwards though them
     72                        // to find the first differing element. The last non-differing block is our LCA. If none
     73                        // exists for any two paths, this instruction cannot be sunk (or would just be sunk to the
     74                        // same position it's at now.)
     75
     76                        PabloBlock * lca = nullptr;
     77                        auto p1 = P1.rbegin(), p2 = P2.rbegin();
     78
     79                        for (; p1 != P1.rend() && p2 != P2.rend(); ++p1, ++p2) {
     80                            if (*p1 != *p2) {
     81                                break;
     82                            }
     83
     84                            lca = *p1;
     85                        }
     86
     87                        if (lca == nullptr) {
     88                            canSinkInstruction = false;
     89                            break;
     90                        }
     91
     92                        P1.clear();
     93                        P2.clear();
     94                        ancestors.insert(lca);
     95                    }
     96                }
     97
     98                if (canSinkInstruction) {
     99                    assert (ancestors.size() == 1);
     100                    PabloBlock * const lca = *ancestors.begin();
     101                    stmt->insertBefore(lca->front());
     102                }
    66103            }
    67104        }
    68105        stmt = next;
    69106    }
    70 }
    71 
    72 
    73 
    74 CodeSinking::CodeSinking()
    75 {
     107    mProcessed.insert(&block);
    76108}
    77109
  • icGREP/icgrep-devel/icgrep/pablo/optimizers/pablo_codesinking.hpp

    r4516 r4521  
    33
    44#include <pablo/codegenstate.h>
     5#include <vector>
     6#include <algorithm>
    57
    68namespace pablo {
    79
    8 class CodeSinking
    9 {
     10class CodeSinking {
     11
     12    struct BlockSetVector : public std::vector<PabloBlock *> {
     13        inline bool insert(PabloBlock * block) {
     14            const auto i = std::lower_bound(begin(), end(), block);
     15            if (i == end() || *i != block) {
     16                std::vector<PabloBlock *>::insert(i, block);
     17                assert (std::is_sorted(begin(), end()));
     18                return true;
     19            }
     20            return false;
     21        }
     22        inline bool count(PabloBlock * block) {
     23            const auto i = std::lower_bound(begin(), end(), block);
     24            return (i != end() && *i == block);
     25        }
     26    };
     27
    1028public:
    1129    static bool optimize(PabloBlock & block);
    1230protected:
    13     static void sink(PabloBlock & block);
    14     CodeSinking();
     31    void sink(PabloBlock & block);
     32    CodeSinking() { }
     33private:
     34    BlockSetVector mProcessed;
    1535};
    1636
Note: See TracChangeset for help on using the changeset viewer.