source: icGREP/icgrep-devel/icgrep/pablo/analysis/useanalysis.cpp @ 4410

Last change on this file since 4410 was 4410, checked in by nmedfort, 5 years ago

Changes to support 3-operand form for all instructions. CSE disabled but partially redundant now.

File size: 8.7 KB
Line 
1#include "useanalysis.h"
2#include <queue>
3#include <iostream>
4
5using namespace boost;
6
7namespace pablo {
8
9bool UseAnalysis::optimize(PabloBlock & block) {
10    UseAnalysis analyzer;
11    analyzer.gatherUseDefInformation(block.statements());
12    analyzer.dce();
13    analyzer.cse(block);
14    return true;
15}
16
17void UseAnalysis::cse(PabloBlock & block) {
18//    VertexIterator vi, vi_end;
19//    const auto nodeOf = get(vertex_name, mUseDefGraph);
20//    for (std::tie(vi, vi_end) = vertices(mUseDefGraph); vi != vi_end; ++vi) {
21//        const Vertex u = *vi;
22//        const auto count = out_degree(u, mUseDefGraph);
23//        if (count > 1) {
24//            PabloAST * expr = nodeOf[u];
25//            if (isa<Statement>(expr) || isa<Var>(expr)) {
26//                continue;
27//            }
28//            // create the new nodes
29//            Assign * assign = block.createAssign("cse", expr);
30//            Var * var = block.createVar(assign);
31//            if (expr == var) {
32//                continue;
33//            }
34//            const Vertex s = find(assign);
35//            const Vertex v = find(var);
36//            // update the program and graph
37//            OutEdgeIterator ei, ei_end;
38//            for (std::tie(ei, ei_end) = out_edges(u, mUseDefGraph); ei != ei_end; ++ei) {
39//                const Vertex t = target(*ei, mUseDefGraph);
40//                add_edge(v, t, mUseDefGraph);
41//                PabloAST * user = nodeOf[t];
42//                user->replaceUsesOfWith(expr, var);
43//            }
44//            clear_out_edges(u, mUseDefGraph);
45//            add_edge(u, s, mUseDefGraph);
46//            add_edge(s, v, mUseDefGraph);
47//            Statement * ip = findInsertionPointFor(u, block);
48//            if (ip == nullptr) {
49//                assign->insertBefore(block.statements().front());
50//            }
51//            else {
52//                assign->insertAfter(ip);
53//            }
54//        }
55//    }
56}
57
58inline Statement * UseAnalysis::findInsertionPointFor(const Vertex v, PabloBlock & block) {
59//    // We want to find a predecessor of v that is the last statement in the AST.
60//    const auto nodeOf = get(vertex_name, mUseDefGraph);
61//    PredecessorSet predecessors;
62//    std::queue<Vertex> Q;
63//    InEdgeIterator ei, ei_end;
64//    for (std::tie(ei, ei_end) = in_edges(v, mUseDefGraph); ei != ei_end; ++ei) {
65//        const Vertex u = source(*ei, mUseDefGraph);
66//        PabloAST * n = nodeOf[u];
67//        if (isa<Statement>(n)) {
68//            predecessors.insert(cast<Statement>(n));
69//        }
70//        else {
71//            Q.push(u);
72//        }
73//    }
74
75//    while (!Q.empty()) {
76//        const Vertex u = Q.front();
77//        Q.pop();
78//        PabloAST * n = nodeOf[u];
79
80//        if (isa<Statement>(n)) {
81//            predecessors.insert(cast<Statement>(n));
82//        }
83//        else {
84//            InEdgeIterator ei, ei_end;
85//            for (std::tie(ei, ei_end) = in_edges(u, mUseDefGraph); ei != ei_end; ++ei) {
86//                Q.push(source(*ei, mUseDefGraph));
87//            }
88//        }
89//    }
90//    if (predecessors.empty()) {
91//        return nullptr;
92//    }
93//    return findLastStatement(predecessors, block.statements());
94}
95
96Statement * UseAnalysis::findLastStatement(const PredecessorSet & predecessors, StatementList & statements) {
97//    for (auto ri = statements.rbegin(); ri != statements.rend(); ++ri) {
98//        Statement * stmt = *ri;
99//        if (predecessors.count(stmt)) {
100//            return stmt;
101//        }
102//        else if (isa<If>(stmt)) {
103//            Statement * innerstmt = findLastStatement(predecessors, cast<If>(stmt)->getBody());
104//            if (innerstmt) {
105//                return stmt;
106//            }
107//        }
108//        else if (isa<While>(stmt)) {
109//            stmt = findLastStatement(predecessors, cast<While>(stmt)->getBody());
110//            if (stmt) {
111//                return stmt;
112//            }
113//        }
114//    }
115//    return nullptr;
116}
117
118void UseAnalysis::dce() {
119//    const auto nodeOf = get(vertex_name, mUseDefGraph);
120//    std::queue<Vertex> Q;
121//    // gather up all of the nodes that aren't output assignments and have no users
122//    VertexIterator vi, vi_end;
123//    for (std::tie(vi, vi_end) = vertices(mUseDefGraph); vi != vi_end; ++vi) {
124//        const Vertex v = *vi;
125//        if (out_degree(v, mUseDefGraph) == 0) {
126//            PabloAST * n = nodeOf[v];
127//            if (!isa<Assign>(n) || (cast<Assign>(n)->isOutputAssignment())) {
128//                continue;
129//            }
130//            Q.push(v);
131//        }
132//    }
133//    while (!Q.empty()) {
134//        const Vertex v = Q.front();
135//        Q.pop();
136//        PabloAST * n = nodeOf[v];
137//        if (isa<Assign>(n)) {
138//            cast<Assign>(n)->removeFromParent();
139//        }
140//        InEdgeIterator ei, ei_end;
141//        for (std::tie(ei, ei_end) = in_edges(v, mUseDefGraph); ei != ei_end; ++ei) {
142//            const Vertex u = source(*ei, mUseDefGraph);
143//            if (out_degree(u, mUseDefGraph) == 1) {
144//                Q.push(u);
145//            }
146//        }
147//        clear_in_edges(v, mUseDefGraph);
148//    }
149}
150
151void UseAnalysis::gatherUseDefInformation(const StatementList & statements) {
152    for (const Statement * stmt : statements) {
153        const Vertex v = find(stmt);
154        if (const Assign * assign = dyn_cast<Assign>(stmt)) {
155            gatherUseDefInformation(v, assign->getExpr());
156        }
157        else if (const If * ifStatement = dyn_cast<If>(stmt)) {
158            gatherUseDefInformation(v, ifStatement->getCondition());
159            gatherUseDefInformation(v, ifStatement->getBody());
160        }
161        else if (const While * whileStatement = dyn_cast<While>(stmt)) {
162            gatherUseDefInformation(v, whileStatement->getCondition());
163            gatherUseDefInformation(v, whileStatement->getBody());
164        }
165        else if (isa<Next>(stmt)) {
166            throw std::runtime_error("Next node is illegal in main block!");
167        }
168    }
169}
170
171void UseAnalysis::gatherUseDefInformation(const Vertex v, const StatementList & statements) {
172    for (const Statement * stmt : statements) {
173        const Vertex u = find(stmt);
174        add_edge(u, v, mUseDefGraph);
175        if (const Assign * assign = dyn_cast<Assign>(stmt)) {
176            gatherUseDefInformation(u, assign->getExpr());
177        }
178        else if (const Next * next = dyn_cast<Next>(stmt)) {
179            add_edge(find(next->getInitial()), u, mUseDefGraph);
180            gatherUseDefInformation(u, next->getExpr());
181        }
182        else if (const If * ifStatement = dyn_cast<If>(stmt)) {
183            gatherUseDefInformation(u, ifStatement->getCondition());
184            gatherUseDefInformation(u, ifStatement->getBody());
185        }
186        else if (const While * whileStatement = dyn_cast<While>(stmt)) {
187            gatherUseDefInformation(u, whileStatement->getCondition());
188            gatherUseDefInformation(u, whileStatement->getBody());
189        }
190    }
191}
192
193void UseAnalysis::gatherUseDefInformation(const Vertex v, const PabloAST * expr) {
194//    if (isa<Var>(expr) && cast<Var>(expr)->isExternal()) {
195//        return;
196//    }
197    const Vertex u = find(expr);
198    add_edge(u, v, mUseDefGraph);
199    if (const Var * var = dyn_cast<Var>(expr)) {
200//        gatherUseDefInformation(u, var->getVar());
201    }
202    else if (const And * pablo_and = dyn_cast<const And>(expr)) {
203        gatherUseDefInformation(u, pablo_and->getExpr1());
204        gatherUseDefInformation(u, pablo_and->getExpr2());
205    }
206    else if (const Or * pablo_or = dyn_cast<const Or>(expr)) {
207        gatherUseDefInformation(u, pablo_or->getExpr1());
208        gatherUseDefInformation(u, pablo_or->getExpr2());
209    }
210    else if (const Sel * pablo_sel = dyn_cast<const Sel>(expr)) {
211        gatherUseDefInformation(u, pablo_sel->getCondition());
212        gatherUseDefInformation(u, pablo_sel->getTrueExpr());
213        gatherUseDefInformation(u, pablo_sel->getFalseExpr());
214    }
215    else if (const Not * pablo_not = dyn_cast<const Not>(expr)) {
216        gatherUseDefInformation(u, pablo_not->getExpr());
217    }
218    else if (const Advance * adv = dyn_cast<const Advance>(expr)) {
219        gatherUseDefInformation(u, adv->getExpr());
220    }
221    else if (const MatchStar * mstar = dyn_cast<const MatchStar>(expr)) {
222        gatherUseDefInformation(u, mstar->getMarker());
223        gatherUseDefInformation(u, mstar->getCharClass());
224    }
225    else if (const ScanThru * sthru = dyn_cast<const ScanThru>(expr)) {
226        gatherUseDefInformation(u, sthru->getScanFrom());
227        gatherUseDefInformation(u, sthru->getScanThru());
228    }
229}
230
231inline UseAnalysis::Vertex UseAnalysis::find(const PabloAST * const node) {
232    auto f = mUseDefMap.find(node);
233    if (f == mUseDefMap.end()) {
234        const Vertex v = add_vertex(mUseDefGraph);
235        mUseDefMap.insert(std::make_pair(node, v));
236        get(vertex_name, mUseDefGraph)[v] = const_cast<PabloAST*>(node);
237        return v;
238    }
239    return f->second;
240}
241}
Note: See TracBrowser for help on using the repository browser.