Changeset 4723


Ignore:
Timestamp:
Aug 11, 2015, 4:31:48 PM (4 years ago)
Author:
nmedfort
Message:

More work on the dependency chain metrics.

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

Legend:

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

    r4722 r4723  
    3737#include <llvm/Support/raw_ostream.h>
    3838#include <llvm/Analysis/DependenceAnalysis.h>
    39 
     39#include <boost/container/flat_map.hpp>
    4040#include <queue>
    4141#include <unordered_map>
     
    4545using namespace cc;
    4646using namespace llvm;
     47using namespace boost::container;
    4748
    4849static cl::opt<std::string>
     
    5253UCDSourcePath("dir", cl::desc("UCD source code directory"), cl::value_desc("directory"), cl::Required);
    5354
    54 static cl::opt<bool> PrintDependenceAnalysis("pablo-ldc", cl::init(false), cl::desc("print Pablo longest dependency chain metrics."));
    55 
     55static cl::opt<std::string>
     56PrintLongestDependenceChain("ldc", cl::desc("print longest dependency chain metrics."), cl::value_desc("filename"));
     57
     58static raw_fd_ostream * LongestDependenceChainFile = nullptr;
    5659
    5760#ifdef ENABLE_MULTIPLEXING
     
    6164static cl::opt<std::string>
    6265MultiplexingDistribution("multiplexing-dist",
    63     cl::desc("Generate a CSV containing the # of Advances found in each UCD function before and after applying multiplexing."), cl::value_desc("filename"));
     66    cl::desc("Generate a CSV containing the # of Advances found in each UCD function before and after applying multiplexing."),
     67    cl::value_desc("filename"));
    6468
    6569static raw_fd_ostream * MultiplexingDistributionFile = nullptr;
     70#else
     71const bool EnableMultiplexing = false;
    6672#endif
    6773
     
    8793 * @brief computePabloDependencyMetrics
    8894 ** ------------------------------------------------------------------------------------------------------------- */
    89 void computePabloDependencyChainMetrics(const PabloFunction & f) {
    90 
    91     std::queue<const PabloAST *> Q;
    92     std::unordered_map<const PabloAST *, unsigned> V;
    93 
     95unsigned computePabloDependencyChainMetrics(const PabloBlock & b, std::unordered_map<const PabloAST *, unsigned> G) {
     96    unsigned lpl = 0;
     97    flat_map<const PabloAST *, unsigned> L;
     98    for (const Statement * stmt : b) {
     99        unsigned local_lpl = 0;
     100        unsigned global_lpl = 0;
     101        for (unsigned i = 0; i != stmt->getNumOperands(); ++i) {
     102            const auto l = L.find(stmt->getOperand(i));
     103            if (l != L.end()) {
     104                local_lpl = std::max<unsigned>(local_lpl, l->second);
     105            }
     106            const auto g = G.find(stmt->getOperand(i));
     107            if (LLVM_UNLIKELY(g == G.end())) {
     108                throw std::runtime_error("Could not find dependency chain length for all operands!");
     109            }
     110            global_lpl = std::max<unsigned>(global_lpl, g->second);
     111        }
     112        L.emplace(stmt, local_lpl + 1);
     113        G.insert(std::make_pair(stmt, global_lpl + 1));
     114        if (LLVM_UNLIKELY(isa<If>(stmt) || isa<While>(stmt))) {
     115            for (const auto & l : L) {
     116                lpl = std::max(lpl, l.second);
     117            }
     118            L.clear();
     119            lpl = std::max(lpl, computePabloDependencyChainMetrics(isa<If>(stmt) ? cast<If>(stmt)->getBody() : cast<While>(stmt)->getBody(), G));
     120        }
     121    }
     122    return lpl;
     123}
     124
     125/** ------------------------------------------------------------------------------------------------------------- *
     126 * @brief computePabloDependencyMetrics
     127 ** ------------------------------------------------------------------------------------------------------------- */
     128std::pair<unsigned, unsigned> computePabloDependencyChainMetrics(const PabloFunction & f) {
     129    std::unordered_map<const PabloAST *, unsigned> G;
     130    for (unsigned i = 0; i != f.getNumOfParameters(); ++i) {
     131        G.insert(std::make_pair(f.getParameter(i), 0));
     132    }
     133    const unsigned local_lpl = computePabloDependencyChainMetrics(f.getEntryBlock(), G);
     134    unsigned global_lpl = 0;
    94135    for (unsigned i = 0; i != f.getNumOfResults(); ++i) {
    95         V.insert(std::make_pair(f.getResult(i), 0));
    96         const PabloAST * expr = f.getResult(i)->getExpression();
    97         if (expr->getNumUses() == 1 && V.count(expr) == 0) {
    98             V.insert(std::make_pair(expr, 1));
    99             if (LLVM_LIKELY(isa<Statement>(expr))) {
    100                 Q.push(cast<Statement>(expr));
    101             }
    102         }
    103     }
    104 
    105     while (!Q.empty()) {
    106         const PabloAST * expr = Q.front(); Q.pop();
    107         unsigned lpl = 0; // longest path length
    108         for (const PabloAST * user : expr->users()) {
    109             lpl = std::max<unsigned>(lpl, V[user]);
    110         }
    111         V.insert(std::make_pair(expr, lpl + 1));
    112         if (const Statement * stmt = dyn_cast<Statement>(expr)) {
    113             for (unsigned i = 0; i != stmt->getNumOperands(); ++i) {
    114                 assert (V.count(stmt->getOperand(i)) == 0);
    115                 bool everyUserOfThisOperandWasProcessed = true;
    116                 for (const PabloAST * user : stmt->getOperand(i)->users()) {
    117                     if (V.count(user) == 0) {
    118                         everyUserOfThisOperandWasProcessed = false;
    119                         break;
    120                     }
     136        assert (V.count(f.getParameter(i)));
     137        global_lpl = std::max<unsigned>(global_lpl, G[f.getResult(i)]);
     138    }
     139    return std::make_pair(global_lpl, local_lpl);
     140}
     141
     142
     143/** ------------------------------------------------------------------------------------------------------------- *
     144 * @brief computeLLVMDependencyMetrics
     145 ** ------------------------------------------------------------------------------------------------------------- */
     146unsigned computeLLVMDependencyChainMetrics(const llvm::BasicBlock & b, std::unordered_map<const llvm::Value *, unsigned> G) {
     147    unsigned lpl = 0;
     148    if (true) {
     149        flat_map<const llvm::Value *, unsigned> L;
     150        for (const llvm::Instruction & inst : b) {
     151            unsigned local_lpl = 0;
     152            unsigned global_lpl = 0;
     153            for (unsigned i = 0; i != inst.getNumOperands(); ++i) {
     154                const auto l = L.find(inst.getOperand(i));
     155                if (l != L.end()) {
     156                    local_lpl = std::max<unsigned>(local_lpl, l->second);
    121157                }
    122                 if (everyUserOfThisOperandWasProcessed) {
    123                     Q.push(stmt->getOperand(i));
     158                const auto g = G.find(inst.getOperand(i));
     159                if (LLVM_UNLIKELY(g == G.end())) {
     160                    throw std::runtime_error("Could not find dependency chain length for all operands!");
    124161                }
    125             }
    126         }
    127     }
    128 
    129     unsigned lpl = 0;
    130     for (unsigned i = 0; i != f.getNumOfParameters(); ++i) {
    131         assert (V.count(f.getParameter(i)));
    132         lpl = std::max<unsigned>(lpl, V[f.getParameter(i)]);
    133     }
    134 
    135 
    136 
     162                global_lpl = std::max<unsigned>(global_lpl, g->second);
     163            }
     164            L.emplace(&inst, local_lpl + 1);
     165            G.insert(std::make_pair(&inst, global_lpl + 1));
     166        }
     167        for (const auto & l : L) {
     168            lpl = std::max(lpl, l.second);
     169        }
     170    }
     171    const TerminatorInst * t = b.getTerminator();
     172    if (LLVM_LIKELY(isa<BranchInst>(t))) {
     173        for (unsigned i = t->getNumSuccessors(); i-- != 0; ) {
     174            lpl = std::max(lpl, computeLLVMDependencyChainMetrics(*(t->getSuccessor(i)), G));
     175        }
     176    }
     177    return lpl;
    137178}
    138179
     
    140181 * @brief computeLLVMDependencyMetrics
    141182 ** ------------------------------------------------------------------------------------------------------------- */
    142 void computeLLVMDependencyChainMetrics(const llvm::Function & f) {
    143 
    144 
    145 
     183std::pair<unsigned, unsigned> computeLLVMDependencyChainMetrics(const llvm::Function & f) {
     184    std::unordered_map<const llvm::Value *, unsigned> G;
     185    auto arg_itr = f.getArgumentList().begin();
     186    const Argument & input = *arg_itr++;
     187    input.dump();
     188    for (const auto user : input.users()) {
     189        user->dump();
     190        G.insert(std::make_pair(user, 0));
     191    }
     192    const unsigned local_lpl = computeLLVMDependencyChainMetrics(f.getEntryBlock(), G);
     193    const Argument & output = *arg_itr;
     194    unsigned global_lpl = 0;
     195    for (const auto user : output.users()) {
     196        user->dump();
     197        global_lpl = std::max<unsigned>(global_lpl, G[user]);
     198    }
     199    return std::make_pair(global_lpl, local_lpl);
    146200}
    147201
     
    155209    }
    156210    #endif
     211    if (LongestDependenceChainFile) {
     212        (*LongestDependenceChainFile) << name;
     213    }
     214
    157215    PabloFunction function = PabloFunction::Create(std::move(name), 8, 1);
    158216    Encoding encoding(Encoding::Type::UTF_8, 8);
     
    165223    Simplifier::optimize(function);
    166224    CodeSinking::optimize(function);
     225
    167226    #ifdef ENABLE_MULTIPLEXING
    168227    if (EnableMultiplexing) {
     
    175234            (*MultiplexingDistributionFile) << ',' << getNumOfAdvances(function.getEntryBlock()) << '\n';
    176235        }
     236
     237        if (LongestDependenceChainFile) {
     238            const auto pablo_metrix = computePabloDependencyChainMetrics(function);
     239            (*LongestDependenceChainFile) << ',' << pablo_metrix.first << ',' << pablo_metrix.second;
     240            Module module("tmp", getGlobalContext());
     241            auto func = pc.compile(function, &module);
     242            const auto llvm_metrix = computeLLVMDependencyChainMetrics(func.second);
     243            (*LongestDependenceChainFile) << ',' << llvm_metrix.first << ',' << llvm_metrix.second;
     244        }
    177245    }
    178246    #endif
     
    180248    auto func = pc.compile(function, module);
    181249    releaseSlabAllocatorMemory();
     250
     251    if (LongestDependenceChainFile) {
     252        const auto pablo_metrix = computePabloDependencyChainMetrics(function);
     253        (*LongestDependenceChainFile) << ',' << pablo_metrix.first << ',' << pablo_metrix.second;
     254        const auto llvm_metrix = computeLLVMDependencyChainMetrics(*func.first);
     255        (*LongestDependenceChainFile) << ',' << llvm_metrix.first << ',' << llvm_metrix.second << '\n';
     256    }
    182257
    183258    return func.second;
     
    387462
    388463
    389 
    390 
    391464    #ifdef ENABLE_MULTIPLEXING
    392465    if (MultiplexingDistribution.length() > 0) {
     
    406479    }
    407480    #endif
     481
     482    if (PrintLongestDependenceChain.length() > 0) {
     483        #ifdef USE_LLVM_3_5
     484        std::string error;
     485        LongestDependenceChainFile = new raw_fd_ostream(PrintLongestDependenceChain.c_str(), error, sys::fs::F_Text);
     486        if (!error.empty()) {
     487            throw std::runtime_error(error);
     488        }
     489        #else
     490        std::error_code error;
     491        LongestDependenceChainFile = new raw_fd_ostream(PrintLongestDependenceChain, error, sys::fs::F_Text);
     492        if (error) {
     493            throw std::runtime_error(error.message());
     494        }
     495        #endif
     496
     497        if (LongestDependenceChainFile) {
     498            if (EnableMultiplexing) {
     499                (*LongestDependenceChainFile) << ",Pre-Multiplexing,,,,Post-Multiplexing\n";
     500            }
     501            (*LongestDependenceChainFile) << ",Pablo,,LLVM,";
     502            if (EnableMultiplexing) {
     503                (*LongestDependenceChainFile) << ",Pablo,,LLVM,";
     504            }
     505            (*LongestDependenceChainFile) << "\nName,Global,Max Local,Global,Max Local";
     506            if (EnableMultiplexing) {
     507                (*LongestDependenceChainFile) << ",Global,Max Local,Global,Max Local";
     508            }
     509            (*LongestDependenceChainFile) << "\n";
     510        }
     511    }
     512
    408513    Module * module = generateUCDModule();
    409514    #ifdef ENABLE_MULTIPLEXING
     
    411516        MultiplexingDistributionFile->close();
    412517        delete MultiplexingDistributionFile;
    413     }
    414     #endif
     518    }   
     519    #endif
     520    if (LongestDependenceChainFile) {
     521        LongestDependenceChainFile->close();
     522        delete LongestDependenceChainFile;
     523    }
    415524    compileUCDModule(module);
    416525    return 0;
  • icGREP/icgrep-devel/icgrep/pablo/pabloAST.cpp

    r4722 r4723  
    131131    }
    132132    else if (LLVM_UNLIKELY(statement == nullptr)) {
    133         throw std::runtime_error("Cannot insert before Null statement!");
     133        throw std::runtime_error("cannot insert before null statement!");
    134134    }
    135135    else if (LLVM_UNLIKELY(statement->mParent == nullptr)) {
    136         throw std::runtime_error("Cannot insert before before statement in Null AST!");
     136        throw std::runtime_error("statement is not contained in a pablo block!");
    137137    }
    138138    removeFromParent();
     
    158158    }
    159159    else if (LLVM_UNLIKELY(statement == nullptr)) {
    160         throw std::runtime_error("Cannot insert before Null statement!");
     160        throw std::runtime_error("cannot insert after null statement!");
    161161    }
    162162    else if (LLVM_UNLIKELY(statement->mParent == nullptr)) {
    163         throw std::runtime_error("Cannot insert before before statement in Null AST!");
     163        throw std::runtime_error("statement is not contained in a pablo block!");
    164164    }
    165165    removeFromParent();
Note: See TracChangeset for help on using the changeset viewer.