| /* |
| * Copyright 2011 Christoph Bumiller |
| * |
| * Permission is hereby granted, free of charge, to any person obtaining a |
| * copy of this software and associated documentation files (the "Software"), |
| * to deal in the Software without restriction, including without limitation |
| * the rights to use, copy, modify, merge, publish, distribute, sublicense, |
| * and/or sell copies of the Software, and to permit persons to whom the |
| * Software is furnished to do so, subject to the following conditions: |
| * |
| * The above copyright notice and this permission notice shall be included in |
| * all copies or substantial portions of the Software. |
| * |
| * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR |
| * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, |
| * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL |
| * THE AUTHORS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, |
| * WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF |
| * OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE |
| * SOFTWARE. |
| */ |
| |
| #ifndef __NV50_IR_GRAPH_H__ |
| #define __NV50_IR_GRAPH_H__ |
| |
| #include "nv50_ir_util.h" |
| #include <vector> |
| |
| namespace nv50_ir { |
| |
| #define ITER_NODE(x) reinterpret_cast<Graph::Node *>((x).get()) |
| #define ITER_EDGE(x) reinterpret_cast<Graph::Edge *>((x).get()) |
| |
| // A connected graph. |
| class Graph |
| { |
| public: |
| class Node; |
| |
| class Edge |
| { |
| public: |
| enum Type |
| { |
| UNKNOWN, |
| TREE, |
| FORWARD, |
| BACK, |
| CROSS, // e.g. loop break |
| DUMMY |
| }; |
| |
| Edge(Node *dst, Node *src, Type kind); |
| ~Edge() { unlink(); } |
| |
| inline Node *getOrigin() const { return origin; } |
| inline Node *getTarget() const { return target; } |
| |
| inline Type getType() const { return type; } |
| const char *typeStr() const; |
| |
| private: |
| Node *origin; |
| Node *target; |
| |
| Type type; |
| Edge *next[2]; // next edge outgoing/incident from/to origin/target |
| Edge *prev[2]; |
| |
| void unlink(); |
| |
| friend class Graph; |
| }; |
| |
| class EdgeIterator : public Iterator |
| { |
| public: |
| EdgeIterator() : e(0), t(0), d(0), rev(false) { } |
| EdgeIterator(Graph::Edge *first, int dir, bool reverse) |
| : d(dir), rev(reverse) |
| { |
| t = e = ((rev && first) ? first->prev[d] : first); |
| } |
| |
| virtual void next() |
| { |
| Graph::Edge *n = (rev ? e->prev[d] : e->next[d]); |
| e = (n == t ? NULL : n); |
| } |
| virtual bool end() const { return !e; } |
| virtual void *get() const { return e; } |
| |
| inline Node *getNode() const { assert(e); return d ? |
| e->origin : e->target; } |
| inline Edge *getEdge() const { return e; } |
| inline Edge::Type getType() { return e ? e->getType() : Edge::UNKNOWN; } |
| |
| private: |
| Graph::Edge *e; |
| Graph::Edge *t; |
| int d; |
| bool rev; |
| }; |
| |
| class Node |
| { |
| public: |
| Node(void *); |
| ~Node() { cut(); } |
| |
| void attach(Node *, Edge::Type); |
| bool detach(Node *); |
| void cut(); |
| |
| inline EdgeIterator outgoing(bool reverse = false) const; |
| inline EdgeIterator incident(bool reverse = false) const; |
| |
| inline Node *parent() const; // returns NULL if count(incident edges) != 1 |
| |
| bool reachableBy(const Node *node, const Node *term) const; |
| |
| inline bool visit(int); |
| inline int getSequence() const; |
| |
| inline int incidentCountFwd() const; // count of incident non-back edges |
| inline int incidentCount() const { return inCount; } |
| inline int outgoingCount() const { return outCount; } |
| |
| Graph *getGraph() const { return graph; } |
| |
| void *data; |
| |
| private: |
| Edge *in; |
| Edge *out; |
| Graph *graph; |
| |
| int visited; |
| |
| int16_t inCount; |
| int16_t outCount; |
| public: |
| int tag; // for temporary use |
| |
| friend class Graph; |
| }; |
| |
| public: |
| Graph(); |
| ~Graph(); // does *not* free the nodes (make it an option ?) |
| |
| inline Node *getRoot() const { return root; } |
| |
| inline unsigned int getSize() const { return size; } |
| |
| inline int nextSequence(); |
| |
| void insert(Node *node); // attach to or set as root |
| |
| IteratorRef iteratorDFS(bool preorder = true); |
| IteratorRef iteratorCFG(); |
| |
| // safe iterators are unaffected by changes to the *edges* of the graph |
| IteratorRef safeIteratorDFS(bool preorder = true); |
| IteratorRef safeIteratorCFG(); |
| |
| void classifyEdges(); |
| |
| // @weights: indexed by Node::tag |
| int findLightestPathWeight(Node *, Node *, const std::vector<int>& weights); |
| |
| private: |
| void classifyDFS(Node *, int&); |
| |
| private: |
| Node *root; |
| unsigned int size; |
| int sequence; |
| }; |
| |
| int Graph::nextSequence() |
| { |
| return ++sequence; |
| } |
| |
| Graph::Node *Graph::Node::parent() const |
| { |
| if (inCount != 1) |
| return NULL; |
| assert(in); |
| return in->origin; |
| } |
| |
| bool Graph::Node::visit(int v) |
| { |
| if (visited == v) |
| return false; |
| visited = v; |
| return true; |
| } |
| |
| int Graph::Node::getSequence() const |
| { |
| return visited; |
| } |
| |
| Graph::EdgeIterator Graph::Node::outgoing(bool reverse) const |
| { |
| return EdgeIterator(out, 0, reverse); |
| } |
| |
| Graph::EdgeIterator Graph::Node::incident(bool reverse) const |
| { |
| return EdgeIterator(in, 1, reverse); |
| } |
| |
| int Graph::Node::incidentCountFwd() const |
| { |
| int n = 0; |
| for (EdgeIterator ei = incident(); !ei.end(); ei.next()) |
| if (ei.getType() != Edge::BACK) |
| ++n; |
| return n; |
| } |
| |
| } // namespace nv50_ir |
| |
| #endif // __NV50_IR_GRAPH_H__ |