mcs/class/dlr/Runtime/Microsoft.Scripting.Core/Compiler/LambdaCompiler.Logical.cs

   1 /* ****************************************************************************
   2  *
   3  * Copyright (c) Microsoft Corporation.
   4  *
   5  * This source code is subject to terms and conditions of the Apache License, Version 2.0. A
   6  * copy of the license can be found in the License.html file at the root of this distribution. If
   7  * you cannot locate the  Apache License, Version 2.0, please send an email to
   8  * dlr@microsoft.com. By using this source code in any fashion, you are agreeing to be bound
   9  * by the terms of the Apache License, Version 2.0.
  10  *
  11  * You must not remove this notice, or any other, from this software.
  12  *
  13  *
  14  * ***************************************************************************/
  15
  16 using System;
  17 using System.Diagnostics;
  18 using System.Dynamic.Utils;
  19 using System.Reflection;
  20 using System.Reflection.Emit;
  21
  22 #if !FEATURE_CORE_DLR
  23 namespace Microsoft.Scripting.Ast.Compiler {
  24 #else
  25 namespace System.Linq.Expressions.Compiler {
  26 #endif
  27
  28     partial class LambdaCompiler {
  29
  30         #region Conditional
  31
  32         private void EmitConditionalExpression(Expression expr, CompilationFlags flags) {
  33             ConditionalExpression node = (ConditionalExpression)expr;
  34             Debug.Assert(node.Test.Type == typeof(bool));
  35             Label labFalse = _ilg.DefineLabel();
  36             EmitExpressionAndBranch(false, node.Test, labFalse);
  37             EmitExpressionAsType(node.IfTrue, node.Type, flags);
  38
  39             if (NotEmpty(node.IfFalse)) {
  40                 Label labEnd = _ilg.DefineLabel();
  41                 if ((flags & CompilationFlags.EmitAsTailCallMask) == CompilationFlags.EmitAsTail) {
  42                     // We know the conditional expression is at the end of the lambda,
  43                     // so it is safe to emit Ret here.
  44                     _ilg.Emit(OpCodes.Ret);
  45                 } else {
  46                     _ilg.Emit(OpCodes.Br, labEnd);
  47                 }
  48                 _ilg.MarkLabel(labFalse);
  49                 EmitExpressionAsType(node.IfFalse, node.Type, flags);
  50                 _ilg.MarkLabel(labEnd);
  51             } else {
  52                 _ilg.MarkLabel(labFalse);
  53             }
  54         }
  55
  56         /// <summary>
  57         /// returns true if the expression is not empty, otherwise false.
  58         /// </summary>
  59         private static bool NotEmpty(Expression node) {
  60             var empty = node as DefaultExpression;
  61             if (empty == null || empty.Type != typeof(void)) {
  62                 return true;
  63             }
  64
  65             return false;
  66         }
  67
  68         /// <summary>
  69         /// returns true if the expression is NOT empty and is not debug info,
  70         /// or a block that contains only insignificant expressions.
  71         /// </summary>
  72         private static bool Significant(Expression node) {
  73             var block = node as BlockExpression;
  74             if (block != null) {
  75                 for (int i = 0; i < block.ExpressionCount; i++) {
  76                     if (Significant(block.GetExpression(i))) {
  77                         return true;
  78                     }
  79                 }
  80                 return false;
  81             }
  82             return NotEmpty(node) && !(node is DebugInfoExpression);
  83         }
  84
  85         #endregion
  86
  87         #region Coalesce
  88
  89
  90         private void EmitCoalesceBinaryExpression(Expression expr) {
  91             BinaryExpression b = (BinaryExpression)expr;
  92             Debug.Assert(b.Method == null);
  93
  94             if (TypeUtils.IsNullableType(b.Left.Type)) {
  95                 EmitNullableCoalesce(b);
  96             } else if (b.Left.Type.IsValueType) {
  97                 throw Error.CoalesceUsedOnNonNullType();
  98             } else if (b.Conversion != null) {
  99                 EmitLambdaReferenceCoalesce(b);
 100             } else {
 101                 EmitReferenceCoalesceWithoutConversion(b);
 102             }
 103         }
 104
 105
 106         private void EmitNullableCoalesce(BinaryExpression b) {
 107             Debug.Assert(b.Method == null);
 108
 109             LocalBuilder loc = GetLocal(b.Left.Type);
 110             Label labIfNull = _ilg.DefineLabel();
 111             Label labEnd = _ilg.DefineLabel();
 112             EmitExpression(b.Left);
 113             _ilg.Emit(OpCodes.Stloc, loc);
 114             _ilg.Emit(OpCodes.Ldloca, loc);
 115             _ilg.EmitHasValue(b.Left.Type);
 116             _ilg.Emit(OpCodes.Brfalse, labIfNull);
 117
 118             Type nnLeftType = TypeUtils.GetNonNullableType(b.Left.Type);
 119             if (b.Conversion != null) {
 120                 Debug.Assert(b.Conversion.Parameters.Count == 1);
 121                 ParameterExpression p = b.Conversion.Parameters[0];
 122                 Debug.Assert(p.Type.IsAssignableFrom(b.Left.Type) ||
 123                              p.Type.IsAssignableFrom(nnLeftType));
 124
 125                 // emit the delegate instance
 126                 EmitLambdaExpression(b.Conversion);
 127
 128                 // emit argument
 129                 if (!p.Type.IsAssignableFrom(b.Left.Type)) {
 130                     _ilg.Emit(OpCodes.Ldloca, loc);
 131                     _ilg.EmitGetValueOrDefault(b.Left.Type);
 132                 } else {
 133                     _ilg.Emit(OpCodes.Ldloc, loc);
 134                 }
 135
 136                 // emit call to invoke
 137                 _ilg.Emit(OpCodes.Callvirt, b.Conversion.Type.GetMethod("Invoke"));
 138             } else if (!TypeUtils.AreEquivalent(b.Type, nnLeftType)) {
 139                 _ilg.Emit(OpCodes.Ldloca, loc);
 140                 _ilg.EmitGetValueOrDefault(b.Left.Type);
 141                 _ilg.EmitConvertToType(nnLeftType, b.Type, true);
 142             } else {
 143                 _ilg.Emit(OpCodes.Ldloca, loc);
 144                 _ilg.EmitGetValueOrDefault(b.Left.Type);
 145             }
 146             FreeLocal(loc);
 147
 148             _ilg.Emit(OpCodes.Br, labEnd);
 149             _ilg.MarkLabel(labIfNull);
 150             EmitExpression(b.Right);
 151             if (!TypeUtils.AreEquivalent(b.Right.Type, b.Type)) {
 152                 _ilg.EmitConvertToType(b.Right.Type, b.Type, true);
 153             }
 154             _ilg.MarkLabel(labEnd);
 155         }
 156
 157
 158         private void EmitLambdaReferenceCoalesce(BinaryExpression b) {
 159             LocalBuilder loc = GetLocal(b.Left.Type);
 160             Label labEnd = _ilg.DefineLabel();
 161             Label labNotNull = _ilg.DefineLabel();
 162             EmitExpression(b.Left);
 163             _ilg.Emit(OpCodes.Dup);
 164             _ilg.Emit(OpCodes.Stloc, loc);
 165             _ilg.Emit(OpCodes.Ldnull);
 166             _ilg.Emit(OpCodes.Ceq);
 167             _ilg.Emit(OpCodes.Brfalse, labNotNull);
 168             EmitExpression(b.Right);
 169             _ilg.Emit(OpCodes.Br, labEnd);
 170
 171             // if not null, call conversion
 172             _ilg.MarkLabel(labNotNull);
 173             Debug.Assert(b.Conversion.Parameters.Count == 1);
 174
 175             // emit the delegate instance
 176             EmitLambdaExpression(b.Conversion);
 177
 178             // emit argument
 179             _ilg.Emit(OpCodes.Ldloc, loc);
 180             FreeLocal(loc);
 181
 182             // emit call to invoke
 183             _ilg.Emit(OpCodes.Callvirt, b.Conversion.Type.GetMethod("Invoke"));
 184
 185             _ilg.MarkLabel(labEnd);
 186         }
 187
 188
 189         private void EmitReferenceCoalesceWithoutConversion(BinaryExpression b) {
 190             Label labEnd = _ilg.DefineLabel();
 191             Label labCast = _ilg.DefineLabel();
 192             EmitExpression(b.Left);
 193             _ilg.Emit(OpCodes.Dup);
 194             _ilg.Emit(OpCodes.Ldnull);
 195             _ilg.Emit(OpCodes.Ceq);
 196             _ilg.Emit(OpCodes.Brfalse, labCast);
 197             _ilg.Emit(OpCodes.Pop);
 198             EmitExpression(b.Right);
 199             if (!TypeUtils.AreEquivalent(b.Right.Type, b.Type)) {
 200                 if (b.Right.Type.IsValueType) {
 201                     _ilg.Emit(OpCodes.Box, b.Right.Type);
 202                 }
 203                 _ilg.Emit(OpCodes.Castclass, b.Type);
 204             }
 205             _ilg.Emit(OpCodes.Br_S, labEnd);
 206             _ilg.MarkLabel(labCast);
 207             if (!TypeUtils.AreEquivalent(b.Left.Type, b.Type)) {
 208                 Debug.Assert(!b.Left.Type.IsValueType);
 209                 _ilg.Emit(OpCodes.Castclass, b.Type);
 210             }
 211             _ilg.MarkLabel(labEnd);
 212         }
 213
 214         #endregion
 215
 216         #region AndAlso
 217
 218         private void EmitLiftedAndAlso(BinaryExpression b) {
 219             Type type = typeof(bool?);
 220             Label labComputeRight = _ilg.DefineLabel();
 221             Label labReturnFalse = _ilg.DefineLabel();
 222             Label labReturnNull = _ilg.DefineLabel();
 223             Label labReturnValue = _ilg.DefineLabel();
 224             Label labExit = _ilg.DefineLabel();
 225             LocalBuilder locLeft = GetLocal(type);
 226             LocalBuilder locRight = GetLocal(type);
 227             EmitExpression(b.Left);
 228             _ilg.Emit(OpCodes.Stloc, locLeft);
 229             _ilg.Emit(OpCodes.Ldloca, locLeft);
 230             _ilg.EmitHasValue(type);
 231             _ilg.Emit(OpCodes.Brfalse, labComputeRight);
 232             _ilg.Emit(OpCodes.Ldloca, locLeft);
 233             _ilg.EmitGetValueOrDefault(type);
 234             _ilg.Emit(OpCodes.Ldc_I4_0);
 235             _ilg.Emit(OpCodes.Ceq);
 236             _ilg.Emit(OpCodes.Brtrue, labReturnFalse);
 237             // compute right
 238             _ilg.MarkLabel(labComputeRight);
 239             EmitExpression(b.Right);
 240             _ilg.Emit(OpCodes.Stloc, locRight);
 241             _ilg.Emit(OpCodes.Ldloca, locRight);
 242             _ilg.EmitHasValue(type);
 243             _ilg.Emit(OpCodes.Brfalse_S, labReturnNull);
 244             _ilg.Emit(OpCodes.Ldloca, locRight);
 245             _ilg.EmitGetValueOrDefault(type);
 246             _ilg.Emit(OpCodes.Ldc_I4_0);
 247             _ilg.Emit(OpCodes.Ceq);
 248             _ilg.Emit(OpCodes.Brtrue_S, labReturnFalse);
 249             // check left for null again
 250             _ilg.Emit(OpCodes.Ldloca, locLeft);
 251             _ilg.EmitHasValue(type);
 252             _ilg.Emit(OpCodes.Brfalse, labReturnNull);
 253             // return true
 254             _ilg.Emit(OpCodes.Ldc_I4_1);
 255             _ilg.Emit(OpCodes.Br_S, labReturnValue);
 256             // return false
 257             _ilg.MarkLabel(labReturnFalse);
 258             _ilg.Emit(OpCodes.Ldc_I4_0);
 259             _ilg.Emit(OpCodes.Br_S, labReturnValue);
 260             _ilg.MarkLabel(labReturnValue);
 261             ConstructorInfo ci = type.GetConstructor(new Type[] { typeof(bool) });
 262             _ilg.Emit(OpCodes.Newobj, ci);
 263             _ilg.Emit(OpCodes.Stloc, locLeft);
 264             _ilg.Emit(OpCodes.Br, labExit);
 265             // return null
 266             _ilg.MarkLabel(labReturnNull);
 267             _ilg.Emit(OpCodes.Ldloca, locLeft);
 268             _ilg.Emit(OpCodes.Initobj, type);
 269             _ilg.MarkLabel(labExit);
 270             _ilg.Emit(OpCodes.Ldloc, locLeft);
 271             FreeLocal(locLeft);
 272             FreeLocal(locRight);
 273         }
 274
 275         private void EmitMethodAndAlso(BinaryExpression b, CompilationFlags flags) {
 276             Label labEnd = _ilg.DefineLabel();
 277             EmitExpression(b.Left);
 278             _ilg.Emit(OpCodes.Dup);
 279             MethodInfo opFalse = TypeUtils.GetBooleanOperator(b.Method.DeclaringType, "op_False");
 280             Debug.Assert(opFalse != null, "factory should check that the method exists");
 281             _ilg.Emit(OpCodes.Call, opFalse);
 282             _ilg.Emit(OpCodes.Brtrue, labEnd);
 283
 284             //store the value of the left value before emitting b.Right to empty the evaluation stack
 285             LocalBuilder locLeft = GetLocal(b.Left.Type);
 286             _ilg.Emit(OpCodes.Stloc, locLeft);
 287
 288             EmitExpression(b.Right);
 289             //store the right value to local
 290             LocalBuilder locRight = GetLocal(b.Right.Type);
 291             _ilg.Emit(OpCodes.Stloc, locRight);
 292
 293             Debug.Assert(b.Method.IsStatic);
 294             _ilg.Emit(OpCodes.Ldloc, locLeft);
 295             _ilg.Emit(OpCodes.Ldloc, locRight);
 296             if ((flags & CompilationFlags.EmitAsTailCallMask) == CompilationFlags.EmitAsTail) {
 297                 _ilg.Emit(OpCodes.Tailcall);
 298             }
 299             _ilg.Emit(OpCodes.Call, b.Method);
 300             FreeLocal(locLeft);
 301             FreeLocal(locRight);
 302             _ilg.MarkLabel(labEnd);
 303         }
 304
 305         private void EmitUnliftedAndAlso(BinaryExpression b) {
 306             Label @else = _ilg.DefineLabel();
 307             Label end = _ilg.DefineLabel();
 308             EmitExpressionAndBranch(false, b.Left, @else);
 309             EmitExpression(b.Right);
 310             _ilg.Emit(OpCodes.Br, end);
 311             _ilg.MarkLabel(@else);
 312             _ilg.Emit(OpCodes.Ldc_I4_0);
 313             _ilg.MarkLabel(end);
 314         }
 315
 316         private void EmitAndAlsoBinaryExpression(Expression expr, CompilationFlags flags) {
 317             BinaryExpression b = (BinaryExpression)expr;
 318
 319             if (b.Method != null && !b.IsLiftedLogical) {
 320                 EmitMethodAndAlso(b, flags);
 321             } else if (b.Left.Type == typeof(bool?)) {
 322                 EmitLiftedAndAlso(b);
 323             } else if (b.IsLiftedLogical) {
 324                 EmitExpression(b.ReduceUserdefinedLifted());
 325             } else {
 326                 EmitUnliftedAndAlso(b);
 327             }
 328         }
 329
 330         #endregion
 331
 332         #region OrElse
 333
 334         private void EmitLiftedOrElse(BinaryExpression b) {
 335             Type type = typeof(bool?);
 336             Label labComputeRight = _ilg.DefineLabel();
 337             Label labReturnTrue = _ilg.DefineLabel();
 338             Label labReturnNull = _ilg.DefineLabel();
 339             Label labReturnValue = _ilg.DefineLabel();
 340             Label labExit = _ilg.DefineLabel();
 341             LocalBuilder locLeft = GetLocal(type);
 342             LocalBuilder locRight = GetLocal(type);
 343             EmitExpression(b.Left);
 344             _ilg.Emit(OpCodes.Stloc, locLeft);
 345             _ilg.Emit(OpCodes.Ldloca, locLeft);
 346             _ilg.EmitHasValue(type);
 347             _ilg.Emit(OpCodes.Brfalse, labComputeRight);
 348             _ilg.Emit(OpCodes.Ldloca, locLeft);
 349             _ilg.EmitGetValueOrDefault(type);
 350             _ilg.Emit(OpCodes.Ldc_I4_0);
 351             _ilg.Emit(OpCodes.Ceq);
 352             _ilg.Emit(OpCodes.Brfalse, labReturnTrue);
 353             // compute right
 354             _ilg.MarkLabel(labComputeRight);
 355             EmitExpression(b.Right);
 356             _ilg.Emit(OpCodes.Stloc, locRight);
 357             _ilg.Emit(OpCodes.Ldloca, locRight);
 358             _ilg.EmitHasValue(type);
 359             _ilg.Emit(OpCodes.Brfalse_S, labReturnNull);
 360             _ilg.Emit(OpCodes.Ldloca, locRight);
 361             _ilg.EmitGetValueOrDefault(type);
 362             _ilg.Emit(OpCodes.Ldc_I4_0);
 363             _ilg.Emit(OpCodes.Ceq);
 364             _ilg.Emit(OpCodes.Brfalse_S, labReturnTrue);
 365             // check left for null again
 366             _ilg.Emit(OpCodes.Ldloca, locLeft);
 367             _ilg.EmitHasValue(type);
 368             _ilg.Emit(OpCodes.Brfalse, labReturnNull);
 369             // return false
 370             _ilg.Emit(OpCodes.Ldc_I4_0);
 371             _ilg.Emit(OpCodes.Br_S, labReturnValue);
 372             // return true
 373             _ilg.MarkLabel(labReturnTrue);
 374             _ilg.Emit(OpCodes.Ldc_I4_1);
 375             _ilg.Emit(OpCodes.Br_S, labReturnValue);
 376             _ilg.MarkLabel(labReturnValue);
 377             ConstructorInfo ci = type.GetConstructor(new Type[] { typeof(bool) });
 378             _ilg.Emit(OpCodes.Newobj, ci);
 379             _ilg.Emit(OpCodes.Stloc, locLeft);
 380             _ilg.Emit(OpCodes.Br, labExit);
 381             // return null
 382             _ilg.MarkLabel(labReturnNull);
 383             _ilg.Emit(OpCodes.Ldloca, locLeft);
 384             _ilg.Emit(OpCodes.Initobj, type);
 385             _ilg.MarkLabel(labExit);
 386             _ilg.Emit(OpCodes.Ldloc, locLeft);
 387             FreeLocal(locLeft);
 388             FreeLocal(locRight);
 389         }
 390
 391         private void EmitUnliftedOrElse(BinaryExpression b) {
 392             Label @else = _ilg.DefineLabel();
 393             Label end = _ilg.DefineLabel();
 394             EmitExpressionAndBranch(false, b.Left, @else);
 395             _ilg.Emit(OpCodes.Ldc_I4_1);
 396             _ilg.Emit(OpCodes.Br, end);
 397             _ilg.MarkLabel(@else);
 398             EmitExpression(b.Right);
 399             _ilg.MarkLabel(end);
 400         }
 401
 402         private void EmitMethodOrElse(BinaryExpression b, CompilationFlags flags) {
 403             Label labEnd = _ilg.DefineLabel();
 404             EmitExpression(b.Left);
 405             _ilg.Emit(OpCodes.Dup);
 406             MethodInfo opTrue = TypeUtils.GetBooleanOperator(b.Method.DeclaringType, "op_True");
 407             Debug.Assert(opTrue != null, "factory should check that the method exists");
 408             _ilg.Emit(OpCodes.Call, opTrue);
 409             _ilg.Emit(OpCodes.Brtrue, labEnd);
 410
 411             //store the value of the left value before emitting b.Right to empty the evaluation stack
 412             LocalBuilder locLeft = GetLocal(b.Left.Type);
 413             _ilg.Emit(OpCodes.Stloc, locLeft);
 414
 415             EmitExpression(b.Right);
 416             //store the right value to local
 417             LocalBuilder locRight = GetLocal(b.Right.Type);
 418             _ilg.Emit(OpCodes.Stloc, locRight);
 419
 420             Debug.Assert(b.Method.IsStatic);
 421             _ilg.Emit(OpCodes.Ldloc, locLeft);
 422             _ilg.Emit(OpCodes.Ldloc, locRight);
 423             if ((flags & CompilationFlags.EmitAsTailCallMask) == CompilationFlags.EmitAsTail) {
 424                 _ilg.Emit(OpCodes.Tailcall);
 425             }
 426             _ilg.Emit(OpCodes.Call, b.Method);
 427             FreeLocal(locLeft);
 428             FreeLocal(locRight);
 429             _ilg.MarkLabel(labEnd);
 430         }
 431
 432         private void EmitOrElseBinaryExpression(Expression expr, CompilationFlags flags) {
 433             BinaryExpression b = (BinaryExpression)expr;
 434
 435             if (b.Method != null && !b.IsLiftedLogical) {
 436                 EmitMethodOrElse(b, flags);
 437             } else if (b.Left.Type == typeof(bool?)) {
 438                 EmitLiftedOrElse(b);
 439             } else if (b.IsLiftedLogical) {
 440                 EmitExpression(b.ReduceUserdefinedLifted());
 441             } else {
 442                 EmitUnliftedOrElse(b);
 443             }
 444         }
 445
 446         #endregion
 447
 448         #region Optimized branching
 449
 450         /// <summary>
 451         /// Emits the expression and then either brtrue/brfalse to the label.
 452         /// </summary>
 453         /// <param name="branchValue">True for brtrue, false for brfalse.</param>
 454         /// <param name="node">The expression to emit.</param>
 455         /// <param name="label">The label to conditionally branch to.</param>
 456         /// <remarks>
 457         /// This function optimizes equality and short circuiting logical
 458         /// operators to avoid double-branching, minimize instruction count,
 459         /// and generate similar IL to the C# compiler. This is important for
 460         /// the JIT to optimize patterns like:
 461         ///     x != null AndAlso x.GetType() == typeof(SomeType)
 462         ///
 463         /// One optimization we don't do: we always emits at least one
 464         /// conditional branch to the label, and always possibly falls through,
 465         /// even if we know if the branch will always succeed or always fail.
 466         /// We do this to avoid generating unreachable code, which is fine for
 467         /// the CLR JIT, but doesn't verify with peverify.
 468         ///
 469         /// This kind of optimization could be implemented safely, by doing
 470         /// constant folding over conditionals and logical expressions at the
 471         /// tree level.
 472         /// </remarks>
 473         [System.Diagnostics.CodeAnalysis.SuppressMessage("Microsoft.Performance", "CA1800:DoNotCastUnnecessarily")]
 474         private void EmitExpressionAndBranch(bool branchValue, Expression node, Label label) {
 475             CompilationFlags startEmitted = EmitExpressionStart(node);
 476             try {
 477                 if (node.Type == typeof(bool)) {
 478                     switch (node.NodeType) {
 479                         case ExpressionType.Not:
 480                             EmitBranchNot(branchValue, (UnaryExpression)node, label);
 481                             return;
 482                         case ExpressionType.AndAlso:
 483                         case ExpressionType.OrElse:
 484                             EmitBranchLogical(branchValue, (BinaryExpression)node, label);
 485                             return;
 486                         case ExpressionType.Block:
 487                             EmitBranchBlock(branchValue, (BlockExpression)node, label);
 488                             return;
 489                         case ExpressionType.Equal:
 490                         case ExpressionType.NotEqual:
 491                             EmitBranchComparison(branchValue, (BinaryExpression)node, label);
 492                             return;
 493                     }
 494                 }
 495                 EmitExpression(node, CompilationFlags.EmitAsNoTail | CompilationFlags.EmitNoExpressionStart);
 496                 EmitBranchOp(branchValue, label);
 497             } finally {
 498                 EmitExpressionEnd(startEmitted);
 499             }
 500         }
 501
 502         private void EmitBranchOp(bool branch, Label label) {
 503             _ilg.Emit(branch ? OpCodes.Brtrue : OpCodes.Brfalse, label);
 504         }
 505
 506         private void EmitBranchNot(bool branch, UnaryExpression node, Label label) {
 507             if (node.Method != null) {
 508                 EmitExpression(node, CompilationFlags.EmitAsNoTail | CompilationFlags.EmitNoExpressionStart);
 509                 EmitBranchOp(branch, label);
 510                 return;
 511             }
 512             EmitExpressionAndBranch(!branch, node.Operand, label);
 513         }
 514
 515         private void EmitBranchComparison(bool branch, BinaryExpression node, Label label) {
 516             Debug.Assert(node.NodeType == ExpressionType.Equal || node.NodeType == ExpressionType.NotEqual);
 517             Debug.Assert(!node.IsLiftedToNull);
 518
 519             // To share code paths, we want to treat NotEqual as an inverted Equal
 520             bool branchWhenEqual = branch == (node.NodeType == ExpressionType.Equal);
 521
 522             if (node.Method != null) {
 523                 EmitBinaryMethod(node, CompilationFlags.EmitAsNoTail);
 524                 // EmitBinaryMethod takes into account the Equal/NotEqual
 525                 // node kind, so use the original branch value
 526                 EmitBranchOp(branch, label);
 527             } else if (ConstantCheck.IsNull(node.Left)) {
 528                 if (TypeUtils.IsNullableType(node.Right.Type)) {
 529                     EmitAddress(node.Right, node.Right.Type);
 530                     _ilg.EmitHasValue(node.Right.Type);
 531                 } else {
 532                     Debug.Assert(!node.Right.Type.IsValueType);
 533                     EmitExpression(GetEqualityOperand(node.Right));
 534                 }
 535                 EmitBranchOp(!branchWhenEqual, label);
 536             } else if (ConstantCheck.IsNull(node.Right)) {
 537                 if (TypeUtils.IsNullableType(node.Left.Type)) {
 538                     EmitAddress(node.Left, node.Left.Type);
 539                     _ilg.EmitHasValue(node.Left.Type);
 540                 } else {
 541                     Debug.Assert(!node.Left.Type.IsValueType);
 542                     EmitExpression(GetEqualityOperand(node.Left));
 543                 }
 544                 EmitBranchOp(!branchWhenEqual, label);
 545             } else if (TypeUtils.IsNullableType(node.Left.Type) || TypeUtils.IsNullableType(node.Right.Type)) {
 546                 EmitBinaryExpression(node);
 547                 // EmitBinaryExpression takes into account the Equal/NotEqual
 548                 // node kind, so use the original branch value
 549                 EmitBranchOp(branch, label);
 550             } else {
 551                 EmitExpression(GetEqualityOperand(node.Left));
 552                 EmitExpression(GetEqualityOperand(node.Right));
 553                 if (branchWhenEqual) {
 554                     _ilg.Emit(OpCodes.Beq, label);
 555                 } else {
 556                     _ilg.Emit(OpCodes.Ceq);
 557                     _ilg.Emit(OpCodes.Brfalse, label);
 558                 }
 559             }
 560         }
 561
 562         // For optimized Equal/NotEqual, we can eliminate reference
 563         // conversions. IL allows comparing managed pointers regardless of
 564         // type. See ECMA-335 "Binary Comparison or Branch Operations", in
 565         // Partition III, Section 1.5 Table 4.
 566         private static Expression GetEqualityOperand(Expression expression) {
 567             if (expression.NodeType == ExpressionType.Convert) {
 568                 var convert = (UnaryExpression)expression;
 569                 if (TypeUtils.AreReferenceAssignable(convert.Type, convert.Operand.Type)) {
 570                     return convert.Operand;
 571                 }
 572             }
 573             return expression;
 574         }
 575
 576         private void EmitBranchLogical(bool branch, BinaryExpression node, Label label) {
 577             Debug.Assert(node.NodeType == ExpressionType.AndAlso || node.NodeType == ExpressionType.OrElse);
 578             Debug.Assert(!node.IsLiftedToNull);
 579
 580             if (node.Method != null || node.IsLifted) {
 581                 EmitExpression(node);
 582                 EmitBranchOp(branch, label);
 583                 return;
 584             }
 585
 586
 587             bool isAnd = node.NodeType == ExpressionType.AndAlso;
 588
 589             // To share code, we make the following substitutions:
 590             //     if (!(left || right)) branch value
 591             // becomes:
 592             //     if (!left && !right) branch value
 593             // and:
 594             //     if (!(left && right)) branch value
 595             // becomes:
 596             //     if (!left || !right) branch value
 597             //
 598             // The observation is that "brtrue(x && y)" has the same codegen as
 599             // "brfalse(x || y)" except the branches have the opposite sign.
 600             // Same for "brfalse(x && y)" and "brtrue(x || y)".
 601             //
 602             if (branch == isAnd) {
 603                 EmitBranchAnd(branch, node, label);
 604             } else {
 605                 EmitBranchOr(branch, node, label);
 606             }
 607         }
 608
 609         // Generates optimized AndAlso with branch == true
 610         // or optimized OrElse with branch == false
 611         private void EmitBranchAnd(bool branch, BinaryExpression node, Label label) {
 612             // if (left) then
 613             //   if (right) branch label
 614             // endif
 615
 616             Label endif = _ilg.DefineLabel();
 617             EmitExpressionAndBranch(!branch, node.Left, endif);
 618             EmitExpressionAndBranch(branch, node.Right, label);
 619             _ilg.MarkLabel(endif);
 620         }
 621
 622         // Generates optimized OrElse with branch == true
 623         // or optimized AndAlso with branch == false
 624         private void EmitBranchOr(bool branch, BinaryExpression node, Label label) {
 625             // if (left OR right) branch label
 626
 627             EmitExpressionAndBranch(branch, node.Left, label);
 628             EmitExpressionAndBranch(branch, node.Right, label);
 629         }
 630
 631         private void EmitBranchBlock(bool branch, BlockExpression node, Label label) {
 632             EnterScope(node);
 633
 634             int count = node.ExpressionCount;
 635             for (int i = 0; i < count - 1; i++) {
 636                 EmitExpressionAsVoid(node.GetExpression(i));
 637             }
 638             EmitExpressionAndBranch(branch, node.GetExpression(count - 1), label);
 639
 640             ExitScope(node);
 641         }
 642
 643         #endregion
 644     }
 645 }