METHOD FOR DIVERGENCE ANALYSIS OF POINTER-BASED PROGRAM

摘要

A method comprises generating an intermediate representation of a pointer-based program; providing a control flow graph of the intermediate representation; selecting an analysis candidate from the intermediate representation as a traced variable and a root node; determining a definition site of the trace variable according to a use-define chain and the control flow graph; defining a node for each definition site variable; defining an edge by using each definition site variable and the traced variable; using each definition site variable of the definition site as a traced variable; repeating the steps of determining a definition site, defining a node, defining an edge and using each definition site to obtain a divergence relation graph; transforming the divergence relation graph into a directed acyclic graph; and determining whether the analysis candidate is divergent or not according to a divergent node and the directed acyclic graph.

主权项

1. A computer-implemented divergence analysis method for a pointer-based program, comprising:
generating an intermediate representation of a pointer-based program, wherein the intermediate representation is at least in gated single static assignment form; providing a control flow graph of the intermediate representation; selecting a variable of the intermediate representation as an analysis candidate; using the analysis candidate as a traced variable and a root node; determining a definition site of the trace variable according to a corresponding use-define chain and the control flow graph; defining a node for each definition site variable of the definition site if the definition site of the traced variable does not comprise a predetermined built-in function; defining an edge by using each definition site variable of the definition site and the traced variable if the definition site of the traced variable does not comprise the predetermined built-in function; using each definition site variable of the definition site as a traced variable; repeating the steps of determining a definition site, defining a node, defining an edge, and using each definition site to obtain a divergence relation graph; transforming the divergence relation graph into a directed acyclic graph; identifying at least one divergent node of the directed acyclic graph; and determining whether the analysis candidate is divergent or not according to the at least one divergent node and the directed acyclic graph.