I have an AST of toy programming language. I need to find unused assignments, that is, assignments such that the value written to this variable remains unread until the end of the program, or until the next assignment. The problem looks quite simple, but I can't come up with a quick algorithm. My approach: Build a control flow graph and from each assignment run a DFS that will not pass through other assignments to this variable. This way we will understand whether there is a path from the assignment to reading this value, that is, whether this assignment is used or not.Rough complexity estimates: the control flow graph will have O(n) edges and vertices, where n is the number of tokens. Then the complexity of the algorithm is O(n^2). And this looks like a large number, considering that the source code of the programs can contain millions of tokens in theory
Static analysis of unused assignments
55 Views Asked by otstalyi At
1
There are 1 best solutions below
Related Questions in ABSTRACT-SYNTAX-TREE
- Why does Azure Auto-Scale scale go lower then minimum amount of instances?
- Data execution plan ended with error on DB restore
- Why does Azure CloudConfigurationManager.GetSetting return null
- Do I need other roles than Worker Role for a web site and service layer in Azure?
- Azure Web App PATH Variable Modification
- Azure Data Factory: LinkedService for AzureSql in failed state
- How To Update a Web Application In Azure and Keep The App Up the whole time
- Using Azure MobileServices library with my own LAN WebApi
- ionCube loader error on Azure IIS
- App crash (if closed) after click on notification
Related Questions in STATIC-ANALYSIS
- Why does Azure Auto-Scale scale go lower then minimum amount of instances?
- Data execution plan ended with error on DB restore
- Why does Azure CloudConfigurationManager.GetSetting return null
- Do I need other roles than Worker Role for a web site and service layer in Azure?
- Azure Web App PATH Variable Modification
- Azure Data Factory: LinkedService for AzureSql in failed state
- How To Update a Web Application In Azure and Keep The App Up the whole time
- Using Azure MobileServices library with my own LAN WebApi
- ionCube loader error on Azure IIS
- App crash (if closed) after click on notification
Related Questions in CONTROL-FLOW-GRAPH
- Why does Azure Auto-Scale scale go lower then minimum amount of instances?
- Data execution plan ended with error on DB restore
- Why does Azure CloudConfigurationManager.GetSetting return null
- Do I need other roles than Worker Role for a web site and service layer in Azure?
- Azure Web App PATH Variable Modification
- Azure Data Factory: LinkedService for AzureSql in failed state
- How To Update a Web Application In Azure and Keep The App Up the whole time
- Using Azure MobileServices library with my own LAN WebApi
- ionCube loader error on Azure IIS
- App crash (if closed) after click on notification
Trending Questions
- UIImageView Frame Doesn't Reflect Constraints
- Is it possible to use adb commands to click on a view by finding its ID?
- How to create a new web character symbol recognizable by html/javascript?
- Why isn't my CSS3 animation smooth in Google Chrome (but very smooth on other browsers)?
- Heap Gives Page Fault
- Connect ffmpeg to Visual Studio 2008
- Both Object- and ValueAnimator jumps when Duration is set above API LvL 24
- How to avoid default initialization of objects in std::vector?
- second argument of the command line arguments in a format other than char** argv or char* argv[]
- How to improve efficiency of algorithm which generates next lexicographic permutation?
- Navigating to the another actvity app getting crash in android
- How to read the particular message format in android and store in sqlite database?
- Resetting inventory status after order is cancelled
- Efficiently compute powers of X in SSE/AVX
- Insert into an external database using ajax and php : POST 500 (Internal Server Error)
Popular # Hahtags
Popular Questions
- How do I undo the most recent local commits in Git?
- How can I remove a specific item from an array in JavaScript?
- How do I delete a Git branch locally and remotely?
- Find all files containing a specific text (string) on Linux?
- How do I revert a Git repository to a previous commit?
- How do I create an HTML button that acts like a link?
- How do I check out a remote Git branch?
- How do I force "git pull" to overwrite local files?
- How do I list all files of a directory?
- How to check whether a string contains a substring in JavaScript?
- How do I redirect to another webpage?
- How can I iterate over rows in a Pandas DataFrame?
- How do I convert a String to an int in Java?
- Does Python have a string 'contains' substring method?
- How do I check if a string contains a specific word?
It seems that your "unused assignments analysis" is similar to the problem of "live-variable analysis". If you care about the theoretical complexity of the algorithm for solving this, it can be solved by applying the lattice theorems. If you care about the implementation, there are some open-source implementations on GitHub of liveness analysis for C/C++, JAVA (my code for course homework, maybe buggy).