Share 'when' expressions in DAGs when needed by jcouv · Pull Request #55981 · dotnet/roslyn

jcouv · 2021-08-27T23:18:23Z

alrz · 2021-08-28T16:44:27Z

+                // So we can't just lower each `BoundWhenDecisionDagNode` separately, as that would result in duplicate blocks
+                // for the same `WhenExpression` and such expressions might contains labels which must be emitted once only.


Out of curiosity, would it make sense to rewrite when-expressions and replace offending nodes? similar to spilling but for jumps and labels. Just wondering if a nested dispatch could be avoided. #Resolved

Yes, that's definitely an option.

Three broad approaches were considered:

avoid the bifurcation with duplication in the first place (we need branches of the DAG to join back together, this likely involves replacing the selected pattern test with checking the cached result of previous test)

using subroutine/dispatch approach to share body of when-expressions (or extracting share-when expressions to a local function).

properly cloning such shared BoundExpressions rather than re-using instances

In terms of trade-offs, options 1 is the most difficult to land safely and successfully for 17.0 timeframe.
As for choosing option 2 over 3, one reason is when-expressions can be arbitrarily complex so duplicating them could inflate the IL. Also we'd have to review all bound nodes (are BoundLabelStatements the only nodes that need adjustment when cloning?).

jcouv · 2021-08-28T17:16:50Z

+    public static void M(int i, bool b1, bool b2)
+    {
+        string text;
+        switch (i)


📝 To help visualize what's going on, here's the DAG for this example (notice that states 1 and 4 would match if b2 is true) and the corresponding lowered switch statement (with label <sharedWhenExpression-6> indicating the shared when expression):

DAG

State 0 1. [case not 1 when b1:] Not (?DagValueTest(t0 == ConstantValueOne(1: Int32))) WHEN[b1] 2. [case var _ when b2:] MATCH WHEN[b2] 3. [case 1:] ?DagValueTest(t0 == ConstantValueOne(1: Int32)) Test: ?DagValueTest(t0 == ConstantValueOne(1: Int32)) TrueBranch: 1 FalseBranch: 3 *State 1 REMAINING t0:[1..1] 2. [case var _ when b2:] MATCH WHEN[b2] 3. [case 1:] MATCH FalseBranch: 2 *State 2 REMAINING t0:[1..1] 3. [case 1:] MATCH *State 3 REMAINING t0:[-2147483648..0],[2..2147483647] 1. [case not 1 when b1:] MATCH WHEN[b1] 2. [case var _ when b2:] MATCH WHEN[b2] FalseBranch: 4 *State 4 REMAINING t0:[-2147483648..0],[2..2147483647] 2. [case var _ when b2:] MATCH WHEN[b2] FalseBranch: 5 *State 5 FAIL REMAINING t0:[-2147483648..0],[2..2147483647]

Lowered bound tree

block ├─locals: {text} └─statements ├─sequencePointWithSpan │ ├─statementOpt │ └─span: [213..214) ├─sequencePointWithSpan │ ├─statementOpt │ │ └─block │ │ ├─locals: {System.Int32 LoweringTemp.2, System.Int32 SwitchCasePatternMatching.1} │ │ └─statements │ │ ├─expressionStatement │ │ │ └─expression │ │ │ └─assignmentOperator │ │ │ ├─left │ │ │ │ └─local │ │ │ │ ├─localSymbol: System.Int32 SwitchCasePatternMatching.1 │ │ │ │ ├─declarationKind: None │ │ │ │ ├─constantValueOpt │ │ │ │ ├─isNullableUnknown: False │ │ │ │ └─type: int │ │ │ ├─right │ │ │ │ └─parameter │ │ │ │ ├─parameterSymbol: int │ │ │ │ └─type: int │ │ │ └─type: int │ │ ├─sequencePoint │ │ │ └─statementOpt │ │ ├─block │ │ │ └─statements │ │ │ ├─conditionalGoto │ │ │ │ ├─condition │ │ │ │ │ └─binaryOperator │ │ │ │ │ ├─operatorKind: IntEqual │ │ │ │ │ ├─data │ │ │ │ │ ├─resultKind: Viable │ │ │ │ │ ├─left │ │ │ │ │ │ └─local │ │ │ │ │ │ ├─localSymbol: System.Int32 SwitchCasePatternMatching.1 │ │ │ │ │ │ ├─declarationKind: None │ │ │ │ │ │ ├─constantValueOpt │ │ │ │ │ │ ├─isNullableUnknown: False │ │ │ │ │ │ └─type: int │ │ │ │ │ ├─right │ │ │ │ │ │ └─literal │ │ │ │ │ │ ├─constantValueOpt: ConstantValueOne(1: Int32) │ │ │ │ │ │ └─type: int │ │ │ │ │ └─type: bool │ │ │ │ ├─jumpIfTrue: True │ │ │ │ └─label: <dagNode-3> │ │ │ └─gotoStatement │ │ │ ├─label: <dagNode-4> │ │ │ ├─caseExpressionOpt │ │ │ └─labelExpressionOpt │ │ ├─statementList │ │ │ └─statements │ │ │ ├─sequencePoint │ │ │ │ └─statementOpt │ │ │ ├─labelStatement │ │ │ │ └─label: <dagNode-4> │ │ │ ├─sequencePointWithSpan │ │ │ │ ├─statementOpt │ │ │ │ │ └─conditionalGoto │ │ │ │ │ ├─condition │ │ │ │ │ │ └─parameter │ │ │ │ │ │ ├─parameterSymbol: bool │ │ │ │ │ │ └─type: bool │ │ │ │ │ ├─jumpIfTrue: True │ │ │ │ │ └─label: case not 1 when b1: │ │ │ │ └─span: [292..299) │ │ │ ├─sequencePoint │ │ │ │ └─statementOpt │ │ │ │ └─gotoStatement │ │ │ │ ├─label: <dagNode-5> │ │ │ │ ├─caseExpressionOpt │ │ │ │ └─labelExpressionOpt │ │ │ ├─labelStatement │ │ │ │ └─label: case not 1 when b1: │ │ │ ├─sequencePoint │ │ │ │ └─statementOpt │ │ │ │ └─expressionStatement │ │ │ │ └─expression │ │ │ │ └─assignmentOperator │ │ │ │ ├─left │ │ │ │ │ └─local │ │ │ │ │ ├─localSymbol: text │ │ │ │ │ ├─declarationKind: None │ │ │ │ │ ├─constantValueOpt │ │ │ │ │ ├─isNullableUnknown: False │ │ │ │ │ └─type: string │ │ │ │ ├─right │ │ │ │ │ └─literal │ │ │ │ │ ├─constantValueOpt: ConstantValueString("b1": String) │ │ │ │ │ └─type: string │ │ │ │ └─type: string │ │ │ └─sequencePoint │ │ │ └─statementOpt │ │ │ └─gotoStatement │ │ │ ├─label: <break-2> │ │ │ ├─caseExpressionOpt │ │ │ └─labelExpressionOpt │ │ ├─statementList │ │ │ └─statements │ │ │ ├─sequencePoint │ │ │ │ └─statementOpt │ │ │ ├─labelStatement │ │ │ │ └─label: <dagNode-3> │ │ │ ├─expressionStatement │ │ │ │ └─expression │ │ │ │ └─assignmentOperator │ │ │ │ ├─left │ │ │ │ │ └─local │ │ │ │ │ ├─localSymbol: System.Int32 LoweringTemp.2 │ │ │ │ │ ├─declarationKind: None │ │ │ │ │ ├─constantValueOpt │ │ │ │ │ ├─isNullableUnknown: False │ │ │ │ │ └─type: int │ │ │ │ ├─right │ │ │ │ │ └─literal │ │ │ │ │ ├─constantValueOpt: ConstantValueDefault(0: Int32) │ │ │ │ │ └─type: int │ │ │ │ └─type: int │ │ │ ├─gotoStatement │ │ │ │ ├─label: <sharedWhenExpression-6> │ │ │ │ ├─caseExpressionOpt │ │ │ │ └─labelExpressionOpt │ │ │ ├─labelStatement │ │ │ │ └─label: <dagNode-5> │ │ │ ├─expressionStatement │ │ │ │ └─expression │ │ │ │ └─assignmentOperator │ │ │ │ ├─left │ │ │ │ │ └─local │ │ │ │ │ ├─localSymbol: System.Int32 LoweringTemp.2 │ │ │ │ │ ├─declarationKind: None │ │ │ │ │ ├─constantValueOpt │ │ │ │ │ ├─isNullableUnknown: False │ │ │ │ │ └─type: int │ │ │ │ ├─right │ │ │ │ │ └─literal │ │ │ │ │ ├─constantValueOpt: ConstantValueI32(2: Int32) │ │ │ │ │ └─type: int │ │ │ │ └─type: int │ │ │ ├─gotoStatement │ │ │ │ ├─label: <sharedWhenExpression-6> │ │ │ │ ├─caseExpressionOpt │ │ │ │ └─labelExpressionOpt │ │ │ ├─labelStatement │ │ │ │ └─label: <sharedWhenExpression-6> │ │ │ ├─sequencePointWithSpan │ │ │ │ ├─statementOpt │ │ │ │ │ └─block │ │ │ │ │ └─statements │ │ │ │ │ ├─conditionalGoto │ │ │ │ │ │ ├─condition │ │ │ │ │ │ │ └─parameter │ │ │ │ │ │ │ ├─parameterSymbol: bool │ │ │ │ │ │ │ └─type: bool │ │ │ │ │ │ ├─jumpIfTrue: False │ │ │ │ │ │ └─label: <afterif-11> │ │ │ │ │ ├─block │ │ │ │ │ │ └─statements │ │ │ │ │ │ ├─switchDispatch │ │ │ │ │ │ │ ├─expression │ │ │ │ │ │ │ │ └─local │ │ │ │ │ │ │ │ ├─localSymbol: System.Int32 LoweringTemp.2 │ │ │ │ │ │ │ │ ├─declarationKind: None │ │ │ │ │ │ │ │ ├─constantValueOpt │ │ │ │ │ │ │ │ ├─isNullableUnknown: False │ │ │ │ │ │ │ │ └─type: int │ │ │ │ │ │ │ ├─cases: {(ConstantValueDefault(0: Int32), <case 0-9>), (ConstantValueI32(2: Int32), <case 2-10>)} │ │ │ │ │ │ │ ├─defaultLabel: <break-8> │ │ │ │ │ │ │ └─equalityMethod │ │ │ │ │ │ ├─labelStatement │ │ │ │ │ │ │ └─label: <case 0-9> │ │ │ │ │ │ ├─gotoStatement │ │ │ │ │ │ │ ├─label: case var _ when b2: │ │ │ │ │ │ │ ├─caseExpressionOpt │ │ │ │ │ │ │ └─labelExpressionOpt │ │ │ │ │ │ ├─labelStatement │ │ │ │ │ │ │ └─label: <case 2-10> │ │ │ │ │ │ ├─gotoStatement │ │ │ │ │ │ │ ├─label: case var _ when b2: │ │ │ │ │ │ │ ├─caseExpressionOpt │ │ │ │ │ │ │ └─labelExpressionOpt │ │ │ │ │ │ └─labelStatement │ │ │ │ │ │ └─label: <break-8> │ │ │ │ │ └─labelStatement │ │ │ │ │ └─label: <afterif-11> │ │ │ │ └─span: [379..386) │ │ │ ├─sequencePoint │ │ │ │ └─statementOpt │ │ │ │ └─block │ │ │ │ └─statements │ │ │ │ ├─switchDispatch │ │ │ │ │ ├─expression │ │ │ │ │ │ └─local │ │ │ │ │ │ ├─localSymbol: System.Int32 LoweringTemp.2 │ │ │ │ │ │ ├─declarationKind: None │ │ │ │ │ │ ├─constantValueOpt │ │ │ │ │ │ ├─isNullableUnknown: False │ │ │ │ │ │ └─type: int │ │ │ │ │ ├─cases: {(ConstantValueDefault(0: Int32), <case 0-13>), (ConstantValueI32(2: Int32), <case 2-14>)} │ │ │ │ │ ├─defaultLabel: <break-12> │ │ │ │ │ └─equalityMethod │ │ │ │ ├─labelStatement │ │ │ │ │ └─label: <case 0-13> │ │ │ │ ├─gotoStatement │ │ │ │ │ ├─label: case 1: │ │ │ │ │ ├─caseExpressionOpt │ │ │ │ │ └─labelExpressionOpt │ │ │ │ ├─labelStatement │ │ │ │ │ └─label: <case 2-14> │ │ │ │ ├─gotoStatement │ │ │ │ │ ├─label: default │ │ │ │ │ ├─caseExpressionOpt │ │ │ │ │ └─labelExpressionOpt │ │ │ │ └─labelStatement │ │ │ │ └─label: <break-12> │ │ │ ├─labelStatement │ │ │ │ └─label: case var _ when b2: │ │ │ ├─sequencePoint │ │ │ │ └─statementOpt │ │ │ │ └─expressionStatement │ │ │ │ └─expression │ │ │ │ └─assignmentOperator │ │ │ │ ├─left │ │ │ │ │ └─local │ │ │ │ │ ├─localSymbol: text │ │ │ │ │ ├─declarationKind: None │ │ │ │ │ ├─constantValueOpt │ │ │ │ │ ├─isNullableUnknown: False │ │ │ │ │ └─type: string │ │ │ │ ├─right │ │ │ │ │ └─literal │ │ │ │ │ ├─constantValueOpt: ConstantValueString("b2": String) │ │ │ │ │ └─type: string │ │ │ │ └─type: string │ │ │ └─sequencePoint │ │ │ └─statementOpt │ │ │ └─gotoStatement │ │ │ ├─label: <break-2> │ │ │ ├─caseExpressionOpt │ │ │ └─labelExpressionOpt │ │ ├─statementList │ │ │ └─statements │ │ │ ├─sequencePoint │ │ │ │ └─statementOpt │ │ │ ├─labelStatement │ │ │ │ └─label: case 1: │ │ │ ├─sequencePoint │ │ │ │ └─statementOpt │ │ │ │ └─expressionStatement │ │ │ │ └─expression │ │ │ │ └─assignmentOperator │ │ │ │ ├─left │ │ │ │ │ └─local │ │ │ │ │ ├─localSymbol: text │ │ │ │ │ ├─declarationKind: None │ │ │ │ │ ├─constantValueOpt │ │ │ │ │ ├─isNullableUnknown: False │ │ │ │ │ └─type: string │ │ │ │ ├─right │ │ │ │ │ └─literal │ │ │ │ │ ├─constantValueOpt: ConstantValueString("1": String) │ │ │ │ │ └─type: string │ │ │ │ └─type: string │ │ │ └─sequencePoint │ │ │ └─statementOpt │ │ │ └─gotoStatement │ │ │ ├─label: <break-2> │ │ │ ├─caseExpressionOpt │ │ │ └─labelExpressionOpt │ │ ├─statementList │ │ │ └─statements │ │ │ ├─sequencePoint │ │ │ │ └─statementOpt │ │ │ ├─labelStatement │ │ │ │ └─label: default │ │ │ ├─sequencePoint │ │ │ │ └─statementOpt │ │ │ │ └─expressionStatement │ │ │ │ └─expression │ │ │ │ └─assignmentOperator │ │ │ │ ├─left │ │ │ │ │ └─local │ │ │ │ │ ├─localSymbol: text │ │ │ │ │ ├─declarationKind: None │ │ │ │ │ ├─constantValueOpt │ │ │ │ │ ├─isNullableUnknown: False │ │ │ │ │ └─type: string │ │ │ │ ├─right │ │ │ │ │ └─literal │ │ │ │ │ ├─constantValueOpt: ConstantValueString("default": String) │ │ │ │ │ └─type: string │ │ │ │ └─type: string │ │ │ └─sequencePoint │ │ │ └─statementOpt │ │ │ └─gotoStatement │ │ │ ├─label: <break-2> │ │ │ ├─caseExpressionOpt │ │ │ └─labelExpressionOpt │ │ ├─sequencePoint │ │ │ └─statementOpt │ │ └─labelStatement │ │ └─label: <break-2> │ └─span: [246..256) ├─sequencePoint │ └─statementOpt │ └─expressionStatement │ └─expression │ └─call │ ├─receiverOpt │ │ └─typeExpression │ │ ├─aliasOpt │ │ ├─boundContainingTypeOpt │ │ ├─boundDimensionsOpt │ │ ├─typeWithAnnotations: System.Console │ │ └─type: System.Console │ ├─method: System.Console.WriteLine(object) │ ├─arguments │ │ └─conversion │ │ ├─operand │ │ │ └─objectCreationExpression │ │ │ ├─constructor: (int i, bool b1, bool b2, string text).ValueTuple(int, bool, bool, string) │ │ │ ├─constructorsGroup: {} │ │ │ ├─arguments │ │ │ │ ├─parameter │ │ │ │ │ ├─parameterSymbol: int │ │ │ │ │ └─type: int │ │ │ │ ├─parameter │ │ │ │ │ ├─parameterSymbol: bool │ │ │ │ │ └─type: bool │ │ │ │ ├─parameter │ │ │ │ │ ├─parameterSymbol: bool │ │ │ │ │ └─type: bool │ │ │ │ └─local │ │ │ │ ├─localSymbol: text │ │ │ │ ├─declarationKind: None │ │ │ │ ├─constantValueOpt │ │ │ │ ├─isNullableUnknown: False │ │ │ │ └─type: string │ │ │ ├─argumentNamesOpt: (null) │ │ │ ├─argumentRefKindsOpt: (null) │ │ │ ├─expanded: False │ │ │ ├─argsToParamsOpt: (null) │ │ │ ├─defaultArguments: Microsoft.CodeAnalysis.BitVector │ │ │ ├─constantValueOpt │ │ │ ├─initializerExpressionOpt │ │ │ ├─wasTargetTyped: False │ │ │ └─type: (int i, bool b1, bool b2, string text) │ │ ├─conversion: Boxing │ │ ├─isBaseConversion: False │ │ ├─@checked: False │ │ ├─explicitCastInCode: False │ │ ├─constantValueOpt │ │ ├─conversionGroupOpt │ │ ├─originalUserDefinedConversionsOpt: {} │ │ └─type: object │ ├─argumentNamesOpt: (null) │ ├─argumentRefKindsOpt: (null) │ ├─isDelegateCall: False │ ├─expanded: False │ ├─invokedAsExtensionMethod: False │ ├─argsToParamsOpt: (null) │ ├─defaultArguments: Microsoft.CodeAnalysis.BitVector │ ├─resultKind: Viable │ ├─originalMethodsOpt: (null) │ └─type: void └─sequencePointWithSpan ├─statementOpt │ └─returnStatement │ ├─refKind: None │ └─expressionOpt └─span: [669..670)

#Resolved

jcouv · 2021-08-28T17:17:29Z

                DoDumpCompact(child, indent + (i == children.Count - 1 ? "  " : "\u2502 "));
            }
+
+            static IEnumerable<TreeDumperNode> filter(IEnumerable<TreeDumperNode> nodes)


📝 this is not essential to the PR, but greatly helps when staring with large bound trees #Resolved

jcouv · 2021-08-28T17:24:09Z

+static string M(int i1, int i2, int i3, bool b0, bool b1, bool b2, bool b3)
+{
+    object o = null;
+    switch (i1, i2, i3)


📝 Below is the dump of this DAG. Notice that states 10, 14, 18 and 20 will match when b3 is true, and states 8 and 17 match when b1 is true.

DAG dump

State 0 1. [case (var x, var y, var z) when f(x, y, z):] AND(t1=DagFieldEvaluation(t0.i1), t2=DagFieldEvaluation(t0.i2), t3=DagFieldEvaluation(t0.i3)) BIND[x=t1; y=t2; z=t3] WHEN[f(x, y, z)] 2. [case (not 0, 0, _) when b0:] AND(t1=DagFieldEvaluation(t0.i1), Not (?DagValueTest(t1 == ConstantValueDefault(0: Int32))), t2=DagFieldEvaluation(t0.i2), ?DagValueTest(t2 == ConstantValueDefault(0: Int32))) WHEN[b0] 3. [case (_, not 0, 0) when b1:] AND(t2=DagFieldEvaluation(t0.i2), Not (?DagValueTest(t2 == ConstantValueDefault(0: Int32))), t3=DagFieldEvaluation(t0.i3), ?DagValueTest(t3 == ConstantValueDefault(0: Int32))) WHEN[b1] 4. [case (0, _, not 0) when b2:] AND(t1=DagFieldEvaluation(t0.i1), ?DagValueTest(t1 == ConstantValueDefault(0: Int32)), t3=DagFieldEvaluation(t0.i3), Not (?DagValueTest(t3 == ConstantValueDefault(0: Int32)))) WHEN[b2] 5. [case (_, _, _) when b3:] MATCH WHEN[b3] 6. [case (0, _, _):] AND(t1=DagFieldEvaluation(t0.i1), ?DagValueTest(t1 == ConstantValueDefault(0: Int32))) 7. [case (_, 0, _):] AND(t2=DagFieldEvaluation(t0.i2), ?DagValueTest(t2 == ConstantValueDefault(0: Int32))) 8. [case (_, _, 0):] AND(t3=DagFieldEvaluation(t0.i3), ?DagValueTest(t3 == ConstantValueDefault(0: Int32))) Test: t1=DagFieldEvaluation(t0.i1) TrueBranch: 1 State 1 1. [case (var x, var y, var z) when f(x, y, z):] AND(t2=DagFieldEvaluation(t0.i2), t3=DagFieldEvaluation(t0.i3)) BIND[x=t1; y=t2; z=t3] WHEN[f(x, y, z)] 2. [case (not 0, 0, _) when b0:] AND(Not (?DagValueTest(t1 == ConstantValueDefault(0: Int32))), t2=DagFieldEvaluation(t0.i2), ?DagValueTest(t2 == ConstantValueDefault(0: Int32))) WHEN[b0] 3. [case (_, not 0, 0) when b1:] AND(t2=DagFieldEvaluation(t0.i2), Not (?DagValueTest(t2 == ConstantValueDefault(0: Int32))), t3=DagFieldEvaluation(t0.i3), ?DagValueTest(t3 == ConstantValueDefault(0: Int32))) WHEN[b1] 4. [case (0, _, not 0) when b2:] AND(?DagValueTest(t1 == ConstantValueDefault(0: Int32)), t3=DagFieldEvaluation(t0.i3), Not (?DagValueTest(t3 == ConstantValueDefault(0: Int32)))) WHEN[b2] 5. [case (_, _, _) when b3:] MATCH WHEN[b3] 6. [case (0, _, _):] ?DagValueTest(t1 == ConstantValueDefault(0: Int32)) 7. [case (_, 0, _):] AND(t2=DagFieldEvaluation(t0.i2), ?DagValueTest(t2 == ConstantValueDefault(0: Int32))) 8. [case (_, _, 0):] AND(t3=DagFieldEvaluation(t0.i3), ?DagValueTest(t3 == ConstantValueDefault(0: Int32))) Test: t2=DagFieldEvaluation(t0.i2) TrueBranch: 2 State 2 1. [case (var x, var y, var z) when f(x, y, z):] t3=DagFieldEvaluation(t0.i3) BIND[x=t1; y=t2; z=t3] WHEN[f(x, y, z)] 2. [case (not 0, 0, _) when b0:] AND(Not (?DagValueTest(t1 == ConstantValueDefault(0: Int32))), ?DagValueTest(t2 == ConstantValueDefault(0: Int32))) WHEN[b0] 3. [case (_, not 0, 0) when b1:] AND(Not (?DagValueTest(t2 == ConstantValueDefault(0: Int32))), t3=DagFieldEvaluation(t0.i3), ?DagValueTest(t3 == ConstantValueDefault(0: Int32))) WHEN[b1] 4. [case (0, _, not 0) when b2:] AND(?DagValueTest(t1 == ConstantValueDefault(0: Int32)), t3=DagFieldEvaluation(t0.i3), Not (?DagValueTest(t3 == ConstantValueDefault(0: Int32)))) WHEN[b2] 5. [case (_, _, _) when b3:] MATCH WHEN[b3] 6. [case (0, _, _):] ?DagValueTest(t1 == ConstantValueDefault(0: Int32)) 7. [case (_, 0, _):] ?DagValueTest(t2 == ConstantValueDefault(0: Int32)) 8. [case (_, _, 0):] AND(t3=DagFieldEvaluation(t0.i3), ?DagValueTest(t3 == ConstantValueDefault(0: Int32))) Test: t3=DagFieldEvaluation(t0.i3) TrueBranch: 3 *State 3 1. [case (var x, var y, var z) when f(x, y, z):] MATCH BIND[x=t1; y=t2; z=t3] WHEN[f(x, y, z)] 2. [case (not 0, 0, _) when b0:] AND(Not (?DagValueTest(t1 == ConstantValueDefault(0: Int32))), ?DagValueTest(t2 == ConstantValueDefault(0: Int32))) WHEN[b0] 3. [case (_, not 0, 0) when b1:] AND(Not (?DagValueTest(t2 == ConstantValueDefault(0: Int32))), ?DagValueTest(t3 == ConstantValueDefault(0: Int32))) WHEN[b1] 4. [case (0, _, not 0) when b2:] AND(?DagValueTest(t1 == ConstantValueDefault(0: Int32)), Not (?DagValueTest(t3 == ConstantValueDefault(0: Int32)))) WHEN[b2] 5. [case (_, _, _) when b3:] MATCH WHEN[b3] 6. [case (0, _, _):] ?DagValueTest(t1 == ConstantValueDefault(0: Int32)) 7. [case (_, 0, _):] ?DagValueTest(t2 == ConstantValueDefault(0: Int32)) 8. [case (_, _, 0):] ?DagValueTest(t3 == ConstantValueDefault(0: Int32)) FalseBranch: 4 State 4 2. [case (not 0, 0, _) when b0:] AND(Not (?DagValueTest(t1 == ConstantValueDefault(0: Int32))), ?DagValueTest(t2 == ConstantValueDefault(0: Int32))) WHEN[b0] 3. [case (_, not 0, 0) when b1:] AND(Not (?DagValueTest(t2 == ConstantValueDefault(0: Int32))), ?DagValueTest(t3 == ConstantValueDefault(0: Int32))) WHEN[b1] 4. [case (0, _, not 0) when b2:] AND(?DagValueTest(t1 == ConstantValueDefault(0: Int32)), Not (?DagValueTest(t3 == ConstantValueDefault(0: Int32)))) WHEN[b2] 5. [case (_, _, _) when b3:] MATCH WHEN[b3] 6. [case (0, _, _):] ?DagValueTest(t1 == ConstantValueDefault(0: Int32)) 7. [case (_, 0, _):] ?DagValueTest(t2 == ConstantValueDefault(0: Int32)) 8. [case (_, _, 0):] ?DagValueTest(t3 == ConstantValueDefault(0: Int32)) Test: ?DagValueTest(t1 == ConstantValueDefault(0: Int32)) TrueBranch: 5 FalseBranch: 12 State 5 REMAINING t1:[0..0] 3. [case (_, not 0, 0) when b1:] AND(Not (?DagValueTest(t2 == ConstantValueDefault(0: Int32))), ?DagValueTest(t3 == ConstantValueDefault(0: Int32))) WHEN[b1] 4. [case (0, _, not 0) when b2:] Not (?DagValueTest(t3 == ConstantValueDefault(0: Int32))) WHEN[b2] 5. [case (_, _, _) when b3:] MATCH WHEN[b3] 6. [case (0, _, _):] MATCH Test: ?DagValueTest(t2 == ConstantValueDefault(0: Int32)) TrueBranch: 6 FalseBranch: 7 State 6 REMAINING t1:[0..0] t2:[0..0] 4. [case (0, _, not 0) when b2:] Not (?DagValueTest(t3 == ConstantValueDefault(0: Int32))) WHEN[b2] 5. [case (_, _, _) when b3:] MATCH WHEN[b3] 6. [case (0, _, _):] MATCH Test: ?DagValueTest(t3 == ConstantValueDefault(0: Int32)) TrueBranch: 10 FalseBranch: 9 State 7 REMAINING t1:[0..0] t2:[-2147483648..-1],[1..2147483647] 3. [case (_, not 0, 0) when b1:] ?DagValueTest(t3 == ConstantValueDefault(0: Int32)) WHEN[b1] 4. [case (0, _, not 0) when b2:] Not (?DagValueTest(t3 == ConstantValueDefault(0: Int32))) WHEN[b2] 5. [case (_, _, _) when b3:] MATCH WHEN[b3] 6. [case (0, _, _):] MATCH Test: ?DagValueTest(t3 == ConstantValueDefault(0: Int32)) TrueBranch: 8 FalseBranch: 9 *State 8 REMAINING t3:[0..0] t1:[0..0] t2:[-2147483648..-1],[1..2147483647] 3. [case (_, not 0, 0) when b1:] MATCH WHEN[b1] 5. [case (_, _, _) when b3:] MATCH WHEN[b3] 6. [case (0, _, _):] MATCH FalseBranch: 10 *State 9 REMAINING t3:[-2147483648..-1],[1..2147483647] t1:[0..0] t2:[-2147483648..2147483647] 4. [case (0, _, not 0) when b2:] MATCH WHEN[b2] 5. [case (_, _, _) when b3:] MATCH WHEN[b3] 6. [case (0, _, _):] MATCH FalseBranch: 10 *State 10 REMAINING t3:[-2147483648..2147483647] t1:[0..0] t2:[-2147483648..2147483647] 5. [case (_, _, _) when b3:] MATCH WHEN[b3] 6. [case (0, _, _):] MATCH FalseBranch: 11 *State 11 REMAINING t3:[-2147483648..2147483647] t1:[0..0] t2:[-2147483648..2147483647] 6. [case (0, _, _):] MATCH State 12 REMAINING t1:[-2147483648..-1],[1..2147483647] 2. [case (not 0, 0, _) when b0:] ?DagValueTest(t2 == ConstantValueDefault(0: Int32)) WHEN[b0] 3. [case (_, not 0, 0) when b1:] AND(Not (?DagValueTest(t2 == ConstantValueDefault(0: Int32))), ?DagValueTest(t3 == ConstantValueDefault(0: Int32))) WHEN[b1] 5. [case (_, _, _) when b3:] MATCH WHEN[b3] 7. [case (_, 0, _):] ?DagValueTest(t2 == ConstantValueDefault(0: Int32)) 8. [case (_, _, 0):] ?DagValueTest(t3 == ConstantValueDefault(0: Int32)) Test: ?DagValueTest(t2 == ConstantValueDefault(0: Int32)) TrueBranch: 13 FalseBranch: 16 *State 13 REMAINING t1:[-2147483648..-1],[1..2147483647] t2:[0..0] 2. [case (not 0, 0, _) when b0:] MATCH WHEN[b0] 5. [case (_, _, _) when b3:] MATCH WHEN[b3] 7. [case (_, 0, _):] MATCH FalseBranch: 14 *State 14 REMAINING t1:[-2147483648..-1],[1..2147483647] t2:[0..0] 5. [case (_, _, _) when b3:] MATCH WHEN[b3] 7. [case (_, 0, _):] MATCH FalseBranch: 15 *State 15 REMAINING t1:[-2147483648..-1],[1..2147483647] t2:[0..0] 7. [case (_, 0, _):] MATCH State 16 REMAINING t1:[-2147483648..-1],[1..2147483647] t2:[-2147483648..-1],[1..2147483647] 3. [case (_, not 0, 0) when b1:] ?DagValueTest(t3 == ConstantValueDefault(0: Int32)) WHEN[b1] 5. [case (_, _, _) when b3:] MATCH WHEN[b3] 8. [case (_, _, 0):] ?DagValueTest(t3 == ConstantValueDefault(0: Int32)) Test: ?DagValueTest(t3 == ConstantValueDefault(0: Int32)) TrueBranch: 17 FalseBranch: 20 *State 17 REMAINING t3:[0..0] t1:[-2147483648..-1],[1..2147483647] t2:[-2147483648..-1],[1..2147483647] 3. [case (_, not 0, 0) when b1:] MATCH WHEN[b1] 5. [case (_, _, _) when b3:] MATCH WHEN[b3] 8. [case (_, _, 0):] MATCH FalseBranch: 18 *State 18 REMAINING t3:[0..0] t1:[-2147483648..-1],[1..2147483647] t2:[-2147483648..-1],[1..2147483647] 5. [case (_, _, _) when b3:] MATCH WHEN[b3] 8. [case (_, _, 0):] MATCH FalseBranch: 19 *State 19 REMAINING t3:[0..0] t1:[-2147483648..-1],[1..2147483647] t2:[-2147483648..-1],[1..2147483647] 8. [case (_, _, 0):] MATCH *State 20 REMAINING t3:[-2147483648..-1],[1..2147483647] t1:[-2147483648..-1],[1..2147483647] t2:[-2147483648..-1],[1..2147483647] 5. [case (_, _, _) when b3:] MATCH WHEN[b3] FalseBranch: 21 *State 21 FAIL REMAINING t3:[-2147483648..-1],[1..2147483647] t1:[-2147483648..-1],[1..2147483647] t2:[-2147483648..-1],[1..2147483647]

#Resolved

jcouv · 2021-08-30T16:00:00Z

@dotnet/roslyn-compiler for review. Thanks

cston · 2021-08-30T22:26:04Z

+                        conditionalGoto = _localRewriter._instrumenter.InstrumentSwitchWhenClauseConditionalGotoBody(whenExpression, conditionalGoto);
                    }

                    sectionBuilder.Add(conditionalGoto);


Consider extracting to a local function, for use here and in lowerWhenClause(). #Resolved

I did consider it and was on the fence... Let's see how it looks

cston · 2021-08-30T22:29:16Z

                }
-                else
+
+                bool isSharedWhenExpression(BoundExpression? whenExpression)


static #ByDesign

cston · 2021-08-30T22:39:17Z

+  IL_001c:  ldc.i4.7
+  IL_001d:  stloc.0
+  IL_001e:  ldsfld     ""bool Program.b""
+  IL_0023:  brtrue.s   IL_0077


I'm confused. These statements are repeated below, with what appears to be a dispatch to a single return location after each. Isn't this a case of a when expression where the evaluation should be shared with one dispatch following? #Closed

It seems like the shared dispatch should only occur when a single when clause in source is used in multiple dag nodes. It wasn't clear to me that any of the when clauses in this test are shared between multiple dag nodes.

Here is the bound dag dump:

[0]: t0 is int ? [1] : [13] [1]: t1 = (int)t0; [2] [2]: when (b) ? [12] : [3] [3]: when (b) ? [21] : [4] [4]: when (b) ? [11] : [5] [5]: when (b) ? [20] : [6] [6]: when (b) ? [10] : [7] [7]: when (b) ? [19] : [8] [8]: when (b) ? [9] : [16] [9]: leaf `case int i when b:` [10]: leaf `case int i when b:` [11]: leaf `case int i when b:` [12]: leaf `case int i when b:` [13]: when (b) ? [21] : [14] [14]: when (b) ? [20] : [15] [15]: when (b) ? [19] : [16] [16]: when (b) ? [18] : [17] [17]: leaf <break> `switch (o) { case int i when b: break; case var _ when b: break; case int i when b: break; case var _ when b: break; case int i when b: break; case var _ when b: break; case int i when b: break; case var _ when b: break; }` [18]: leaf `case var _ when b:` [19]: leaf `case var _ when b:` [20]: leaf `case var _ when b:` [21]: leaf `case var _ when b:`

It is a bit hard to distinguish in this format. However, I did not see any of the "tell-tale" groups of when-nodes where the WhenTrue all to the same successor but the WhenFalse go to different places. Therefore it seems like code gen shouldn't really change in this scenario. edit: I spotted them now :) I just needed to look more carefully

cston · 2021-08-30T22:46:40Z

-                Generic<dynamic, System.ValueTuple<int, int>> V_1, //g
-                object V_2,
-                object V_3)
+  // Code size       98 (0x62)


Code size 98 (0x62)

Why did the IL change for this case? M2() doesn't seem to include any shared when clauses. #Resolved

b2 (in second case) is a shared when clause.

cston · 2021-08-30T22:55:43Z

 using Xunit;
 using Roslyn.Test.Utilities;
 using static Microsoft.CodeAnalysis.Test.Utilities.CSharpInstrumentationChecker;
+using System.Reflection.PortableExecutable;


System.Reflection.PortableExecutable

Is this used? #Resolved

RikkiGibson

Looks good, but I was surprised by the baseline change in src/Compilers/CSharp/Test/Emit/CodeGen/SwitchTests.cs and would like to follow up on it before signing off.

RikkiGibson · 2021-08-30T21:23:25Z

                        BoundDecisionDagNode whenTrue = finalState(first.Syntax, first.CaseLabel, default);
                        BoundDecisionDagNode? whenFalse = state.FalseBranch.Dag;
                        RoslynDebug.Assert(whenFalse is { });
+                        // Note: we sharing `when` clauses between multiple DAG nodes, but we deal with that safely during lowering


nit: 'we share' or 'we are sharing' #Resolved

RikkiGibson · 2021-08-30T21:32:05Z

+                //   }
+                //   switch on whenNodeIdentifierLocal with dispatches to whenFalse labels
+
+                // Prepared maps for `when` nodes and expressions


Should we use pooled collections here? #Resolved

RikkiGibson · 2021-08-30T21:33:06Z

+                // for the same `WhenExpression` and such expressions might contains labels which must be emitted once only.
+
+                // For a simple `BoundWhenDecisionDagNode` (with a unique `WhenExpression`), we lower to something like:
+                //   labelToSectionScope;


I'm confused by the semicolon here. Is this meant to be a label declaration? #Resolved

That's correct. After evaluating patterns, we'll jump to the when clause using this label.

RikkiGibson · 2021-08-30T21:36:11Z

                    {
-                        sectionBuilder.Add(_factory.Assignment(left, right));
+                        var whenExpression = whenNode.WhenExpression;
+                        if (whenExpression is not null && whenExpression.ConstantValue != ConstantValue.True)


It wasn't obvious to me why 'ConstantValue.True' is treated differently than other constant-valued when expressions here. #Resolved

I agree, it feels like the optimizer/emitter can handle this and knows about constants in conditional jumps. But that special case existed in the original code (line 896) so I kept it here too.

RikkiGibson · 2021-08-30T22:12:28Z

+                            else
+                            {
+                                labelToWhenExpression = _factory.GenerateLabel("sharedWhenExpression");
+                                var list = new List<BoundWhenDecisionDagNode>();


Should we use pooled collections here? #Resolved

RikkiGibson · 2021-08-30T22:17:08Z

+
+                    var whenClauseSyntax = whenNodes[0].Syntax;
+                    var whenTrueLabel = GetDagNodeLabel(whenNodes[0].WhenTrue);
+                    Debug.Assert(whenNodes.All(n => n.Syntax == whenClauseSyntax));


Consider asserting whenNodes.Count > 1 here. #Resolved

RikkiGibson · 2021-08-30T22:32:33Z

+                    Debug.Assert(whenNodes.All(n => n.Bindings == whenNodes[0].Bindings));
+                    Debug.Assert(whenNodes.All(n => whenTrueLabel == GetDagNodeLabel(whenNodes[0].WhenTrue)));
+
+                    ArrayBuilder<BoundStatement> sectionBuilder = BuilderForSection(whenClauseSyntax);


Should we assert anything about the initial state of this builder?

I'm not sure what you mean

RikkiGibson · 2021-08-30T22:50:12Z

+  IL_001c:  ldc.i4.7
+  IL_001d:  stloc.0
+  IL_001e:  ldsfld     ""bool Program.b""
+  IL_0023:  brtrue.s   IL_0077


It seems like the shared dispatch should only occur when a single when clause in source is used in multiple dag nodes. It wasn't clear to me that any of the when clauses in this test are shared between multiple dag nodes.

Here is the bound dag dump:

[0]: t0 is int ? [1] : [13] [1]: t1 = (int)t0; [2] [2]: when (b) ? [12] : [3] [3]: when (b) ? [21] : [4] [4]: when (b) ? [11] : [5] [5]: when (b) ? [20] : [6] [6]: when (b) ? [10] : [7] [7]: when (b) ? [19] : [8] [8]: when (b) ? [9] : [16] [9]: leaf `case int i when b:` [10]: leaf `case int i when b:` [11]: leaf `case int i when b:` [12]: leaf `case int i when b:` [13]: when (b) ? [21] : [14] [14]: when (b) ? [20] : [15] [15]: when (b) ? [19] : [16] [16]: when (b) ? [18] : [17] [17]: leaf <break> `switch (o) { case int i when b: break; case var _ when b: break; case int i when b: break; case var _ when b: break; case int i when b: break; case var _ when b: break; case int i when b: break; case var _ when b: break; }` [18]: leaf `case var _ when b:` [19]: leaf `case var _ when b:` [20]: leaf `case var _ when b:` [21]: leaf `case var _ when b:`

It is a bit hard to distinguish in this format. However, I did not see any of the "tell-tale" groups of when-nodes where the WhenTrue all to the same successor but the WhenFalse go to different places. Therefore it seems like code gen shouldn't really change in this scenario. edit: I spotted them now :) I just needed to look more carefully

RikkiGibson · 2021-08-30T22:52:07Z

+True
+True
+True
+True


Do you have any tips on how to interpret this baseline to determine whether it is correct? #Resolved

Yes, look at the test TestPatternSpans_WithSharedWhenExpression (linked above). It shows what source code corresponds to each boolean here. We can see which portions of the code were executed.

RikkiGibson · 2021-08-30T22:56:25Z

+        <entry offset=""0x10e"" hidden=""true"" document=""1"" />
+        <entry offset=""0x11f"" hidden=""true"" document=""1"" />
+        <entry offset=""0x12f"" hidden=""true"" document=""1"" />
+        <entry offset=""0x140"" hidden=""true"" document=""1"" />


nit: Please try to match the original indentation of the baselines when possible. #Resolved

Sorry, I didn't notice the indentation change (CodeFlow ignores those by default)

cston · 2021-08-30T23:57:38Z

+                    // We hide the jump back into the decision dag, as it is not logically part of the when clause
+                    sectionBuilder.Add(GenerateInstrumentation ? _factory.HiddenSequencePoint(jumps) : jumps);
+
                }


Trailing blank line. #Resolved

jcouv added Area-Compilers Feature - Pattern Matching Pattern Matching labels Aug 27, 2021

jcouv added this to the 17.0.P4 milestone Aug 27, 2021

jcouv self-assigned this Aug 27, 2021

jcouv force-pushed the bad-switch branch from 3ff1439 to 7d4689e Compare August 27, 2021 23:43

Share 'when' expressions in DAGs when needed

6522476

jcouv force-pushed the bad-switch branch from 11a31cb to 6522476 Compare August 28, 2021 16:37

alrz reviewed Aug 28, 2021

View reviewed changes

jcouv commented Aug 28, 2021

View reviewed changes

Test all permutations

53d8971

jcouv marked this pull request as ready for review August 28, 2021 19:54

jcouv requested a review from a team as a code owner August 28, 2021 19:54

alrz reviewed Aug 29, 2021

View reviewed changes

Comment thread src/Compilers/CSharp/Portable/Lowering/LocalRewriter/LocalRewriter.DecisionDagRewriter.cs Outdated

Julien Couvreur added 2 commits August 29, 2021 08:35

Simple whenTrue jump

f4facfa

refactor

df728bb

runfoapp bot mentioned this pull request Aug 30, 2021

Flaky test: TupleWithElementNamedWithDefaultName #52658

Closed

RikkiGibson self-assigned this Aug 30, 2021