Patent ID: 8266598
Filing Date: 2012-09-11
Classification: G06F

Abstract:
1. A method of statically computing a bound on a resource utilized during execution of code, the method comprising: decomposing a program call graph into a directed acyclic graph (DAG) of maximal strongly connected components (SCCs), wherein the SCCs include a main procedure and one or more constituent procedures; processing the SCCs in reverse topological order, including computing procedure summaries for each constituent procedure by applying a first technique if the constituent procedure is a non-recursive procedure and applying a second technique if the constituent procedure is a recursive procedure, wherein the second technique comprises: associating a resource unit cost to each constituent recursive procedure called transitively by the recursive procedure under consideration; combining a computational complexity of constituent code-fragments of each constituent recursive procedure in a bottom-up manner; determining the resource bounds of each constituent code-fragment of each constituent recursive procedure in terms of upper and lower bounds on loop iterations for loops present inside the constituent code-fragment of the constituent recursive procedure; computing a procedure summary for the main procedure based on the procedure summaries of the constituent procedures; and determining a resource utilization bound from the procedure summary of the main procedure.