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
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).