mcs/class/dlr/Runtime/Microsoft.Scripting.Core/Compiler/LambdaCompiler.Expressions.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.Collections.Generic;
  18 using System.Collections.ObjectModel;
  19 using System.Diagnostics;
  20 using System.Dynamic.Utils;
  21 using System.Reflection;
  22 using System.Reflection.Emit;
  23 using System.Runtime.CompilerServices;
  24
  25 #if !FEATURE_CORE_DLR
  26 namespace Microsoft.Scripting.Ast.Compiler {
  27 #else
  28 namespace System.Linq.Expressions.Compiler {
  29 #endif
  30     partial class LambdaCompiler {
  31         [Flags]
  32         internal enum CompilationFlags {
  33             EmitExpressionStart = 0x0001,
  34             EmitNoExpressionStart = 0x0002,
  35             EmitAsDefaultType = 0x0010,
  36             EmitAsVoidType = 0x0020,
  37             EmitAsTail = 0x0100,   // at the tail position of a lambda, tail call can be safely emitted
  38             EmitAsMiddle = 0x0200, // in the middle of a lambda, tail call can be emitted if it is in a return
  39             EmitAsNoTail = 0x0400, // neither at the tail or in a return, or tail call is not turned on, no tail call is emitted
  40
  41             EmitExpressionStartMask = 0x000f,
  42             EmitAsTypeMask = 0x00f0,
  43             EmitAsTailCallMask = 0x0f00
  44         }
  45
  46         /// <summary>
  47         /// Update the flag with a new EmitAsTailCall flag
  48         /// </summary>
  49         private static CompilationFlags UpdateEmitAsTailCallFlag(CompilationFlags flags, CompilationFlags newValue) {
  50             Debug.Assert(newValue == CompilationFlags.EmitAsTail || newValue == CompilationFlags.EmitAsMiddle || newValue == CompilationFlags.EmitAsNoTail);
  51             var oldValue = flags & CompilationFlags.EmitAsTailCallMask;
  52             return flags ^ oldValue | newValue;
  53         }
  54
  55         /// <summary>
  56         /// Update the flag with a new EmitExpressionStart flag
  57         /// </summary>
  58         private static CompilationFlags UpdateEmitExpressionStartFlag(CompilationFlags flags, CompilationFlags newValue) {
  59             Debug.Assert(newValue == CompilationFlags.EmitExpressionStart || newValue == CompilationFlags.EmitNoExpressionStart);
  60             var oldValue = flags & CompilationFlags.EmitExpressionStartMask;
  61             return flags ^ oldValue | newValue;
  62         }
  63
  64         /// <summary>
  65         /// Update the flag with a new EmitAsType flag
  66         /// </summary>
  67         private static CompilationFlags UpdateEmitAsTypeFlag(CompilationFlags flags, CompilationFlags newValue) {
  68             Debug.Assert(newValue == CompilationFlags.EmitAsDefaultType || newValue == CompilationFlags.EmitAsVoidType);
  69             var oldValue = flags & CompilationFlags.EmitAsTypeMask;
  70             return flags ^ oldValue | newValue;
  71         }
  72
  73         /// <summary>
  74         /// Generates code for this expression in a value position.
  75         /// This method will leave the value of the expression
  76         /// on the top of the stack typed as Type.
  77         /// </summary>
  78         internal void EmitExpression(Expression node) {
  79             EmitExpression(node, CompilationFlags.EmitAsNoTail | CompilationFlags.EmitExpressionStart);
  80         }
  81
  82         /// <summary>
  83         /// Emits an expression and discards the result.  For some nodes this emits
  84         /// more optimial code then EmitExpression/Pop
  85         /// </summary>
  86         private void EmitExpressionAsVoid(Expression node) {
  87             EmitExpressionAsVoid(node, CompilationFlags.EmitAsNoTail);
  88         }
  89
  90         private void EmitExpressionAsVoid(Expression node, CompilationFlags flags) {
  91             Debug.Assert(node != null);
  92
  93             CompilationFlags startEmitted = EmitExpressionStart(node);
  94
  95             switch (node.NodeType) {
  96                 case ExpressionType.Assign:
  97                     EmitAssign((BinaryExpression)node, CompilationFlags.EmitAsVoidType);
  98                     break;
  99                 case ExpressionType.Block:
 100                     Emit((BlockExpression)node, UpdateEmitAsTypeFlag(flags, CompilationFlags.EmitAsVoidType));
 101                     break;
 102                 case ExpressionType.Throw:
 103                     EmitThrow((UnaryExpression)node, CompilationFlags.EmitAsVoidType);
 104                     break;
 105                 case ExpressionType.Goto:
 106                     EmitGotoExpression(node, UpdateEmitAsTypeFlag(flags, CompilationFlags.EmitAsVoidType));
 107                     break;
 108                 case ExpressionType.Constant:
 109                 case ExpressionType.Default:
 110                 case ExpressionType.Parameter:
 111                     // no-op
 112                     break;
 113                 default:
 114                     if (node.Type == typeof(void)) {
 115                         EmitExpression(node, UpdateEmitExpressionStartFlag(flags, CompilationFlags.EmitNoExpressionStart));
 116                     } else {
 117                         EmitExpression(node, CompilationFlags.EmitAsNoTail | CompilationFlags.EmitNoExpressionStart);
 118                         _ilg.Emit(OpCodes.Pop);
 119                     }
 120                     break;
 121             }
 122             EmitExpressionEnd(startEmitted);
 123         }
 124
 125         private void EmitExpressionAsType(Expression node, Type type, CompilationFlags flags) {
 126
 127             if (type == typeof(void)) {
 128                 EmitExpressionAsVoid(node, flags);
 129             } else {
 130                 // if the node is emitted as a different type, CastClass IL is emitted at the end,
 131                 // should not emit with tail calls.
 132                 if (!TypeUtils.AreEquivalent(node.Type, type)) {
 133                     EmitExpression(node);
 134                     Debug.Assert(TypeUtils.AreReferenceAssignable(type, node.Type));
 135                     _ilg.Emit(OpCodes.Castclass, type);
 136                 } else {
 137                     // emit the with the flags and emit emit expression start
 138                     EmitExpression(node, UpdateEmitExpressionStartFlag(flags, CompilationFlags.EmitExpressionStart));
 139                 }
 140             }
 141         }
 142
 143         #region label block tracking
 144
 145         private CompilationFlags EmitExpressionStart(Expression node) {
 146             if (TryPushLabelBlock(node)) {
 147                 return CompilationFlags.EmitExpressionStart;
 148             }
 149             return CompilationFlags.EmitNoExpressionStart;
 150         }
 151
 152         private void EmitExpressionEnd(CompilationFlags flags) {
 153             if ((flags & CompilationFlags.EmitExpressionStartMask) == CompilationFlags.EmitExpressionStart) {
 154                 PopLabelBlock(_labelBlock.Kind);
 155             }
 156         }
 157
 158         #endregion
 159
 160         #region InvocationExpression
 161
 162         private void EmitInvocationExpression(Expression expr, CompilationFlags flags) {
 163             InvocationExpression node = (InvocationExpression)expr;
 164
 165             // Optimization: inline code for literal lambda's directly
 166             //
 167             // This is worth it because otherwise we end up with a extra call
 168             // to DynamicMethod.CreateDelegate, which is expensive.
 169             //
 170             if (node.LambdaOperand != null) {
 171                 EmitInlinedInvoke(node, flags);
 172                 return;
 173             }
 174
 175             expr = node.Expression;
 176             if (typeof(LambdaExpression).IsAssignableFrom(expr.Type)) {
 177                 // if the invoke target is a lambda expression tree, first compile it into a delegate
 178                 expr = Expression.Call(expr, expr.Type.GetMethod("Compile", new Type[0]));
 179             }
 180             expr = Expression.Call(expr, expr.Type.GetMethod("Invoke"), node.Arguments);
 181
 182             EmitExpression(expr);
 183         }
 184
 185         private void EmitInlinedInvoke(InvocationExpression invoke, CompilationFlags flags) {
 186             var lambda = invoke.LambdaOperand;
 187
 188             // This is tricky: we need to emit the arguments outside of the
 189             // scope, but set them inside the scope. Fortunately, using the IL
 190             // stack it is entirely doable.
 191
 192             // 1. Emit invoke arguments
 193             List<WriteBack> wb = EmitArguments(lambda.Type.GetMethod("Invoke"), invoke);
 194
 195             // 2. Create the nested LambdaCompiler
 196             var inner = new LambdaCompiler(this, lambda);
 197
 198             // 3. Emit the body
 199             // if the inlined lambda is the last expression of the whole lambda,
 200             // tail call can be applied.
 201             if (wb.Count != 0) {
 202                 flags = UpdateEmitAsTailCallFlag(flags, CompilationFlags.EmitAsNoTail);
 203             }
 204             inner.EmitLambdaBody(_scope, true, flags);
 205
 206             // 4. Emit writebacks if needed
 207             EmitWriteBack(wb);
 208         }
 209
 210         #endregion
 211
 212         #region IndexExpression
 213
 214         private void EmitIndexExpression(Expression expr) {
 215             var node = (IndexExpression)expr;
 216
 217             // Emit instance, if calling an instance method
 218             Type objectType = null;
 219             if (node.Object != null) {
 220                 EmitInstance(node.Object, objectType = node.Object.Type);
 221             }
 222
 223             // Emit indexes. We don't allow byref args, so no need to worry
 224             // about writebacks or EmitAddress
 225             foreach (var arg in node.Arguments) {
 226                 EmitExpression(arg);
 227             }
 228
 229             EmitGetIndexCall(node, objectType);
 230         }
 231
 232         private void EmitIndexAssignment(BinaryExpression node, CompilationFlags flags) {
 233             var index = (IndexExpression)node.Left;
 234
 235             var emitAs = flags & CompilationFlags.EmitAsTypeMask;
 236
 237             // Emit instance, if calling an instance method
 238             Type objectType = null;
 239             if (index.Object != null) {
 240                 EmitInstance(index.Object, objectType = index.Object.Type);
 241             }
 242
 243             // Emit indexes. We don't allow byref args, so no need to worry
 244             // about writebacks or EmitAddress
 245             foreach (var arg in index.Arguments) {
 246                 EmitExpression(arg);
 247             }
 248
 249             // Emit value
 250             EmitExpression(node.Right);
 251
 252             // Save the expression value, if needed
 253             LocalBuilder temp = null;
 254             if (emitAs != CompilationFlags.EmitAsVoidType) {
 255                 _ilg.Emit(OpCodes.Dup);
 256                 _ilg.Emit(OpCodes.Stloc, temp = GetLocal(node.Type));
 257             }
 258
 259             EmitSetIndexCall(index, objectType);
 260
 261             // Restore the value
 262             if (emitAs != CompilationFlags.EmitAsVoidType) {
 263                 _ilg.Emit(OpCodes.Ldloc, temp);
 264                 FreeLocal(temp);
 265             }
 266         }
 267
 268         private void EmitGetIndexCall(IndexExpression node, Type objectType) {
 269             if (node.Indexer != null) {
 270                 // For indexed properties, just call the getter
 271                 var method = node.Indexer.GetGetMethod(true);
 272                 EmitCall(objectType, method);
 273             } else if (node.Arguments.Count != 1) {
 274                 // Multidimensional arrays, call get
 275                 _ilg.Emit(OpCodes.Call, node.Object.Type.GetMethod("Get", BindingFlags.Public | BindingFlags.Instance));
 276             } else {
 277                 // For one dimensional arrays, emit load
 278                 _ilg.EmitLoadElement(node.Type);
 279             }
 280         }
 281
 282         private void EmitSetIndexCall(IndexExpression node, Type objectType) {
 283             if (node.Indexer != null) {
 284                 // For indexed properties, just call the setter
 285                 var method = node.Indexer.GetSetMethod(true);
 286                 EmitCall(objectType, method);
 287             } else if (node.Arguments.Count != 1) {
 288                 // Multidimensional arrays, call set
 289                 _ilg.Emit(OpCodes.Call, node.Object.Type.GetMethod("Set", BindingFlags.Public | BindingFlags.Instance));
 290             } else {
 291                 // For one dimensional arrays, emit store
 292                 _ilg.EmitStoreElement(node.Type);
 293             }
 294         }
 295
 296         #endregion
 297
 298         #region MethodCallExpression
 299
 300         private void EmitMethodCallExpression(Expression expr, CompilationFlags flags) {
 301             MethodCallExpression node = (MethodCallExpression)expr;
 302
 303             EmitMethodCall(node.Object, node.Method, node, flags);
 304         }
 305
 306         private void EmitMethodCallExpression(Expression expr) {
 307             EmitMethodCallExpression(expr, CompilationFlags.EmitAsNoTail);
 308         }
 309
 310         private void EmitMethodCall(Expression obj, MethodInfo method, IArgumentProvider methodCallExpr) {
 311             EmitMethodCall(obj, method, methodCallExpr, CompilationFlags.EmitAsNoTail);
 312         }
 313
 314         private void EmitMethodCall(Expression obj, MethodInfo method, IArgumentProvider methodCallExpr, CompilationFlags flags) {
 315             // Emit instance, if calling an instance method
 316             Type objectType = null;
 317             if (!method.IsStatic) {
 318                 EmitInstance(obj, objectType = obj.Type);
 319             }
 320             // if the obj has a value type, its address is passed to the method call so we cannot destroy the
 321             // stack by emitting a tail call
 322             if (obj != null && obj.Type.IsValueType) {
 323                 EmitMethodCall(method, methodCallExpr, objectType);
 324             } else {
 325                 EmitMethodCall(method, methodCallExpr, objectType, flags);
 326             }
 327         }
 328
 329         // assumes 'object' of non-static call is already on stack
 330         private void EmitMethodCall(MethodInfo mi, IArgumentProvider args, Type objectType) {
 331             EmitMethodCall(mi, args, objectType, CompilationFlags.EmitAsNoTail);
 332         }
 333
 334         // assumes 'object' of non-static call is already on stack
 335         private void EmitMethodCall(MethodInfo mi, IArgumentProvider args, Type objectType, CompilationFlags flags) {
 336
 337             // Emit arguments
 338             List<WriteBack> wb = EmitArguments(mi, args);
 339
 340             // Emit the actual call
 341             OpCode callOp = UseVirtual(mi) ? OpCodes.Callvirt : OpCodes.Call;
 342             if (callOp == OpCodes.Callvirt && objectType.IsValueType) {
 343                 // This automatically boxes value types if necessary.
 344                 _ilg.Emit(OpCodes.Constrained, objectType);
 345             }
 346             // The method call can be a tail call if
 347             // 1) the method call is the last instruction before Ret
 348             // 2) the method does not have any ByRef parameters, refer to ECMA-335 Partition III Section 2.4.
 349             //    "Verification requires that no managed pointers are passed to the method being called, since
 350             //    it does not track pointers into the current frame."
 351             if ((flags & CompilationFlags.EmitAsTailCallMask) == CompilationFlags.EmitAsTail && !MethodHasByRefParameter(mi)) {
 352                 _ilg.Emit(OpCodes.Tailcall);
 353             }
 354             if (mi.CallingConvention == CallingConventions.VarArgs) {
 355                 _ilg.EmitCall(callOp, mi, args.Map(a => a.Type));
 356             } else {
 357                 _ilg.Emit(callOp, mi);
 358             }
 359
 360             // Emit writebacks for properties passed as "ref" arguments
 361             EmitWriteBack(wb);
 362         }
 363
 364         private static bool MethodHasByRefParameter(MethodInfo mi) {
 365             foreach (var pi in mi.GetParametersCached()) {
 366                 if (pi.IsByRefParameter()) {
 367                     return true;
 368                 }
 369             }
 370             return false;
 371         }
 372
 373         private void EmitCall(Type objectType, MethodInfo method) {
 374             if (method.CallingConvention == CallingConventions.VarArgs) {
 375                 throw Error.UnexpectedVarArgsCall(method);
 376             }
 377
 378             OpCode callOp = UseVirtual(method) ? OpCodes.Callvirt : OpCodes.Call;
 379             if (callOp == OpCodes.Callvirt && objectType.IsValueType) {
 380                 _ilg.Emit(OpCodes.Constrained, objectType);
 381             }
 382             _ilg.Emit(callOp, method);
 383         }
 384
 385         private static bool UseVirtual(MethodInfo mi) {
 386             // There are two factors: is the method static, virtual or non-virtual instance?
 387             // And is the object ref or value?
 388             // The cases are:
 389             //
 390             // static, ref:     call
 391             // static, value:   call
 392             // virtual, ref:    callvirt
 393             // virtual, value:  call -- eg, double.ToString must be a non-virtual call to be verifiable.
 394             // instance, ref:   callvirt -- this looks wrong, but is verifiable and gives us a free null check.
 395             // instance, value: call
 396             //
 397             // We never need to generate a nonvirtual call to a virtual method on a reference type because
 398             // expression trees do not support "base.Foo()" style calling.
 399             //
 400             // We could do an optimization here for the case where we know that the object is a non-null
 401             // reference type and the method is a non-virtual instance method.  For example, if we had
 402             // (new Foo()).Bar() for instance method Bar we don't need the null check so we could do a
 403             // call rather than a callvirt.  However that seems like it would not be a very big win for
 404             // most dynamically generated code scenarios, so let's not do that for now.
 405
 406             if (mi.IsStatic) {
 407                 return false;
 408             }
 409             if (mi.DeclaringType.IsValueType) {
 410                 return false;
 411             }
 412             return true;
 413         }
 414
 415         /// <summary>
 416         /// Emits arguments to a call, and returns an array of writebacks that
 417         /// should happen after the call.
 418         /// </summary>
 419         private List<WriteBack> EmitArguments(MethodBase method, IArgumentProvider args) {
 420             return EmitArguments(method, args, 0);
 421         }
 422
 423         /// <summary>
 424         /// Emits arguments to a call, and returns an array of writebacks that
 425         /// should happen after the call. For emitting dynamic expressions, we
 426         /// need to skip the first parameter of the method (the call site).
 427         /// </summary>
 428         private List<WriteBack> EmitArguments(MethodBase method, IArgumentProvider args, int skipParameters) {
 429             ParameterInfo[] pis = method.GetParametersCached();
 430             Debug.Assert(args.ArgumentCount + skipParameters == pis.Length);
 431
 432             var writeBacks = new List<WriteBack>();
 433             for (int i = skipParameters, n = pis.Length; i < n; i++) {
 434                 ParameterInfo parameter = pis[i];
 435                 Expression argument = args.GetArgument(i - skipParameters);
 436                 Type type = parameter.ParameterType;
 437
 438                 if (type.IsByRef) {
 439                     type = type.GetElementType();
 440
 441                     WriteBack wb = EmitAddressWriteBack(argument, type);
 442                     if (wb != null) {
 443                         writeBacks.Add(wb);
 444                     }
 445                 } else {
 446                     EmitExpression(argument);
 447                 }
 448             }
 449             return writeBacks;
 450         }
 451
 452         private static void EmitWriteBack(IList<WriteBack> writeBacks) {
 453             foreach (WriteBack wb in writeBacks) {
 454                 wb();
 455             }
 456         }
 457
 458         #endregion
 459
 460         private void EmitConstantExpression(Expression expr) {
 461             ConstantExpression node = (ConstantExpression)expr;
 462
 463             EmitConstant(node.Value, node.Type);
 464         }
 465
 466         private void EmitConstant(object value, Type type) {
 467             // Try to emit the constant directly into IL
 468             if (ILGen.CanEmitConstant(value, type)) {
 469                 _ilg.EmitConstant(value, type);
 470                 return;
 471             }
 472
 473             _boundConstants.EmitConstant(this, value, type);
 474         }
 475
 476         private void EmitDynamicExpression(Expression expr) {
 477             if (!(_method is DynamicMethod)) {
 478                 throw Error.CannotCompileDynamic();
 479             }
 480
 481             var node = (DynamicExpression)expr;
 482
 483             var site = CallSite.Create(node.DelegateType, node.Binder);
 484             Type siteType = site.GetType();
 485
 486             var invoke = node.DelegateType.GetMethod("Invoke");
 487
 488             // site.Target.Invoke(site, args)
 489             EmitConstant(site, siteType);
 490
 491             // Emit the temp as type CallSite so we get more reuse
 492             _ilg.Emit(OpCodes.Dup);
 493 #if !FEATURE_CORE_DLR
 494             // For 3.5, emit the temp as CallSite<T> to work around a Jit32
 495             // verifier issue (fixed in 3.5 sp1)
 496             var siteTemp = GetLocal(siteType);
 497 #else
 498             var siteTemp = GetLocal(typeof(CallSite));
 499 #endif
 500             _ilg.Emit(OpCodes.Stloc, siteTemp);
 501             _ilg.Emit(OpCodes.Ldfld, siteType.GetField("Target"));
 502             _ilg.Emit(OpCodes.Ldloc, siteTemp);
 503             FreeLocal(siteTemp);
 504
 505             List<WriteBack> wb = EmitArguments(invoke, node, 1);
 506             _ilg.Emit(OpCodes.Callvirt, invoke);
 507             EmitWriteBack(wb);
 508         }
 509
 510         private void EmitNewExpression(Expression expr) {
 511             NewExpression node = (NewExpression)expr;
 512
 513             if (node.Constructor != null) {
 514                 List<WriteBack> wb = EmitArguments(node.Constructor, node);
 515                 _ilg.Emit(OpCodes.Newobj, node.Constructor);
 516                 EmitWriteBack(wb);
 517             } else {
 518                 Debug.Assert(node.Arguments.Count == 0, "Node with arguments must have a constructor.");
 519                 Debug.Assert(node.Type.IsValueType, "Only value type may have constructor not set.");
 520                 LocalBuilder temp = GetLocal(node.Type);
 521                 _ilg.Emit(OpCodes.Ldloca, temp);
 522                 _ilg.Emit(OpCodes.Initobj, node.Type);
 523                 _ilg.Emit(OpCodes.Ldloc, temp);
 524                 FreeLocal(temp);
 525             }
 526         }
 527
 528         private void EmitTypeBinaryExpression(Expression expr) {
 529             TypeBinaryExpression node = (TypeBinaryExpression)expr;
 530
 531             if (node.NodeType == ExpressionType.TypeEqual) {
 532                 EmitExpression(node.ReduceTypeEqual());
 533                 return;
 534             }
 535
 536             Type type = node.Expression.Type;
 537
 538             // Try to determine the result statically
 539             AnalyzeTypeIsResult result = ConstantCheck.AnalyzeTypeIs(node);
 540
 541             if (result == AnalyzeTypeIsResult.KnownTrue ||
 542                 result == AnalyzeTypeIsResult.KnownFalse) {
 543                 // Result is known statically, so just emit the expression for
 544                 // its side effects and return the result
 545                 EmitExpressionAsVoid(node.Expression);
 546                 _ilg.EmitBoolean(result == AnalyzeTypeIsResult.KnownTrue);
 547                 return;
 548             }
 549
 550             if (result == AnalyzeTypeIsResult.KnownAssignable) {
 551                 // We know the type can be assigned, but still need to check
 552                 // for null at runtime
 553                 if (type.IsNullableType()) {
 554                     EmitAddress(node.Expression, type);
 555                     _ilg.EmitHasValue(type);
 556                     return;
 557                 }
 558
 559                 Debug.Assert(!type.IsValueType);
 560                 EmitExpression(node.Expression);
 561                 _ilg.Emit(OpCodes.Ldnull);
 562                 _ilg.Emit(OpCodes.Ceq);
 563                 _ilg.Emit(OpCodes.Ldc_I4_0);
 564                 _ilg.Emit(OpCodes.Ceq);
 565                 return;
 566             }
 567
 568             Debug.Assert(result == AnalyzeTypeIsResult.Unknown);
 569
 570             // Emit a full runtime "isinst" check
 571             EmitExpression(node.Expression);
 572             if (type.IsValueType) {
 573                 _ilg.Emit(OpCodes.Box, type);
 574             }
 575             _ilg.Emit(OpCodes.Isinst, node.TypeOperand);
 576             _ilg.Emit(OpCodes.Ldnull);
 577             _ilg.Emit(OpCodes.Cgt_Un);
 578         }
 579
 580         private void EmitVariableAssignment(BinaryExpression node, CompilationFlags flags) {
 581             var variable = (ParameterExpression)node.Left;
 582             var emitAs = flags & CompilationFlags.EmitAsTypeMask;
 583
 584             EmitExpression(node.Right);
 585             if (emitAs != CompilationFlags.EmitAsVoidType) {
 586                 _ilg.Emit(OpCodes.Dup);
 587             }
 588
 589             if (variable.IsByRef) {
 590                 // Note: the stloc/ldloc pattern is a bit suboptimal, but it
 591                 // saves us from having to spill stack when assigning to a
 592                 // byref parameter. We already make this same tradeoff for
 593                 // hoisted variables, see ElementStorage.EmitStore
 594
 595                 LocalBuilder value = GetLocal(variable.Type);
 596                 _ilg.Emit(OpCodes.Stloc, value);
 597                 _scope.EmitGet(variable);
 598                 _ilg.Emit(OpCodes.Ldloc, value);
 599                 FreeLocal(value);
 600                 _ilg.EmitStoreValueIndirect(variable.Type);
 601             } else {
 602                 _scope.EmitSet(variable);
 603             }
 604         }
 605
 606         private void EmitAssignBinaryExpression(Expression expr) {
 607             EmitAssign((BinaryExpression)expr, CompilationFlags.EmitAsDefaultType);
 608         }
 609
 610         private void EmitAssign(BinaryExpression node, CompilationFlags emitAs) {
 611             switch (node.Left.NodeType) {
 612                 case ExpressionType.Index:
 613                     EmitIndexAssignment(node, emitAs);
 614                     return;
 615                 case ExpressionType.MemberAccess:
 616                     EmitMemberAssignment(node, emitAs);
 617                     return;
 618                 case ExpressionType.Parameter:
 619                     EmitVariableAssignment(node, emitAs);
 620                     return;
 621                 default:
 622                     throw Error.InvalidLvalue(node.Left.NodeType);
 623             }
 624         }
 625
 626         private void EmitParameterExpression(Expression expr) {
 627             ParameterExpression node = (ParameterExpression)expr;
 628             _scope.EmitGet(node);
 629             if (node.IsByRef) {
 630                 _ilg.EmitLoadValueIndirect(node.Type);
 631             }
 632         }
 633
 634         private void EmitLambdaExpression(Expression expr) {
 635             LambdaExpression node = (LambdaExpression)expr;
 636             EmitDelegateConstruction(node);
 637         }
 638
 639         private void EmitRuntimeVariablesExpression(Expression expr) {
 640             RuntimeVariablesExpression node = (RuntimeVariablesExpression)expr;
 641             _scope.EmitVariableAccess(this, node.Variables);
 642         }
 643
 644         private void EmitMemberAssignment(BinaryExpression node, CompilationFlags flags) {
 645             MemberExpression lvalue = (MemberExpression)node.Left;
 646             MemberInfo member = lvalue.Member;
 647
 648             // emit "this", if any
 649             Type objectType = null;
 650             if (lvalue.Expression != null) {
 651                 EmitInstance(lvalue.Expression, objectType = lvalue.Expression.Type);
 652             }
 653
 654             // emit value
 655             EmitExpression(node.Right);
 656
 657             LocalBuilder temp = null;
 658             var emitAs = flags & CompilationFlags.EmitAsTypeMask;
 659             if (emitAs != CompilationFlags.EmitAsVoidType) {
 660                 // save the value so we can return it
 661                 _ilg.Emit(OpCodes.Dup);
 662                 _ilg.Emit(OpCodes.Stloc, temp = GetLocal(node.Type));
 663             }
 664
 665             switch (member.MemberType) {
 666                 case MemberTypes.Field:
 667                     _ilg.EmitFieldSet((FieldInfo)member);
 668                     break;
 669                 case MemberTypes.Property:
 670                     EmitCall(objectType, ((PropertyInfo)member).GetSetMethod(true));
 671                     break;
 672                 default:
 673                     throw Error.InvalidMemberType(member.MemberType);
 674             }
 675
 676             if (emitAs != CompilationFlags.EmitAsVoidType) {
 677                 _ilg.Emit(OpCodes.Ldloc, temp);
 678                 FreeLocal(temp);
 679             }
 680         }
 681
 682         private void EmitMemberExpression(Expression expr) {
 683             MemberExpression node = (MemberExpression)expr;
 684
 685             // emit "this", if any
 686             Type instanceType = null;
 687             if (node.Expression != null) {
 688                 EmitInstance(node.Expression, instanceType = node.Expression.Type);
 689             }
 690
 691             EmitMemberGet(node.Member, instanceType);
 692         }
 693
 694         // assumes instance is already on the stack
 695         private void EmitMemberGet(MemberInfo member, Type objectType) {
 696             switch (member.MemberType) {
 697                 case MemberTypes.Field:
 698                     FieldInfo fi = (FieldInfo)member;
 699                     if (fi.IsLiteral) {
 700                         EmitConstant(fi.GetRawConstantValue(), fi.FieldType);
 701                     } else {
 702                         _ilg.EmitFieldGet(fi);
 703                     }
 704                     break;
 705                 case MemberTypes.Property:
 706                     EmitCall(objectType, ((PropertyInfo)member).GetGetMethod(true));
 707                     break;
 708                 default:
 709                     throw ContractUtils.Unreachable;
 710             }
 711         }
 712
 713         private void EmitInstance(Expression instance, Type type) {
 714             if (instance != null) {
 715                 if (type.IsValueType) {
 716                     EmitAddress(instance, type);
 717                 } else {
 718                     EmitExpression(instance);
 719                 }
 720             }
 721         }
 722
 723         private void EmitNewArrayExpression(Expression expr) {
 724             NewArrayExpression node = (NewArrayExpression)expr;
 725
 726             if (node.NodeType == ExpressionType.NewArrayInit) {
 727                 _ilg.EmitArray(
 728                     node.Type.GetElementType(),
 729                     node.Expressions.Count,
 730                     delegate(int index) {
 731                         EmitExpression(node.Expressions[index]);
 732                     }
 733                 );
 734             } else {
 735                 ReadOnlyCollection<Expression> bounds = node.Expressions;
 736                 for (int i = 0; i < bounds.Count; i++) {
 737                     Expression x = bounds[i];
 738                     EmitExpression(x);
 739                     _ilg.EmitConvertToType(x.Type, typeof(int), true);
 740                 }
 741                 _ilg.EmitArray(node.Type);
 742             }
 743         }
 744
 745         private void EmitDebugInfoExpression(Expression expr) {
 746             if (!EmitDebugSymbols) {
 747                 return;
 748             }
 749             var node = (DebugInfoExpression)expr;
 750
 751             if (node.IsClear && _sequencePointCleared) {
 752                 // Emitting another clearance after one clearance does not
 753                 // have any effect, so we can save it.
 754                 return;
 755             }
 756
 757             _tree.DebugInfoGenerator.MarkSequencePoint(_lambda, _method, _ilg, node);
 758             _ilg.Emit(OpCodes.Nop);
 759             _sequencePointCleared = node.IsClear;
 760         }
 761
 762         [System.Diagnostics.CodeAnalysis.SuppressMessage("Microsoft.Usage", "CA1801:ReviewUnusedParameters", MessageId = "expr")]
 763         private static void EmitExtensionExpression(Expression expr) {
 764             throw Error.ExtensionNotReduced();
 765         }
 766
 767         #region ListInit, MemberInit
 768
 769         private void EmitListInitExpression(Expression expr) {
 770             EmitListInit((ListInitExpression)expr);
 771         }
 772
 773         private void EmitMemberInitExpression(Expression expr) {
 774             EmitMemberInit((MemberInitExpression)expr);
 775         }
 776
 777         private void EmitBinding(MemberBinding binding, Type objectType) {
 778             switch (binding.BindingType) {
 779                 case MemberBindingType.Assignment:
 780                     EmitMemberAssignment((MemberAssignment)binding, objectType);
 781                     break;
 782                 case MemberBindingType.ListBinding:
 783                     EmitMemberListBinding((MemberListBinding)binding);
 784                     break;
 785                 case MemberBindingType.MemberBinding:
 786                     EmitMemberMemberBinding((MemberMemberBinding)binding);
 787                     break;
 788                 default:
 789                     throw Error.UnknownBindingType();
 790             }
 791         }
 792
 793         private void EmitMemberAssignment(MemberAssignment binding, Type objectType) {
 794             EmitExpression(binding.Expression);
 795             FieldInfo fi = binding.Member as FieldInfo;
 796             if (fi != null) {
 797                 _ilg.Emit(OpCodes.Stfld, fi);
 798             } else {
 799                 PropertyInfo pi = binding.Member as PropertyInfo;
 800                 if (pi != null) {
 801                     EmitCall(objectType, pi.GetSetMethod(true));
 802                 } else {
 803                     throw Error.UnhandledBinding();
 804                 }
 805             }
 806         }
 807
 808         private void EmitMemberMemberBinding(MemberMemberBinding binding) {
 809             Type type = GetMemberType(binding.Member);
 810             if (binding.Member is PropertyInfo && type.IsValueType) {
 811                 throw Error.CannotAutoInitializeValueTypeMemberThroughProperty(binding.Member);
 812             }
 813             if (type.IsValueType) {
 814                 EmitMemberAddress(binding.Member, binding.Member.DeclaringType);
 815             } else {
 816                 EmitMemberGet(binding.Member, binding.Member.DeclaringType);
 817             }
 818             EmitMemberInit(binding.Bindings, false, type);
 819         }
 820
 821         private void EmitMemberListBinding(MemberListBinding binding) {
 822             Type type = GetMemberType(binding.Member);
 823             if (binding.Member is PropertyInfo && type.IsValueType) {
 824                 throw Error.CannotAutoInitializeValueTypeElementThroughProperty(binding.Member);
 825             }
 826             if (type.IsValueType) {
 827                 EmitMemberAddress(binding.Member, binding.Member.DeclaringType);
 828             } else {
 829                 EmitMemberGet(binding.Member, binding.Member.DeclaringType);
 830             }
 831             EmitListInit(binding.Initializers, false, type);
 832         }
 833
 834         private void EmitMemberInit(MemberInitExpression init) {
 835             EmitExpression(init.NewExpression);
 836             LocalBuilder loc = null;
 837             if (init.NewExpression.Type.IsValueType && init.Bindings.Count > 0) {
 838                 loc = _ilg.DeclareLocal(init.NewExpression.Type);
 839                 _ilg.Emit(OpCodes.Stloc, loc);
 840                 _ilg.Emit(OpCodes.Ldloca, loc);
 841             }
 842             EmitMemberInit(init.Bindings, loc == null, init.NewExpression.Type);
 843             if (loc != null) {
 844                 _ilg.Emit(OpCodes.Ldloc, loc);
 845             }
 846         }
 847
 848         // This method assumes that the instance is on the stack and is expected, based on "keepOnStack" flag
 849         // to either leave the instance on the stack, or pop it.
 850         private void EmitMemberInit(ReadOnlyCollection<MemberBinding> bindings, bool keepOnStack, Type objectType) {
 851             int n = bindings.Count;
 852             if (n == 0) {
 853                 // If there are no initializers and instance is not to be kept on the stack, we must pop explicitly.
 854                 if (!keepOnStack) {
 855                     _ilg.Emit(OpCodes.Pop);
 856                 }
 857             } else {
 858                 for (int i = 0; i < n; i++) {
 859                     if (keepOnStack || i < n - 1) {
 860                         _ilg.Emit(OpCodes.Dup);
 861                     }
 862                     EmitBinding(bindings[i], objectType);
 863                 }
 864             }
 865         }
 866
 867         private void EmitListInit(ListInitExpression init) {
 868             EmitExpression(init.NewExpression);
 869             LocalBuilder loc = null;
 870             if (init.NewExpression.Type.IsValueType) {
 871                 loc = _ilg.DeclareLocal(init.NewExpression.Type);
 872                 _ilg.Emit(OpCodes.Stloc, loc);
 873                 _ilg.Emit(OpCodes.Ldloca, loc);
 874             }
 875             EmitListInit(init.Initializers, loc == null, init.NewExpression.Type);
 876             if (loc != null) {
 877                 _ilg.Emit(OpCodes.Ldloc, loc);
 878             }
 879         }
 880
 881         // This method assumes that the list instance is on the stack and is expected, based on "keepOnStack" flag
 882         // to either leave the list instance on the stack, or pop it.
 883         private void EmitListInit(ReadOnlyCollection<ElementInit> initializers, bool keepOnStack, Type objectType) {
 884             int n = initializers.Count;
 885
 886             if (n == 0) {
 887                 // If there are no initializers and instance is not to be kept on the stack, we must pop explicitly.
 888                 if (!keepOnStack) {
 889                     _ilg.Emit(OpCodes.Pop);
 890                 }
 891             } else {
 892                 for (int i = 0; i < n; i++) {
 893                     if (keepOnStack || i < n - 1) {
 894                         _ilg.Emit(OpCodes.Dup);
 895                     }
 896                     EmitMethodCall(initializers[i].AddMethod, initializers[i], objectType);
 897
 898                     // Aome add methods, ArrayList.Add for example, return non-void
 899                     if (initializers[i].AddMethod.ReturnType != typeof(void)) {
 900                         _ilg.Emit(OpCodes.Pop);
 901                     }
 902                 }
 903             }
 904         }
 905
 906         private static Type GetMemberType(MemberInfo member) {
 907             FieldInfo fi = member as FieldInfo;
 908             if (fi != null) return fi.FieldType;
 909             PropertyInfo pi = member as PropertyInfo;
 910             if (pi != null) return pi.PropertyType;
 911             throw Error.MemberNotFieldOrProperty(member);
 912         }
 913
 914         #endregion
 915
 916         #region Expression helpers
 917
 918         internal static void ValidateLift(IList<ParameterExpression> variables, IList<Expression> arguments) {
 919             System.Diagnostics.Debug.Assert(variables != null);
 920             System.Diagnostics.Debug.Assert(arguments != null);
 921
 922             if (variables.Count != arguments.Count) {
 923                 throw Error.IncorrectNumberOfIndexes();
 924             }
 925             for (int i = 0, n = variables.Count; i < n; i++) {
 926                 if (!TypeUtils.AreReferenceAssignable(variables[i].Type, TypeUtils.GetNonNullableType(arguments[i].Type))) {
 927                     throw Error.ArgumentTypesMustMatch();
 928                 }
 929             }
 930         }
 931
 932         [System.Diagnostics.CodeAnalysis.SuppressMessage("Microsoft.Maintainability", "CA1502:AvoidExcessiveComplexity")]
 933         private void EmitLift(ExpressionType nodeType, Type resultType, MethodCallExpression mc, ParameterExpression[] paramList, Expression[] argList) {
 934             Debug.Assert(TypeUtils.AreEquivalent(TypeUtils.GetNonNullableType(resultType), TypeUtils.GetNonNullableType(mc.Type)));
 935
 936             switch (nodeType) {
 937                 default:
 938                 case ExpressionType.LessThan:
 939                 case ExpressionType.LessThanOrEqual:
 940                 case ExpressionType.GreaterThan:
 941                 case ExpressionType.GreaterThanOrEqual: {
 942                         Label exit = _ilg.DefineLabel();
 943                         Label exitNull = _ilg.DefineLabel();
 944                         LocalBuilder anyNull = _ilg.DeclareLocal(typeof(bool));
 945                         for (int i = 0, n = paramList.Length; i < n; i++) {
 946                             ParameterExpression v = paramList[i];
 947                             Expression arg = argList[i];
 948                             if (TypeUtils.IsNullableType(arg.Type)) {
 949                                 _scope.AddLocal(this, v);
 950                                 EmitAddress(arg, arg.Type);
 951                                 _ilg.Emit(OpCodes.Dup);
 952                                 _ilg.EmitHasValue(arg.Type);
 953                                 _ilg.Emit(OpCodes.Ldc_I4_0);
 954                                 _ilg.Emit(OpCodes.Ceq);
 955                                 _ilg.Emit(OpCodes.Stloc, anyNull);
 956                                 _ilg.EmitGetValueOrDefault(arg.Type);
 957                                 _scope.EmitSet(v);
 958                             } else {
 959                                 _scope.AddLocal(this, v);
 960                                 EmitExpression(arg);
 961                                 if (!arg.Type.IsValueType) {
 962                                     _ilg.Emit(OpCodes.Dup);
 963                                     _ilg.Emit(OpCodes.Ldnull);
 964                                     _ilg.Emit(OpCodes.Ceq);
 965                                     _ilg.Emit(OpCodes.Stloc, anyNull);
 966                                 }
 967                                 _scope.EmitSet(v);
 968                             }
 969                             _ilg.Emit(OpCodes.Ldloc, anyNull);
 970                             _ilg.Emit(OpCodes.Brtrue, exitNull);
 971                         }
 972                         EmitMethodCallExpression(mc);
 973                         if (TypeUtils.IsNullableType(resultType) && !TypeUtils.AreEquivalent(resultType, mc.Type)) {
 974                             ConstructorInfo ci = resultType.GetConstructor(new Type[] { mc.Type });
 975                             _ilg.Emit(OpCodes.Newobj, ci);
 976                         }
 977                         _ilg.Emit(OpCodes.Br_S, exit);
 978                         _ilg.MarkLabel(exitNull);
 979                         if (TypeUtils.AreEquivalent(resultType, TypeUtils.GetNullableType(mc.Type))) {
 980                             if (resultType.IsValueType) {
 981                                 LocalBuilder result = GetLocal(resultType);
 982                                 _ilg.Emit(OpCodes.Ldloca, result);
 983                                 _ilg.Emit(OpCodes.Initobj, resultType);
 984                                 _ilg.Emit(OpCodes.Ldloc, result);
 985                                 FreeLocal(result);
 986                             } else {
 987                                 _ilg.Emit(OpCodes.Ldnull);
 988                             }
 989                         } else {
 990                             switch (nodeType) {
 991                                 case ExpressionType.LessThan:
 992                                 case ExpressionType.LessThanOrEqual:
 993                                 case ExpressionType.GreaterThan:
 994                                 case ExpressionType.GreaterThanOrEqual:
 995                                     _ilg.Emit(OpCodes.Ldc_I4_0);
 996                                     break;
 997                                 default:
 998                                     throw Error.UnknownLiftType(nodeType);
 999                             }
1000                         }
1001                         _ilg.MarkLabel(exit);
1002                         return;
1003                     }
1004                 case ExpressionType.Equal:
1005                 case ExpressionType.NotEqual: {
1006                         if (TypeUtils.AreEquivalent(resultType, TypeUtils.GetNullableType(mc.Type))) {
1007                             goto default;
1008                         }
1009                         Label exit = _ilg.DefineLabel();
1010                         Label exitAllNull = _ilg.DefineLabel();
1011                         Label exitAnyNull = _ilg.DefineLabel();
1012
1013                         LocalBuilder anyNull = _ilg.DeclareLocal(typeof(bool));
1014                         LocalBuilder allNull = _ilg.DeclareLocal(typeof(bool));
1015                         _ilg.Emit(OpCodes.Ldc_I4_0);
1016                         _ilg.Emit(OpCodes.Stloc, anyNull);
1017                         _ilg.Emit(OpCodes.Ldc_I4_1);
1018                         _ilg.Emit(OpCodes.Stloc, allNull);
1019
1020                         for (int i = 0, n = paramList.Length; i < n; i++) {
1021                             ParameterExpression v = paramList[i];
1022                             Expression arg = argList[i];
1023                             _scope.AddLocal(this, v);
1024                             if (TypeUtils.IsNullableType(arg.Type)) {
1025                                 EmitAddress(arg, arg.Type);
1026                                 _ilg.Emit(OpCodes.Dup);
1027                                 _ilg.EmitHasValue(arg.Type);
1028                                 _ilg.Emit(OpCodes.Ldc_I4_0);
1029                                 _ilg.Emit(OpCodes.Ceq);
1030                                 _ilg.Emit(OpCodes.Dup);
1031                                 _ilg.Emit(OpCodes.Ldloc, anyNull);
1032                                 _ilg.Emit(OpCodes.Or);
1033                                 _ilg.Emit(OpCodes.Stloc, anyNull);
1034                                 _ilg.Emit(OpCodes.Ldloc, allNull);
1035                                 _ilg.Emit(OpCodes.And);
1036                                 _ilg.Emit(OpCodes.Stloc, allNull);
1037                                 _ilg.EmitGetValueOrDefault(arg.Type);
1038                             } else {
1039                                 EmitExpression(arg);
1040                                 if (!arg.Type.IsValueType) {
1041                                     _ilg.Emit(OpCodes.Dup);
1042                                     _ilg.Emit(OpCodes.Ldnull);
1043                                     _ilg.Emit(OpCodes.Ceq);
1044                                     _ilg.Emit(OpCodes.Dup);
1045                                     _ilg.Emit(OpCodes.Ldloc, anyNull);
1046                                     _ilg.Emit(OpCodes.Or);
1047                                     _ilg.Emit(OpCodes.Stloc, anyNull);
1048                                     _ilg.Emit(OpCodes.Ldloc, allNull);
1049                                     _ilg.Emit(OpCodes.And);
1050                                     _ilg.Emit(OpCodes.Stloc, allNull);
1051                                 } else {
1052                                     _ilg.Emit(OpCodes.Ldc_I4_0);
1053                                     _ilg.Emit(OpCodes.Stloc, allNull);
1054                                 }
1055                             }
1056                             _scope.EmitSet(v);
1057                         }
1058                         _ilg.Emit(OpCodes.Ldloc, allNull);
1059                         _ilg.Emit(OpCodes.Brtrue, exitAllNull);
1060                         _ilg.Emit(OpCodes.Ldloc, anyNull);
1061                         _ilg.Emit(OpCodes.Brtrue, exitAnyNull);
1062
1063                         EmitMethodCallExpression(mc);
1064                         if (TypeUtils.IsNullableType(resultType) && !TypeUtils.AreEquivalent(resultType, mc.Type)) {
1065                             ConstructorInfo ci = resultType.GetConstructor(new Type[] { mc.Type });
1066                             _ilg.Emit(OpCodes.Newobj, ci);
1067                         }
1068                         _ilg.Emit(OpCodes.Br_S, exit);
1069
1070                         _ilg.MarkLabel(exitAllNull);
1071                         _ilg.EmitBoolean(nodeType == ExpressionType.Equal);
1072                         _ilg.Emit(OpCodes.Br_S, exit);
1073
1074                         _ilg.MarkLabel(exitAnyNull);
1075                         _ilg.EmitBoolean(nodeType == ExpressionType.NotEqual);
1076
1077                         _ilg.MarkLabel(exit);
1078                         return;
1079                     }
1080             }
1081         }
1082
1083         #endregion
1084     }
1085 }