1 /* Copyright 2020 The TensorFlow Authors. All Rights Reserved. 2 3 Licensed under the Apache License, Version 2.0 (the "License"); 4 you may not use this file except in compliance with the License. 5 You may obtain a copy of the License at 6 7 http://www.apache.org/licenses/LICENSE-2.0 8 9 Unless required by applicable law or agreed to in writing, software 10 distributed under the License is distributed on an "AS IS" BASIS, 11 WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 12 See the License for the specific language governing permissions and 13 limitations under the License. 14 ==============================================================================*/ 15 16 #ifndef TENSORFLOW_COMPILER_MLIR_HLO_INCLUDE_MLIR_HLO_UTILS_CYCLE_DETECTOR_H_ 17 #define TENSORFLOW_COMPILER_MLIR_HLO_INCLUDE_MLIR_HLO_UTILS_CYCLE_DETECTOR_H_ 18 19 #include <vector> 20 21 #include "llvm/ADT/DenseMap.h" 22 #include "llvm/ADT/Optional.h" 23 24 namespace mlir { 25 26 // ------------------------------------------------------------------- 27 28 // This file contains a light version of GraphCycles implemented in 29 // tensorflow/compiler/jit/graphcycles/graphcycles.h 30 // 31 // We re-implement it here because we do not want to rely 32 // on TensorFlow data structures, and hence we can move 33 // corresponding passes to llvm repo. easily in case necessnary. 34 35 // -------------------------------------------------------------------- 36 37 // This is a set data structure that provides a deterministic iteration order. 38 // The iteration order of elements only depends on the sequence of 39 // inserts/deletes, so as long as the inserts/deletes happen in the same 40 // sequence, the set will have the same iteration order. 41 // 42 // Assumes that T can be cheaply copied for simplicity. 43 template <typename T> 44 class OrderedSet { 45 public: 46 // Inserts `value` into the ordered set. Returns true if the value was not 47 // present in the set before the insertion. Insert(T value)48 bool Insert(T value) { 49 bool new_insertion = 50 value_to_index_.insert({value, value_sequence_.size()}).second; 51 if (new_insertion) { 52 value_sequence_.push_back(value); 53 } 54 return new_insertion; 55 } 56 57 // Removes `value` from the set. Assumes `value` is already present in the 58 // set. Erase(T value)59 void Erase(T value) { 60 auto it = value_to_index_.find(value); 61 62 // Since we don't want to move values around in `value_sequence_` we swap 63 // the value in the last position and with value to be deleted and then 64 // pop_back. 65 value_to_index_[value_sequence_.back()] = it->second; 66 std::swap(value_sequence_[it->second], value_sequence_.back()); 67 value_sequence_.pop_back(); 68 value_to_index_.erase(it); 69 } 70 Reserve(size_t new_size)71 void Reserve(size_t new_size) { 72 value_to_index_.reserve(new_size); 73 value_sequence_.reserve(new_size); 74 } 75 Clear()76 void Clear() { 77 value_to_index_.clear(); 78 value_sequence_.clear(); 79 } 80 Contains(T value)81 bool Contains(T value) const { return value_to_index_.count(value); } Size()82 size_t Size() const { return value_sequence_.size(); } 83 GetSequence()84 const std::vector<T>& GetSequence() const { return value_sequence_; } 85 86 private: 87 // The stable order that we maintain through insertions and deletions. 88 std::vector<T> value_sequence_; 89 90 // Maps values to their indices in `value_sequence_`. 91 llvm::DenseMap<T, int> value_to_index_; 92 }; 93 94 // --------------------------------------------------------------------- 95 96 // GraphCycles detects the introduction of a cycle into a directed 97 // graph that is being built up incrementally. 98 // 99 // Nodes are identified by small integers. It is not possible to 100 // record multiple edges with the same (source, destination) pair; 101 // requests to add an edge where one already exists are silently 102 // ignored. 103 // 104 // It is also not possible to introduce a cycle; an attempt to insert 105 // an edge that would introduce a cycle fails and returns false. 106 // 107 // GraphCycles uses no internal locking; calls into it should be 108 // serialized externally. 109 110 // Performance considerations: 111 // Works well on sparse graphs, poorly on dense graphs. 112 // Extra information is maintained incrementally to detect cycles quickly. 113 // InsertEdge() is very fast when the edge already exists, and reasonably fast 114 // otherwise. 115 // FindPath() is linear in the size of the graph. 116 // The current implementation uses O(|V|+|E|) space. 117 118 class GraphCycles { 119 public: 120 explicit GraphCycles(int32_t num_nodes); 121 ~GraphCycles(); 122 123 // Attempt to insert an edge from x to y. If the 124 // edge would introduce a cycle, return false without making any 125 // changes. Otherwise add the edge and return true. 126 bool InsertEdge(int32_t x, int32_t y); 127 128 // Remove any edge that exists from x to y. 129 void RemoveEdge(int32_t x, int32_t y); 130 131 // Return whether there is an edge directly from x to y. 132 bool HasEdge(int32_t x, int32_t y) const; 133 134 // Contracts the edge from 'a' to node 'b', merging nodes 'a' and 'b'. One of 135 // the nodes is removed from the graph, and edges to/from it are added to 136 // the remaining one, which is returned. If contracting the edge would create 137 // a cycle, does nothing and return no value. 138 llvm::Optional<int32_t> ContractEdge(int32_t a, int32_t b); 139 140 // Return whether dest_node `y` is reachable from source_node `x` 141 // by following edges. This is non-thread-safe version. 142 bool IsReachable(int32_t x, int32_t y); 143 144 // Return a copy of the successors set. This is needed for code using the 145 // collection while modifying the GraphCycles. 146 std::vector<int32_t> SuccessorsCopy(int32_t node) const; 147 148 // Returns all nodes in post order. 149 // 150 // If there is a path from X to Y then X appears after Y in the 151 // returned vector. 152 std::vector<int32_t> AllNodesInPostOrder() const; 153 154 // ---------------------------------------------------- 155 struct Rep; 156 157 private: 158 GraphCycles(const GraphCycles&) = delete; 159 GraphCycles& operator=(const GraphCycles&) = delete; 160 161 Rep* rep_; // opaque representation 162 }; 163 164 } // namespace mlir 165 166 #endif // TENSORFLOW_COMPILER_MLIR_HLO_INCLUDE_MLIR_HLO_UTILS_CYCLE_DETECTOR_H_ 167