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

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

Minor changes.

File size: 3.8 KB
Line 
1#include "useanalysis.h"
2#include <queue>
3
4namespace pablo {
5
6void UseAnalysis::optimize(PabloBlock & block) {
7    UseAnalysis analyzer;
8    analyzer.gatherUseDefInformation(analyzer.mRoot, block.statements());
9
10}
11
12void UseAnalysis::identifyDeadVariables() {
13    std::queue<Vertex> Q;
14    // gather up all of the nodes that aren't output assignments and have no users
15    const auto vMap = get(vertex_name, mUseDefGraph);
16    VertexIterator vi, vi_end;
17    for (std::tie(vi, vi_end) = vertices(mUseDefGraph); vi != vi_end; ++vi) {
18        const Vertex v = *vi;
19        if (out_degree(v) == 0) {
20            const PabloAST * n = vMap[v];
21            if (isa<Assign>(n) && (cast<Assign>(n)->isOutputAssignment())) {
22                continue;
23            }
24            Q.push(v);
25        }
26    }
27    while (!Q.empty()) {
28        const Vertex v = Q.front();
29        Q.pop();
30        InEdgeIterator ei, ei_end;
31        for (std::tie(ei, ei_end) = in_edges(v, mUseDefGraph); ei != ei_end; ++ei) {
32            const Vertex u = source(*ei, mUseDefGraph);
33            if (out_degree(u, mUseDefGraph) == 1) {
34                Q.push(u);
35            }
36        }
37        clear_in_edges(v, mUseDefGraph);
38    }
39}
40
41void UseAnalysis::gatherUseDefInformation(const Vertex v, StatementList & statements) {
42    for (PabloAST * stmt : statements) {
43        const Vertex u = find(stmt);
44        add_edge(u, v, mUseDefGraph);
45        if (const Assign * assign = dyn_cast<Assign>(stmt)) {
46            gatherUseDefInformation(u, assign->getExpr());
47        }
48        if (const Next * next = dyn_cast<Next>(stmt)) {
49            gatherUseDefInformation(u, next->getExpr());
50        }
51        else if (If * ifStatement = dyn_cast<If>(stmt)) {
52            gatherUseDefInformation(u, ifStatement->getCondition());
53            gatherUseDefInformation(u, ifStatement->getBody());
54        }
55        else if (While * whileStatement = dyn_cast<While>(stmt)) {
56            gatherUseDefInformation(u, whileStatement->getCondition());
57            gatherUseDefInformation(u, whileStatement->getBody());
58        }
59    }
60}
61
62void UseAnalysis::gatherUseDefInformation(const Vertex v, PabloAST * expr) {
63    const Vertex u = find(expr);
64    add_edge(u, v, mUseDefGraph);
65    if (const And * pablo_and = dyn_cast<const And>(expr)) {
66        gatherUseDefInformation(u, pablo_and->getExpr1());
67        gatherUseDefInformation(u, pablo_and->getExpr2());
68    }
69    else if (const Or * pablo_or = dyn_cast<const Or>(expr)) {
70        gatherUseDefInformation(u, pablo_or->getExpr1());
71        gatherUseDefInformation(u, pablo_or->getExpr2());
72    }
73    else if (const Sel * pablo_sel = dyn_cast<const Sel>(expr)) {
74        gatherUseDefInformation(u, pablo_sel->getCondition());
75        gatherUseDefInformation(u, pablo_sel->getTrueExpr());
76        gatherUseDefInformation(u, pablo_sel->getFalseExpr());
77    }
78    else if (const Not * pablo_not = dyn_cast<const Not>(expr)) {
79        gatherUseDefInformation(u, pablo_not->getExpr());
80    }
81    else if (const Advance * adv = dyn_cast<const Advance>(expr)) {
82        gatherUseDefInformation(u, adv->getExpr());
83    }
84    else if (const MatchStar * mstar = dyn_cast<const MatchStar>(expr)) {
85        gatherUseDefInformation(u, mstar->getMarker());
86        gatherUseDefInformation(u, mstar->getCharClass());
87    }
88    else if (const ScanThru * sthru = dyn_cast<const ScanThru>(expr)) {
89        gatherUseDefInformation(u, sthru->getScanFrom());
90        gatherUseDefInformation(u, sthru->getScanThru());
91    }
92}
93
94inline UseAnalysis::Vertex UseAnalysis::find(const PabloAST * const node) {
95    auto f = mUseDefMap.find(node);
96    if (f == mUseDefMap.end()) {
97        Vertex v = add_vertex(mUseDefGraph, node);
98        mUseDefMap.insert(std::make_pair(node, v));
99        return v;
100    }
101    return f->second;
102}
103
104UseAnalysis::UseAnalysis()
105: mRoot(add_vertex(mUseDefGraph, nullptr))
106{
107
108}
109
110}
Note: See TracBrowser for help on using the repository browser.