Research On Lightweight Interprocedural Escape Analysis For C Programs

Escape analysis is a static program analysis that determines whether variables will escape the current scope by analyzing the scope of pointer variables,deciding whether memory can be allocated on the stack instead of the heap.Escape analysis can effectively optimize program memory allocation strategy and improve its executive efficiency and performance.At present,the mainstream escape analysis mostly uses the connection graph and constructs a large interprocedural connection graph which can be used to search for the corresponding escape information to solve the context-sensitive problem.Although this escape analysis has improved accuracy compared to other methods,the accuracy of it may be still decreased due to the uncertainty of search paths when searching the connection graph on programs with complex method calls.The decrease of the accuracy of interprocedural escape analysis will affect program executive performance and safety.To improve the accuracy of the interprocedural escape analysis and effectively reduce its cost,this paper proposes a lightweight interprocedural escape analysis and applies it to C programs.The main work done is as follows:This article proposes a lightweight interprocedural escape analysis based on higher-order functions to address issues of low accuracy and high cost in current interprocedural escape analysis which is based on the connection graph in programs with complex method calls.In intraprocedural escape analysis,we firstly reduce the escape analysis area by using value flow analysis to remove redundant code.Then,we employ flow-sensitive points-to analysis based on set inclusion relationships and solve a set of constraints on the points-to sets with inclusion relations.Finally,we analysis escape variables in the solved points-to sets.By utilizing features of higher-order functions in functional programming,we employ intraprocedural escape analysis for points-to sets with parameters and store the escape analysis results in the form of a higher-order function.During the execution of interprocedural escape analysis,we extract the escape analysis result stored as the higher-order function summaries of the called function at the function call-site and substitute parameters which are instantiated according to the correspondence between formal and actual parameters into the result for calculation to get the the relevant escape information of the target program.This method avoids constructing a huge interprocedural connection graph and improves the efficiency of interprocedural escape analysis.It also effectively resolves the calling-context question involved in interprocedural escape analysis and increases the accuracy of interprocedural escape analysis.To further increase the accuracy of the proposed lightweight interprocedural escape analysis,this paper proposes a domain-sensitive interprocedural escape analysis method based on the symbolic access path.This method is built upon the aforementioned lightweight interprocedural escape analysis based on the higher-order function framework.During intraprocedural escape analysis,we first introduce the concept of symbolized access paths and utilize it to extract access paths with data-carrying parameter variables within a function.Subsequently,we incorporate the analysis process of access paths into the higher-order functional escape analysis summary of the function.During interprocedural escape analysis,we extract the higher-order functional escape analysis summary information of the callee and update the data-carrying access path information of the actual parameter variables at the method call-site.Finally,we combine the updated access path information of structure variables with the escape points set within callees for constraint solving to capture the relevant escaped variables.This paper verifies the feasibility of a lightweight interprocedural escape analysis method for C programs through experiments.The experiment results show that the proposed lightweight interprocedural escape analysis method based on higher-order functions has certain accuracy improvements compared to the traditional method based on the connection graph and it also reduces the time cost.The domain-sensitive interprocedural escape analysis method based on symbolic access path further improves the accuracy of the interprocedural escape analysis method based on higher-order functions.