| # Copyright (c) 2021, Alliance for Open Media. All rights reserved | |
| # | |
| # This source code is subject to the terms of the BSD 2 Clause License and | |
| # the Alliance for Open Media Patent License 1.0. If the BSD 2 Clause License | |
| # was not distributed with this source code in the LICENSE file, you can | |
| # obtain it at www.aomedia.org/license/software. If the Alliance for Open | |
| # Media Patent License 1.0 was not distributed with this source code in the | |
| # PATENTS file, you can obtain it at www.aomedia.org/license/patent. | |
| # | |
| from __future__ import print_function | |
| import sys | |
| import os | |
| import operator | |
| from pycparser import c_parser, c_ast, parse_file | |
| from math import * | |
| from inspect import currentframe, getframeinfo | |
| from collections import deque | |
| def debug_print(frameinfo): | |
| print('******** ERROR:', frameinfo.filename, frameinfo.lineno, '********') | |
| class StructItem(): | |
| def __init__(self, | |
| typedef_name=None, | |
| struct_name=None, | |
| struct_node=None, | |
| is_union=False): | |
| self.typedef_name = typedef_name | |
| self.struct_name = struct_name | |
| self.struct_node = struct_node | |
| self.is_union = is_union | |
| self.child_decl_map = None | |
| def __str__(self): | |
| return str(self.typedef_name) + ' ' + str(self.struct_name) + ' ' + str( | |
| self.is_union) | |
| def compute_child_decl_map(self, struct_info): | |
| self.child_decl_map = {} | |
| if self.struct_node != None and self.struct_node.decls != None: | |
| for decl_node in self.struct_node.decls: | |
| if decl_node.name == None: | |
| for sub_decl_node in decl_node.type.decls: | |
| sub_decl_status = parse_decl_node(struct_info, sub_decl_node) | |
| self.child_decl_map[sub_decl_node.name] = sub_decl_status | |
| else: | |
| decl_status = parse_decl_node(struct_info, decl_node) | |
| self.child_decl_map[decl_status.name] = decl_status | |
| def get_child_decl_status(self, decl_name): | |
| if self.child_decl_map == None: | |
| debug_print(getframeinfo(currentframe())) | |
| print('child_decl_map is None') | |
| return None | |
| if decl_name not in self.child_decl_map: | |
| debug_print(getframeinfo(currentframe())) | |
| print(decl_name, 'does not exist ') | |
| return None | |
| return self.child_decl_map[decl_name] | |
| class StructInfo(): | |
| def __init__(self): | |
| self.struct_name_dic = {} | |
| self.typedef_name_dic = {} | |
| self.enum_value_dic = {} # enum value -> enum_node | |
| self.enum_name_dic = {} # enum name -> enum_node | |
| self.struct_item_list = [] | |
| def get_struct_by_typedef_name(self, typedef_name): | |
| if typedef_name in self.typedef_name_dic: | |
| return self.typedef_name_dic[typedef_name] | |
| else: | |
| return None | |
| def get_struct_by_struct_name(self, struct_name): | |
| if struct_name in self.struct_name_dic: | |
| return self.struct_name_dic[struct_name] | |
| else: | |
| debug_print(getframeinfo(currentframe())) | |
| print('Cant find', struct_name) | |
| return None | |
| def update_struct_item_list(self): | |
| # Collect all struct_items from struct_name_dic and typedef_name_dic | |
| # Compute child_decl_map for each struct item. | |
| for struct_name in self.struct_name_dic.keys(): | |
| struct_item = self.struct_name_dic[struct_name] | |
| struct_item.compute_child_decl_map(self) | |
| self.struct_item_list.append(struct_item) | |
| for typedef_name in self.typedef_name_dic.keys(): | |
| struct_item = self.typedef_name_dic[typedef_name] | |
| if struct_item.struct_name not in self.struct_name_dic: | |
| struct_item.compute_child_decl_map(self) | |
| self.struct_item_list.append(struct_item) | |
| def update_enum(self, enum_node): | |
| if enum_node.name != None: | |
| self.enum_name_dic[enum_node.name] = enum_node | |
| if enum_node.values != None: | |
| enumerator_list = enum_node.values.enumerators | |
| for enumerator in enumerator_list: | |
| self.enum_value_dic[enumerator.name] = enum_node | |
| def update(self, | |
| typedef_name=None, | |
| struct_name=None, | |
| struct_node=None, | |
| is_union=False): | |
| """T: typedef_name S: struct_name N: struct_node | |
| T S N | |
| case 1: o o o | |
| typedef struct P { | |
| int u; | |
| } K; | |
| T S N | |
| case 2: o o x | |
| typedef struct P K; | |
| T S N | |
| case 3: x o o | |
| struct P { | |
| int u; | |
| }; | |
| T S N | |
| case 4: o x o | |
| typedef struct { | |
| int u; | |
| } K; | |
| """ | |
| struct_item = None | |
| # Check whether struct_name or typedef_name is already in the dictionary | |
| if struct_name in self.struct_name_dic: | |
| struct_item = self.struct_name_dic[struct_name] | |
| if typedef_name in self.typedef_name_dic: | |
| struct_item = self.typedef_name_dic[typedef_name] | |
| if struct_item == None: | |
| struct_item = StructItem(typedef_name, struct_name, struct_node, is_union) | |
| if struct_node.decls != None: | |
| struct_item.struct_node = struct_node | |
| if struct_name != None: | |
| self.struct_name_dic[struct_name] = struct_item | |
| if typedef_name != None: | |
| self.typedef_name_dic[typedef_name] = struct_item | |
| class StructDefVisitor(c_ast.NodeVisitor): | |
| def __init__(self): | |
| self.struct_info = StructInfo() | |
| def visit_Struct(self, node): | |
| if node.decls != None: | |
| self.struct_info.update(None, node.name, node) | |
| self.generic_visit(node) | |
| def visit_Union(self, node): | |
| if node.decls != None: | |
| self.struct_info.update(None, node.name, node, True) | |
| self.generic_visit(node) | |
| def visit_Enum(self, node): | |
| self.struct_info.update_enum(node) | |
| self.generic_visit(node) | |
| def visit_Typedef(self, node): | |
| if node.type.__class__.__name__ == 'TypeDecl': | |
| typedecl = node.type | |
| if typedecl.type.__class__.__name__ == 'Struct': | |
| struct_node = typedecl.type | |
| typedef_name = node.name | |
| struct_name = struct_node.name | |
| self.struct_info.update(typedef_name, struct_name, struct_node) | |
| elif typedecl.type.__class__.__name__ == 'Union': | |
| union_node = typedecl.type | |
| typedef_name = node.name | |
| union_name = union_node.name | |
| self.struct_info.update(typedef_name, union_name, union_node, True) | |
| # TODO(angiebird): Do we need to deal with enum here? | |
| self.generic_visit(node) | |
| def build_struct_info(ast): | |
| v = StructDefVisitor() | |
| v.visit(ast) | |
| struct_info = v.struct_info | |
| struct_info.update_struct_item_list() | |
| return v.struct_info | |
| class DeclStatus(): | |
| def __init__(self, name, struct_item=None, is_ptr_decl=False): | |
| self.name = name | |
| self.struct_item = struct_item | |
| self.is_ptr_decl = is_ptr_decl | |
| def get_child_decl_status(self, decl_name): | |
| if self.struct_item != None: | |
| return self.struct_item.get_child_decl_status(decl_name) | |
| else: | |
| #TODO(angiebird): 2. Investigage the situation when a struct's definition can't be found. | |
| return None | |
| def __str__(self): | |
| return str(self.struct_item) + ' ' + str(self.name) + ' ' + str( | |
| self.is_ptr_decl) | |
| def peel_ptr_decl(decl_type_node): | |
| """ Remove PtrDecl and ArrayDecl layer """ | |
| is_ptr_decl = False | |
| peeled_decl_type_node = decl_type_node | |
| while peeled_decl_type_node.__class__.__name__ == 'PtrDecl' or peeled_decl_type_node.__class__.__name__ == 'ArrayDecl': | |
| is_ptr_decl = True | |
| peeled_decl_type_node = peeled_decl_type_node.type | |
| return is_ptr_decl, peeled_decl_type_node | |
| def parse_peeled_decl_type_node(struct_info, node): | |
| struct_item = None | |
| if node.__class__.__name__ == 'TypeDecl': | |
| if node.type.__class__.__name__ == 'IdentifierType': | |
| identifier_type_node = node.type | |
| typedef_name = identifier_type_node.names[0] | |
| struct_item = struct_info.get_struct_by_typedef_name(typedef_name) | |
| elif node.type.__class__.__name__ == 'Struct': | |
| struct_node = node.type | |
| if struct_node.name != None: | |
| struct_item = struct_info.get_struct_by_struct_name(struct_node.name) | |
| else: | |
| struct_item = StructItem(None, None, struct_node, False) | |
| struct_item.compute_child_decl_map(struct_info) | |
| elif node.type.__class__.__name__ == 'Union': | |
| # TODO(angiebird): Special treatment for Union? | |
| struct_node = node.type | |
| if struct_node.name != None: | |
| struct_item = struct_info.get_struct_by_struct_name(struct_node.name) | |
| else: | |
| struct_item = StructItem(None, None, struct_node, True) | |
| struct_item.compute_child_decl_map(struct_info) | |
| elif node.type.__class__.__name__ == 'Enum': | |
| # TODO(angiebird): Special treatment for Union? | |
| struct_node = node.type | |
| struct_item = None | |
| else: | |
| print('Unrecognized peeled_decl_type_node.type', | |
| node.type.__class__.__name__) | |
| else: | |
| # debug_print(getframeinfo(currentframe())) | |
| # print(node.__class__.__name__) | |
| #TODO(angiebird): Do we need to take care of this part? | |
| pass | |
| return struct_item | |
| def parse_decl_node(struct_info, decl_node): | |
| # struct_item is None if this decl_node is not a struct_item | |
| decl_node_name = decl_node.name | |
| decl_type_node = decl_node.type | |
| is_ptr_decl, peeled_decl_type_node = peel_ptr_decl(decl_type_node) | |
| struct_item = parse_peeled_decl_type_node(struct_info, peeled_decl_type_node) | |
| return DeclStatus(decl_node_name, struct_item, is_ptr_decl) | |
| def get_lvalue_lead(lvalue_node): | |
| """return '&' or '*' of lvalue if available""" | |
| if lvalue_node.__class__.__name__ == 'UnaryOp' and lvalue_node.op == '&': | |
| return '&' | |
| elif lvalue_node.__class__.__name__ == 'UnaryOp' and lvalue_node.op == '*': | |
| return '*' | |
| return None | |
| def parse_lvalue(lvalue_node): | |
| """get id_chain from lvalue""" | |
| id_chain = parse_lvalue_recursive(lvalue_node, []) | |
| return id_chain | |
| def parse_lvalue_recursive(lvalue_node, id_chain): | |
| """cpi->rd->u -> (cpi->rd)->u""" | |
| if lvalue_node.__class__.__name__ == 'ID': | |
| id_chain.append(lvalue_node.name) | |
| id_chain.reverse() | |
| return id_chain | |
| elif lvalue_node.__class__.__name__ == 'StructRef': | |
| id_chain.append(lvalue_node.field.name) | |
| return parse_lvalue_recursive(lvalue_node.name, id_chain) | |
| elif lvalue_node.__class__.__name__ == 'ArrayRef': | |
| return parse_lvalue_recursive(lvalue_node.name, id_chain) | |
| elif lvalue_node.__class__.__name__ == 'UnaryOp' and lvalue_node.op == '&': | |
| return parse_lvalue_recursive(lvalue_node.expr, id_chain) | |
| elif lvalue_node.__class__.__name__ == 'UnaryOp' and lvalue_node.op == '*': | |
| return parse_lvalue_recursive(lvalue_node.expr, id_chain) | |
| else: | |
| return None | |
| class FuncDefVisitor(c_ast.NodeVisitor): | |
| func_dictionary = {} | |
| def visit_FuncDef(self, node): | |
| func_name = node.decl.name | |
| self.func_dictionary[func_name] = node | |
| def build_func_dictionary(ast): | |
| v = FuncDefVisitor() | |
| v.visit(ast) | |
| return v.func_dictionary | |
| def get_func_start_coord(func_node): | |
| return func_node.coord | |
| def find_end_node(node): | |
| node_list = [] | |
| for c in node: | |
| node_list.append(c) | |
| if len(node_list) == 0: | |
| return node | |
| else: | |
| return find_end_node(node_list[-1]) | |
| def get_func_end_coord(func_node): | |
| return find_end_node(func_node).coord | |
| def get_func_size(func_node): | |
| start_coord = get_func_start_coord(func_node) | |
| end_coord = get_func_end_coord(func_node) | |
| if start_coord.file == end_coord.file: | |
| return end_coord.line - start_coord.line + 1 | |
| else: | |
| return None | |
| def save_object(obj, filename): | |
| with open(filename, 'wb') as obj_fp: | |
| pickle.dump(obj, obj_fp, protocol=-1) | |
| def load_object(filename): | |
| obj = None | |
| with open(filename, 'rb') as obj_fp: | |
| obj = pickle.load(obj_fp) | |
| return obj | |
| def get_av1_ast(gen_ast=False): | |
| # TODO(angiebird): Generalize this path | |
| c_filename = './av1_pp.c' | |
| print('generate ast') | |
| ast = parse_file(c_filename) | |
| #save_object(ast, ast_file) | |
| print('finished generate ast') | |
| return ast | |
| def get_func_param_id_map(func_def_node): | |
| param_id_map = {} | |
| func_decl = func_def_node.decl.type | |
| param_list = func_decl.args.params | |
| for decl in param_list: | |
| param_id_map[decl.name] = decl | |
| return param_id_map | |
| class IDTreeStack(): | |
| def __init__(self, global_id_tree): | |
| self.stack = deque() | |
| self.global_id_tree = global_id_tree | |
| def add_link_node(self, node, link_id_chain): | |
| link_node = self.add_id_node(link_id_chain) | |
| node.link_node = link_node | |
| node.link_id_chain = link_id_chain | |
| def push_id_tree(self, id_tree=None): | |
| if id_tree == None: | |
| id_tree = IDStatusNode() | |
| self.stack.append(id_tree) | |
| return id_tree | |
| def pop_id_tree(self): | |
| return self.stack.pop() | |
| def add_id_seed_node(self, id_seed, decl_status): | |
| return self.stack[-1].add_child(id_seed, decl_status) | |
| def get_id_seed_node(self, id_seed): | |
| idx = len(self.stack) - 1 | |
| while idx >= 0: | |
| id_node = self.stack[idx].get_child(id_seed) | |
| if id_node != None: | |
| return id_node | |
| idx -= 1 | |
| id_node = self.global_id_tree.get_child(id_seed) | |
| if id_node != None: | |
| return id_node | |
| return None | |
| def add_id_node(self, id_chain): | |
| id_seed = id_chain[0] | |
| id_seed_node = self.get_id_seed_node(id_seed) | |
| if id_seed_node == None: | |
| return None | |
| if len(id_chain) == 1: | |
| return id_seed_node | |
| return id_seed_node.add_descendant(id_chain[1:]) | |
| def get_id_node(self, id_chain): | |
| id_seed = id_chain[0] | |
| id_seed_node = self.get_id_seed_node(id_seed) | |
| if id_seed_node == None: | |
| return None | |
| if len(id_chain) == 1: | |
| return id_seed_node | |
| return id_seed_node.get_descendant(id_chain[1:]) | |
| def top(self): | |
| return self.stack[-1] | |
| class IDStatusNode(): | |
| def __init__(self, name=None, root=None): | |
| if root is None: | |
| self.root = self | |
| else: | |
| self.root = root | |
| self.name = name | |
| self.parent = None | |
| self.children = {} | |
| self.assign = False | |
| self.last_assign_coord = None | |
| self.refer = False | |
| self.last_refer_coord = None | |
| self.decl_status = None | |
| self.link_id_chain = None | |
| self.link_node = None | |
| self.visit = False | |
| def set_link_id_chain(self, link_id_chain): | |
| self.set_assign(False) | |
| self.link_id_chain = link_id_chain | |
| self.link_node = self.root.get_descendant(link_id_chain) | |
| def set_link_node(self, link_node): | |
| self.set_assign(False) | |
| self.link_id_chain = ['*'] | |
| self.link_node = link_node | |
| def get_link_id_chain(self): | |
| return self.link_id_chain | |
| def get_concrete_node(self): | |
| if self.visit == True: | |
| # return None when there is a loop | |
| return None | |
| self.visit = True | |
| if self.link_node == None: | |
| self.visit = False | |
| return self | |
| else: | |
| concrete_node = self.link_node.get_concrete_node() | |
| self.visit = False | |
| if concrete_node == None: | |
| return self | |
| return concrete_node | |
| def set_assign(self, assign, coord=None): | |
| concrete_node = self.get_concrete_node() | |
| concrete_node.assign = assign | |
| concrete_node.last_assign_coord = coord | |
| def get_assign(self): | |
| concrete_node = self.get_concrete_node() | |
| return concrete_node.assign | |
| def set_refer(self, refer, coord=None): | |
| concrete_node = self.get_concrete_node() | |
| concrete_node.refer = refer | |
| concrete_node.last_refer_coord = coord | |
| def get_refer(self): | |
| concrete_node = self.get_concrete_node() | |
| return concrete_node.refer | |
| def set_parent(self, parent): | |
| concrete_node = self.get_concrete_node() | |
| concrete_node.parent = parent | |
| def add_child(self, name, decl_status=None): | |
| concrete_node = self.get_concrete_node() | |
| if name not in concrete_node.children: | |
| child_id_node = IDStatusNode(name, concrete_node.root) | |
| concrete_node.children[name] = child_id_node | |
| if decl_status == None: | |
| # Check if the child decl_status can be inferred from its parent's | |
| # decl_status | |
| if self.decl_status != None: | |
| decl_status = self.decl_status.get_child_decl_status(name) | |
| child_id_node.set_decl_status(decl_status) | |
| return concrete_node.children[name] | |
| def get_child(self, name): | |
| concrete_node = self.get_concrete_node() | |
| if name in concrete_node.children: | |
| return concrete_node.children[name] | |
| else: | |
| return None | |
| def add_descendant(self, id_chain): | |
| current_node = self.get_concrete_node() | |
| for name in id_chain: | |
| current_node.add_child(name) | |
| parent_node = current_node | |
| current_node = current_node.get_child(name) | |
| current_node.set_parent(parent_node) | |
| return current_node | |
| def get_descendant(self, id_chain): | |
| current_node = self.get_concrete_node() | |
| for name in id_chain: | |
| current_node = current_node.get_child(name) | |
| if current_node == None: | |
| return None | |
| return current_node | |
| def get_children(self): | |
| current_node = self.get_concrete_node() | |
| return current_node.children | |
| def set_decl_status(self, decl_status): | |
| current_node = self.get_concrete_node() | |
| current_node.decl_status = decl_status | |
| def get_decl_status(self): | |
| current_node = self.get_concrete_node() | |
| return current_node.decl_status | |
| def __str__(self): | |
| if self.link_id_chain is None: | |
| return str(self.name) + ' a: ' + str(int(self.assign)) + ' r: ' + str( | |
| int(self.refer)) | |
| else: | |
| return str(self.name) + ' -> ' + ' '.join(self.link_id_chain) | |
| def collect_assign_refer_status(self, | |
| id_chain=None, | |
| assign_ls=None, | |
| refer_ls=None): | |
| if id_chain == None: | |
| id_chain = [] | |
| if assign_ls == None: | |
| assign_ls = [] | |
| if refer_ls == None: | |
| refer_ls = [] | |
| id_chain.append(self.name) | |
| if self.assign: | |
| info_str = ' '.join([ | |
| ' '.join(id_chain[1:]), 'a:', | |
| str(int(self.assign)), 'r:', | |
| str(int(self.refer)), | |
| str(self.last_assign_coord) | |
| ]) | |
| assign_ls.append(info_str) | |
| if self.refer: | |
| info_str = ' '.join([ | |
| ' '.join(id_chain[1:]), 'a:', | |
| str(int(self.assign)), 'r:', | |
| str(int(self.refer)), | |
| str(self.last_refer_coord) | |
| ]) | |
| refer_ls.append(info_str) | |
| for c in self.children: | |
| self.children[c].collect_assign_refer_status(id_chain, assign_ls, | |
| refer_ls) | |
| id_chain.pop() | |
| return assign_ls, refer_ls | |
| def show(self): | |
| assign_ls, refer_ls = self.collect_assign_refer_status() | |
| print('---- assign ----') | |
| for item in assign_ls: | |
| print(item) | |
| print('---- refer ----') | |
| for item in refer_ls: | |
| print(item) | |
| class FuncInOutVisitor(c_ast.NodeVisitor): | |
| def __init__(self, | |
| func_def_node, | |
| struct_info, | |
| func_dictionary, | |
| keep_body_id_tree=True, | |
| call_param_map=None, | |
| global_id_tree=None, | |
| func_history=None, | |
| unknown=None): | |
| self.func_dictionary = func_dictionary | |
| self.struct_info = struct_info | |
| self.param_id_map = get_func_param_id_map(func_def_node) | |
| self.parent_node = None | |
| self.global_id_tree = global_id_tree | |
| self.body_id_tree = None | |
| self.keep_body_id_tree = keep_body_id_tree | |
| if func_history == None: | |
| self.func_history = {} | |
| else: | |
| self.func_history = func_history | |
| if unknown == None: | |
| self.unknown = [] | |
| else: | |
| self.unknown = unknown | |
| self.id_tree_stack = IDTreeStack(global_id_tree) | |
| self.id_tree_stack.push_id_tree() | |
| #TODO move this part into a function | |
| for param in self.param_id_map: | |
| decl_node = self.param_id_map[param] | |
| decl_status = parse_decl_node(self.struct_info, decl_node) | |
| descendant = self.id_tree_stack.add_id_seed_node(decl_status.name, | |
| decl_status) | |
| if call_param_map is not None and param in call_param_map: | |
| # This is a function call. | |
| # Map the input parameter to the caller's nodes | |
| # TODO(angiebird): Can we use add_link_node here? | |
| descendant.set_link_node(call_param_map[param]) | |
| def get_id_tree_stack(self): | |
| return self.id_tree_stack | |
| def generic_visit(self, node): | |
| prev_parent = self.parent_node | |
| self.parent_node = node | |
| for c in node: | |
| self.visit(c) | |
| self.parent_node = prev_parent | |
| # TODO rename | |
| def add_new_id_tree(self, node): | |
| self.id_tree_stack.push_id_tree() | |
| self.generic_visit(node) | |
| id_tree = self.id_tree_stack.pop_id_tree() | |
| if self.parent_node == None and self.keep_body_id_tree == True: | |
| # this is function body | |
| self.body_id_tree = id_tree | |
| def visit_For(self, node): | |
| self.add_new_id_tree(node) | |
| def visit_Compound(self, node): | |
| self.add_new_id_tree(node) | |
| def visit_Decl(self, node): | |
| if node.type.__class__.__name__ != 'FuncDecl': | |
| decl_status = parse_decl_node(self.struct_info, node) | |
| descendant = self.id_tree_stack.add_id_seed_node(decl_status.name, | |
| decl_status) | |
| if node.init is not None: | |
| init_id_chain = self.process_lvalue(node.init) | |
| if init_id_chain != None: | |
| if decl_status.struct_item is None: | |
| init_descendant = self.id_tree_stack.add_id_node(init_id_chain) | |
| if init_descendant != None: | |
| init_descendant.set_refer(True, node.coord) | |
| else: | |
| self.unknown.append(node) | |
| descendant.set_assign(True, node.coord) | |
| else: | |
| self.id_tree_stack.add_link_node(descendant, init_id_chain) | |
| else: | |
| self.unknown.append(node) | |
| else: | |
| descendant.set_assign(True, node.coord) | |
| self.generic_visit(node) | |
| def is_lvalue(self, node): | |
| if self.parent_node is None: | |
| # TODO(angiebird): Do every lvalue has parent_node != None? | |
| return False | |
| if self.parent_node.__class__.__name__ == 'StructRef': | |
| return False | |
| if self.parent_node.__class__.__name__ == 'ArrayRef' and node == self.parent_node.name: | |
| # if node == self.parent_node.subscript, the node could be lvalue | |
| return False | |
| if self.parent_node.__class__.__name__ == 'UnaryOp' and self.parent_node.op == '&': | |
| return False | |
| if self.parent_node.__class__.__name__ == 'UnaryOp' and self.parent_node.op == '*': | |
| return False | |
| return True | |
| def process_lvalue(self, node): | |
| id_chain = parse_lvalue(node) | |
| if id_chain == None: | |
| return id_chain | |
| elif id_chain[0] in self.struct_info.enum_value_dic: | |
| return None | |
| else: | |
| return id_chain | |
| def process_possible_lvalue(self, node): | |
| if self.is_lvalue(node): | |
| id_chain = self.process_lvalue(node) | |
| lead_char = get_lvalue_lead(node) | |
| # make sure the id is not an enum value | |
| if id_chain == None: | |
| self.unknown.append(node) | |
| return | |
| descendant = self.id_tree_stack.add_id_node(id_chain) | |
| if descendant == None: | |
| self.unknown.append(node) | |
| return | |
| decl_status = descendant.get_decl_status() | |
| if decl_status == None: | |
| descendant.set_assign(True, node.coord) | |
| descendant.set_refer(True, node.coord) | |
| self.unknown.append(node) | |
| return | |
| if self.parent_node.__class__.__name__ == 'Assignment': | |
| if node is self.parent_node.lvalue: | |
| if decl_status.struct_item != None: | |
| if len(id_chain) > 1: | |
| descendant.set_assign(True, node.coord) | |
| elif len(id_chain) == 1: | |
| if lead_char == '*': | |
| descendant.set_assign(True, node.coord) | |
| else: | |
| right_id_chain = self.process_lvalue(self.parent_node.rvalue) | |
| if right_id_chain != None: | |
| self.id_tree_stack.add_link_node(descendant, right_id_chain) | |
| else: | |
| #TODO(angiebird): 1.Find a better way to deal with this case. | |
| descendant.set_assign(True, node.coord) | |
| else: | |
| debug_print(getframeinfo(currentframe())) | |
| else: | |
| descendant.set_assign(True, node.coord) | |
| elif node is self.parent_node.rvalue: | |
| if decl_status.struct_item is None: | |
| descendant.set_refer(True, node.coord) | |
| if lead_char == '&': | |
| descendant.set_assign(True, node.coord) | |
| else: | |
| left_id_chain = self.process_lvalue(self.parent_node.lvalue) | |
| left_lead_char = get_lvalue_lead(self.parent_node.lvalue) | |
| if left_id_chain != None: | |
| if len(left_id_chain) > 1: | |
| descendant.set_refer(True, node.coord) | |
| elif len(left_id_chain) == 1: | |
| if left_lead_char == '*': | |
| descendant.set_refer(True, node.coord) | |
| else: | |
| #TODO(angiebird): Check whether the other node is linked to this node. | |
| pass | |
| else: | |
| self.unknown.append(self.parent_node.lvalue) | |
| debug_print(getframeinfo(currentframe())) | |
| else: | |
| self.unknown.append(self.parent_node.lvalue) | |
| debug_print(getframeinfo(currentframe())) | |
| else: | |
| debug_print(getframeinfo(currentframe())) | |
| elif self.parent_node.__class__.__name__ == 'UnaryOp': | |
| # TODO(angiebird): Consider +=, *=, -=, /= etc | |
| if self.parent_node.op == '--' or self.parent_node.op == '++' or\ | |
| self.parent_node.op == 'p--' or self.parent_node.op == 'p++': | |
| descendant.set_assign(True, node.coord) | |
| descendant.set_refer(True, node.coord) | |
| else: | |
| descendant.set_refer(True, node.coord) | |
| elif self.parent_node.__class__.__name__ == 'Decl': | |
| #The logic is at visit_Decl | |
| pass | |
| elif self.parent_node.__class__.__name__ == 'ExprList': | |
| #The logic is at visit_FuncCall | |
| pass | |
| else: | |
| descendant.set_refer(True, node.coord) | |
| def visit_ID(self, node): | |
| # If the parent is a FuncCall, this ID is a function name. | |
| if self.parent_node.__class__.__name__ != 'FuncCall': | |
| self.process_possible_lvalue(node) | |
| self.generic_visit(node) | |
| def visit_StructRef(self, node): | |
| self.process_possible_lvalue(node) | |
| self.generic_visit(node) | |
| def visit_ArrayRef(self, node): | |
| self.process_possible_lvalue(node) | |
| self.generic_visit(node) | |
| def visit_UnaryOp(self, node): | |
| if node.op == '&' or node.op == '*': | |
| self.process_possible_lvalue(node) | |
| self.generic_visit(node) | |
| def visit_FuncCall(self, node): | |
| if node.name.__class__.__name__ == 'ID': | |
| if node.name.name in self.func_dictionary: | |
| if node.name.name not in self.func_history: | |
| self.func_history[node.name.name] = True | |
| func_def_node = self.func_dictionary[node.name.name] | |
| call_param_map = self.process_func_call(node, func_def_node) | |
| visitor = FuncInOutVisitor(func_def_node, self.struct_info, | |
| self.func_dictionary, False, | |
| call_param_map, self.global_id_tree, | |
| self.func_history, self.unknown) | |
| visitor.visit(func_def_node.body) | |
| else: | |
| self.unknown.append(node) | |
| self.generic_visit(node) | |
| def process_func_call(self, func_call_node, func_def_node): | |
| # set up a refer/assign for func parameters | |
| # return call_param_map | |
| call_param_ls = func_call_node.args.exprs | |
| call_param_map = {} | |
| func_decl = func_def_node.decl.type | |
| decl_param_ls = func_decl.args.params | |
| for param_node, decl_node in zip(call_param_ls, decl_param_ls): | |
| id_chain = self.process_lvalue(param_node) | |
| if id_chain != None: | |
| descendant = self.id_tree_stack.add_id_node(id_chain) | |
| if descendant == None: | |
| self.unknown.append(param_node) | |
| else: | |
| decl_status = descendant.get_decl_status() | |
| if decl_status != None: | |
| if decl_status.struct_item == None: | |
| if decl_status.is_ptr_decl == True: | |
| descendant.set_assign(True, param_node.coord) | |
| descendant.set_refer(True, param_node.coord) | |
| else: | |
| descendant.set_refer(True, param_node.coord) | |
| else: | |
| call_param_map[decl_node.name] = descendant | |
| else: | |
| self.unknown.append(param_node) | |
| else: | |
| self.unknown.append(param_node) | |
| return call_param_map | |
| def build_global_id_tree(ast, struct_info): | |
| global_id_tree = IDStatusNode() | |
| for node in ast.ext: | |
| if node.__class__.__name__ == 'Decl': | |
| # id tree is for tracking assign/refer status | |
| # we don't care about function id because they can't be changed | |
| if node.type.__class__.__name__ != 'FuncDecl': | |
| decl_status = parse_decl_node(struct_info, node) | |
| descendant = global_id_tree.add_child(decl_status.name, decl_status) | |
| return global_id_tree | |
| class FuncAnalyzer(): | |
| def __init__(self): | |
| self.ast = get_av1_ast() | |
| self.struct_info = build_struct_info(self.ast) | |
| self.func_dictionary = build_func_dictionary(self.ast) | |
| self.global_id_tree = build_global_id_tree(self.ast, self.struct_info) | |
| def analyze(self, func_name): | |
| if func_name in self.func_dictionary: | |
| func_def_node = self.func_dictionary[func_name] | |
| visitor = FuncInOutVisitor(func_def_node, self.struct_info, | |
| self.func_dictionary, True, None, | |
| self.global_id_tree) | |
| visitor.visit(func_def_node.body) | |
| root = visitor.get_id_tree_stack() | |
| root.top().show() | |
| else: | |
| print(func_name, "doesn't exist") | |
| if __name__ == '__main__': | |
| fa = FuncAnalyzer() | |
| fa.analyze('tpl_get_satd_cost') | |
| pass |