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
103 Views Asked by otstalyi At
1
There are 1 best solutions below
Related Questions in ABSTRACT-SYNTAX-TREE
- Javascript to Java
- Resolve complex types using Typescript AST
- AST matcher for C++ #include
- How to parse and group hierarchical list items from an unindented string in Python?
- How can I parse the standard Go package and print all constant variables?
- How to share lexical environment with recursive functions in a custom interpreter?
- How can I use custom grammar with the ast-grep Python API?
- Adding new enumerators to an Enum specifier using CDT ASTRewrite
- library to generate embedding of each line of java file and embeddings must contain ast information
- the expressionType and includePath of CDT parser
- Why Golang ast.Field can have multiple names?
- How to find ast dictionary item in Python using xpath-like expressions
- python multiprocessing locks inside async function
- How to find all function calls a defined function makes? (including recursive and futher down the stack calls)
- Changing the format of data in Python
Related Questions in STATIC-ANALYSIS
- Ansible role analysis with Checkov - facts evaluation?
- Flutter SonarQube: "The main branch has no lines of code."
- the expressionType and includePath of CDT parser
- Adding entry to program header table
- Static checker that number of arguments to python logging matches number of placeholders
- Why am I getting this error when using dataflow in Codeql
- How to disallow exception to curly_braces_in_flow_control_structures linter rule in dart?
- Security scan flagged local variable for heap inspection in C Function
- Is it possible to use Eclipse JDT static analysis for null annotations when compiling from the command line?
- Remove directory from sonar analyzer
- Sonar qube issue in using aes-256-cbc algoritm, stating Make sure that encrypting data is safe here
- Programming language/library that uses dataflow analysis to fetch only required data from the database
- Export comments from Fortify Software Security Center
- Changing lint configuration based on Cargo profile
- Can I reproduce eslint's "prefer-object-spread" rule using ast-grep?
Related Questions in CONTROL-FLOW-GRAPH
- How to get reasonable "topological order" of control flow graph (CFG) which may have loops when calculating MD index?
- Static analysis of unused assignments
- Drawing cfg using antlr4, graphiz and python and parser is empty
- Decompilation independent pattern structuring of cfg
- Decompilation creating basic blocks
- Is there a way to get Program Dependency Graph of a binary with angr?
- Control Flow Graph : properly identify loop "condition"
- Number of edges and nodes in this control flow graph (CFG)?
- Is there a way to get the filepaths of a given route's middleware in Express? Or create CFG that does?
- How exactly to construct "basic blocks" for a compiler (using JavaScript as an example)?
- Clarification on what exactly constitutes as a continue target in Vulkan SPIR-V
- It is possible to generate CFG + Callgraph in one file?
- How to determine if a BasicBlock is controled by a `if`
- Soot - Get JimpleBody from a CFG
- Time of Day affecting how Python Package is Loaded
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).