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