mcs/class/dlr/Runtime/Microsoft.Dynamic/Interpreter/LightCompiler.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 #if FEATURE_CORE_DLR
  17 using System.Linq.Expressions;
  18 using Microsoft.Scripting.Ast;
  19 #else
  20 using Microsoft.Scripting.Ast;
  21 #endif
  22
  23 using System;
  24 using System.Linq;
  25 using System.Collections.Generic;
  26 using System.Diagnostics;
  27 using System.Reflection;
  28 using System.Runtime.CompilerServices;
  29 #if FEATURE_REFEMIT
  30 using System.Reflection.Emit;
  31 #endif
  32
  33 using AstUtils = Microsoft.Scripting.Ast.Utils;
  34 using Microsoft.Scripting.Utils;
  35 using Microsoft.Scripting.Runtime;
  36 using System.Security;
  37
  38 namespace Microsoft.Scripting.Interpreter {
  39     public sealed class ExceptionHandler {
  40         public readonly Type ExceptionType;
  41         public readonly int StartIndex;
  42         public readonly int EndIndex;
  43         public readonly int LabelIndex;
  44         public readonly int HandlerStartIndex;
  45
  46         public bool IsFault { get { return ExceptionType == null; } }
  47
  48         internal ExceptionHandler(int start, int end, int labelIndex, int handlerStartIndex, Type exceptionType) {
  49             StartIndex = start;
  50             EndIndex = end;
  51             LabelIndex = labelIndex;
  52             ExceptionType = exceptionType;
  53             HandlerStartIndex = handlerStartIndex;
  54         }
  55
  56         public bool Matches(Type exceptionType, int index) {
  57             if (index >= StartIndex && index < EndIndex) {
  58                 if (ExceptionType == null || ExceptionType.IsAssignableFrom(exceptionType)) {
  59                     return true;
  60                 }
  61             }
  62             return false;
  63         }
  64
  65         public bool IsBetterThan(ExceptionHandler other) {
  66             if (other == null) return true;
  67
  68             if (StartIndex == other.StartIndex && EndIndex == other.EndIndex) {
  69                 return HandlerStartIndex < other.HandlerStartIndex;
  70             }
  71
  72             if (StartIndex > other.StartIndex) {
  73                 Debug.Assert(EndIndex <= other.EndIndex);
  74                 return true;
  75             } else if (EndIndex < other.EndIndex) {
  76                 Debug.Assert(StartIndex == other.StartIndex);
  77                 return true;
  78             } else {
  79                 return false;
  80             }
  81         }
  82
  83         internal bool IsInside(int index) {
  84             return index >= StartIndex && index < EndIndex;
  85         }
  86
  87         public override string ToString() {
  88             return String.Format("{0} [{1}-{2}] [{3}->]",
  89                 (IsFault ? "fault" : "catch(" + ExceptionType.Name + ")"),
  90                 StartIndex, EndIndex,
  91                 HandlerStartIndex
  92             );
  93         }
  94     }
  95
  96     [Serializable]
  97     public class DebugInfo {
  98         // TODO: readonly
  99
 100         public int StartLine, EndLine;
 101         public int Index;
 102         public string FileName;
 103         public bool IsClear;
 104         private static readonly DebugInfoComparer _debugComparer = new DebugInfoComparer();
 105
 106         private class DebugInfoComparer : IComparer<DebugInfo> {
 107             //We allow comparison between int and DebugInfo here
 108             int IComparer<DebugInfo>.Compare(DebugInfo d1, DebugInfo d2) {
 109                 if (d1.Index > d2.Index) return 1;
 110                 else if (d1.Index == d2.Index) return 0;
 111                 else return -1;
 112             }
 113         }
 114
 115         public static DebugInfo GetMatchingDebugInfo(DebugInfo[] debugInfos, int index) {
 116             //Create a faked DebugInfo to do the search
 117             DebugInfo d = new DebugInfo { Index = index };
 118
 119             //to find the closest debug info before the current index
 120
 121             int i = Array.BinarySearch<DebugInfo>(debugInfos, d, _debugComparer);
 122             if (i < 0) {
 123                 //~i is the index for the first bigger element
 124                 //if there is no bigger element, ~i is the length of the array
 125                 i = ~i;
 126                 if (i == 0) {
 127                     return null;
 128                 }
 129                 //return the last one that is smaller
 130                 i = i - 1;
 131             }
 132
 133             return debugInfos[i];
 134         }
 135
 136         public override string ToString() {
 137             if (IsClear) {
 138                 return String.Format("{0}: clear", Index);
 139             } else {
 140                 return String.Format("{0}: [{1}-{2}] '{3}'", Index, StartLine, EndLine, FileName);
 141             }
 142         }
 143     }
 144
 145     // TODO:
 146     [System.Diagnostics.CodeAnalysis.SuppressMessage("Microsoft.Performance", "CA1815:OverrideEqualsAndOperatorEqualsOnValueTypes")]
 147     [Serializable]
 148     public struct InterpretedFrameInfo {
 149         public readonly string MethodName;
 150
 151         // TODO:
 152         [System.Diagnostics.CodeAnalysis.SuppressMessage("Microsoft.Security", "CA2104:DoNotDeclareReadOnlyMutableReferenceTypes")]
 153         public readonly DebugInfo DebugInfo;
 154
 155         public InterpretedFrameInfo(string methodName, DebugInfo info) {
 156             MethodName = methodName;
 157             DebugInfo = info;
 158         }
 159
 160         public override string ToString() {
 161             return MethodName + (DebugInfo != null ? ": " + DebugInfo.ToString() : null);
 162         }
 163     }
 164
 165     [System.Diagnostics.CodeAnalysis.SuppressMessage("Microsoft.Maintainability", "CA1506:AvoidExcessiveClassCoupling")]
 166     public sealed class LightCompiler {
 167         internal const int DefaultCompilationThreshold = 32;
 168
 169         // zero: sync compilation
 170         private readonly int _compilationThreshold;
 171
 172         private readonly InstructionList _instructions;
 173         private readonly LocalVariables _locals = new LocalVariables();
 174
 175         private readonly List<ExceptionHandler> _handlers = new List<ExceptionHandler>();
 176
 177         private readonly List<DebugInfo> _debugInfos = new List<DebugInfo>();
 178         private readonly HybridReferenceDictionary<LabelTarget, LabelInfo> _treeLabels = new HybridReferenceDictionary<LabelTarget, LabelInfo>();
 179         private LabelScopeInfo _labelBlock = new LabelScopeInfo(null, LabelScopeKind.Lambda);
 180
 181         private readonly Stack<ParameterExpression> _exceptionForRethrowStack = new Stack<ParameterExpression>();
 182
 183         // Set to true to force compiliation of this lambda.
 184         // This disables the interpreter for this lambda. We still need to
 185         // walk it, however, to resolve variables closed over from the parent
 186         // lambdas (because they may be interpreted).
 187         private bool _forceCompile;
 188
 189         private readonly LightCompiler _parent;
 190
 191         private static LocalDefinition[] EmptyLocals = new LocalDefinition[0];
 192
 193         internal LightCompiler(int compilationThreshold) {
 194             _instructions = new InstructionList();
 195             _compilationThreshold = compilationThreshold < 0 ? DefaultCompilationThreshold : compilationThreshold;
 196         }
 197
 198         private LightCompiler(LightCompiler parent)
 199             : this(parent._compilationThreshold) {
 200             _parent = parent;
 201         }
 202
 203         public InstructionList Instructions {
 204             get { return _instructions; }
 205         }
 206
 207         public LocalVariables Locals {
 208             get { return _locals; }
 209         }
 210
 211         internal static Expression Unbox(Expression strongBoxExpression) {
 212             return Expression.Field(strongBoxExpression, typeof(StrongBox<object>).GetDeclaredField("Value"));
 213         }
 214
 215         internal LightDelegateCreator CompileTop(LambdaExpression node) {
 216             foreach (var p in node.Parameters) {
 217                 var local = _locals.DefineLocal(p, 0);
 218                 _instructions.EmitInitializeParameter(local.Index);
 219             }
 220
 221             Compile(node.Body);
 222
 223             // pop the result of the last expression:
 224             if (node.Body.Type != typeof(void) && node.ReturnType == typeof(void)) {
 225                 _instructions.EmitPop();
 226             }
 227
 228             Debug.Assert(_instructions.CurrentStackDepth == (node.ReturnType != typeof(void) ? 1 : 0));
 229
 230             return new LightDelegateCreator(MakeInterpreter(node.Name), node);
 231         }
 232
 233         internal LightDelegateCreator CompileTop(LightLambdaExpression node) {
 234             foreach (var p in node.Parameters) {
 235                 var local = _locals.DefineLocal(p, 0);
 236                 _instructions.EmitInitializeParameter(local.Index);
 237             }
 238
 239             Compile(node.Body);
 240
 241             // pop the result of the last expression:
 242             if (node.Body.Type != typeof(void) && node.ReturnType == typeof(void)) {
 243                 _instructions.EmitPop();
 244             }
 245
 246             Debug.Assert(_instructions.CurrentStackDepth == (node.ReturnType != typeof(void) ? 1 : 0));
 247
 248             return new LightDelegateCreator(MakeInterpreter(node.Name), node);
 249         }
 250
 251         private Interpreter MakeInterpreter(string lambdaName) {
 252             if (_forceCompile) {
 253                 return null;
 254             }
 255
 256             var handlers = _handlers.ToArray();
 257             var debugInfos = _debugInfos.ToArray();
 258
 259             return new Interpreter(lambdaName, _locals, GetBranchMapping(), _instructions.ToArray(), handlers, debugInfos, _compilationThreshold);
 260         }
 261
 262
 263         private void CompileConstantExpression(Expression expr) {
 264             var node = (ConstantExpression)expr;
 265             _instructions.EmitLoad(node.Value, node.Type);
 266         }
 267
 268         private void CompileDefaultExpression(Expression expr) {
 269             CompileDefaultExpression(expr.Type);
 270         }
 271
 272         private void CompileDefaultExpression(Type type) {
 273             if (type != typeof(void)) {
 274                 if (type.IsValueType()) {
 275                     object value = ScriptingRuntimeHelpers.GetPrimitiveDefaultValue(type);
 276                     if (value != null) {
 277                         _instructions.EmitLoad(value);
 278                     } else {
 279                         _instructions.EmitDefaultValue(type);
 280                     }
 281                 } else {
 282                     _instructions.EmitLoad(null);
 283                 }
 284             }
 285         }
 286
 287         private LocalVariable EnsureAvailableForClosure(ParameterExpression expr) {
 288             LocalVariable local;
 289             if (_locals.TryGetLocalOrClosure(expr, out local)) {
 290                 if (!local.InClosure && !local.IsBoxed) {
 291                     _locals.Box(expr, _instructions);
 292                 }
 293                 return local;
 294             } else if (_parent != null) {
 295                 _parent.EnsureAvailableForClosure(expr);
 296                 return _locals.AddClosureVariable(expr);
 297             } else {
 298                 throw new InvalidOperationException("unbound variable: " + expr);
 299             }
 300         }
 301
 302         private void EnsureVariable(ParameterExpression variable) {
 303             if (!_locals.ContainsVariable(variable)) {
 304                 EnsureAvailableForClosure(variable);
 305             }
 306         }
 307
 308         private LocalVariable ResolveLocal(ParameterExpression variable) {
 309             LocalVariable local;
 310             if (!_locals.TryGetLocalOrClosure(variable, out local)) {
 311                 local = EnsureAvailableForClosure(variable);
 312             }
 313             return local;
 314         }
 315
 316         public void CompileGetVariable(ParameterExpression variable) {
 317             LocalVariable local = ResolveLocal(variable);
 318
 319             if (local.InClosure) {
 320                 _instructions.EmitLoadLocalFromClosure(local.Index);
 321             } else if (local.IsBoxed) {
 322                 _instructions.EmitLoadLocalBoxed(local.Index);
 323             } else {
 324                 _instructions.EmitLoadLocal(local.Index);
 325             }
 326
 327             _instructions.SetDebugCookie(variable.Name);
 328         }
 329
 330         public void CompileGetBoxedVariable(ParameterExpression variable) {
 331             LocalVariable local = ResolveLocal(variable);
 332
 333             if (local.InClosure) {
 334                 _instructions.EmitLoadLocalFromClosureBoxed(local.Index);
 335             } else {
 336                 Debug.Assert(local.IsBoxed);
 337                 _instructions.EmitLoadLocal(local.Index);
 338             }
 339
 340             _instructions.SetDebugCookie(variable.Name);
 341         }
 342
 343         public void CompileSetVariable(ParameterExpression variable, bool isVoid) {
 344             LocalVariable local = ResolveLocal(variable);
 345
 346             if (local.InClosure) {
 347                 if (isVoid) {
 348                     _instructions.EmitStoreLocalToClosure(local.Index);
 349                 } else {
 350                     _instructions.EmitAssignLocalToClosure(local.Index);
 351                 }
 352             } else if (local.IsBoxed) {
 353                 if (isVoid) {
 354                     _instructions.EmitStoreLocalBoxed(local.Index);
 355                 } else {
 356                     _instructions.EmitAssignLocalBoxed(local.Index);
 357                 }
 358             } else {
 359                 if (isVoid) {
 360                     _instructions.EmitStoreLocal(local.Index);
 361                 } else {
 362                     _instructions.EmitAssignLocal(local.Index);
 363                 }
 364             }
 365
 366             _instructions.SetDebugCookie(variable.Name);
 367         }
 368
 369         public void CompileParameterExpression(Expression expr) {
 370             var node = (ParameterExpression)expr;
 371             CompileGetVariable(node);
 372         }
 373
 374         private void CompileBlockExpression(Expression expr, bool asVoid) {
 375             var node = (BlockExpression)expr;
 376             var end = CompileBlockStart(node);
 377
 378             var lastExpression = node.Expressions[node.Expressions.Count - 1];
 379             Compile(lastExpression, asVoid);
 380             CompileBlockEnd(end);
 381         }
 382
 383         private LocalDefinition[] CompileBlockStart(BlockExpression node) {
 384             var start = _instructions.Count;
 385
 386             LocalDefinition[] locals;
 387             var variables = node.Variables;
 388             if (variables.Count != 0) {
 389                 // TODO: basic flow analysis so we don't have to initialize all
 390                 // variables.
 391                 locals = new LocalDefinition[variables.Count];
 392                 int localCnt = 0;
 393                 foreach (var variable in variables) {
 394                     var local = _locals.DefineLocal(variable, start);
 395                     locals[localCnt++] = local;
 396
 397                     _instructions.EmitInitializeLocal(local.Index, variable.Type);
 398                     _instructions.SetDebugCookie(variable.Name);
 399                 }
 400             } else {
 401                 locals = EmptyLocals;
 402             }
 403
 404             for (int i = 0; i < node.Expressions.Count - 1; i++) {
 405                 CompileAsVoid(node.Expressions[i]);
 406             }
 407             return locals;
 408         }
 409
 410         private void CompileBlockEnd(LocalDefinition[] locals) {
 411             foreach (var local in locals) {
 412                 _locals.UndefineLocal(local, _instructions.Count);
 413             }
 414         }
 415
 416         private void CompileIndexExpression(Expression expr) {
 417             var index = (IndexExpression)expr;
 418
 419             // instance:
 420             if (index.Object != null) {
 421                 Compile(index.Object);
 422             }
 423
 424             // indexes, byref args not allowed.
 425             foreach (var arg in index.Arguments) {
 426                 Compile(arg);
 427             }
 428
 429             if (index.Indexer != null) {
 430                 EmitCall(index.Indexer.GetGetMethod(true));
 431             } else if (index.Arguments.Count != 1) {
 432                 EmitCall(index.Object.Type.GetMethod("Get", BindingFlags.Public | BindingFlags.Instance));
 433             } else {
 434                 _instructions.EmitGetArrayItem(index.Object.Type);
 435             }
 436         }
 437
 438         private void CompileIndexAssignment(BinaryExpression node, bool asVoid) {
 439             var index = (IndexExpression)node.Left;
 440
 441             if (!asVoid) {
 442                 throw new NotImplementedException();
 443             }
 444
 445             // instance:
 446             if (index.Object != null) {
 447                 Compile(index.Object);
 448             }
 449
 450             // indexes, byref args not allowed.
 451             foreach (var arg in index.Arguments) {
 452                 Compile(arg);
 453             }
 454
 455             // value:
 456             Compile(node.Right);
 457
 458             if (index.Indexer != null) {
 459                 EmitCall(index.Indexer.GetSetMethod(true));
 460             } else if (index.Arguments.Count != 1) {
 461                 EmitCall(index.Object.Type.GetMethod("Set", BindingFlags.Public | BindingFlags.Instance));
 462             } else {
 463                 _instructions.EmitSetArrayItem(index.Object.Type);
 464             }
 465         }
 466
 467         private void CompileMemberAssignment(BinaryExpression node, bool asVoid) {
 468             var member = (MemberExpression)node.Left;
 469
 470             PropertyInfo pi = member.Member as PropertyInfo;
 471             if (pi != null) {
 472                 var method = pi.GetSetMethod(true);
 473                 Compile(member.Expression);
 474                 Compile(node.Right);
 475
 476                 int start = _instructions.Count;
 477                 if (!asVoid) {
 478                     LocalDefinition local = _locals.DefineLocal(Expression.Parameter(node.Right.Type), start);
 479                     _instructions.EmitAssignLocal(local.Index);
 480                     EmitCall(method);
 481                     _instructions.EmitLoadLocal(local.Index);
 482                     _locals.UndefineLocal(local, _instructions.Count);
 483                 } else {
 484                     EmitCall(method);
 485                 }
 486                 return;
 487             }
 488
 489             FieldInfo fi = member.Member as FieldInfo;
 490             if (fi != null) {
 491                 if (member.Expression != null) {
 492                     Compile(member.Expression);
 493                 }
 494                 Compile(node.Right);
 495
 496                 int start = _instructions.Count;
 497                 if (!asVoid) {
 498                     LocalDefinition local = _locals.DefineLocal(Expression.Parameter(node.Right.Type), start);
 499                     _instructions.EmitAssignLocal(local.Index);
 500                     _instructions.EmitStoreField(fi);
 501                     _instructions.EmitLoadLocal(local.Index);
 502                     _locals.UndefineLocal(local, _instructions.Count);
 503                 } else {
 504                     _instructions.EmitStoreField(fi);
 505                 }
 506                 return;
 507             }
 508
 509             throw new NotImplementedException();
 510         }
 511
 512         private void CompileVariableAssignment(BinaryExpression node, bool asVoid) {
 513             this.Compile(node.Right);
 514
 515             var target = (ParameterExpression)node.Left;
 516             CompileSetVariable(target, asVoid);
 517         }
 518
 519         private void CompileAssignBinaryExpression(Expression expr, bool asVoid) {
 520             var node = (BinaryExpression)expr;
 521
 522             switch (node.Left.NodeType) {
 523                 case ExpressionType.Index:
 524                     CompileIndexAssignment(node, asVoid);
 525                     break;
 526
 527                 case ExpressionType.MemberAccess:
 528                     CompileMemberAssignment(node, asVoid);
 529                     break;
 530
 531                 case ExpressionType.Parameter:
 532                 case ExpressionType.Extension:
 533                     CompileVariableAssignment(node, asVoid);
 534                     break;
 535
 536                 default:
 537                     throw new InvalidOperationException("Invalid lvalue for assignment: " + node.Left.NodeType);
 538             }
 539         }
 540
 541         private void CompileBinaryExpression(Expression expr) {
 542             var node = (BinaryExpression)expr;
 543
 544             if (node.Method != null) {
 545                 Compile(node.Left);
 546                 Compile(node.Right);
 547                 EmitCall(node.Method);
 548             } else {
 549                 switch (node.NodeType) {
 550                     case ExpressionType.ArrayIndex:
 551                         Debug.Assert(node.Right.Type == typeof(int));
 552                         Compile(node.Left);
 553                         Compile(node.Right);
 554                         _instructions.EmitGetArrayItem(node.Left.Type);
 555                         return;
 556
 557                     case ExpressionType.Add:
 558                     case ExpressionType.AddChecked:
 559                     case ExpressionType.Subtract:
 560                     case ExpressionType.SubtractChecked:
 561                     case ExpressionType.Multiply:
 562                     case ExpressionType.MultiplyChecked:
 563                     case ExpressionType.Divide:
 564                     case ExpressionType.Modulo:
 565                         CompileArithmetic(node.NodeType, node.Left, node.Right);
 566                         return;
 567
 568                     case ExpressionType.Equal:
 569                         CompileEqual(node.Left, node.Right, node.IsLiftedToNull);
 570                         return;
 571
 572                     case ExpressionType.NotEqual:
 573                         CompileNotEqual(node.Left, node.Right, node.IsLiftedToNull);
 574                         return;
 575
 576                     case ExpressionType.LessThan:
 577                     case ExpressionType.LessThanOrEqual:
 578                     case ExpressionType.GreaterThan:
 579                     case ExpressionType.GreaterThanOrEqual:
 580                                                 CompileComparison(node.NodeType, node.Left, node.Right, node.IsLiftedToNull);
 581                         return;
 582
 583                     case ExpressionType.LeftShift:
 584                     case ExpressionType.RightShift:
 585                         CompileShift(node.NodeType, node.Left, node.Right, node.IsLifted);
 586                         return;
 587
 588                     case ExpressionType.And:
 589                     case ExpressionType.Or:
 590                     case ExpressionType.ExclusiveOr:
 591                         CompileLogical(node.NodeType, node.Left, node.Right, node.IsLifted);
 592                         return;
 593
 594                     default:
 595                         throw new NotImplementedException(node.NodeType.ToString());
 596                 }
 597             }
 598         }
 599
 600         private void CompileEqual(Expression left, Expression right, bool liftedResult) {
 601             Debug.Assert(left.Type == right.Type || !left.Type.IsValueType() && !right.Type.IsValueType());
 602             Compile(left);
 603             Compile(right);
 604             _instructions.EmitEqual(left.Type, liftedResult);
 605         }
 606
 607         private void CompileNotEqual(Expression left, Expression right, bool liftedResult) {
 608             Debug.Assert(left.Type == right.Type || !left.Type.IsValueType() && !right.Type.IsValueType());
 609             Compile(left);
 610             Compile(right);
 611             _instructions.EmitNotEqual(left.Type, liftedResult);
 612         }
 613
 614                 private void CompileComparison(ExpressionType nodeType, Expression left, Expression right, bool liftedResult) {
 615             Debug.Assert(left.Type == right.Type && TypeUtils.IsNumeric(left.Type));
 616
 617             Compile(left);
 618             Compile(right);
 619
 620             switch (nodeType) {
 621                 case ExpressionType.LessThan: _instructions.EmitLessThan(left.Type, liftedResult); break;
 622                 case ExpressionType.LessThanOrEqual: _instructions.EmitLessThanOrEqual(left.Type, liftedResult); break;
 623                 case ExpressionType.GreaterThan: _instructions.EmitGreaterThan(left.Type, liftedResult); break;
 624                 case ExpressionType.GreaterThanOrEqual: _instructions.EmitGreaterThanOrEqual(left.Type, liftedResult); break;
 625                 default: throw Assert.Unreachable;
 626             }
 627         }
 628
 629         private void CompileArithmetic(ExpressionType nodeType, Expression left, Expression right) {
 630             Debug.Assert(left.Type == right.Type && TypeUtils.IsArithmetic(left.Type));
 631             Compile(left);
 632             Compile(right);
 633             switch (nodeType) {
 634                 case ExpressionType.Add: _instructions.EmitAdd(left.Type, false); break;
 635                 case ExpressionType.AddChecked: _instructions.EmitAdd(left.Type, true); break;
 636                 case ExpressionType.Subtract: _instructions.EmitSub(left.Type, false); break;
 637                 case ExpressionType.SubtractChecked: _instructions.EmitSub(left.Type, true); break;
 638                 case ExpressionType.Multiply: _instructions.EmitMul(left.Type, false); break;
 639                 case ExpressionType.MultiplyChecked: _instructions.EmitMul(left.Type, true); break;
 640                 case ExpressionType.Divide: _instructions.EmitDiv(left.Type); break;
 641                 case ExpressionType.Modulo: _instructions.EmitMod(left.Type); break;
 642                 default: throw Assert.Unreachable;
 643             }
 644         }
 645
 646         private void CompileShift(ExpressionType nodeType, Expression left, Expression right, bool lifted) {
 647             Debug.Assert(right.Type == typeof (int) || right.Type == typeof (int?));
 648             Compile(left);
 649             Compile(right);
 650             switch (nodeType) {
 651                 case ExpressionType.LeftShift: _instructions.EmitShl(TypeUtils.GetNonNullableType (left.Type), lifted); break;
 652                 case ExpressionType.RightShift: _instructions.EmitShr(TypeUtils.GetNonNullableType (left.Type), lifted); break;
 653                 default: throw Assert.Unreachable;
 654             }
 655         }
 656
 657         private void CompileLogical(ExpressionType nodeType, Expression left, Expression right, bool lifted) {
 658             Debug.Assert(left.Type == right.Type); // && TypeUtils.IsIntegerOrBool(left.Type));
 659             Compile(left);
 660             Compile(right);
 661             switch (nodeType) {
 662                 case ExpressionType.And: _instructions.EmitAnd(TypeUtils.GetNonNullableType (left.Type), lifted); break;
 663                 case ExpressionType.Or: _instructions.EmitOr(TypeUtils.GetNonNullableType (left.Type), lifted); break;
 664                 case ExpressionType.ExclusiveOr: _instructions.EmitExclusiveOr(TypeUtils.GetNonNullableType (left.Type), lifted); break;
 665                 default: throw Assert.Unreachable;
 666             }
 667         }
 668
 669         private void CompileConvertUnaryExpression(Expression expr) {
 670             var node = (UnaryExpression)expr;
 671             if (node.Method != null) {
 672                 Compile(node.Operand);
 673
 674                                 if (node.IsLifted)
 675                                         throw new NotImplementedException ();
 676
 677                 // We should be able to ignore Int32ToObject
 678                 if (node.Method != Runtime.ScriptingRuntimeHelpers.Int32ToObjectMethod) {
 679                     EmitCall(node.Method);
 680                 }
 681             } else if (node.Type == typeof(void)) {
 682                 CompileAsVoid(node.Operand);
 683             } else {
 684                 Compile(node.Operand);
 685                 CompileConvertToType(node.Operand.Type, node.Type, node.NodeType == ExpressionType.ConvertChecked);
 686             }
 687         }
 688
 689         private void CompileConvertToType(Type typeFrom, Type typeTo, bool isChecked) {
 690             Debug.Assert(typeFrom != typeof(void) && typeTo != typeof(void));
 691
 692             if (TypeUtils.AreEquivalent(typeTo, typeFrom)) {
 693                 return;
 694             }
 695
 696             if (TypeUtils.IsNullableType (typeTo)) {
 697                 typeFrom = TypeUtils.GetNonNullableType (typeFrom);
 698                 typeTo = TypeUtils.GetNonNullableType (typeTo);
 699
 700                 var nullValue = _instructions.MakeLabel();
 701                 var end = _instructions.MakeLabel();
 702
 703                 _instructions.EmitDup ();
 704                 _instructions.EmitBranchNull(nullValue);
 705                 CompileConvertToType (typeFrom, typeTo, isChecked);
 706                 _instructions.EmitWrap (typeTo);
 707                 _instructions.MarkLabel(nullValue);
 708                 return;
 709             }
 710
 711             if (TypeUtils.IsNullableType (typeFrom)) {
 712                 if (typeTo.IsClass)
 713                     return;
 714
 715                 // TODO: should throw same exception as (int)(int?)null
 716                 throw new NotImplementedException ();
 717             }
 718
 719             TypeCode from = typeFrom.GetTypeCode();
 720             TypeCode to = typeTo.GetTypeCode();
 721             if (TypeUtils.IsNumeric(from) && TypeUtils.IsNumeric(to)) {
 722                 if (isChecked) {
 723                     _instructions.EmitNumericConvertChecked(from, to);
 724                 } else {
 725                     _instructions.EmitNumericConvertUnchecked(from, to);
 726                 }
 727                 return;
 728             }
 729
 730             // TODO: Conversions to a super-class or implemented interfaces are no-op.
 731             // A conversion to a non-implemented interface or an unrelated class, etc. should fail.
 732             return;
 733         }
 734
 735         private void CompileNegateExpression(UnaryExpression node, bool @checked, bool lifted) {
 736             Compile(node.Operand);
 737             _instructions.EmitNegate(TypeUtils.GetNonNullableType (node.Type), @checked, lifted);
 738         }
 739
 740         private void CompileNotExpression(UnaryExpression node, bool lifted) {
 741             Compile(node.Operand);
 742             _instructions.EmitNot(TypeUtils.GetNonNullableType (node.Type), lifted);
 743         }
 744
 745         private void CompileUnaryExpression(Expression expr) {
 746             var node = (UnaryExpression)expr;
 747
 748             if (node.Method != null) {
 749                 Compile(node.Operand);
 750                 EmitCall(node.Method);
 751             } else {
 752                 switch (node.NodeType) {
 753                     case ExpressionType.ArrayLength:
 754                         Compile(node.Operand);
 755                         _instructions.EmitGetArrayLength (node.Type);
 756                         return;
 757                     case ExpressionType.Negate:
 758                         CompileNegateExpression(node, false, node.IsLifted);
 759                         return;
 760                     case ExpressionType.NegateChecked:
 761                         CompileNegateExpression(node, true, node.IsLifted);
 762                         return;
 763                     case ExpressionType.Not:
 764                         CompileNotExpression(node, node.IsLifted);
 765                         return;
 766                     case ExpressionType.UnaryPlus:
 767                         // unary plus is a nop:
 768                         Compile(node.Operand);
 769                         return;
 770                     case ExpressionType.TypeAs:
 771                         CompileTypeAsExpression(node);
 772                         return;
 773                     default:
 774                         throw new NotImplementedException(node.NodeType.ToString());
 775                 }
 776             }
 777         }
 778
 779         private void CompileAndAlsoBinaryExpression(Expression expr) {
 780             CompileLogicalBinaryExpression(expr, true);
 781         }
 782
 783         private void CompileOrElseBinaryExpression(Expression expr) {
 784             CompileLogicalBinaryExpression(expr, false);
 785         }
 786
 787         private void CompileLogicalBinaryExpression(Expression expr, bool andAlso) {
 788             var node = (BinaryExpression)expr;
 789             if (node.Method != null) {
 790                 throw new NotImplementedException();
 791             }
 792
 793             Debug.Assert(node.Left.Type == node.Right.Type);
 794
 795             if (node.Left.Type == typeof(bool)) {
 796                 var elseLabel = _instructions.MakeLabel();
 797                 var endLabel = _instructions.MakeLabel();
 798                 Compile(node.Left);
 799                 if (andAlso) {
 800                     _instructions.EmitBranchFalse(elseLabel);
 801                 } else {
 802                     _instructions.EmitBranchTrue(elseLabel);
 803                 }
 804                 Compile(node.Right);
 805                 _instructions.EmitBranch(endLabel, false, true);
 806                 _instructions.MarkLabel(elseLabel);
 807                 _instructions.EmitLoad(!andAlso);
 808                 _instructions.MarkLabel(endLabel);
 809                 return;
 810             }
 811
 812             Debug.Assert(node.Left.Type == typeof(bool?));
 813             throw new NotImplementedException();
 814         }
 815
 816         private void CompileConditionalExpression(Expression expr, bool asVoid) {
 817             var node = (ConditionalExpression)expr;
 818             Compile(node.Test);
 819
 820             if (node.IfTrue == AstUtils.Empty()) {
 821                 var endOfFalse = _instructions.MakeLabel();
 822                 _instructions.EmitBranchTrue(endOfFalse);
 823                 Compile(node.IfFalse, asVoid);
 824                 _instructions.MarkLabel(endOfFalse);
 825             } else {
 826                 var endOfTrue = _instructions.MakeLabel();
 827                 _instructions.EmitBranchFalse(endOfTrue);
 828                 Compile(node.IfTrue, asVoid);
 829
 830                 if (node.IfFalse != AstUtils.Empty()) {
 831                     var endOfFalse = _instructions.MakeLabel();
 832                     _instructions.EmitBranch(endOfFalse, false, !asVoid);
 833                     _instructions.MarkLabel(endOfTrue);
 834                     Compile(node.IfFalse, asVoid);
 835                     _instructions.MarkLabel(endOfFalse);
 836                 } else {
 837                     _instructions.MarkLabel(endOfTrue);
 838                 }
 839             }
 840         }
 841
 842         #region Loops
 843
 844         private void CompileLoopExpression(Expression expr) {
 845             var node = (LoopExpression)expr;
 846             var enterLoop = new EnterLoopInstruction(node, _locals, _compilationThreshold, _instructions.Count);
 847
 848             PushLabelBlock(LabelScopeKind.Statement);
 849             LabelInfo breakLabel = DefineLabel(node.BreakLabel);
 850             LabelInfo continueLabel = DefineLabel(node.ContinueLabel);
 851
 852             _instructions.MarkLabel(continueLabel.GetLabel(this));
 853
 854             // emit loop body:
 855             _instructions.Emit(enterLoop);
 856             CompileAsVoid(node.Body);
 857
 858             // emit loop branch:
 859             _instructions.EmitBranch(continueLabel.GetLabel(this), expr.Type != typeof(void), false);
 860
 861             _instructions.MarkLabel(breakLabel.GetLabel(this));
 862
 863             PopLabelBlock(LabelScopeKind.Statement);
 864
 865             enterLoop.FinishLoop(_instructions.Count);
 866         }
 867
 868         #endregion
 869
 870         private void CompileSwitchExpression(Expression expr) {
 871             var node = (SwitchExpression)expr;
 872
 873             // Currently only supports int test values, with no method
 874             if (node.SwitchValue.Type != typeof(int) || node.Comparison != null) {
 875                 throw new NotImplementedException();
 876             }
 877
 878             // Test values must be constant
 879             if (!node.Cases.All(c => c.TestValues.All(t => t is ConstantExpression))) {
 880                 throw new NotImplementedException();
 881             }
 882             LabelInfo end = DefineLabel(null);
 883             bool hasValue = node.Type != typeof(void);
 884
 885             Compile(node.SwitchValue);
 886             var caseDict = new Dictionary<int, int>();
 887             int switchIndex = _instructions.Count;
 888             _instructions.EmitSwitch(caseDict);
 889
 890             if (node.DefaultBody != null) {
 891                 Compile(node.DefaultBody);
 892             } else {
 893                 Debug.Assert(!hasValue);
 894             }
 895             _instructions.EmitBranch(end.GetLabel(this), false, hasValue);
 896
 897             for (int i = 0; i < node.Cases.Count; i++) {
 898                 var switchCase = node.Cases[i];
 899
 900                 int caseOffset = _instructions.Count - switchIndex;
 901                 foreach (ConstantExpression testValue in switchCase.TestValues) {
 902                     caseDict[(int)testValue.Value] = caseOffset;
 903                 }
 904
 905                 Compile(switchCase.Body);
 906
 907                 if (i < node.Cases.Count - 1) {
 908                     _instructions.EmitBranch(end.GetLabel(this), false, hasValue);
 909                 }
 910             }
 911
 912             _instructions.MarkLabel(end.GetLabel(this));
 913         }
 914
 915         private void CompileLabelExpression(Expression expr) {
 916             var node = (LabelExpression)expr;
 917
 918             // If we're an immediate child of a block, our label will already
 919             // be defined. If not, we need to define our own block so this
 920             // label isn't exposed except to its own child expression.
 921             LabelInfo label = null;
 922
 923             if (_labelBlock.Kind == LabelScopeKind.Block) {
 924                 _labelBlock.TryGetLabelInfo(node.Target, out label);
 925
 926                 // We're in a block but didn't find our label, try switch
 927                 if (label == null && _labelBlock.Parent.Kind == LabelScopeKind.Switch) {
 928                     _labelBlock.Parent.TryGetLabelInfo(node.Target, out label);
 929                 }
 930
 931                 // if we're in a switch or block, we should've found the label
 932                 Debug.Assert(label != null);
 933             }
 934
 935             if (label == null) {
 936                 label = DefineLabel(node.Target);
 937             }
 938
 939             if (node.DefaultValue != null) {
 940                 if (node.Target.Type == typeof(void)) {
 941                     CompileAsVoid(node.DefaultValue);
 942                 } else {
 943                     Compile(node.DefaultValue);
 944                 }
 945             }
 946
 947             _instructions.MarkLabel(label.GetLabel(this));
 948         }
 949
 950         private void CompileGotoExpression(Expression expr) {
 951             var node = (GotoExpression)expr;
 952             var labelInfo = ReferenceLabel(node.Target);
 953
 954             if (node.Value != null) {
 955                 Compile(node.Value);
 956             }
 957
 958             _instructions.EmitGoto(labelInfo.GetLabel(this), node.Type != typeof(void), node.Value != null && node.Value.Type != typeof(void));
 959         }
 960
 961         public BranchLabel GetBranchLabel(LabelTarget target) {
 962             return ReferenceLabel(target).GetLabel(this);
 963         }
 964
 965         public void PushLabelBlock(LabelScopeKind type) {
 966             _labelBlock = new LabelScopeInfo(_labelBlock, type);
 967         }
 968
 969         [System.Diagnostics.CodeAnalysis.SuppressMessage("Microsoft.Usage", "CA1801:ReviewUnusedParameters", MessageId = "kind")]
 970         public void PopLabelBlock(LabelScopeKind kind) {
 971             Debug.Assert(_labelBlock != null && _labelBlock.Kind == kind);
 972             _labelBlock = _labelBlock.Parent;
 973         }
 974
 975         private LabelInfo EnsureLabel(LabelTarget node) {
 976             LabelInfo result;
 977             if (!_treeLabels.TryGetValue(node, out result)) {
 978                 _treeLabels[node] = result = new LabelInfo(node);
 979             }
 980             return result;
 981         }
 982
 983         private LabelInfo ReferenceLabel(LabelTarget node) {
 984             LabelInfo result = EnsureLabel(node);
 985             result.Reference(_labelBlock);
 986             return result;
 987         }
 988
 989         internal LabelInfo DefineLabel(LabelTarget node) {
 990             if (node == null) {
 991                 return new LabelInfo(null);
 992             }
 993             LabelInfo result = EnsureLabel(node);
 994             result.Define(_labelBlock);
 995             return result;
 996         }
 997
 998         private bool TryPushLabelBlock(Expression node) {
 999             // Anything that is "statement-like" -- e.g. has no associated
1000             // stack state can be jumped into, with the exception of try-blocks
1001             // We indicate this by a "Block"
1002             //
1003             // Otherwise, we push an "Expression" to indicate that it can't be
1004             // jumped into
1005             switch (node.NodeType) {
1006                 default:
1007                     if (_labelBlock.Kind != LabelScopeKind.Expression) {
1008                         PushLabelBlock(LabelScopeKind.Expression);
1009                         return true;
1010                     }
1011                     return false;
1012                 case ExpressionType.Label:
1013                     // LabelExpression is a bit special, if it's directly in a
1014                     // block it becomes associate with the block's scope. Same
1015                     // thing if it's in a switch case body.
1016                     if (_labelBlock.Kind == LabelScopeKind.Block) {
1017                         var label = ((LabelExpression)node).Target;
1018                         if (_labelBlock.ContainsTarget(label)) {
1019                             return false;
1020                         }
1021                         if (_labelBlock.Parent.Kind == LabelScopeKind.Switch &&
1022                             _labelBlock.Parent.ContainsTarget(label)) {
1023                             return false;
1024                         }
1025                     }
1026                     PushLabelBlock(LabelScopeKind.Statement);
1027                     return true;
1028                 case ExpressionType.Block:
1029                     PushLabelBlock(LabelScopeKind.Block);
1030                     // Labels defined immediately in the block are valid for
1031                     // the whole block.
1032                     if (_labelBlock.Parent.Kind != LabelScopeKind.Switch) {
1033                         DefineBlockLabels(node);
1034                     }
1035                     return true;
1036                 case ExpressionType.Switch:
1037                     PushLabelBlock(LabelScopeKind.Switch);
1038                     // Define labels inside of the switch cases so theyare in
1039                     // scope for the whole switch. This allows "goto case" and
1040                     // "goto default" to be considered as local jumps.
1041                     var @switch = (SwitchExpression)node;
1042                     foreach (SwitchCase c in @switch.Cases) {
1043                         DefineBlockLabels(c.Body);
1044                     }
1045                     DefineBlockLabels(@switch.DefaultBody);
1046                     return true;
1047
1048                 // Remove this when Convert(Void) goes away.
1049                 case ExpressionType.Convert:
1050                     if (node.Type != typeof(void)) {
1051                         // treat it as an expression
1052                         goto default;
1053                     }
1054                     PushLabelBlock(LabelScopeKind.Statement);
1055                     return true;
1056
1057                 case ExpressionType.Conditional:
1058                 case ExpressionType.Loop:
1059                 case ExpressionType.Goto:
1060                     PushLabelBlock(LabelScopeKind.Statement);
1061                     return true;
1062             }
1063         }
1064
1065         private void DefineBlockLabels(Expression node) {
1066             var block = node as BlockExpression;
1067             if (block == null) {
1068                 return;
1069             }
1070
1071             for (int i = 0, n = block.Expressions.Count; i < n; i++) {
1072                 Expression e = block.Expressions[i];
1073
1074                 var label = e as LabelExpression;
1075                 if (label != null) {
1076                     DefineLabel(label.Target);
1077                 }
1078             }
1079         }
1080
1081         private HybridReferenceDictionary<LabelTarget, BranchLabel> GetBranchMapping() {
1082             var newLabelMapping = new HybridReferenceDictionary<LabelTarget, BranchLabel>(_treeLabels.Count);
1083             foreach (var kvp in _treeLabels) {
1084                 newLabelMapping[kvp.Key] = kvp.Value.GetLabel(this);
1085             }
1086             return newLabelMapping;
1087         }
1088
1089         private void CompileThrowUnaryExpression(Expression expr, bool asVoid) {
1090             var node = (UnaryExpression)expr;
1091
1092             if (node.Operand == null) {
1093                 CompileParameterExpression(_exceptionForRethrowStack.Peek());
1094                 if (asVoid) {
1095                     _instructions.EmitRethrowVoid();
1096                 } else {
1097                     _instructions.EmitRethrow();
1098                 }
1099             } else {
1100                 Compile(node.Operand);
1101                 if (asVoid) {
1102                     _instructions.EmitThrowVoid();
1103                 } else {
1104                     _instructions.EmitThrow();
1105                 }
1106             }
1107
1108         }
1109
1110         // TODO: remove (replace by true fault support)
1111         private bool EndsWithRethrow(Expression expr) {
1112             if (expr.NodeType == ExpressionType.Throw) {
1113                 var node = (UnaryExpression)expr;
1114                 return node.Operand == null;
1115             }
1116
1117             BlockExpression block = expr as BlockExpression;
1118             if (block != null) {
1119                 return EndsWithRethrow(block.Expressions[block.Expressions.Count - 1]);
1120             }
1121             return false;
1122         }
1123
1124
1125         // TODO: remove (replace by true fault support)
1126         private void CompileAsVoidRemoveRethrow(Expression expr) {
1127             int stackDepth = _instructions.CurrentStackDepth;
1128
1129             if (expr.NodeType == ExpressionType.Throw) {
1130                 Debug.Assert(((UnaryExpression)expr).Operand == null);
1131                 return;
1132             }
1133
1134             var node = (BlockExpression)expr;
1135             var end = CompileBlockStart(node);
1136
1137             CompileAsVoidRemoveRethrow(node.Expressions[node.Expressions.Count - 1]);
1138
1139             Debug.Assert(stackDepth == _instructions.CurrentStackDepth);
1140
1141             CompileBlockEnd(end);
1142         }
1143
1144         private void CompileTryExpression(Expression expr) {
1145             var node = (TryExpression)expr;
1146
1147             BranchLabel end = _instructions.MakeLabel();
1148             BranchLabel gotoEnd = _instructions.MakeLabel();
1149
1150             int tryStart = _instructions.Count;
1151
1152             BranchLabel startOfFinally = null;
1153             if (node.Finally != null) {
1154                 startOfFinally = _instructions.MakeLabel();
1155                 _instructions.EmitEnterTryFinally(startOfFinally);
1156             }
1157
1158             PushLabelBlock(LabelScopeKind.Try);
1159             Compile(node.Body);
1160
1161             bool hasValue = node.Body.Type != typeof(void);
1162             int tryEnd = _instructions.Count;
1163
1164             // handlers jump here:
1165             _instructions.MarkLabel(gotoEnd);
1166             _instructions.EmitGoto(end, hasValue, hasValue);
1167
1168             // keep the result on the stack:
1169             if (node.Handlers.Count > 0) {
1170                 // TODO: emulates faults (replace by true fault support)
1171                 if (node.Finally == null && node.Handlers.Count == 1) {
1172                     var handler = node.Handlers[0];
1173                     if (handler.Filter == null && handler.Test == typeof(Exception) && handler.Variable == null) {
1174                         if (EndsWithRethrow(handler.Body)) {
1175                             if (hasValue) {
1176                                 _instructions.EmitEnterExceptionHandlerNonVoid();
1177                             } else {
1178                                 _instructions.EmitEnterExceptionHandlerVoid();
1179                             }
1180
1181                             // at this point the stack balance is prepared for the hidden exception variable:
1182                             int handlerLabel = _instructions.MarkRuntimeLabel();
1183                             int handlerStart = _instructions.Count;
1184
1185                             CompileAsVoidRemoveRethrow(handler.Body);
1186                             _instructions.EmitLeaveFault(hasValue);
1187                             _instructions.MarkLabel(end);
1188
1189                             _handlers.Add(new ExceptionHandler(tryStart, tryEnd, handlerLabel, handlerStart, null));
1190                             PopLabelBlock(LabelScopeKind.Try);
1191                             return;
1192                         }
1193                     }
1194                 }
1195
1196                 foreach (var handler in node.Handlers) {
1197                     PushLabelBlock(LabelScopeKind.Catch);
1198
1199                     if (handler.Filter != null) {
1200                         //PushLabelBlock(LabelScopeKind.Filter);
1201                         throw new NotImplementedException();
1202                         //PopLabelBlock(LabelScopeKind.Filter);
1203                     }
1204
1205                     var parameter = handler.Variable ?? Expression.Parameter(handler.Test);
1206
1207                     var local = _locals.DefineLocal(parameter, _instructions.Count);
1208                     _exceptionForRethrowStack.Push(parameter);
1209
1210                     // add a stack balancing nop instruction (exception handling pushes the current exception):
1211                     if (hasValue) {
1212                         _instructions.EmitEnterExceptionHandlerNonVoid();
1213                     } else {
1214                         _instructions.EmitEnterExceptionHandlerVoid();
1215                     }
1216
1217                     // at this point the stack balance is prepared for the hidden exception variable:
1218                     int handlerLabel = _instructions.MarkRuntimeLabel();
1219                     int handlerStart = _instructions.Count;
1220
1221                     CompileSetVariable(parameter, true);
1222                     Compile(handler.Body);
1223
1224                     _exceptionForRethrowStack.Pop();
1225
1226                     // keep the value of the body on the stack:
1227                     Debug.Assert(hasValue == (handler.Body.Type != typeof(void)));
1228                     _instructions.EmitLeaveExceptionHandler(hasValue, gotoEnd);
1229
1230                     _handlers.Add(new ExceptionHandler(tryStart, tryEnd, handlerLabel, handlerStart, handler.Test));
1231
1232                     PopLabelBlock(LabelScopeKind.Catch);
1233
1234                     _locals.UndefineLocal(local, _instructions.Count);
1235                 }
1236
1237                 if (node.Fault != null) {
1238                     throw new NotImplementedException();
1239                 }
1240             }
1241
1242             if (node.Finally != null) {
1243                 PushLabelBlock(LabelScopeKind.Finally);
1244
1245                 _instructions.MarkLabel(startOfFinally);
1246                 _instructions.EmitEnterFinally();
1247                 CompileAsVoid(node.Finally);
1248                 _instructions.EmitLeaveFinally();
1249
1250                 PopLabelBlock(LabelScopeKind.Finally);
1251             }
1252
1253             _instructions.MarkLabel(end);
1254
1255             PopLabelBlock(LabelScopeKind.Try);
1256         }
1257
1258         private void CompileDynamicExpression(Expression expr) {
1259             var node = (DynamicExpression)expr;
1260
1261             foreach (var arg in node.Arguments) {
1262                 Compile(arg);
1263             }
1264
1265             _instructions.EmitDynamic(node.DelegateType, node.Binder);
1266         }
1267
1268         private void CompileMethodCallExpression(Expression expr) {
1269             var node = (MethodCallExpression)expr;
1270
1271             var parameters = node.Method.GetParameters();
1272
1273             // TODO:
1274             // Support pass by reference.
1275             // Note that LoopCompiler needs to be updated too.
1276
1277             // force compilation for now for ref types
1278             // also could be a mutable value type, Delegate.CreateDelegate and MethodInfo.Invoke both can't handle this, we
1279             // need to generate code.
1280             if (!CollectionUtils.TrueForAll(parameters, (p) => !p.ParameterType.IsByRef) ||
1281                 (!node.Method.IsStatic && node.Method.DeclaringType.IsValueType && node.Method.DeclaringType.Assembly != typeof (object).Assembly)) {
1282 #if MONO_INTERPRETER
1283                 throw new NotImplementedException ("Interpreter of ref types");
1284 #else
1285                 _forceCompile = true;
1286 #endif
1287             }
1288
1289             // CF bug workaround
1290             // TODO: can we do better if the delegate targets LightLambda.Run* method?
1291             if (PlatformAdaptationLayer.IsCompactFramework &&
1292                 node.Method.Name == "Invoke" && typeof(Delegate).IsAssignableFrom(node.Object.Type) && !node.Method.IsStatic) {
1293
1294                 Compile(
1295                     AstUtils.Convert(
1296                         Expression.Call(
1297                             node.Object,
1298                             node.Object.Type.GetMethod("DynamicInvoke"),
1299                             Expression.NewArrayInit(typeof(object), node.Arguments.Map((e) => AstUtils.Convert(e, typeof(object))))
1300                         ),
1301                         node.Type
1302                     )
1303                 );
1304
1305             } else {
1306                 if (!node.Method.IsStatic) {
1307                     Compile(node.Object);
1308                 }
1309
1310                 foreach (var arg in node.Arguments) {
1311                     Compile(arg);
1312                 }
1313
1314                 EmitCall(node.Method, parameters);
1315             }
1316         }
1317
1318         public void EmitCall(MethodInfo method) {
1319             EmitCall(method, method.GetParameters());
1320         }
1321
1322         public void EmitCall(MethodInfo method, ParameterInfo[] parameters) {
1323             Instruction instruction;
1324
1325             try {
1326                 instruction = CallInstruction.Create(method, parameters);
1327             } catch (SecurityException) {
1328                 _forceCompile = true;
1329
1330                 _instructions.Emit(new PopNInstruction((method.IsStatic ? 0 : 1) + parameters.Length));
1331                 if (method.ReturnType != typeof(void)) {
1332                     _instructions.EmitLoad(null);
1333                 }
1334
1335                 return;
1336             }
1337
1338             _instructions.Emit(instruction);
1339         }
1340
1341         private void CompileNewExpression(Expression expr) {
1342             var node = (NewExpression)expr;
1343
1344             if (node.Constructor != null) {
1345                 var parameters = node.Constructor.GetParameters();
1346                 if (!CollectionUtils.TrueForAll(parameters, (p) => !p.ParameterType.IsByRef)
1347 #if FEATURE_LCG
1348                      || node.Constructor.DeclaringType == typeof(DynamicMethod)
1349 #endif
1350                 ) {
1351                     _forceCompile = true;
1352                 }
1353             }
1354
1355             if (node.Constructor != null) {
1356                 foreach (var arg in node.Arguments) {
1357                     this.Compile(arg);
1358                 }
1359                 _instructions.EmitNew(node.Constructor);
1360             } else {
1361                 Debug.Assert(expr.Type.IsValueType());
1362                 _instructions.EmitDefaultValue(node.Type);
1363             }
1364         }
1365
1366         private void CompileMemberExpression(Expression expr) {
1367             var node = (MemberExpression)expr;
1368
1369             var member = node.Member;
1370             FieldInfo fi = member as FieldInfo;
1371             if (fi != null) {
1372                 if (fi.IsLiteral) {
1373                     _instructions.EmitLoad(fi.GetRawConstantValue(), fi.FieldType);
1374                 } else if (fi.IsStatic) {
1375                     if (fi.IsInitOnly) {
1376                         _instructions.EmitLoad(fi.GetValue(null), fi.FieldType);
1377                     } else {
1378                         _instructions.EmitLoadField(fi);
1379                     }
1380                 } else {
1381                     Compile(node.Expression);
1382                     _instructions.EmitLoadField(fi);
1383                 }
1384                 return;
1385             }
1386
1387             PropertyInfo pi = member as PropertyInfo;
1388             if (pi != null) {
1389                 var method = pi.GetGetMethod(true);
1390                 if (node.Expression != null) {
1391                     Compile(node.Expression);
1392                 }
1393                 EmitCall(method);
1394                 return;
1395             }
1396
1397
1398             throw new System.NotImplementedException();
1399         }
1400
1401         private void CompileNewArrayExpression(Expression expr) {
1402             var node = (NewArrayExpression)expr;
1403
1404             foreach (var arg in node.Expressions) {
1405                 Compile(arg);
1406             }
1407
1408             Type elementType = node.Type.GetElementType();
1409             int rank = node.Expressions.Count;
1410
1411             if (node.NodeType == ExpressionType.NewArrayInit) {
1412                 _instructions.EmitNewArrayInit(elementType, rank);
1413             } else if (node.NodeType == ExpressionType.NewArrayBounds) {
1414                 if (rank == 1) {
1415                     _instructions.EmitNewArray(elementType);
1416                 } else {
1417                     _instructions.EmitNewArrayBounds(elementType, rank);
1418                 }
1419             } else {
1420                 throw new System.NotImplementedException();
1421             }
1422         }
1423
1424         private void CompileExtensionExpression(Expression expr) {
1425             var instructionProvider = expr as IInstructionProvider;
1426             if (instructionProvider != null) {
1427                 instructionProvider.AddInstructions(this);
1428                 return;
1429             }
1430
1431             if (expr.CanReduce) {
1432                 Compile(expr.Reduce());
1433             } else {
1434                 throw new System.NotImplementedException();
1435             }
1436         }
1437
1438
1439         private void CompileDebugInfoExpression(Expression expr) {
1440             var node = (DebugInfoExpression)expr;
1441             int start = _instructions.Count;
1442             var info = new DebugInfo()
1443             {
1444                 Index = start,
1445                 FileName = node.Document.FileName,
1446                 StartLine = node.StartLine,
1447                 EndLine = node.EndLine,
1448                 IsClear = node.IsClear
1449             };
1450             _debugInfos.Add(info);
1451         }
1452
1453         private void CompileRuntimeVariablesExpression(Expression expr) {
1454             // Generates IRuntimeVariables for all requested variables
1455             var node = (RuntimeVariablesExpression)expr;
1456             foreach (var variable in node.Variables) {
1457                 EnsureAvailableForClosure(variable);
1458                 CompileGetBoxedVariable(variable);
1459             }
1460
1461             _instructions.EmitNewRuntimeVariables(node.Variables.Count);
1462         }
1463
1464
1465         private void CompileLambdaExpression(Expression expr) {
1466             var node = (LambdaExpression)expr;
1467             var compiler = new LightCompiler(this);
1468             var creator = compiler.CompileTop(node);
1469
1470             if (compiler._locals.ClosureVariables != null) {
1471                 foreach (ParameterExpression variable in compiler._locals.ClosureVariables.Keys) {
1472                     CompileGetBoxedVariable(variable);
1473                 }
1474             }
1475             _instructions.EmitCreateDelegate(creator);
1476         }
1477
1478                 private void CompileQuotedLambdaExpression(Expression expr) {
1479                         _instructions.EmitStore (expr);
1480                 }
1481
1482         private void CompileCoalesceBinaryExpression(Expression expr) {
1483             var node = (BinaryExpression)expr;
1484
1485             if (TypeUtils.IsNullableType(node.Left.Type)) {
1486                 throw new NotImplementedException();
1487             } else if (node.Conversion != null) {
1488                 throw new NotImplementedException();
1489             } else {
1490                 var leftNotNull = _instructions.MakeLabel();
1491                 Compile(node.Left);
1492                 _instructions.EmitCoalescingBranch(leftNotNull);
1493                 _instructions.EmitPop();
1494                 Compile(node.Right);
1495                 _instructions.MarkLabel(leftNotNull);
1496             }
1497         }
1498
1499         private void CompileInvocationExpression(Expression expr) {
1500             var node = (InvocationExpression)expr;
1501
1502             // TODO: LambdaOperand optimization (see compiler)
1503             if (typeof(LambdaExpression).IsAssignableFrom(node.Expression.Type)) {
1504                 throw new System.NotImplementedException();
1505             }
1506
1507             // TODO: do not create a new Call Expression
1508             if (PlatformAdaptationLayer.IsCompactFramework) {
1509                 // Workaround for a bug in Compact Framework
1510                 Compile(
1511                     AstUtils.Convert(
1512                         Expression.Call(
1513                             node.Expression,
1514                             node.Expression.Type.GetMethod("DynamicInvoke"),
1515                             Expression.NewArrayInit(typeof(object), node.Arguments.Map((e) => AstUtils.Convert(e, typeof(object))))
1516                         ),
1517                         node.Type
1518                     )
1519                 );
1520             } else {
1521                 CompileMethodCallExpression(Expression.Call(node.Expression, node.Expression.Type.GetMethod("Invoke"), node.Arguments));
1522             }
1523         }
1524
1525         [System.Diagnostics.CodeAnalysis.SuppressMessage("Microsoft.Usage", "CA1801:ReviewUnusedParameters", MessageId = "expr")]
1526         private void CompileListInitExpression(Expression expr) {
1527             throw new System.NotImplementedException();
1528         }
1529
1530         [System.Diagnostics.CodeAnalysis.SuppressMessage("Microsoft.Usage", "CA1801:ReviewUnusedParameters", MessageId = "expr")]
1531         private void CompileMemberInitExpression(Expression expr) {
1532             throw new System.NotImplementedException();
1533         }
1534
1535                 private void CompileQuoteUnaryExpression(Expression expr) {
1536                         var qe = (UnaryExpression)expr;
1537                         CompileQuotedLambdaExpression (qe.Operand);
1538         }
1539
1540         private void CompileUnboxUnaryExpression(Expression expr) {
1541             var node = (UnaryExpression)expr;
1542             // unboxing is a nop:
1543             Compile(node.Operand);
1544         }
1545
1546         private void CompileTypeEqualExpression(Expression expr) {
1547             Debug.Assert(expr.NodeType == ExpressionType.TypeEqual);
1548             var node = (TypeBinaryExpression)expr;
1549
1550             Compile(node.Expression);
1551             _instructions.EmitLoad(node.TypeOperand);
1552             _instructions.EmitTypeEquals();
1553         }
1554
1555         private void CompileTypeAsExpression(UnaryExpression node) {
1556             Compile(node.Operand);
1557             _instructions.EmitTypeAs(node.Type);
1558         }
1559
1560         private void CompileTypeIsExpression(Expression expr) {
1561             Debug.Assert(expr.NodeType == ExpressionType.TypeIs);
1562             var node = (TypeBinaryExpression)expr;
1563
1564             Compile(node.Expression);
1565             if (node.Expression.Type == typeof (void)) {
1566                 _instructions.Emit (InstructionFactory<bool>.Factory.DefaultValue ());
1567                 return;
1568             }
1569
1570             // use TypeEqual for sealed types:
1571             if (node.TypeOperand.IsSealed()) {
1572                 _instructions.EmitLoad(node.TypeOperand);
1573                 _instructions.EmitTypeEquals();
1574             } else {
1575                 _instructions.EmitTypeIs(node.TypeOperand);
1576             }
1577         }
1578
1579         private void CompileReducibleExpression(Expression expr) {
1580             switch (expr.NodeType) {
1581             case ExpressionType.PreIncrementAssign:
1582                 _instructions.EmitIncrement (expr.Type);
1583                 break;
1584             default:
1585                 throw Assert.Unreachable;
1586             }
1587         }
1588
1589         internal void Compile(Expression expr, bool asVoid) {
1590             if (asVoid) {
1591                 CompileAsVoid(expr);
1592             } else {
1593                 Compile(expr);
1594             }
1595         }
1596
1597         internal void CompileAsVoid(Expression expr) {
1598             bool pushLabelBlock = TryPushLabelBlock(expr);
1599             int startingStackDepth = _instructions.CurrentStackDepth;
1600             switch (expr.NodeType) {
1601                 case ExpressionType.Assign:
1602                     CompileAssignBinaryExpression(expr, true);
1603                     break;
1604
1605                 case ExpressionType.Block:
1606                     CompileBlockExpression(expr, true);
1607                     break;
1608
1609                 case ExpressionType.Throw:
1610                     CompileThrowUnaryExpression(expr, true);
1611                     break;
1612
1613                 case ExpressionType.Constant:
1614                 case ExpressionType.Default:
1615                 case ExpressionType.Parameter:
1616                     // no-op
1617                     break;
1618
1619                 default:
1620                     CompileNoLabelPush(expr);
1621                     if (expr.Type != typeof(void)) {
1622                         _instructions.EmitPop();
1623                     }
1624                     break;
1625             }
1626             Debug.Assert(_instructions.CurrentStackDepth == startingStackDepth);
1627             if (pushLabelBlock) {
1628                 PopLabelBlock(_labelBlock.Kind);
1629             }
1630         }
1631
1632         [System.Diagnostics.CodeAnalysis.SuppressMessage("Microsoft.Maintainability", "CA1502:AvoidExcessiveComplexity")]
1633         private void CompileNoLabelPush(Expression expr) {
1634             int startingStackDepth = _instructions.CurrentStackDepth;
1635             switch (expr.NodeType) {
1636                 case ExpressionType.Add: CompileBinaryExpression(expr); break;
1637                 case ExpressionType.AddChecked: CompileBinaryExpression(expr); break;
1638                 case ExpressionType.And: CompileBinaryExpression(expr); break;
1639                 case ExpressionType.AndAlso: CompileAndAlsoBinaryExpression(expr); break;
1640                 case ExpressionType.ArrayLength: CompileUnaryExpression(expr); break;
1641                 case ExpressionType.ArrayIndex: CompileBinaryExpression(expr); break;
1642                 case ExpressionType.Call: CompileMethodCallExpression(expr); break;
1643                 case ExpressionType.Coalesce: CompileCoalesceBinaryExpression(expr); break;
1644                 case ExpressionType.Conditional: CompileConditionalExpression(expr, expr.Type == typeof(void)); break;
1645                 case ExpressionType.Constant: CompileConstantExpression(expr); break;
1646                 case ExpressionType.Convert: CompileConvertUnaryExpression(expr); break;
1647                 case ExpressionType.ConvertChecked: CompileConvertUnaryExpression(expr); break;
1648                 case ExpressionType.Divide: CompileBinaryExpression(expr); break;
1649                 case ExpressionType.Equal: CompileBinaryExpression(expr); break;
1650                 case ExpressionType.ExclusiveOr: CompileBinaryExpression(expr); break;
1651                 case ExpressionType.GreaterThan: CompileBinaryExpression(expr); break;
1652                 case ExpressionType.GreaterThanOrEqual: CompileBinaryExpression(expr); break;
1653                 case ExpressionType.Invoke: CompileInvocationExpression(expr); break;
1654                 case ExpressionType.Lambda: CompileLambdaExpression(expr); break;
1655                 case ExpressionType.LeftShift: CompileBinaryExpression(expr); break;
1656                 case ExpressionType.LessThan: CompileBinaryExpression(expr); break;
1657                 case ExpressionType.LessThanOrEqual: CompileBinaryExpression(expr); break;
1658                 case ExpressionType.ListInit: CompileListInitExpression(expr); break;
1659                 case ExpressionType.MemberAccess: CompileMemberExpression(expr); break;
1660                 case ExpressionType.MemberInit: CompileMemberInitExpression(expr); break;
1661                 case ExpressionType.Modulo: CompileBinaryExpression(expr); break;
1662                 case ExpressionType.Multiply: CompileBinaryExpression(expr); break;
1663                 case ExpressionType.MultiplyChecked: CompileBinaryExpression(expr); break;
1664                 case ExpressionType.Negate: CompileUnaryExpression(expr); break;
1665                 case ExpressionType.UnaryPlus: CompileUnaryExpression(expr); break;
1666                 case ExpressionType.NegateChecked: CompileUnaryExpression(expr); break;
1667                 case ExpressionType.New: CompileNewExpression(expr); break;
1668                 case ExpressionType.NewArrayInit: CompileNewArrayExpression(expr); break;
1669                 case ExpressionType.NewArrayBounds: CompileNewArrayExpression(expr); break;
1670                 case ExpressionType.Not: CompileUnaryExpression(expr); break;
1671                 case ExpressionType.NotEqual: CompileBinaryExpression(expr); break;
1672                 case ExpressionType.Or: CompileBinaryExpression(expr); break;
1673                 case ExpressionType.OrElse: CompileOrElseBinaryExpression(expr); break;
1674                 case ExpressionType.Parameter: CompileParameterExpression(expr); break;
1675                 case ExpressionType.Power: CompileBinaryExpression(expr); break;
1676                 case ExpressionType.Quote: CompileQuoteUnaryExpression(expr); break;
1677                 case ExpressionType.RightShift: CompileBinaryExpression(expr); break;
1678                 case ExpressionType.Subtract: CompileBinaryExpression(expr); break;
1679                 case ExpressionType.SubtractChecked: CompileBinaryExpression(expr); break;
1680                 case ExpressionType.TypeAs: CompileUnaryExpression(expr); break;
1681                 case ExpressionType.TypeIs: CompileTypeIsExpression(expr); break;
1682                 case ExpressionType.Assign: CompileAssignBinaryExpression(expr, expr.Type == typeof(void)); break;
1683                 case ExpressionType.Block: CompileBlockExpression(expr, expr.Type == typeof(void)); break;
1684                 case ExpressionType.DebugInfo: CompileDebugInfoExpression(expr); break;
1685                 case ExpressionType.Decrement: CompileUnaryExpression(expr); break;
1686                 case ExpressionType.Dynamic: CompileDynamicExpression(expr); break;
1687                 case ExpressionType.Default: CompileDefaultExpression(expr); break;
1688                 case ExpressionType.Extension: CompileExtensionExpression(expr); break;
1689                 case ExpressionType.Goto: CompileGotoExpression(expr); break;
1690                 case ExpressionType.Increment: CompileUnaryExpression(expr); break;
1691                 case ExpressionType.Index: CompileIndexExpression(expr); break;
1692                 case ExpressionType.Label: CompileLabelExpression(expr); break;
1693                 case ExpressionType.RuntimeVariables: CompileRuntimeVariablesExpression(expr); break;
1694                 case ExpressionType.Loop: CompileLoopExpression(expr); break;
1695                 case ExpressionType.Switch: CompileSwitchExpression(expr); break;
1696                 case ExpressionType.Throw: CompileThrowUnaryExpression(expr, expr.Type == typeof(void)); break;
1697                 case ExpressionType.Try: CompileTryExpression(expr); break;
1698                 case ExpressionType.Unbox: CompileUnboxUnaryExpression(expr); break;
1699                 case ExpressionType.TypeEqual: CompileTypeEqualExpression(expr); break;
1700                 case ExpressionType.OnesComplement: CompileUnaryExpression(expr); break;
1701                 case ExpressionType.IsTrue: CompileUnaryExpression(expr); break;
1702                 case ExpressionType.IsFalse: CompileUnaryExpression(expr); break;
1703                 case ExpressionType.AddAssign:
1704                 case ExpressionType.AndAssign:
1705                 case ExpressionType.DivideAssign:
1706                 case ExpressionType.ExclusiveOrAssign:
1707                 case ExpressionType.LeftShiftAssign:
1708                 case ExpressionType.ModuloAssign:
1709                 case ExpressionType.MultiplyAssign:
1710                 case ExpressionType.OrAssign:
1711                 case ExpressionType.PowerAssign:
1712                 case ExpressionType.RightShiftAssign:
1713                 case ExpressionType.SubtractAssign:
1714                 case ExpressionType.AddAssignChecked:
1715                 case ExpressionType.MultiplyAssignChecked:
1716                 case ExpressionType.SubtractAssignChecked:
1717                 case ExpressionType.PreIncrementAssign:
1718                 case ExpressionType.PreDecrementAssign:
1719                 case ExpressionType.PostIncrementAssign:
1720                 case ExpressionType.PostDecrementAssign:
1721                     CompileReducibleExpression(expr); break;
1722                 default: throw Assert.Unreachable;
1723             };
1724             Debug.Assert(_instructions.CurrentStackDepth == startingStackDepth + (expr.Type == typeof(void) ? 0 : 1));
1725         }
1726
1727         public void Compile(Expression expr) {
1728             bool pushLabelBlock = TryPushLabelBlock(expr);
1729             CompileNoLabelPush(expr);
1730             if (pushLabelBlock) {
1731                 PopLabelBlock(_labelBlock.Kind);
1732             }
1733         }
1734
1735     }
1736 }