xazax.hun accepted this revision. xazax.hun added inline comments. This revision is now accepted and ready to land.
================ Comment at: clang/lib/Analysis/IntervalPartition.cpp:26 + + std::queue<const CFGBlock *> Worklist; + for (const CFGBlock *S : Header.succs()) ---------------- ymandel wrote: > xazax.hun wrote: > > Is it possible we end up adding the same node to the queue multiple times? > > Is that desirable or do we want to make sure we only have each node at most > > once? > Added an answer in comments, but repeating here in case you want to discuss > further: > > // The worklist *may* contain duplicates. We guard against this possibility > by > // checking each popped element for completion (that is, presence in > // `Partitioned`). We choose this approach over using a set because the > queue > // allows us to flexibly insert and delete elements while iterating through > // the list. A set would require two separate phases for iterating and > // mutation. I see, thanks! This addresses my concerns. I think in some cases we use a bitset with the blocks' ids to more efficiently track things like that. ================ Comment at: clang/lib/Analysis/IntervalPartition.cpp:46-47 + + // Check whether all predecessors are in the interval, in which case `B` + // is included as well. + bool AllInInterval = true; ---------------- ymandel wrote: > xazax.hun wrote: > > I wonder if this approach is correct. Consider the following scenario: > > > > ``` > > A > > / \ > > B C > > | | > > | D > > \ / > > E > > ``` > > > > In the BFS, we might visit: ABCED. Since we visit `E` before `D`, we might > > not recognize that `E` is part of the interval. Do I miss something? > > I wonder if this approach is correct. Consider the following scenario: > > > > ``` > > A > > / \ > > B C > > | | > > | D > > \ / > > E > > ``` > > > > In the BFS, we might visit: ABCED. Since we visit `E` before `D`, we might > > not recognize that `E` is part of the interval. Do I miss something? > > When we add `D` to the interval, we'll push `E` onto the queue again (lines > 58-59). The second time that `E` is considered it will have both successors > in the interval and will be added as well. Ah, I see, makse sense, thanks! This also makes me wonder, would this algorithm be more efficient if we used RPO (in case we can use that without recalculating the order)? :D But we do not need to benchmark this for the first version. Repository: rG LLVM Github Monorepo CHANGES SINCE LAST ACTION https://reviews.llvm.org/D152263/new/ https://reviews.llvm.org/D152263 _______________________________________________ cfe-commits mailing list cfe-commits@lists.llvm.org https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits
