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
96 Views Asked by otstalyi At
1
There are 1 best solutions below
Related Questions in ABSTRACT-SYNTAX-TREE
- Generate C++ style code using LLVM
- How to traverse all nodes of clang AST?
- deleting a if statements using ASTParser from a given .java file
- is there there way to access stylus AST
- JDT AstParser - How to get Assignment (parent) from MethodInvocation
- Obtaning the AST of JavaScript code from Spidermonkey
- Three-address code and symbol tables
- Alternate way to read a file as json using python
- HQL unexpected AST node:unexpected AST node:
- How can I evaluate a list of strings as a list of tuples in Python?
- Parse Python Function's Class Name
- Custom Lint for Java / Android Report if we find a class call without implementing its interface
- How can I detect by static analysis, if a project is using Java8?
- Is it possible to work with AST inside D code?
- Java Runtime Compiling within scope
Related Questions in STATIC-ANALYSIS
- How to detect functions, that are only called from unused functions using cppcheck?
- Use static analysis tools to check null pointers and memory leaks in Linux device drivers
- Why it is not suggested to pass hardcoded absolute path name to File object constructor File(String)
- Visual Studio - Discover if method is called by another method at some point
- False positive: precondition is redundant
- Cppcheck GUI: Excluding a file or folder from checking
- How to get better results from LLVM's MemoryDependenceAnalysis pass?
- How to enforce static imports for some methods using checkstyle?
- Dealing with code movement when comparing static analysis reports
- Is there a way to find the ignored JUnit Test with the most lines of code in a large codebase?
- JSHint in javascript is not showing all warnings for code to be corrected
- Parsing Hack code into Abstract Syntax Tree
- Understanding x86 r/m32 instruction
- LLVM Error When Using a Pass from Another Pass
- Sonar - Python plugin rules, what tools it uses behind?
Related Questions in CONTROL-FLOW-GRAPH
- Control Flow Graphs - find all linearly independent paths
- Understand control flow graph in lcov branch coverage output
- Can I translate an AST to SSA, or do I need to translate to a CFG then to SSA?
- Tool to compare control flow of disassembly and C
- control edge rendering of a network in vis.js
- Extracting Basic Blocks/CFG from LLVM/clang on the Backend
- Control flow graph dominance
- Flattening a control flow graph to structured code
- Decompilation creating basic blocks
- Decompilation independent pattern structuring of cfg
- Drawing cfg using antlr4, graphiz and python and parser is empty
- Static analysis of unused assignments
- identifying a loop in LLVM CFG
- How to determine if a BasicBlock is controled by a `if`
- Why are the variables "i" and "j" considered dead in the control flow graph?
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 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).