1# Copyright (c) 2021, Alliance for Open Media. All rights reserved. 2# 3# This source code is subject to the terms of the BSD 2 Clause License and 4# the Alliance for Open Media Patent License 1.0. If the BSD 2 Clause License 5# was not distributed with this source code in the LICENSE file, you can 6# obtain it at www.aomedia.org/license/software. If the Alliance for Open 7# Media Patent License 1.0 was not distributed with this source code in the 8# PATENTS file, you can obtain it at www.aomedia.org/license/patent. 9# 10 11from __future__ import print_function 12import sys 13import os 14import operator 15from pycparser import c_parser, c_ast, parse_file 16from math import * 17 18from inspect import currentframe, getframeinfo 19from collections import deque 20 21 22def debug_print(frameinfo): 23 print('******** ERROR:', frameinfo.filename, frameinfo.lineno, '********') 24 25 26class StructItem(): 27 28 def __init__(self, 29 typedef_name=None, 30 struct_name=None, 31 struct_node=None, 32 is_union=False): 33 self.typedef_name = typedef_name 34 self.struct_name = struct_name 35 self.struct_node = struct_node 36 self.is_union = is_union 37 self.child_decl_map = None 38 39 def __str__(self): 40 return str(self.typedef_name) + ' ' + str(self.struct_name) + ' ' + str( 41 self.is_union) 42 43 def compute_child_decl_map(self, struct_info): 44 self.child_decl_map = {} 45 if self.struct_node != None and self.struct_node.decls != None: 46 for decl_node in self.struct_node.decls: 47 if decl_node.name == None: 48 for sub_decl_node in decl_node.type.decls: 49 sub_decl_status = parse_decl_node(struct_info, sub_decl_node) 50 self.child_decl_map[sub_decl_node.name] = sub_decl_status 51 else: 52 decl_status = parse_decl_node(struct_info, decl_node) 53 self.child_decl_map[decl_status.name] = decl_status 54 55 def get_child_decl_status(self, decl_name): 56 if self.child_decl_map == None: 57 debug_print(getframeinfo(currentframe())) 58 print('child_decl_map is None') 59 return None 60 if decl_name not in self.child_decl_map: 61 debug_print(getframeinfo(currentframe())) 62 print(decl_name, 'does not exist ') 63 return None 64 return self.child_decl_map[decl_name] 65 66 67class StructInfo(): 68 69 def __init__(self): 70 self.struct_name_dic = {} 71 self.typedef_name_dic = {} 72 self.enum_value_dic = {} # enum value -> enum_node 73 self.enum_name_dic = {} # enum name -> enum_node 74 self.struct_item_list = [] 75 76 def get_struct_by_typedef_name(self, typedef_name): 77 if typedef_name in self.typedef_name_dic: 78 return self.typedef_name_dic[typedef_name] 79 else: 80 return None 81 82 def get_struct_by_struct_name(self, struct_name): 83 if struct_name in self.struct_name_dic: 84 return self.struct_name_dic[struct_name] 85 else: 86 debug_print(getframeinfo(currentframe())) 87 print('Cant find', struct_name) 88 return None 89 90 def update_struct_item_list(self): 91 # Collect all struct_items from struct_name_dic and typedef_name_dic 92 # Compute child_decl_map for each struct item. 93 for struct_name in self.struct_name_dic.keys(): 94 struct_item = self.struct_name_dic[struct_name] 95 struct_item.compute_child_decl_map(self) 96 self.struct_item_list.append(struct_item) 97 98 for typedef_name in self.typedef_name_dic.keys(): 99 struct_item = self.typedef_name_dic[typedef_name] 100 if struct_item.struct_name not in self.struct_name_dic: 101 struct_item.compute_child_decl_map(self) 102 self.struct_item_list.append(struct_item) 103 104 def update_enum(self, enum_node): 105 if enum_node.name != None: 106 self.enum_name_dic[enum_node.name] = enum_node 107 108 if enum_node.values != None: 109 enumerator_list = enum_node.values.enumerators 110 for enumerator in enumerator_list: 111 self.enum_value_dic[enumerator.name] = enum_node 112 113 def update(self, 114 typedef_name=None, 115 struct_name=None, 116 struct_node=None, 117 is_union=False): 118 """T: typedef_name S: struct_name N: struct_node 119 120 T S N 121 case 1: o o o 122 typedef struct P { 123 int u; 124 } K; 125 T S N 126 case 2: o o x 127 typedef struct P K; 128 129 T S N 130 case 3: x o o 131 struct P { 132 int u; 133 }; 134 135 T S N 136 case 4: o x o 137 typedef struct { 138 int u; 139 } K; 140 """ 141 struct_item = None 142 143 # Check whether struct_name or typedef_name is already in the dictionary 144 if struct_name in self.struct_name_dic: 145 struct_item = self.struct_name_dic[struct_name] 146 147 if typedef_name in self.typedef_name_dic: 148 struct_item = self.typedef_name_dic[typedef_name] 149 150 if struct_item == None: 151 struct_item = StructItem(typedef_name, struct_name, struct_node, is_union) 152 153 if struct_node.decls != None: 154 struct_item.struct_node = struct_node 155 156 if struct_name != None: 157 self.struct_name_dic[struct_name] = struct_item 158 159 if typedef_name != None: 160 self.typedef_name_dic[typedef_name] = struct_item 161 162 163class StructDefVisitor(c_ast.NodeVisitor): 164 165 def __init__(self): 166 self.struct_info = StructInfo() 167 168 def visit_Struct(self, node): 169 if node.decls != None: 170 self.struct_info.update(None, node.name, node) 171 self.generic_visit(node) 172 173 def visit_Union(self, node): 174 if node.decls != None: 175 self.struct_info.update(None, node.name, node, True) 176 self.generic_visit(node) 177 178 def visit_Enum(self, node): 179 self.struct_info.update_enum(node) 180 self.generic_visit(node) 181 182 def visit_Typedef(self, node): 183 if node.type.__class__.__name__ == 'TypeDecl': 184 typedecl = node.type 185 if typedecl.type.__class__.__name__ == 'Struct': 186 struct_node = typedecl.type 187 typedef_name = node.name 188 struct_name = struct_node.name 189 self.struct_info.update(typedef_name, struct_name, struct_node) 190 elif typedecl.type.__class__.__name__ == 'Union': 191 union_node = typedecl.type 192 typedef_name = node.name 193 union_name = union_node.name 194 self.struct_info.update(typedef_name, union_name, union_node, True) 195 # TODO(angiebird): Do we need to deal with enum here? 196 self.generic_visit(node) 197 198 199def build_struct_info(ast): 200 v = StructDefVisitor() 201 v.visit(ast) 202 struct_info = v.struct_info 203 struct_info.update_struct_item_list() 204 return v.struct_info 205 206 207class DeclStatus(): 208 209 def __init__(self, name, struct_item=None, is_ptr_decl=False): 210 self.name = name 211 self.struct_item = struct_item 212 self.is_ptr_decl = is_ptr_decl 213 214 def get_child_decl_status(self, decl_name): 215 if self.struct_item != None: 216 return self.struct_item.get_child_decl_status(decl_name) 217 else: 218 #TODO(angiebird): 2. Investigage the situation when a struct's definition can't be found. 219 return None 220 221 def __str__(self): 222 return str(self.struct_item) + ' ' + str(self.name) + ' ' + str( 223 self.is_ptr_decl) 224 225 226def peel_ptr_decl(decl_type_node): 227 """ Remove PtrDecl and ArrayDecl layer """ 228 is_ptr_decl = False 229 peeled_decl_type_node = decl_type_node 230 while peeled_decl_type_node.__class__.__name__ == 'PtrDecl' or peeled_decl_type_node.__class__.__name__ == 'ArrayDecl': 231 is_ptr_decl = True 232 peeled_decl_type_node = peeled_decl_type_node.type 233 return is_ptr_decl, peeled_decl_type_node 234 235 236def parse_peeled_decl_type_node(struct_info, node): 237 struct_item = None 238 if node.__class__.__name__ == 'TypeDecl': 239 if node.type.__class__.__name__ == 'IdentifierType': 240 identifier_type_node = node.type 241 typedef_name = identifier_type_node.names[0] 242 struct_item = struct_info.get_struct_by_typedef_name(typedef_name) 243 elif node.type.__class__.__name__ == 'Struct': 244 struct_node = node.type 245 if struct_node.name != None: 246 struct_item = struct_info.get_struct_by_struct_name(struct_node.name) 247 else: 248 struct_item = StructItem(None, None, struct_node, False) 249 struct_item.compute_child_decl_map(struct_info) 250 elif node.type.__class__.__name__ == 'Union': 251 # TODO(angiebird): Special treatment for Union? 252 struct_node = node.type 253 if struct_node.name != None: 254 struct_item = struct_info.get_struct_by_struct_name(struct_node.name) 255 else: 256 struct_item = StructItem(None, None, struct_node, True) 257 struct_item.compute_child_decl_map(struct_info) 258 elif node.type.__class__.__name__ == 'Enum': 259 # TODO(angiebird): Special treatment for Union? 260 struct_node = node.type 261 struct_item = None 262 else: 263 print('Unrecognized peeled_decl_type_node.type', 264 node.type.__class__.__name__) 265 else: 266 # debug_print(getframeinfo(currentframe())) 267 # print(node.__class__.__name__) 268 #TODO(angiebird): Do we need to take care of this part? 269 pass 270 271 return struct_item 272 273 274def parse_decl_node(struct_info, decl_node): 275 # struct_item is None if this decl_node is not a struct_item 276 decl_node_name = decl_node.name 277 decl_type_node = decl_node.type 278 is_ptr_decl, peeled_decl_type_node = peel_ptr_decl(decl_type_node) 279 struct_item = parse_peeled_decl_type_node(struct_info, peeled_decl_type_node) 280 return DeclStatus(decl_node_name, struct_item, is_ptr_decl) 281 282 283def get_lvalue_lead(lvalue_node): 284 """return '&' or '*' of lvalue if available""" 285 if lvalue_node.__class__.__name__ == 'UnaryOp' and lvalue_node.op == '&': 286 return '&' 287 elif lvalue_node.__class__.__name__ == 'UnaryOp' and lvalue_node.op == '*': 288 return '*' 289 return None 290 291 292def parse_lvalue(lvalue_node): 293 """get id_chain from lvalue""" 294 id_chain = parse_lvalue_recursive(lvalue_node, []) 295 return id_chain 296 297 298def parse_lvalue_recursive(lvalue_node, id_chain): 299 """cpi->rd->u -> (cpi->rd)->u""" 300 if lvalue_node.__class__.__name__ == 'ID': 301 id_chain.append(lvalue_node.name) 302 id_chain.reverse() 303 return id_chain 304 elif lvalue_node.__class__.__name__ == 'StructRef': 305 id_chain.append(lvalue_node.field.name) 306 return parse_lvalue_recursive(lvalue_node.name, id_chain) 307 elif lvalue_node.__class__.__name__ == 'ArrayRef': 308 return parse_lvalue_recursive(lvalue_node.name, id_chain) 309 elif lvalue_node.__class__.__name__ == 'UnaryOp' and lvalue_node.op == '&': 310 return parse_lvalue_recursive(lvalue_node.expr, id_chain) 311 elif lvalue_node.__class__.__name__ == 'UnaryOp' and lvalue_node.op == '*': 312 return parse_lvalue_recursive(lvalue_node.expr, id_chain) 313 else: 314 return None 315 316 317class FuncDefVisitor(c_ast.NodeVisitor): 318 func_dictionary = {} 319 320 def visit_FuncDef(self, node): 321 func_name = node.decl.name 322 self.func_dictionary[func_name] = node 323 324 325def build_func_dictionary(ast): 326 v = FuncDefVisitor() 327 v.visit(ast) 328 return v.func_dictionary 329 330 331def get_func_start_coord(func_node): 332 return func_node.coord 333 334 335def find_end_node(node): 336 node_list = [] 337 for c in node: 338 node_list.append(c) 339 if len(node_list) == 0: 340 return node 341 else: 342 return find_end_node(node_list[-1]) 343 344 345def get_func_end_coord(func_node): 346 return find_end_node(func_node).coord 347 348 349def get_func_size(func_node): 350 start_coord = get_func_start_coord(func_node) 351 end_coord = get_func_end_coord(func_node) 352 if start_coord.file == end_coord.file: 353 return end_coord.line - start_coord.line + 1 354 else: 355 return None 356 357 358def save_object(obj, filename): 359 with open(filename, 'wb') as obj_fp: 360 pickle.dump(obj, obj_fp, protocol=-1) 361 362 363def load_object(filename): 364 obj = None 365 with open(filename, 'rb') as obj_fp: 366 obj = pickle.load(obj_fp) 367 return obj 368 369 370def get_av1_ast(gen_ast=False): 371 # TODO(angiebird): Generalize this path 372 c_filename = './av1_pp.c' 373 print('generate ast') 374 ast = parse_file(c_filename) 375 #save_object(ast, ast_file) 376 print('finished generate ast') 377 return ast 378 379 380def get_func_param_id_map(func_def_node): 381 param_id_map = {} 382 func_decl = func_def_node.decl.type 383 param_list = func_decl.args.params 384 for decl in param_list: 385 param_id_map[decl.name] = decl 386 return param_id_map 387 388 389class IDTreeStack(): 390 391 def __init__(self, global_id_tree): 392 self.stack = deque() 393 self.global_id_tree = global_id_tree 394 395 def add_link_node(self, node, link_id_chain): 396 link_node = self.add_id_node(link_id_chain) 397 node.link_node = link_node 398 node.link_id_chain = link_id_chain 399 400 def push_id_tree(self, id_tree=None): 401 if id_tree == None: 402 id_tree = IDStatusNode() 403 self.stack.append(id_tree) 404 return id_tree 405 406 def pop_id_tree(self): 407 return self.stack.pop() 408 409 def add_id_seed_node(self, id_seed, decl_status): 410 return self.stack[-1].add_child(id_seed, decl_status) 411 412 def get_id_seed_node(self, id_seed): 413 idx = len(self.stack) - 1 414 while idx >= 0: 415 id_node = self.stack[idx].get_child(id_seed) 416 if id_node != None: 417 return id_node 418 idx -= 1 419 420 id_node = self.global_id_tree.get_child(id_seed) 421 if id_node != None: 422 return id_node 423 return None 424 425 def add_id_node(self, id_chain): 426 id_seed = id_chain[0] 427 id_seed_node = self.get_id_seed_node(id_seed) 428 if id_seed_node == None: 429 return None 430 if len(id_chain) == 1: 431 return id_seed_node 432 return id_seed_node.add_descendant(id_chain[1:]) 433 434 def get_id_node(self, id_chain): 435 id_seed = id_chain[0] 436 id_seed_node = self.get_id_seed_node(id_seed) 437 if id_seed_node == None: 438 return None 439 if len(id_chain) == 1: 440 return id_seed_node 441 return id_seed_node.get_descendant(id_chain[1:]) 442 443 def top(self): 444 return self.stack[-1] 445 446 447class IDStatusNode(): 448 449 def __init__(self, name=None, root=None): 450 if root is None: 451 self.root = self 452 else: 453 self.root = root 454 455 self.name = name 456 457 self.parent = None 458 self.children = {} 459 460 self.assign = False 461 self.last_assign_coord = None 462 self.refer = False 463 self.last_refer_coord = None 464 465 self.decl_status = None 466 467 self.link_id_chain = None 468 self.link_node = None 469 470 self.visit = False 471 472 def set_link_id_chain(self, link_id_chain): 473 self.set_assign(False) 474 self.link_id_chain = link_id_chain 475 self.link_node = self.root.get_descendant(link_id_chain) 476 477 def set_link_node(self, link_node): 478 self.set_assign(False) 479 self.link_id_chain = ['*'] 480 self.link_node = link_node 481 482 def get_link_id_chain(self): 483 return self.link_id_chain 484 485 def get_concrete_node(self): 486 if self.visit == True: 487 # return None when there is a loop 488 return None 489 self.visit = True 490 if self.link_node == None: 491 self.visit = False 492 return self 493 else: 494 concrete_node = self.link_node.get_concrete_node() 495 self.visit = False 496 if concrete_node == None: 497 return self 498 return concrete_node 499 500 def set_assign(self, assign, coord=None): 501 concrete_node = self.get_concrete_node() 502 concrete_node.assign = assign 503 concrete_node.last_assign_coord = coord 504 505 def get_assign(self): 506 concrete_node = self.get_concrete_node() 507 return concrete_node.assign 508 509 def set_refer(self, refer, coord=None): 510 concrete_node = self.get_concrete_node() 511 concrete_node.refer = refer 512 concrete_node.last_refer_coord = coord 513 514 def get_refer(self): 515 concrete_node = self.get_concrete_node() 516 return concrete_node.refer 517 518 def set_parent(self, parent): 519 concrete_node = self.get_concrete_node() 520 concrete_node.parent = parent 521 522 def add_child(self, name, decl_status=None): 523 concrete_node = self.get_concrete_node() 524 if name not in concrete_node.children: 525 child_id_node = IDStatusNode(name, concrete_node.root) 526 concrete_node.children[name] = child_id_node 527 if decl_status == None: 528 # Check if the child decl_status can be inferred from its parent's 529 # decl_status 530 if self.decl_status != None: 531 decl_status = self.decl_status.get_child_decl_status(name) 532 child_id_node.set_decl_status(decl_status) 533 return concrete_node.children[name] 534 535 def get_child(self, name): 536 concrete_node = self.get_concrete_node() 537 if name in concrete_node.children: 538 return concrete_node.children[name] 539 else: 540 return None 541 542 def add_descendant(self, id_chain): 543 current_node = self.get_concrete_node() 544 for name in id_chain: 545 current_node.add_child(name) 546 parent_node = current_node 547 current_node = current_node.get_child(name) 548 current_node.set_parent(parent_node) 549 return current_node 550 551 def get_descendant(self, id_chain): 552 current_node = self.get_concrete_node() 553 for name in id_chain: 554 current_node = current_node.get_child(name) 555 if current_node == None: 556 return None 557 return current_node 558 559 def get_children(self): 560 current_node = self.get_concrete_node() 561 return current_node.children 562 563 def set_decl_status(self, decl_status): 564 current_node = self.get_concrete_node() 565 current_node.decl_status = decl_status 566 567 def get_decl_status(self): 568 current_node = self.get_concrete_node() 569 return current_node.decl_status 570 571 def __str__(self): 572 if self.link_id_chain is None: 573 return str(self.name) + ' a: ' + str(int(self.assign)) + ' r: ' + str( 574 int(self.refer)) 575 else: 576 return str(self.name) + ' -> ' + ' '.join(self.link_id_chain) 577 578 def collect_assign_refer_status(self, 579 id_chain=None, 580 assign_ls=None, 581 refer_ls=None): 582 if id_chain == None: 583 id_chain = [] 584 if assign_ls == None: 585 assign_ls = [] 586 if refer_ls == None: 587 refer_ls = [] 588 id_chain.append(self.name) 589 if self.assign: 590 info_str = ' '.join([ 591 ' '.join(id_chain[1:]), 'a:', 592 str(int(self.assign)), 'r:', 593 str(int(self.refer)), 594 str(self.last_assign_coord) 595 ]) 596 assign_ls.append(info_str) 597 if self.refer: 598 info_str = ' '.join([ 599 ' '.join(id_chain[1:]), 'a:', 600 str(int(self.assign)), 'r:', 601 str(int(self.refer)), 602 str(self.last_refer_coord) 603 ]) 604 refer_ls.append(info_str) 605 for c in self.children: 606 self.children[c].collect_assign_refer_status(id_chain, assign_ls, 607 refer_ls) 608 id_chain.pop() 609 return assign_ls, refer_ls 610 611 def show(self): 612 assign_ls, refer_ls = self.collect_assign_refer_status() 613 print('---- assign ----') 614 for item in assign_ls: 615 print(item) 616 print('---- refer ----') 617 for item in refer_ls: 618 print(item) 619 620 621class FuncInOutVisitor(c_ast.NodeVisitor): 622 623 def __init__(self, 624 func_def_node, 625 struct_info, 626 func_dictionary, 627 keep_body_id_tree=True, 628 call_param_map=None, 629 global_id_tree=None, 630 func_history=None, 631 unknown=None): 632 self.func_dictionary = func_dictionary 633 self.struct_info = struct_info 634 self.param_id_map = get_func_param_id_map(func_def_node) 635 self.parent_node = None 636 self.global_id_tree = global_id_tree 637 self.body_id_tree = None 638 self.keep_body_id_tree = keep_body_id_tree 639 if func_history == None: 640 self.func_history = {} 641 else: 642 self.func_history = func_history 643 644 if unknown == None: 645 self.unknown = [] 646 else: 647 self.unknown = unknown 648 649 self.id_tree_stack = IDTreeStack(global_id_tree) 650 self.id_tree_stack.push_id_tree() 651 652 #TODO move this part into a function 653 for param in self.param_id_map: 654 decl_node = self.param_id_map[param] 655 decl_status = parse_decl_node(self.struct_info, decl_node) 656 descendant = self.id_tree_stack.add_id_seed_node(decl_status.name, 657 decl_status) 658 if call_param_map is not None and param in call_param_map: 659 # This is a function call. 660 # Map the input parameter to the caller's nodes 661 # TODO(angiebird): Can we use add_link_node here? 662 descendant.set_link_node(call_param_map[param]) 663 664 def get_id_tree_stack(self): 665 return self.id_tree_stack 666 667 def generic_visit(self, node): 668 prev_parent = self.parent_node 669 self.parent_node = node 670 for c in node: 671 self.visit(c) 672 self.parent_node = prev_parent 673 674 # TODO rename 675 def add_new_id_tree(self, node): 676 self.id_tree_stack.push_id_tree() 677 self.generic_visit(node) 678 id_tree = self.id_tree_stack.pop_id_tree() 679 if self.parent_node == None and self.keep_body_id_tree == True: 680 # this is function body 681 self.body_id_tree = id_tree 682 683 def visit_For(self, node): 684 self.add_new_id_tree(node) 685 686 def visit_Compound(self, node): 687 self.add_new_id_tree(node) 688 689 def visit_Decl(self, node): 690 if node.type.__class__.__name__ != 'FuncDecl': 691 decl_status = parse_decl_node(self.struct_info, node) 692 descendant = self.id_tree_stack.add_id_seed_node(decl_status.name, 693 decl_status) 694 if node.init is not None: 695 init_id_chain = self.process_lvalue(node.init) 696 if init_id_chain != None: 697 if decl_status.struct_item is None: 698 init_descendant = self.id_tree_stack.add_id_node(init_id_chain) 699 if init_descendant != None: 700 init_descendant.set_refer(True, node.coord) 701 else: 702 self.unknown.append(node) 703 descendant.set_assign(True, node.coord) 704 else: 705 self.id_tree_stack.add_link_node(descendant, init_id_chain) 706 else: 707 self.unknown.append(node) 708 else: 709 descendant.set_assign(True, node.coord) 710 self.generic_visit(node) 711 712 def is_lvalue(self, node): 713 if self.parent_node is None: 714 # TODO(angiebird): Do every lvalue has parent_node != None? 715 return False 716 if self.parent_node.__class__.__name__ == 'StructRef': 717 return False 718 if self.parent_node.__class__.__name__ == 'ArrayRef' and node == self.parent_node.name: 719 # if node == self.parent_node.subscript, the node could be lvalue 720 return False 721 if self.parent_node.__class__.__name__ == 'UnaryOp' and self.parent_node.op == '&': 722 return False 723 if self.parent_node.__class__.__name__ == 'UnaryOp' and self.parent_node.op == '*': 724 return False 725 return True 726 727 def process_lvalue(self, node): 728 id_chain = parse_lvalue(node) 729 if id_chain == None: 730 return id_chain 731 elif id_chain[0] in self.struct_info.enum_value_dic: 732 return None 733 else: 734 return id_chain 735 736 def process_possible_lvalue(self, node): 737 if self.is_lvalue(node): 738 id_chain = self.process_lvalue(node) 739 lead_char = get_lvalue_lead(node) 740 # make sure the id is not an enum value 741 if id_chain == None: 742 self.unknown.append(node) 743 return 744 descendant = self.id_tree_stack.add_id_node(id_chain) 745 if descendant == None: 746 self.unknown.append(node) 747 return 748 decl_status = descendant.get_decl_status() 749 if decl_status == None: 750 descendant.set_assign(True, node.coord) 751 descendant.set_refer(True, node.coord) 752 self.unknown.append(node) 753 return 754 if self.parent_node.__class__.__name__ == 'Assignment': 755 if node is self.parent_node.lvalue: 756 if decl_status.struct_item != None: 757 if len(id_chain) > 1: 758 descendant.set_assign(True, node.coord) 759 elif len(id_chain) == 1: 760 if lead_char == '*': 761 descendant.set_assign(True, node.coord) 762 else: 763 right_id_chain = self.process_lvalue(self.parent_node.rvalue) 764 if right_id_chain != None: 765 self.id_tree_stack.add_link_node(descendant, right_id_chain) 766 else: 767 #TODO(angiebird): 1.Find a better way to deal with this case. 768 descendant.set_assign(True, node.coord) 769 else: 770 debug_print(getframeinfo(currentframe())) 771 else: 772 descendant.set_assign(True, node.coord) 773 elif node is self.parent_node.rvalue: 774 if decl_status.struct_item is None: 775 descendant.set_refer(True, node.coord) 776 if lead_char == '&': 777 descendant.set_assign(True, node.coord) 778 else: 779 left_id_chain = self.process_lvalue(self.parent_node.lvalue) 780 left_lead_char = get_lvalue_lead(self.parent_node.lvalue) 781 if left_id_chain != None: 782 if len(left_id_chain) > 1: 783 descendant.set_refer(True, node.coord) 784 elif len(left_id_chain) == 1: 785 if left_lead_char == '*': 786 descendant.set_refer(True, node.coord) 787 else: 788 #TODO(angiebird): Check whether the other node is linked to this node. 789 pass 790 else: 791 self.unknown.append(self.parent_node.lvalue) 792 debug_print(getframeinfo(currentframe())) 793 else: 794 self.unknown.append(self.parent_node.lvalue) 795 debug_print(getframeinfo(currentframe())) 796 else: 797 debug_print(getframeinfo(currentframe())) 798 elif self.parent_node.__class__.__name__ == 'UnaryOp': 799 # TODO(angiebird): Consider +=, *=, -=, /= etc 800 if self.parent_node.op == '--' or self.parent_node.op == '++' or\ 801 self.parent_node.op == 'p--' or self.parent_node.op == 'p++': 802 descendant.set_assign(True, node.coord) 803 descendant.set_refer(True, node.coord) 804 else: 805 descendant.set_refer(True, node.coord) 806 elif self.parent_node.__class__.__name__ == 'Decl': 807 #The logic is at visit_Decl 808 pass 809 elif self.parent_node.__class__.__name__ == 'ExprList': 810 #The logic is at visit_FuncCall 811 pass 812 else: 813 descendant.set_refer(True, node.coord) 814 815 def visit_ID(self, node): 816 # If the parent is a FuncCall, this ID is a function name. 817 if self.parent_node.__class__.__name__ != 'FuncCall': 818 self.process_possible_lvalue(node) 819 self.generic_visit(node) 820 821 def visit_StructRef(self, node): 822 self.process_possible_lvalue(node) 823 self.generic_visit(node) 824 825 def visit_ArrayRef(self, node): 826 self.process_possible_lvalue(node) 827 self.generic_visit(node) 828 829 def visit_UnaryOp(self, node): 830 if node.op == '&' or node.op == '*': 831 self.process_possible_lvalue(node) 832 self.generic_visit(node) 833 834 def visit_FuncCall(self, node): 835 if node.name.__class__.__name__ == 'ID': 836 if node.name.name in self.func_dictionary: 837 if node.name.name not in self.func_history: 838 self.func_history[node.name.name] = True 839 func_def_node = self.func_dictionary[node.name.name] 840 call_param_map = self.process_func_call(node, func_def_node) 841 842 visitor = FuncInOutVisitor(func_def_node, self.struct_info, 843 self.func_dictionary, False, 844 call_param_map, self.global_id_tree, 845 self.func_history, self.unknown) 846 visitor.visit(func_def_node.body) 847 else: 848 self.unknown.append(node) 849 self.generic_visit(node) 850 851 def process_func_call(self, func_call_node, func_def_node): 852 # set up a refer/assign for func parameters 853 # return call_param_map 854 call_param_ls = func_call_node.args.exprs 855 call_param_map = {} 856 857 func_decl = func_def_node.decl.type 858 decl_param_ls = func_decl.args.params 859 for param_node, decl_node in zip(call_param_ls, decl_param_ls): 860 id_chain = self.process_lvalue(param_node) 861 if id_chain != None: 862 descendant = self.id_tree_stack.add_id_node(id_chain) 863 if descendant == None: 864 self.unknown.append(param_node) 865 else: 866 decl_status = descendant.get_decl_status() 867 if decl_status != None: 868 if decl_status.struct_item == None: 869 if decl_status.is_ptr_decl == True: 870 descendant.set_assign(True, param_node.coord) 871 descendant.set_refer(True, param_node.coord) 872 else: 873 descendant.set_refer(True, param_node.coord) 874 else: 875 call_param_map[decl_node.name] = descendant 876 else: 877 self.unknown.append(param_node) 878 else: 879 self.unknown.append(param_node) 880 return call_param_map 881 882 883def build_global_id_tree(ast, struct_info): 884 global_id_tree = IDStatusNode() 885 for node in ast.ext: 886 if node.__class__.__name__ == 'Decl': 887 # id tree is for tracking assign/refer status 888 # we don't care about function id because they can't be changed 889 if node.type.__class__.__name__ != 'FuncDecl': 890 decl_status = parse_decl_node(struct_info, node) 891 descendant = global_id_tree.add_child(decl_status.name, decl_status) 892 return global_id_tree 893 894 895class FuncAnalyzer(): 896 897 def __init__(self): 898 self.ast = get_av1_ast() 899 self.struct_info = build_struct_info(self.ast) 900 self.func_dictionary = build_func_dictionary(self.ast) 901 self.global_id_tree = build_global_id_tree(self.ast, self.struct_info) 902 903 def analyze(self, func_name): 904 if func_name in self.func_dictionary: 905 func_def_node = self.func_dictionary[func_name] 906 visitor = FuncInOutVisitor(func_def_node, self.struct_info, 907 self.func_dictionary, True, None, 908 self.global_id_tree) 909 visitor.visit(func_def_node.body) 910 root = visitor.get_id_tree_stack() 911 root.top().show() 912 else: 913 print(func_name, "doesn't exist") 914 915 916if __name__ == '__main__': 917 fa = FuncAnalyzer() 918 fa.analyze('tpl_get_satd_cost') 919 pass 920