Granted Patent B2

US 12,619,405 · App. 18/243,710 · Granted May 5, 2026

Inventors: Anushri Jana (Pune, IN); Bharti Chimdyalwar (Pune, IN); Ramanathan Venkatesh (Pune, IN); Shrawan Kumar (Pune, IN)

Assignee: TATA CONSULTANCY SERVICES LIMITED

G06F8/433G06F8/71

Abstract

Claims (72)

1 . A processor implemented method of performing incremental functional approach-based dataflow analysis in a source code, the method comprising:

performing via one or more hardware processors a static dataflow analysis over a set of functions of a source code;

identifying via the one or more hardware processors a set of edited functions from the set of functions based on at least one change observed in the source code, wherein each function represents a node comprising a set of statements being called in the source code;

obtaining via the one or more hardware processors a set of impacted functions based on at least one change observed between a current version summary of the source code and a previous version summary of the source code;

executing via the one or more hardware processors a dataflow analysis over the set of impacted functions of the source code which recomputes the set of impacted functions by leveraging one or more cached previous analysis results, instead of re-running an analysis for every changed source code by

performing an incremental bottom-up analysis on one or more selected functions from the set of functions being traversed in a bottom-up order of a call graph originated from each edited function, wherein performing the incremental bottom-up analysis further comprises:

loading a bottom-up worklist of a set of edited functions universally available in a worklist;

listing the set of functions to be traversed in the bottom-up order from the bottom-up worklist;

obtaining a previous version summary of the edited function to compute a current version summary of the edited function; and

performing when the current version summary of the edited function is not identical to the previous version summary of the edited function,

identifying a sequence of a set of caller functions from the set of edited functions and recomputing the current version summary of the set of caller functions, wherein recomputing the current version summary is initially started by identifying a chain of callers of the edited function, recomputing and comparing a respective set of summaries recomputed from the callers of the edited function, and stopping re-computation of the current version summary when a procedure with the current version summary matching the previous version summary is found;

updating a summary of each edited function with the current version summary; and

identifying a set of called functions from the set of edited functions and adding a set of called functions universally available to the set of impacted functions;

performing an incremental top-down analysis over the set of impacted functions by traversing the call graph in a top-down order; and

performing via the one or more hardware processors, an incremental functional approach-based dataflow analysis over the set of impacted functions based on the current version summary of the source code, the incremental bottom-up analysis, and the incremental top-down analysis, wherein the incremental functional approach-based dataflow analysis forms a summary of each procedure using a bottom-up traversal over the call graph, analyzes every procedure only once even if the procedure includes multiple calls and resulting summaries computed using the bottom-up traversal replace calls in a set of caller functions to construct a summary of the set of caller functions and the call graph is traversed in bottom-up order,

implementing via the one or more hardware processors, the incremental functional approach-based dataflow analysis as an incremental static analysis tool that upon execution provides analysis and additionally stores program analysis information.

2 . The processor implemented method as claimed in claim 1 , wherein the incremental bottom-up analysis computes a set of edited function summaries and a set of function summaries marked as the set of impacted functions, wherein the summaries are computed based on at least one change observed when the current version summary and the previous version summary are compared.

3 . The processor implemented method as claimed in claim 1 , wherein the incremental top-down analysis updates one or more dataflow values of the set of impacted functions by traversing the call graph in the top-down order.

4 . The processor implemented method as claimed in claim 1 , wherein performing the incremental top-down analysis comprises:

loading a top-down worklist with a set of procedures and listing the set of impacted functions to be traversed in the top-down order from the worklist;

obtaining the set of impacted functions universally available in the set of functions and in the set of impacted functions;

fetching the set of called functions from the set of impacted functions; and

computing an entry of each called function based on a summary of the set of impacted functions and updating the entry of each called function.

5 . A system for performing incremental functional approach-based dataflow analysis in a source code comprising:

a memory storing instructions;

one or more communication interfaces; and

one or more hardware processors coupled to the memory via the one or more communication interfaces, wherein the one or more hardware processors are configured by the instructions to:

perform a static dataflow analysis over a set of functions of a source code;

identify a set of edited functions from the set of functions based on at least one change observed in the source code, wherein each function represents a node comprising a set of statements being called in the source code;

obtain a set of impacted functions based on at least one change observed between a current version summary of the source code and a previous version summary of the source code;

execute a dataflow analysis over the set of impacted functions of the source code which recomputes the set of impacted functions by leveraging one or more cached previous analysis results, instead of re-running an analysis for every changed source code by

performing an incremental bottom-up analysis on one or more selected functions from the set of functions being traversed in a bottom-up order of a call graph originated from each edited function, wherein performing the incremental bottom-up analysis further comprises:

loading a bottom-up worklist of a set of edited functions universally available in a worklist;

listing the set of functions to be traversed in the bottom-up order from the bottom-up worklist;

obtaining a previous version summary of the edited function to compute a current version summary of the edited function; and

performing when the current version summary of the edited function is not identical to the previous version summary of the edited function,

identifying a sequence of a set of caller functions from the set of edited functions and recomputing the current version summary of the set of caller functions, wherein recomputing the current version summary is initially started by identifying a chain of callers of the edited function, recomputing and comparing a respective set of summaries recomputed from the callers of the edited function, and stopping re-computation of the current version summary when a procedure with the current version summary matching the previous version summary is found;

updating a summary of each edited function with the current version summary; and

identifying a set of called functions from the set of edited functions and adding a set of called functions universally available to the set of impacted functions;

performing an incremental top-down analysis over the set of impacted functions by traversing the call graph in a top-down order and

perform an incremental functional approach-based dataflow analysis over the set of impacted functions based on the current version summary of the source code, the incremental bottom-up analysis, and the incremental top-down analysis, wherein the incremental functional approach-based dataflow analysis forms a summary of each procedure using a bottom-up traversal over the call graph, analyzes every procedure only once even if the procedure includes multiple calls and resulting summaries computed using the bottom-up traversal replace calls in a set of caller functions to construct a summary of the set of caller functions and the call graph is traversed in bottom-up order,

implementing the incremental functional approach-based dataflow analysis as an incremental static analysis tool that upon execution provides analysis and additionally stores program analysis information.

6 . The system as claimed in claim 5 , wherein the incremental bottom-up analysis computes a set of edited functions summaries and a set of function summaries marked as the set of impacted functions, wherein the summaries are computed based on at least one change observed when the current version summary and the previous version summary are compared.

7 . The system as claimed in claim 5 , wherein the incremental top-down analysis updates one or more dataflow values of the set of impacted functions by traversing the call graph in the top-down order.

8 . The system as claimed in claim 5 , wherein performing the incremental top-down analysis comprises:

loading a top-down worklist with a set of procedures and listing the set of impacted functions to be traversed in the top-down order from the worklist;

obtaining the set of impacted functions universally available in the set of functions and in the set of impacted functions;

fetching the set of called functions from the set of impacted functions; and

computing an entry of each called function based on a summary of the set of impacted functions and updating the entry of each called function.

9 . One or more non-transitory machine-readable information storage mediums comprising one or more instructions which when executed by one or more hardware processors cause:

performing a static dataflow analysis over a set of functions of a source code;

identifying via the one or more hardware processors, a set of edited functions from the set of functions based on at least one change observed in the source code, wherein each function represents a node comprising a set of statements being called in the source code;

obtaining a set of impacted functions based on at least one change observed between a current version summary of the source code and a previous version summary of the source code;

executing a dataflow analysis over the set of impacted functions of the source code which recomputes the set of impacted functions by leveraging one or more cached previous analysis results, instead of re-running an analysis for every changed source code by

performing an incremental bottom-up analysis on one or more selected functions from the set of functions being traversed in a bottom-up order of a call graph originated from each edited function, wherein performing the incremental bottom-up analysis further comprises:

loading a bottom-up worklist of a set of edited functions universally available in a worklist;

listing the set of functions to be traversed in the bottom-up order from the bottom-up worklist;

obtaining a previous version summary of the edited function to compute a current version summary of the edited function; and

performing when the current version summary of the edited function is not identical to the previous version summary of the edited function,

identifying a sequence of a set of caller functions from the set of edited functions and recomputing the current version summary of the set of caller functions, wherein recomputing the current version summary is initially started by identifying a chain of callers of the edited function, recomputing and comparing a respective set of summaries recomputed from the callers of the edited function, and stopping re-computation of the current version summary when a procedure with the current version summary matching the previous version summary is found;

updating a summary of each edited function with the current version summary; and

identifying a set of called functions from the set of edited functions and adding a set of called functions universally available to the set of impacted functions;

performing an incremental top-down analysis over the set of impacted functions by traversing the call graph in a top-down order; and

performing an incremental functional approach-based dataflow analysis over the set of impacted functions based on the current version summary of the source code, the incremental bottom-up analysis, and the incremental top-down analysis, wherein the incremental functional approach-based dataflow analysis forms a summary of each procedure using a bottom-up traversal over the call graph, analyzes every procedure only once even if the procedure includes multiple calls and resulting summaries computed using the bottom-up traversal replace calls in a set of caller functions to construct a summary of the set of caller functions and the call graph is traversed in bottom-up order,

implementing the incremental functional approach-based dataflow analysis as an incremental static analysis tool that upon execution provides exhaustive analysis and additionally stores store program analysis information.

10 . The one or more non-transitory machine-readable information storage mediums of claim 9 , wherein the incremental bottom-up analysis computes a set of edited function summaries and a set of function summaries marked as the set of impacted functions, wherein the summaries are computed based on at least one change observed when the current version summary and the previous version summary are compared.

11 . The one or more non-transitory machine-readable information storage mediums of claim 9 , wherein the incremental top-down analysis updates one or more dataflow values of the set of impacted functions by traversing the call graph in the top-down order.

12 . The one or more non-transitory machine-readable information storage mediums of claim 9 , wherein performing the incremental top-down analysis comprises:

loading a top-down worklist with a set of procedures and listing the set of impacted functions to be traversed in the top-down order from the worklist;

obtaining the set of impacted functions universally available in the set of functions and in the set of impacted functions;

fetching the set of called functions from the set of impacted functions; and

computing an entry of each called function based on a summary of the set of impacted functions and updating the entry of each called function.

Assignments (1)

Priority Claims (1)

Continuity (1)

References Cited (15)