Defuse analysis fails with "Overwriting definitions"

[vhavel]

The attached file: defuse_fail.p4.txt triggers a failed BUG_CHECK during def-use analysis:

Compiler Bug: Overwriting definitions at <BlockStatement>(1396)

I checked the IR before def-use is invoked - the problematic BlockStatement is reachable on two control-flow program paths, but def-use seems to assume the IR doesn't share nodes. The node sharing is created by the inlining pass (running before defuse since #3591). Inlining substitutes both C1.apply method calls with C1 body, but the body isn't deep-copied, hence the two places where C1 is inlined share part of the IR subtree.

[mihaibudiu]

Indeed, def-use cannot work when IR DAGs are shared, because it keeps a map from statement to definitions, so statements cannot be reused. It was supposed to clone everything needed before running, though. Will have to figure out why.

[vhavel]

Indeed, def-use cannot work when IR DAGs are shared, because it keeps a map from statement to definitions, so statements cannot be reused. It was supposed to clone everything needed before running, though. Will have to figure out why.

Shouldn't inlining be responsible for cloning the inlined IR subtree? Adding Substitutions::preorder(IR::Statement* stmt) method which returns stmt->clone() seems to help in this particular case, but maybe GeneralInliner should just duplicate whole inlined body? Simple clone() isn't enough though, because it shallow-copies.

[mihaibudiu]

The rule is that if a pass needs some preconditions it should establish them by itself.
The order of passes changes, and new passes get inserted.
(But we do expect some changes never to be undone by subsequent passes - the treeness of the IR DAG is not one of them.)

[mihaibudiu]

Also, some statements are simply impossible to clone due to the design of the visitor structure, for example even if you clone the EmptyStatement you still get in the resulting tree the original one - there's a check in the visitor which returns the original node if it is equivalent with the replacement node, and any two EmptyStatements are always equivalent. So the DefUse pass needs to replace them with empty blocks, which fortunately are not considered equivalent.