MLIR dead code analysis

I am writing a pass for Flang using mlir::dataflow::DenseDataFlowAnalysis (⚙ D140415 [flang] stack arrays pass). The dense data flow analysis requires mlir::dataflow::DeadCodeAnalysis to run first.

DeadCodeAnalysis::visitBranchOperation attempts to fetch conditional branch operand values from the constant propagation analysis pass. If constant values cannot be determined for the branch operands, visitBranchOperation will fall back to marking no edges live.

I think it would make more sense to fall back to marking all successor blocks as live, as they are presumably branch targets reachable depending upon information available at runtime.

Have I understood this behavior correctly, or have I set up the analysis wrong? I am loading mlir::dataflow::SparseConstantPropagation before DeadCodeAnalysis into the mlir::DataFlowSolver instance.

Tagging @phisiart @Mogball

The order in which you load the analyses doesn’t matter. If you have loaded SparseConstantPropagation but DeadCodeAnalysis is still marking all successors as dead, then either those successors are dead or there’s a bug somewhere… Can you post more details?

Ahh I have found a bug on my end. I am sorry for the noise. This is not a bug.

Nonetheless, would you mind correcting my understanding of DeadCodeAnalysis::visitBranchOperation?

Why doesn’t visitRegionBranchOperation loop over all branch successors even when constant propagation information for branch arguments is not available?

I’m not the original author but I can provide my theory.

The DataFlowSolver runs all the loaded analyses simultaneously in the same worklist algorithm execution. During the execution, information about ConstantPropagation and 'DeadCodeAnalysis` is propagated together.

When ConstantPropagation and 'DeadCodeAnalysisare both loaded, the fact that some branch operands have noConstantPropagationinformation attached to them means thatConstantPropagation` information has not propagated there yet, which means that the branch op is considered not reachable. Therefore, keeping all successors as dead is the right thing to do.

I think the real problem is that, this design means that you must always load both SparseConstantPropagation and DeadCodeAnalysis into the DataFlowSolver, otherwise you will never mark any edge as live. This limits the flexibility of the API.

I tend to believe that we might as well just make dead code analysis a built-in feature of DataFlowSolver, and ask the analysis writer to provide a callback to specify which successors are live.

1 Like

Is that true? I’ve used just DeadCodeAnalysis along with just another but without constant analysis and it did the correct thing (now to be fair I was surprised I needed to add DeadCodeAnalysis and all the input of interest to me had one block per region, which wasn’t visited without dead code analysis but fine with). It may be good/point to needing more tests for this upstream. I find it surprising that constant analysis is needed (it feels like wrong conservative state).

@jpienaar The constant propagation is used to attempt to predict the outcome of cf.cond_br operations, so if you only had one block per region, DeadCodeAnalysis will work correctly without constant propagation analysis.

@phisiart thank you for the explanation. I agree that including DeadCodeAnalysis as a built-in feature in the DataFlowSolver is a good idea - it was surprising to me first that I needed DeadCodeAnalysis to get the general dense data flow analysis to work, and secondly that I needed the constant propagation analysis to handle control flow blocks correctly…

I tried out the data flow analysis framework, and also realized the DeadCodeAnalysis was required for pretty much every analysis I wanted to do. So I’m sympathetic to making this easier to get started with, but I’m also curious what making it a “built-in” feature would entail. Maybe rather than built-in in the sense of “always included in DataFlowSolver” is too strong, but we could provide some helper that includes some sensible defaults (e.g. DeadCodeAnalysis and SparseConstantPropagation), which users could extend.