mirror of
https://github.com/github/codeql.git
synced 2025-12-17 09:13:20 +01:00
725 lines
25 KiB
Python
725 lines
25 KiB
Python
|
|
|
|
class SmallSet(list):
|
|
|
|
__slots__ = []
|
|
|
|
def update(self, other):
|
|
filtered = [x for x in other if x not in self]
|
|
self.extend(filtered)
|
|
|
|
def add(self, item):
|
|
if item not in self:
|
|
self.append(item)
|
|
|
|
class DiGraph(object):
|
|
'''A simple directed graph class (not necessarily a DAG).
|
|
Nodes must be hashable'''
|
|
|
|
def __init__(self, name = ""):
|
|
self.name = name
|
|
self.pred = {}
|
|
self.succ = {}
|
|
self.all_nodes = []
|
|
self.node_annotations = {}
|
|
self.edge_annotations = {}
|
|
|
|
def add_node(self, n):
|
|
'Add a node to the graph'
|
|
if n not in self.succ:
|
|
self.pred[n] = SmallSet()
|
|
self.succ[n] = SmallSet()
|
|
self.all_nodes.append(n)
|
|
|
|
def add_edge(self, x, y):
|
|
'''Add an edge (x -> y) to the graph. Return true if x, y was
|
|
previously in graph'''
|
|
if x in self.succ:
|
|
if y in self.succ[x]:
|
|
return True
|
|
else:
|
|
self.add_node(x)
|
|
self.add_node(y)
|
|
self.pred[y].add(x)
|
|
self.succ[x].add(y)
|
|
return False
|
|
|
|
def remove_node(self, x):
|
|
if x not in self.succ:
|
|
raise ValueError("Node %s does not exist." % x)
|
|
preds = self.pred[x]
|
|
succs = self.succ[x]
|
|
for p in preds:
|
|
self.succ[p].remove(x)
|
|
for s in succs:
|
|
self.pred[s].remove(x)
|
|
del self.succ[x]
|
|
del self.pred[x]
|
|
|
|
def remove_edge(self, x, y):
|
|
self.pred[y].remove(x)
|
|
self.succ[x].remove(y)
|
|
|
|
def annotate_edge(self, x, y, note):
|
|
'''Set the annotation on the edge (x -> y) to note.
|
|
'''
|
|
if x not in self.succ or y not in self.succ[x]:
|
|
raise ValueError("Edge %s -> %s does not exist." % (x, y))
|
|
self.edge_annotations[(x,y)] = note
|
|
|
|
def annotate_node(self, x, note):
|
|
'''Set the annotation on the node x to note.
|
|
'''
|
|
if x not in self.succ:
|
|
raise ValueError("Node %s does not exist." % x)
|
|
self.node_annotations[x] = note
|
|
|
|
def nodes(self):
|
|
'''Return an iterator for all nodes, in the form (node, note) pairs.
|
|
Do not modify the graph while using this iterator'''
|
|
for node in self.all_nodes:
|
|
yield node, self.node_annotations.get(node)
|
|
|
|
def edges(self):
|
|
'''Return an iterator for all edges, in the form of (pred, succ, note) triple.
|
|
Do not modify the graph while using this iterator'''
|
|
index = dict((n, i) for i, n in enumerate(self.all_nodes))
|
|
for n in self.all_nodes:
|
|
n_succs = self.succ[n]
|
|
for succ in sorted(n_succs, key = lambda n : index[n]):
|
|
yield n, succ, self.edge_annotations.get((n,succ))
|
|
|
|
def sources(self):
|
|
'''Return an iterator for all nodes with no predecessors.
|
|
Do not modify the graph while using this iterator'''
|
|
for n, p in self.pred.items():
|
|
if not p:
|
|
yield n
|
|
|
|
def __contains__(self, node):
|
|
return node in self.succ
|
|
|
|
|
|
class FlowGraph(DiGraph):
|
|
'''A DiGraph that supports the concept of definitions and variables.
|
|
Used to compute dominance and SSA form.
|
|
For more explanation of the algorithms used see
|
|
'Modern Compiler Implementation by Andrew W. Appel.
|
|
'''
|
|
|
|
def __init__(self, root, name):
|
|
DiGraph.__init__(self, name)
|
|
self.definitions = {}
|
|
self.deletions = {}
|
|
self.uses = {}
|
|
self.use_all_nodes = set()
|
|
self.root = root
|
|
|
|
def clear_computed(self):
|
|
to_be_deleted = [attr for attr in self.__dict__ if attr[0] == '_']
|
|
for attr in to_be_deleted:
|
|
delattr(self, attr)
|
|
|
|
def _require(self, what):
|
|
'''Ensures that 'what' has been computed (computing if needed).'''
|
|
if hasattr(self, "_" + what):
|
|
return
|
|
setattr(self, "_" + what, getattr(self, "_compute_" + what)())
|
|
|
|
def add_deletion(self, node, var):
|
|
assert node in self.succ
|
|
self.deletions[node] = var
|
|
|
|
def add_definition(self, node, var):
|
|
assert node in self.succ
|
|
self.definitions[node] = var
|
|
|
|
def add_use(self, node, var):
|
|
assert node in self.succ, node
|
|
self.uses[node] = var
|
|
|
|
def use_all_defined_variables(self, node):
|
|
assert node in self.succ
|
|
self.use_all_nodes.add(node)
|
|
|
|
def _compute_depth_first_pre_order(self):
|
|
self._require("depth_first_pre_order_labels")
|
|
reachable = [ f for f in self.all_nodes if f in self._depth_first_pre_order_labels ]
|
|
return sorted(reachable, key = lambda f : -self._depth_first_pre_order_labels[f])
|
|
|
|
def _compute_reachable(self):
|
|
self._require("depth_first_pre_order")
|
|
return frozenset(self._depth_first_pre_order)
|
|
|
|
def reachable_nodes(self):
|
|
self._require("reachable")
|
|
return self._reachable
|
|
|
|
def _compute_reversed_depth_first_pre_order(self):
|
|
self._require("depth_first_pre_order")
|
|
return reversed(self._depth_first_pre_order)
|
|
|
|
def _compute_bb_depth_first_pre_order(self):
|
|
self._require('depth_first_pre_order')
|
|
self._require('bb_heads')
|
|
bbs = []
|
|
for n in self._depth_first_pre_order:
|
|
if n in self._bb_heads:
|
|
bbs.append(n)
|
|
return bbs
|
|
|
|
def _compute_bb_reversed_depth_first_pre_order(self):
|
|
self._require("bb_depth_first_pre_order")
|
|
return reversed(self._bb_depth_first_pre_order)
|
|
|
|
def _compute_depth_first_pre_order_labels(self):
|
|
'Compute order with depth first search.'
|
|
orders = {}
|
|
order = 0
|
|
nodes_to_visit = [ self.root ]
|
|
while nodes_to_visit:
|
|
node = nodes_to_visit[-1]
|
|
orders[node] = 0
|
|
if node in self.succ:
|
|
for succ in self.succ[node]:
|
|
if succ not in orders:
|
|
nodes_to_visit.append(succ)
|
|
else:
|
|
order += 1
|
|
orders[node] = order
|
|
if node is nodes_to_visit[-1]:
|
|
nodes_to_visit.pop()
|
|
order += 1
|
|
orders[node] = order
|
|
return orders
|
|
|
|
def _compute_idoms(self):
|
|
self._require("depth_first_pre_order")
|
|
idoms = {}
|
|
|
|
def idom_intersection(n1, n2):
|
|
'Determine the last common idom of n1, n2'
|
|
orders = self._depth_first_pre_order_labels
|
|
while n1 is not n2:
|
|
while orders[n1] < orders[n2]:
|
|
n1 = idoms[n1]
|
|
while orders[n2] < orders[n1]:
|
|
n2 = idoms[n2]
|
|
return n1
|
|
|
|
for node in self._depth_first_pre_order:
|
|
if len(self.pred[node]) == 1:
|
|
idoms[node] = next(iter(self.pred[node]))
|
|
else:
|
|
idom = None
|
|
for p in self.pred[node]:
|
|
if p == self.root:
|
|
idom = p
|
|
elif p in idoms:
|
|
if idom is None:
|
|
idom = p
|
|
else:
|
|
idom = idom_intersection(idom, p)
|
|
if idom is not None:
|
|
idoms[node] = idom
|
|
return idoms
|
|
|
|
def idoms(self):
|
|
'''Returns an iterable of node pairs: node, idom(node)'''
|
|
self._require('idoms')
|
|
idoms = self._idoms
|
|
for n in self.all_nodes:
|
|
if n in idoms:
|
|
yield n, idoms[n]
|
|
|
|
|
|
def _compute_dominance_frontier(self):
|
|
'''Compute the dominance frontier:
|
|
DF[n] = DF_local[n] Union over C in children DF_up[c]'''
|
|
|
|
def dominates(dom, node):
|
|
while node in idoms:
|
|
next_node = idoms[node]
|
|
if dom == next_node:
|
|
return True
|
|
node = next_node
|
|
return False
|
|
|
|
self._require('idoms')
|
|
idoms = self._idoms
|
|
dominance_frontier = {}
|
|
df_up = {}
|
|
dom_tree = _reverse_map(idoms)
|
|
self._require('reversed_depth_first_pre_order')
|
|
for node in self._reversed_depth_first_pre_order:
|
|
df_local_n = set(n for n in self.succ[node] if node != idoms[n])
|
|
dfn = df_local_n
|
|
if node in dom_tree:
|
|
for child in dom_tree[node]:
|
|
dfn.update(df_up[child])
|
|
dominance_frontier[node] = dfn
|
|
if node in idoms:
|
|
imm_dom = idoms[node]
|
|
df_up[node] = set(n for n in dfn if not dominates(imm_dom, n))
|
|
else:
|
|
df_up[node] = dfn
|
|
return dominance_frontier
|
|
|
|
def _compute_phi_nodes(self):
|
|
'''Compute the phi nodes for this graph.
|
|
A minimal set of phi-nodes are computed;
|
|
No phi-nodes are added unless the variable is live.
|
|
'''
|
|
self._require('dominance_frontier')
|
|
self._require('liveness')
|
|
dominance_frontier = self._dominance_frontier
|
|
definitions = dict(self.definitions)
|
|
# We must count deletions as definitions here. Otherwise, we can have
|
|
# uses of a deleted variable whose SSA definition is an actual definition,
|
|
# rather than a deletion.
|
|
definitions.update(self.deletions)
|
|
phi_nodes = {}
|
|
defsites = {}
|
|
for a in definitions.values():
|
|
defsites[a] = set()
|
|
for n in definitions:
|
|
a = definitions[n]
|
|
defsites[a].add(n)
|
|
for a in defsites:
|
|
W = set(defsites[a])
|
|
while W:
|
|
n = W.pop()
|
|
if n not in dominance_frontier:
|
|
continue
|
|
for y in dominance_frontier[n]:
|
|
if y not in phi_nodes:
|
|
phi_nodes[y] = set()
|
|
if a not in phi_nodes[y]:
|
|
phi_nodes[y].add(a)
|
|
if y not in definitions or a != definitions[y]:
|
|
W.add(y)
|
|
trimmed = {}
|
|
for node in phi_nodes:
|
|
assert node in self._bb_heads
|
|
if node not in self._liveness:
|
|
continue
|
|
new_phi_vars = set()
|
|
phi_vars = phi_nodes[node]
|
|
for v in phi_vars:
|
|
if v in self._liveness[node]:
|
|
new_phi_vars.add(v)
|
|
if new_phi_vars:
|
|
trimmed[node] = new_phi_vars
|
|
return trimmed
|
|
|
|
def _compute_ssa_data(self):
|
|
''' Compute the SSA variables, definitions, uses and phi-inputs.
|
|
'''
|
|
self._require('basic_blocks')
|
|
self._require('phi_nodes')
|
|
self._require('bb_depth_first_pre_order')
|
|
self._require('use_all')
|
|
phi_nodes = self._phi_nodes
|
|
reaching_ssa_vars = {}
|
|
work_set = set()
|
|
work_set.add(self.root)
|
|
ssa_defns = {}
|
|
ssa_uses = {}
|
|
ssa_phis = {}
|
|
ssa_vars = set()
|
|
ssa_var_cache = {}
|
|
|
|
def make_ssa_var(variable, node):
|
|
'''Ensure that there is no more than one SSA variable for each (variable, node) pair.'''
|
|
uid = (variable, node)
|
|
if uid in ssa_var_cache:
|
|
return ssa_var_cache[uid]
|
|
var = SSA_Var(variable, node)
|
|
ssa_var_cache[uid] = var
|
|
return var
|
|
|
|
for bb in self._bb_depth_first_pre_order:
|
|
#Track SSA variables in each BB.
|
|
reaching_ssa_vars[bb] = {}
|
|
for bb in self._bb_depth_first_pre_order:
|
|
live_vars = reaching_ssa_vars[bb].copy()
|
|
#Add an SSA definition for each phi-node.
|
|
if bb in phi_nodes:
|
|
variables = phi_nodes[bb]
|
|
for v in variables:
|
|
var = make_ssa_var(v, bb)
|
|
ssa_defns[var] = bb
|
|
live_vars[v] = var
|
|
for node in self.nodes_in_bb(bb):
|
|
#Add an SSA use for each use.
|
|
if node in self.uses:
|
|
a = self.uses[node]
|
|
if a not in live_vars:
|
|
#Treat a use as adding a reaching variable,
|
|
#since a second use, if it can be reached,
|
|
#will always find the variable defined.
|
|
var = make_ssa_var(a, node)
|
|
live_vars[a] = var
|
|
else:
|
|
var = live_vars[a]
|
|
ssa_vars.add(var)
|
|
ssa_uses[node] = [ var ]
|
|
#Add an SSA use for all live SSA variables for
|
|
#each use_all (end of module/class scope).
|
|
if node in self._use_all:
|
|
all_live = [ var for var in live_vars.values() if var.variable in self._use_all[node]]
|
|
ssa_uses[node] = all_live
|
|
ssa_vars.update(all_live)
|
|
#Add an SSA definition for each definition.
|
|
if node in self.definitions:
|
|
a = self.definitions[node]
|
|
var = make_ssa_var(a, node)
|
|
ssa_defns[var] = node
|
|
live_vars[a] = var
|
|
#Although deletions are not definitions, we treat them as such.
|
|
#SSA form has no concept of deletion, so we have to treat `del x`
|
|
#as `x = Undefined`.
|
|
if node in self.deletions:
|
|
a = self.deletions[node]
|
|
if a in live_vars:
|
|
var = live_vars[a]
|
|
ssa_vars.add(var)
|
|
ssa_uses[node] = [ var ]
|
|
else:
|
|
#If no var is defined here we don't need to create one
|
|
#as a new one will be immediately be defined by the deletion.
|
|
pass
|
|
var = make_ssa_var(a, node)
|
|
ssa_defns[var] = node
|
|
live_vars[a] = var
|
|
#Propagate set of reaching variables to
|
|
#successor blocks.
|
|
for n in self.succ[node]:
|
|
reaching_ssa_vars[n].update(live_vars)
|
|
if n in phi_nodes:
|
|
for v in phi_nodes[n]:
|
|
if v in live_vars:
|
|
var = make_ssa_var(v, n)
|
|
if var not in ssa_phis:
|
|
ssa_phis[var] = set()
|
|
ssa_vars.add(live_vars[v])
|
|
ssa_phis[var].add(live_vars[v])
|
|
#Prune unused definitions.
|
|
used_ssa_defns = {}
|
|
for var in ssa_defns:
|
|
if var in ssa_vars:
|
|
used_ssa_defns[var] = ssa_defns[var]
|
|
ssa_defns = used_ssa_defns
|
|
sorted_vars = list(self._sort_ssa_variables(ssa_vars))
|
|
assert set(sorted_vars) == ssa_vars
|
|
assert len(sorted_vars) == len(ssa_vars)
|
|
ssa_vars = sorted_vars
|
|
return ssa_vars, ssa_defns, ssa_uses, ssa_phis
|
|
|
|
|
|
def ssa_variables(self):
|
|
'''Returns all the SSA variables for this graph'''
|
|
self._require('ssa_data')
|
|
return self._ssa_data[0]
|
|
|
|
def _sort_ssa_variables(self, ssa_vars):
|
|
node_to_var = {}
|
|
for v in ssa_vars:
|
|
node = v.node
|
|
if node in node_to_var:
|
|
vset = node_to_var[node]
|
|
else:
|
|
vset = set()
|
|
node_to_var[node] = vset
|
|
vset.add(v)
|
|
for n in self.all_nodes:
|
|
if n in node_to_var:
|
|
variables = node_to_var[n]
|
|
for v in sorted(variables, key=lambda v:v.variable.id):
|
|
yield v
|
|
|
|
def ssa_definitions(self):
|
|
'''Returns all the SSA definition as an iterator of (node, variable) pairs.'''
|
|
self._require('ssa_data')
|
|
ssa_defns = self._ssa_data[1]
|
|
reversed_defns = _reverse_map(ssa_defns)
|
|
for n in self.all_nodes:
|
|
if n in reversed_defns:
|
|
variables = reversed_defns[n]
|
|
for v in sorted(variables, key=lambda v:v.variable.id):
|
|
yield n, v
|
|
|
|
def get_ssa_definition(self, var):
|
|
'''Returns the definition node of var. Returns None if there is no definition.'''
|
|
self._require('ssa_data')
|
|
ssa_defns = self._ssa_data[1]
|
|
return ssa_defns.get(var)
|
|
|
|
def ssa_uses(self):
|
|
'''Returns all the SSA uses as an iterator of (node, variable) pairs.'''
|
|
self._require('ssa_data')
|
|
ssa_uses = self._ssa_data[2]
|
|
for n in self.all_nodes:
|
|
if n in ssa_uses:
|
|
variables = ssa_uses[n]
|
|
for v in sorted(variables, key=lambda v:v.variable.id):
|
|
yield n, v
|
|
|
|
def get_ssa_variables_used(self, node):
|
|
'''Returns all the SSA variables used at this node'''
|
|
self._require('ssa_data')
|
|
ssa_uses = self._ssa_data[2]
|
|
return ssa_uses.get(node, ())
|
|
|
|
def ssa_phis(self):
|
|
'''Return all SSA phi inputs as an iterator of (variable, input-variable) pairs.'''
|
|
self._require('ssa_data')
|
|
ssa_phis = self._ssa_data[3]
|
|
ssa_vars = self._ssa_data[0]
|
|
indexed = dict((v, index) for index, v in enumerate(ssa_vars))
|
|
for v in ssa_vars:
|
|
if v not in ssa_phis:
|
|
continue
|
|
phis = ssa_phis[v]
|
|
for phi in sorted(phis, key=lambda v:indexed[v]):
|
|
yield v, phi
|
|
|
|
def _compute_bb_heads(self):
|
|
'''Compute all flow nodes that are the first node in a basic block.'''
|
|
bb_heads = set()
|
|
for node in self.all_nodes:
|
|
preds = self.pred[node]
|
|
if len(preds) != 1 or len(self.succ[preds[0]]) != 1:
|
|
bb_heads.add(node)
|
|
return bb_heads
|
|
|
|
def _compute_basic_blocks(self):
|
|
'''Compute Basic blocks membership'''
|
|
self._require('bb_heads')
|
|
basic_blocks = {}
|
|
bb_tails = {}
|
|
for bb in self._bb_heads:
|
|
for index, node in enumerate(self.nodes_in_bb(bb)):
|
|
basic_blocks[node] = bb, index
|
|
bb_tails[bb] = node
|
|
self._bb_tails = bb_tails
|
|
return basic_blocks
|
|
|
|
def get_basic_blocks(self):
|
|
self._require('basic_blocks')
|
|
return self._basic_blocks
|
|
|
|
def _compute_bb_succ(self):
|
|
self._require('basic_blocks')
|
|
bb_succs = {}
|
|
for bb in self._bb_heads:
|
|
bb_succs[bb] = self.succ[self._bb_tails[bb]]
|
|
return bb_succs
|
|
|
|
def _compute_bb_pred(self):
|
|
self._require('basic_blocks')
|
|
bb_preds = {}
|
|
for bb in self._bb_heads:
|
|
preds_of_bb = self.pred[bb]
|
|
bb_preds[bb] = SmallSet(self._basic_blocks[p][0] for p in preds_of_bb)
|
|
return bb_preds
|
|
|
|
def nodes_in_bb(self, bb):
|
|
'''Return an iterator over all node in basic block 'bb.'''
|
|
node = bb
|
|
while True:
|
|
yield node
|
|
succs = self.succ[node]
|
|
if not succs:
|
|
return
|
|
node = succs[0]
|
|
if node in self._bb_heads:
|
|
return
|
|
|
|
|
|
def _compute_use_all(self):
|
|
'''Compute which variables have been defined.
|
|
A variable is defined at node n, if there is a path to n which
|
|
passes through a definition, but not through a subsequent deletion.
|
|
'''
|
|
|
|
self._require('bb_heads')
|
|
self._require('bb_succ')
|
|
self._require('bb_pred')
|
|
use_all = {}
|
|
|
|
def defined_in_block(bb):
|
|
defined = defined_at_start[bb].copy()
|
|
for node in self.nodes_in_bb(bb):
|
|
if node in self.definitions:
|
|
var = self.definitions[node]
|
|
defined.add(var)
|
|
if node in self.deletions:
|
|
var = self.deletions[node]
|
|
defined.discard(var)
|
|
if node in self.use_all_nodes:
|
|
use_all[node] = frozenset(defined)
|
|
return defined
|
|
|
|
defined_at_start = {}
|
|
work_set = set()
|
|
for bb in self._bb_heads:
|
|
if not self._bb_pred[bb]:
|
|
work_set.add(bb)
|
|
defined_at_start[bb] = set()
|
|
work_list = list(work_set)
|
|
while work_list:
|
|
bb = work_list.pop()
|
|
work_set.remove(bb)
|
|
defined_at_bb_end = defined_in_block(bb)
|
|
for succ in self._bb_succ[bb]:
|
|
if succ not in defined_at_start:
|
|
defined_at_start[succ] = set()
|
|
elif defined_at_start[succ] >= defined_at_bb_end:
|
|
continue
|
|
defined_at_start[succ].update(defined_at_bb_end)
|
|
if succ not in work_set:
|
|
work_list.append(succ)
|
|
work_set.add(succ)
|
|
return use_all
|
|
|
|
def _compute_liveness(self):
|
|
'''Compute liveness of all variables in this flow-graph.
|
|
Return a mapping of basic blocks to the set of variables
|
|
that are live at the start of that basic block.
|
|
See http://en.wikipedia.org/wiki/Live_variable_analysis.'''
|
|
|
|
self._require('bb_pred')
|
|
self._require('use_all')
|
|
|
|
def gen_and_kill_for_block(bb):
|
|
gen = set()
|
|
kill = set()
|
|
for node in reversed(list(self.nodes_in_bb(bb))):
|
|
if node in self.uses:
|
|
var = self.uses[node]
|
|
gen.add(var)
|
|
kill.discard(var)
|
|
if node in self.deletions:
|
|
var = self.deletions[node]
|
|
gen.add(var)
|
|
kill.discard(var)
|
|
if node in self.definitions:
|
|
var = self.definitions[node]
|
|
gen.discard(var)
|
|
kill.add(var)
|
|
if node in self._use_all:
|
|
for var in self._use_all[node]:
|
|
gen.add(var)
|
|
kill.discard(var)
|
|
return gen, kill
|
|
|
|
def liveness_for_block(bb, live_out):
|
|
return gens[bb].union(live_out.difference(kills[bb]))
|
|
|
|
live_at_end = {}
|
|
live_at_start = {}
|
|
gens = {}
|
|
kills = {}
|
|
work_set = set()
|
|
#Initialise
|
|
for bb in self._bb_heads:
|
|
gens[bb], kills[bb] = gen_and_kill_for_block(bb)
|
|
live_at_end[bb] = set()
|
|
live_at_start[bb] = set()
|
|
work_set.add(bb)
|
|
#Find fixed point
|
|
while work_set:
|
|
bb = work_set.pop()
|
|
live_in = liveness_for_block(bb, live_at_end[bb])
|
|
if live_in != live_at_start[bb]:
|
|
assert len(live_in) > len(live_at_start[bb])
|
|
live_at_start[bb] = live_in
|
|
for pred in self._bb_pred[bb]:
|
|
work_set.add(pred)
|
|
live_at_end[pred] = live_at_end[pred].union(live_in)
|
|
return live_at_start
|
|
|
|
|
|
def delete_unreachable_nodes(self):
|
|
self._require("reachable")
|
|
unreachable = [u for u in self.all_nodes if u not in self._reachable]
|
|
if not unreachable:
|
|
return
|
|
for mapping in (self.definitions, self.deletions, self.uses):
|
|
for u in unreachable:
|
|
if u in mapping:
|
|
del mapping[u]
|
|
for u in unreachable:
|
|
self.use_all_nodes.discard(u)
|
|
self.remove_node(u)
|
|
#Make sure we retain the order of all_nodes.
|
|
self.all_nodes = [r for r in self.all_nodes if r in self._reachable]
|
|
self.clear_computed()
|
|
|
|
def dominated_by(self, node):
|
|
self._require('idoms')
|
|
assert node in self, str(node) + " is not in graph"
|
|
dominated = set([node])
|
|
todo = set(self.succ[node])
|
|
while todo:
|
|
n = todo.pop()
|
|
if n in dominated:
|
|
continue
|
|
#Unreachable nodes will not be in self._idoms
|
|
if n in self._idoms and self._idoms[n] in dominated:
|
|
dominated.add(n)
|
|
todo.update(self.succ[n])
|
|
return dominated
|
|
|
|
def strictly_dominates(self, pre, post):
|
|
self._require('idoms')
|
|
while post in self._idoms:
|
|
post = self._idoms[post]
|
|
if pre == post:
|
|
return True
|
|
return False
|
|
|
|
def reaches_while_dominated(self, pre, post, control):
|
|
''' Holds if `pre` reaches `post` while remaining in the
|
|
region dominated by `control`.'''
|
|
self._require('dominance_frontier')
|
|
dominance_frontier = self._dominance_frontier[control]
|
|
todo = { pre }
|
|
reached = set()
|
|
while todo:
|
|
node = todo.pop()
|
|
if node in dominance_frontier:
|
|
continue
|
|
if node == post:
|
|
return True
|
|
if node in reached:
|
|
continue
|
|
reached.add(node)
|
|
todo.update(self.succ[node])
|
|
return False
|
|
|
|
|
|
class SSA_Var(object):
|
|
'A single static assignment variable'
|
|
|
|
__slots__ = [ 'variable', 'node' ]
|
|
|
|
def __init__(self, variable, node):
|
|
self.variable = variable
|
|
self.node = node
|
|
|
|
def __repr__(self):
|
|
return 'SSA_Var(%r, %r)' % (self.variable.id, self.node)
|
|
|
|
|
|
def _reverse_map(mapping):
|
|
'Reverse a mapping of keys -> values to value->set(keys)'
|
|
inv_map = {}
|
|
for k, v in mapping.items():
|
|
if v not in inv_map:
|
|
inv_map[v] = SmallSet()
|
|
inv_map[v].add(k)
|
|
return inv_map
|
|
|