source: icGREP/icgrep-devel/icgrep/pablo/passes/ssapass.cpp @ 5486

Last change on this file since 5486 was 5371, checked in by nmedfort, 2 years ago

Bug fix for long advance

File size: 8.2 KB
Line 
1#include "ssapass.h"
2
3#include <pablo/pablo_kernel.h>
4#include <pablo/codegenstate.h>
5#include <pablo/branch.h>
6#include <pablo/ps_assign.h>
7#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;
19
20namespace pablo {
21
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 TracBrowser for help on using the repository browser.