Ignore:
Timestamp:
Mar 24, 2017, 4:01:22 PM (2 years ago)
Author:
nmedfort
Message:

Bug fix for long advance

File:
1 edited

Legend:

Unmodified
Added
Removed
  • icGREP/icgrep-devel/icgrep/pablo/passes/ssapass.cpp

    r5368 r5371  
    66#include <pablo/ps_assign.h>
    77#include <pablo/pe_var.h>
     8#include <pablo/pe_phi.h>
     9#include <boost/container/flat_map.hpp>
     10#include <boost/container/flat_set.hpp>
     11#include <boost/graph/adjacency_list.hpp>
     12#include <llvm/ADT/SmallVector.h>
     13
     14#include <llvm/Support/raw_ostream.h>
     15#include <pablo/printer_pablos.h>
     16
     17using namespace llvm;
     18using namespace boost;
    819
    920namespace pablo {
    1021
    11 static void SSAPass::toSSAForm(PabloBlock * const block) {
    12 
    13 
    14 
    15 }
    16 
    17 }
     22template<typename K, typename V>
     23using FlatMap = boost::container::flat_map<K, V>;
     24
     25template<typename V>
     26using FlatSet = boost::container::flat_set<V>;
     27
     28using DefinitionMap = FlatMap<PabloAST *, PabloAST *>;
     29using PhiMap = FlatMap<std::pair<PabloAST *, PabloAST *>, Phi *>;
     30using ReachingGraph = adjacency_list<vecS, vecS, bidirectionalS, Statement *, DefinitionMap::value_type>;
     31using Vertex = ReachingGraph::vertex_descriptor;
     32using InEdge = graph_traits<ReachingGraph>::in_edge_iterator;
     33
     34/*
     35 * Y = Y_0
     36 * X = 0                          ...
     37 * While Y:                       While phi(Y_0, Y_i):
     38 *   ...                             X' = phi(0, X'')
     39 *   If Z:                           If Z:
     40 *      X = A                           ...
     41 *   A = Z                           X'' = phi(X', A)
     42 *   Y = Y_i
     43 */
     44
     45/** ------------------------------------------------------------------------------------------------------------- *
     46 * @brief buildReachingGraph
     47 ** ------------------------------------------------------------------------------------------------------------- */
     48Vertex buildReachingGraph(PabloBlock * const block, Vertex entryPoint, ReachingGraph & G, DefinitionMap & D) {
     49    for (Statement * stmt : *block) {
     50        if (LLVM_UNLIKELY(isa<Assign>(stmt))) {
     51            PabloAST * const var = cast<Assign>(stmt)->getVariable();
     52            PabloAST * value = cast<Assign>(stmt)->getValue();
     53            if (isa<Var>(value)) {
     54                auto f = D.find(value);
     55                assert (f != D.end());
     56                value = f->second;
     57            }
     58            D[var] = value;
     59        } else if (LLVM_UNLIKELY(isa<Branch>(stmt))) {
     60            const auto branchPoint = add_vertex(stmt, G);
     61            const auto resumePoint = add_vertex(stmt->getNextNode(), G);
     62            for (auto p : D) {
     63                add_edge(entryPoint, branchPoint, p, G);
     64                add_edge(branchPoint, resumePoint, p, G);
     65            }
     66            const Vertex endPoint = buildReachingGraph(cast<Branch>(stmt)->getBody(), branchPoint, G, D);
     67            if (isa<While>(stmt)) {
     68                for (auto p : D) {
     69                    add_edge(endPoint, branchPoint, p, G);
     70                }
     71            }
     72            for (auto p : D) {
     73                add_edge(endPoint, resumePoint, p, G);
     74            }
     75            entryPoint = resumePoint;
     76        }
     77    }
     78    return entryPoint;
     79}
     80
     81/** ------------------------------------------------------------------------------------------------------------- *
     82 * @brief getVariable
     83 ** ------------------------------------------------------------------------------------------------------------- */
     84inline PabloAST * getVariable(InEdge e, const ReachingGraph & G) {
     85    return std::get<0>(G[*e]);
     86}
     87
     88/** ------------------------------------------------------------------------------------------------------------- *
     89 * @brief getDefinition
     90 ** ------------------------------------------------------------------------------------------------------------- */
     91PabloAST * getDefinition(InEdge e, const ReachingGraph & G, DefinitionMap & D) {
     92    PabloAST * def = std::get<1>(G[*e]);
     93    if (LLVM_UNLIKELY(isa<Var>(def))) {
     94        const auto f = D.find(def);
     95        if (f != D.end()) {
     96            def = f->second;
     97        }
     98    }
     99    return def;
     100}
     101
     102/** ------------------------------------------------------------------------------------------------------------- *
     103 * @brief generatePhiNodeDefinitions
     104 ** ------------------------------------------------------------------------------------------------------------- */
     105void generatePhiNodeDefinitions(const Vertex v, PabloBlock * const block, const ReachingGraph & G, DefinitionMap & D, PhiMap & P) {
     106    FlatSet<PabloAST *> S;
     107    InEdge ei, end;
     108    std::vector<bool> processed(in_degree(v, G), false);
     109    unsigned i = 0;
     110    for (std::tie(ei, end) = in_edges(v, G); ei != end; ++ei, ++i) {
     111        if (processed[i]) {
     112            continue;
     113        }
     114        PabloAST * const var = getVariable(ei, G);
     115        S.insert(getDefinition(ei, G, D));
     116        unsigned j = i + 1;
     117        for (auto ej = ei + 1; ej != end; ++ej, ++j) {
     118            if (var == getVariable(ej, G)) {
     119                S.insert(getDefinition(ej, G, D));
     120            }
     121        }
     122        if (S.size() > 1) {
     123            assert (S.size() == 2);
     124            auto si = S.begin();
     125            auto def = std::make_pair(*si, *(si + 1));
     126            auto f = P.find(def);
     127            Phi * phi = nullptr;
     128            if (f == P.end()) {
     129                phi = block->createPhi(var->getType());
     130                for (PabloAST * incoming : S) {
     131                    phi->addIncomingValue(incoming);
     132                }
     133                P.emplace(def, phi);
     134            } else {
     135                phi = f->second;
     136            }
     137            D[var] = phi;
     138        }
     139        S.clear();
     140    }
     141}
     142
     143/** ------------------------------------------------------------------------------------------------------------- *
     144 * @brief generatePhiNodes
     145 ** ------------------------------------------------------------------------------------------------------------- */
     146Vertex generatePhiNodes(PabloBlock * const block, Vertex entryPoint, ReachingGraph & G, DefinitionMap & D, PhiMap & P) {
     147    for (Statement * stmt : *block) {
     148        if (LLVM_UNLIKELY(isa<Assign>(stmt))) {
     149            Assign * a = cast<Assign>(stmt);
     150            PabloAST * const var = a->getVariable();
     151            PabloAST * value = a->getValue();
     152            if (isa<Var>(value)) {
     153                auto f = D.find(value);
     154                assert (f != D.end());
     155                value = f->second;
     156                a->setValue(value);
     157            }
     158            D[var] = value;
     159        } else if (LLVM_UNLIKELY(isa<Extract>(stmt))) {
     160            continue;
     161        } else if (LLVM_UNLIKELY(isa<Branch>(stmt))) {
     162            const auto branchPoint = entryPoint + 1;
     163            assert (G[branchPoint] == stmt);
     164            if (isa<While>(stmt)) {
     165                generatePhiNodeDefinitions(branchPoint, block, G, D, P);
     166            }
     167            Branch * br = cast<Branch>(stmt);
     168            if (isa<Var>(br->getCondition())) {
     169                auto f = D.find(br->getCondition());
     170                assert (f != D.end());
     171                br->setCondition(f->second);
     172            }
     173            const auto resumePoint = entryPoint + 2;
     174            assert (G[resumePoint] == stmt->getNextNode());
     175
     176            entryPoint = generatePhiNodes(cast<Branch>(stmt)->getBody(), resumePoint, G, D, P);
     177
     178            generatePhiNodeDefinitions(resumePoint, block, G, D, P);
     179
     180        } else {
     181            for (unsigned i = 0; i < stmt->getNumOperands(); ++i) {
     182                PabloAST * op = stmt->getOperand(i);
     183                if (isa<Var>(op)) {
     184                    auto f = D.find(op);
     185                    assert (f != D.end());
     186                    stmt->setOperand(i, f->second);
     187                }
     188            }
     189        }
     190    }
     191    return entryPoint;
     192}
     193
     194/** ------------------------------------------------------------------------------------------------------------- *
     195 * @brief toSSAForm
     196 ** ------------------------------------------------------------------------------------------------------------- */
     197inline void toSSAForm(PabloKernel * const kernel) {
     198    ReachingGraph G;
     199    DefinitionMap D;
     200    PabloBlock * entryBlock = kernel->getEntryBlock();
     201    const auto entryPoint = add_vertex(entryBlock->front(), G);
     202    buildReachingGraph(entryBlock, entryPoint, G, D);
     203    D.clear();
     204    PhiMap P;
     205    generatePhiNodes(entryBlock, entryPoint, G, D, P);
     206}
     207
     208/** ------------------------------------------------------------------------------------------------------------- *
     209 * @brief transform
     210 ** ------------------------------------------------------------------------------------------------------------- */
     211bool SSAPass::transform(PabloKernel * const kernel) {
     212    toSSAForm(kernel);
     213    return false;
     214}
     215
     216
     217}
Note: See TracChangeset for help on using the changeset viewer.