Optimization change false positive leads to infinite loop

[msoeken]

Describe the bug

Running PreEvaluation.All leads to infinite loop triggered false positive in changed flag in OptimizingTransformation

To Reproduce

Steps to reproduce the behavior:

1. Check out branch msoeken/bug-optimization-loop
2. Run test Test.Compiler\Microsoft.Quantum.QsCompiler.Testing\OptimizationTests\trigger infinite loop

Expected behavior

Transformation passes finish after one round of evaluation.

System information

• master branch
• .NET Core 3.0.100
• Microsoft Windows 10 Enterprise 10.0.18363 Build 18363

Additional context

The problem is due to the check (x.Elements, x.Name) <> (newX.Elements, newX.Name) in https://github.com/microsoft/qsharp-compiler/blob/master/src/QsCompiler/Optimizations/Utils/HelperTransformations.fs#L93

Here x.Elements and newX.Elements are not structurally equivalent, but lead to the same output when, e.g., printed with sprintf %A. Going down AST it seems that the difference comes from the TypedParameterResolutions from the call to Length(array). It seems that even though the entries in the ImmutableDictionary are the same, comparing them with <> returns false.

It is sufficient to trigger the bug by only applying the StatementRemover transformation in PreEvaluation.All.

The bug did not exist in 6fa2e76.

[msoeken]

The infinite loop does not occur when replacing this.onTypeParamResolutions ex.TypeParameterResolutions with ex.TypeParameterResolutions in https://github.com/microsoft/qsharp-compiler/blob/master/src/QsCompiler/Core/ExpressionTransformation.fs#L374

[msoeken]

The change was added in #197.

[bettinaheim]

@msoeken
Thank you for the great report pinpointing the issue!
Assigned to you, with your permission.