Coverage for /pythoncovmergedfiles/medio/medio/usr/local/lib/python3.8/site-packages/tensorflow/python/autograph/pyct/static_analysis/liveness.py: 24%
113 statements
« prev ^ index » next coverage.py v7.4.0, created at 2024-01-03 07:57 +0000
1# Copyright 2018 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"""Live variable analysis.
17See https://en.wikipedia.org/wiki/Live_variable_analysis for a definition of
18the following idioms: live variable, live in, live out, which are used
19throughout this file.
21This analysis attaches the following:
22 * symbols that are live at the exit of control flow statements
23 * symbols that are live at the entry of control flow statements
25Requires activity analysis.
26"""
28import gast
30from tensorflow.python.autograph.pyct import anno
31from tensorflow.python.autograph.pyct import cfg
32from tensorflow.python.autograph.pyct import transformer
33from tensorflow.python.autograph.pyct.static_analysis import annos
36class Analyzer(cfg.GraphVisitor):
37 """CFG visitor that performs liveness analysis at statement level."""
39 def __init__(self, graph, include_annotations):
40 super(Analyzer, self).__init__(graph)
41 self.include_annotations = include_annotations
43 def init_state(self, _):
44 return set()
46 def lamba_check(self, fn_ast_node):
47 if isinstance(fn_ast_node, gast.Lambda):
48 # Exception: lambda functions are assumed to be used only in the
49 # place where they are defined, and not later.
50 return True
51 return False
53 def visit_node(self, node):
54 prev_live_in = self.in_[node]
56 if anno.hasanno(node.ast_node, anno.Static.SCOPE):
57 node_scope = anno.getanno(node.ast_node, anno.Static.SCOPE)
59 gen = node_scope.read
60 if not self.include_annotations:
61 gen -= node_scope.annotations
62 # TODO(mdan): verify whether composites' parents need to be added.
63 # E.g. whether x needs to be added if x.y is live. Theoretically the
64 # activity analysis should have both so that wouldn't be needed.
65 kill = node_scope.modified | node_scope.deleted
67 live_out = set()
68 for n in node.next:
69 live_out |= self.in_[n]
70 live_in = gen | (live_out - kill)
72 reaching_functions = anno.getanno(
73 node.ast_node, anno.Static.DEFINED_FNS_IN)
74 for fn_ast_node in reaching_functions:
75 if self.lamba_check(fn_ast_node):
76 continue
77 fn_scope = anno.getanno(fn_ast_node, annos.NodeAnno.ARGS_AND_BODY_SCOPE)
78 # Any closure of a reaching function definition is conservatively
79 # considered live.
80 live_in |= (fn_scope.read - fn_scope.bound)
82 else:
83 assert self.can_ignore(node), (node.ast_node, node)
85 live_out = set()
86 for n in node.next:
87 live_out |= self.in_[n]
88 live_in = live_out
90 self.in_[node] = live_in
91 self.out[node] = live_out
93 # TODO(mdan): Move this to the superclass?
94 return prev_live_in != live_in
97class TreeAnnotator(transformer.Base):
98 """Runs liveness analysis on each of the functions defined in the AST.
100 If a function defined other local functions, those will have separate CFGs.
101 However, dataflow analysis needs to tie up these CFGs to properly emulate the
102 effect of closures. In the case of liveness, the parent function's live
103 variables must account for the variables that are live at the entry of each
104 subfunction. For example:
106 def foo():
107 # baz is live from here on
108 def bar():
109 print(baz)
111 This analyzer runs liveness analysis on each individual function, accounting
112 for the effect above.
113 """
115 def __init__(self, source_info, graphs, include_annotations):
116 super(TreeAnnotator, self).__init__(source_info)
117 self.include_annotations = include_annotations
118 self.allow_skips = False
119 self.graphs = graphs
120 self.current_analyzer = None
122 def visit(self, node):
123 node = super(TreeAnnotator, self).visit(node)
124 if (self.current_analyzer is not None and
125 isinstance(node, gast.stmt) and
126 node in self.current_analyzer.graph.index):
127 cfg_node = self.current_analyzer.graph.index[node]
128 anno.setanno(node, anno.Static.LIVE_VARS_IN,
129 frozenset(self.current_analyzer.in_[cfg_node]))
130 return node
132 def _analyze_function(self, node, is_lambda):
133 parent_analyzer = self.current_analyzer
135 analyzer = Analyzer(self.graphs[node], self.include_annotations)
136 analyzer.visit_reverse()
137 self.current_analyzer = analyzer
138 node = self.generic_visit(node)
140 self.current_analyzer = parent_analyzer
141 return node
143 def visit_Lambda(self, node):
144 return self._analyze_function(node, is_lambda=True)
146 def visit_FunctionDef(self, node):
147 return self._analyze_function(node, is_lambda=False)
149 def _block_statement_live_out(self, node):
150 successors = self.current_analyzer.graph.stmt_next[node]
151 stmt_live_out = set()
152 for s in successors:
153 stmt_live_out.update(self.current_analyzer.in_[s])
154 anno.setanno(node, anno.Static.LIVE_VARS_OUT, frozenset(stmt_live_out))
155 return node
157 def _block_statement_live_in(self, node, entry_node):
158 if entry_node in self.current_analyzer.graph.index:
159 cfg_node = self.current_analyzer.graph.index[entry_node]
160 stmt_live_in = frozenset(self.current_analyzer.in_[cfg_node])
161 else:
162 assert anno.hasanno(entry_node, anno.Static.LIVE_VARS_IN), (
163 'If not matching a CFG node, must be a block statement:'
164 ' {}'.format(entry_node))
165 stmt_live_in = anno.getanno(entry_node, anno.Static.LIVE_VARS_IN)
166 anno.setanno(node, anno.Static.LIVE_VARS_IN, stmt_live_in)
167 return node
169 def visit_If(self, node):
170 node = self.generic_visit(node)
171 node = self._block_statement_live_out(node)
172 return self._block_statement_live_in(node, node.test)
174 def visit_For(self, node):
175 node = self.generic_visit(node)
176 node = self._block_statement_live_out(node)
177 return self._block_statement_live_in(node, node.iter)
179 def visit_While(self, node):
180 node = self.generic_visit(node)
181 node = self._block_statement_live_out(node)
182 return self._block_statement_live_in(node, node.test)
184 def visit_Try(self, node):
185 node = self.generic_visit(node)
186 node = self._block_statement_live_out(node)
187 return self._block_statement_live_in(node, node.body[0])
189 def visit_ExceptHandler(self, node):
190 node = self.generic_visit(node)
191 node = self._block_statement_live_out(node)
192 return self._block_statement_live_in(node, node.body[0])
194 def visit_With(self, node):
195 node = self.generic_visit(node)
196 return self._block_statement_live_in(node, node.items[0])
198 def visit_Expr(self, node):
199 node = self.generic_visit(node)
200 cfg_node = self.current_analyzer.graph.index[node]
201 anno.setanno(node, anno.Static.LIVE_VARS_OUT,
202 frozenset(self.current_analyzer.out[cfg_node]))
203 return node
206# TODO(mdan): Investigate the possibility of removing include_annotations.
207def resolve(node, source_info, graphs, include_annotations=True):
208 """Resolves the live symbols at the exit of control flow statements.
210 Args:
211 node: ast.AST
212 source_info: transformer.SourceInfo
213 graphs: Dict[ast.FunctionDef, cfg.Graph]
214 include_annotations: Bool, whether type annotations should be included in
215 the analysis.
216 Returns:
217 ast.AST
218 """
219 node = TreeAnnotator(source_info, graphs, include_annotations).visit(node)
220 return node