1 /* Copyright 2017 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_TF2XLA_FUNCTIONALIZE_CONTROL_FLOW_UTIL_H_
17 #define TENSORFLOW_COMPILER_TF2XLA_FUNCTIONALIZE_CONTROL_FLOW_UTIL_H_
18
19 #include "absl/strings/str_join.h"
20 #include "tensorflow/compiler/xla/status_macros.h"
21 #include "tensorflow/core/graph/control_flow.h"
22 #include "tensorflow/core/graph/graph.h"
23
24 // Utility functions shared between functionalize cond and while
25 // or used by other graph optimization passes.
26
27 namespace tensorflow {
28
29 using NodeFilter = std::function<bool(const Node*)>;
30
31 // Information about a loop argument.
32 struct WhileLoopArg {
33 // Every loop argument has an Enter node.
34 Node* enter;
35
36 // Is the loop argument a loop-invariant value? Taken from the `is_constant`
37 // attribute on the Enter node.
38 bool is_loop_invariant;
39
40 // If 'is_loop_invariant' is true, the following are all nullptr. Non-constant
41 // arguments must have all of the following nodes:
42 Node* merge = nullptr;
43 Node* switch_node = nullptr;
44 Node* next_iteration = nullptr;
45 Node* exit = nullptr;
46 };
47
48 // Information about a loop frame.
49 struct WhileLoopFrame {
50 string name;
51
52 // Pointer to the parent frame. The root frame has a pointer to itself.
53 WhileLoopFrame* parent = nullptr;
54 int num_children = 0;
55
56 // Arguments to this loop.
57 std::vector<WhileLoopArg> args;
58
59 // The loop condition of the loop. There should be exactly one loop condition
60 // in every loop.
61 Node* loop_cond = nullptr;
62
63 // Set of nodes that belong to the loop frame.
64 std::unordered_set<Node*> nodes;
65
66 // After `ExtractWhileLoopFrames` this is true if for all control flow nodes
67 // of this frame `node_filter` returns true, i.e., the frame should be
68 // functionalized, and false otherwise.
69 bool should_be_functionalized = true;
70 };
71
72 // Extracts v1 while loops within a graph and creates a map of
73 // <ControlFLowInfo.name, WhileLoopFrame>.
74 // If `node_filter` is defined, then we keep track of frames that should be
75 // functionalized according to the filter (see comment for
76 // `FunctionalizeControlFlow` for more details about node filters).
77 Status ExtractWhileLoopFrames(
78 const std::vector<ControlFlowInfo>& cf_info, const Graph* graph,
79 std::unordered_map<string, WhileLoopFrame>* frames,
80 const NodeFilter& node_filter = {});
81
82 // Check that the graph has no cycle containing the given node.
83 Status CheckNodeNotInCycle(const Node* node, const int num_nodes);
84
85 // Comparison function used for sorting nodes consistently.
86 // a) resource variables are last, and
87 // b) sort lexicographically by name (for deterministic output).
88 struct NodeCmpByNameResourcesLast {
89 bool operator()(const Node* lhs, const Node* rhs) const;
90 };
91
92 // Returns the Node* created from the NodeDef in the Graph.
93 xla::StatusOr<Node*> AddNodeDefToGraph(const NodeDef& node_def, Graph* graph);
94
95 // Build a retval node of given type and index.
96 xla::StatusOr<Node*> BuildRetvalNode(Graph* graph, DataType type, int index);
97
98 // Returns a textual representation of the names of the nodes in the input.
99 template <typename T>
NodesToString(const T & nodes)100 string NodesToString(const T& nodes) {
101 return absl::StrCat("{",
102 absl::StrJoin(nodes, ",",
103 [](string* output, const Node* node) {
104 absl::StrAppend(output, node->name());
105 }),
106 "}");
107 }
108
109 } // namespace tensorflow
110
111 #endif // TENSORFLOW_COMPILER_TF2XLA_FUNCTIONALIZE_CONTROL_FLOW_UTIL_H_
112