mcs/class/dlr/Runtime/Microsoft.Scripting.Core/Compiler/StackSpiller.cs

   1 /* ****************************************************************************
   2  *
   3  * Copyright (c) Microsoft Corporation.
   4  *
   5  * This source code is subject to terms and conditions of the Microsoft Public License. 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  Microsoft Public License, 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 Microsoft Public License.
  10  *
  11  * You must not remove this notice, or any other, from this software.
  12  *
  13  *
  14  * ***************************************************************************/
  15 using System; using Microsoft;
  16
  17
  18 using System.Collections.Generic;
  19 using System.Collections.ObjectModel;
  20 using System.Diagnostics;
  21 #if CODEPLEX_40
  22 using System.Dynamic.Utils;
  23 #else
  24 using Microsoft.Scripting.Utils;
  25 #endif
  26 using System.Reflection;
  27 using System.Runtime.CompilerServices;
  28 #if !CODEPLEX_40
  29 using Microsoft.Runtime.CompilerServices;
  30 #endif
  31
  32
  33 #if CODEPLEX_40
  34 namespace System.Linq.Expressions.Compiler {
  35 #else
  36 namespace Microsoft.Linq.Expressions.Compiler {
  37 #endif
  38
  39     /// <summary>
  40     /// Expression rewriting to spill the CLR stack into temporary variables
  41     /// in order to guarantee some properties of code generation, for
  42     /// example that we always enter try block on empty stack.
  43     /// </summary>
  44     internal partial class StackSpiller {
  45
  46         // Is the evaluation stack empty?
  47         private enum Stack {
  48             Empty,
  49             NonEmpty
  50         };
  51
  52         // Should the parent nodes be rewritten, and in what way?
  53         // Designed so bitwise-or produces the correct result when merging two
  54         // subtrees. In particular, SpillStack is preferred over Copy which is
  55         // preferred over None.
  56         //
  57         // Values:
  58         //   None -> no rewrite needed
  59         //   Copy -> copy into a new node
  60         //   SpillStack -> spill stack into temps
  61         [Flags]
  62         private enum RewriteAction {
  63             None = 0,
  64             Copy = 1,
  65             SpillStack = 3,
  66         }
  67
  68         // Result of a rewrite operation. Always contains an action and a node.
  69         private struct Result {
  70             internal readonly RewriteAction Action;
  71             internal readonly Expression Node;
  72
  73             internal Result(RewriteAction action, Expression node) {
  74                 Action = action;
  75                 Node = node;
  76             }
  77         }
  78
  79         /// <summary>
  80         /// The source of temporary variables
  81         /// </summary>
  82         private readonly TempMaker _tm = new TempMaker();
  83
  84         /// <summary>
  85         /// Initial stack state. Normally empty, but when inlining the lambda
  86         /// we might have a non-empty starting stack state.
  87         /// </summary>
  88         private readonly Stack _startingStack;
  89
  90         /// <summary>
  91         /// Lambda rewrite result. We need this for inlined lambdas to figure
  92         /// out whether we need to guarentee it an empty stack.
  93         /// </summary>
  94         private RewriteAction _lambdaRewrite;
  95
  96         /// <summary>
  97         /// Analyzes a lambda, producing a new one that has correct invariants
  98         /// for codegen. In particular, it spills the IL stack to temps in
  99         /// places where it's invalid to have a non-empty stack (for example,
 100         /// entering a try statement).
 101         /// </summary>
 102         internal static LambdaExpression AnalyzeLambda(LambdaExpression lambda) {
 103             return lambda.Accept(new StackSpiller(Stack.Empty));
 104         }
 105
 106         private StackSpiller(Stack stack) {
 107             _startingStack = stack;
 108         }
 109
 110         // called by Expression<T>.Accept
 111         internal Expression<T> Rewrite<T>(Expression<T> lambda) {
 112             VerifyTemps();
 113
 114             // Lambda starts with an empty stack
 115             Result body = RewriteExpressionFreeTemps(lambda.Body, _startingStack);
 116             _lambdaRewrite = body.Action;
 117
 118             VerifyTemps();
 119
 120             if (body.Action != RewriteAction.None) {
 121                 // Create a new scope for temps
 122                 // (none of these will be hoisted so there is no closure impact)
 123                 Expression newBody = body.Node;
 124                 if (_tm.Temps.Count > 0) {
 125                     newBody = Expression.Block(_tm.Temps, newBody);
 126                 }
 127
 128                 // Clone the lambda, replacing the body & variables
 129                 return new Expression<T>(newBody, lambda.Name, lambda.TailCall, lambda.Parameters);
 130             }
 131
 132             return lambda;
 133         }
 134
 135         #region Expressions
 136
 137         [Conditional("DEBUG")]
 138         private static void VerifyRewrite(Result result, Expression node) {
 139             Debug.Assert(result.Node != null);
 140
 141             // (result.Action == RewriteAction.None) if and only if (node == result.Node)
 142             Debug.Assert((result.Action == RewriteAction.None) ^ (node != result.Node), "rewrite action does not match node object identity");
 143
 144             // if the original node is an extension node, it should have been rewritten
 145             Debug.Assert(result.Node.NodeType != ExpressionType.Extension, "extension nodes must be rewritten");
 146
 147             // if we have Copy, then node type must match
 148             Debug.Assert(
 149                 result.Action != RewriteAction.Copy || node.NodeType == result.Node.NodeType || node.CanReduce,
 150                 "rewrite action does not match node object kind"
 151             );
 152
 153             // New type must be reference assignable to the old type
 154             // (our rewrites preserve type exactly, but the rules for rewriting
 155             // an extension node are more lenient, see Expression.ReduceAndCheck())
 156             Debug.Assert(
 157                 TypeUtils.AreReferenceAssignable(node.Type, result.Node.Type),
 158                 "rewritten object must be reference assignable to the original type"
 159             );
 160         }
 161
 162         private Result RewriteExpressionFreeTemps(Expression expression, Stack stack) {
 163             int mark = Mark();
 164             Result result = RewriteExpression(expression, stack);
 165             Free(mark);
 166             return result;
 167         }
 168
 169         // DynamicExpression
 170         [System.Diagnostics.CodeAnalysis.SuppressMessage("Microsoft.Usage", "CA1801:ReviewUnusedParameters", MessageId = "stack")]
 171         private Result RewriteDynamicExpression(Expression expr, Stack stack) {
 172             var node = (DynamicExpression)expr;
 173
 174             // CallSite is on the stack
 175             IArgumentProvider argNode = (IArgumentProvider)node;
 176             ChildRewriter cr = new ChildRewriter(this, Stack.NonEmpty, argNode.ArgumentCount);
 177             cr.AddArguments(argNode);
 178             if (cr.Action == RewriteAction.SpillStack) {
 179                 RequireNoRefArgs(node.DelegateType.GetMethod("Invoke"));
 180             }
 181             return cr.Finish(cr.Rewrite ? node.Rewrite(cr[0, -1]) : expr);
 182         }
 183
 184         private Result RewriteIndexAssignment(BinaryExpression node, Stack stack) {
 185             IndexExpression index = (IndexExpression)node.Left;
 186
 187             ChildRewriter cr = new ChildRewriter(this, stack, 2 + index.Arguments.Count);
 188
 189             cr.Add(index.Object);
 190             cr.Add(index.Arguments);
 191             cr.Add(node.Right);
 192
 193             if (cr.Action == RewriteAction.SpillStack) {
 194                 RequireNotRefInstance(index.Object);
 195             }
 196
 197             if (cr.Rewrite) {
 198                 node = new AssignBinaryExpression(
 199                     new IndexExpression(
 200                         cr[0],                              // Object
 201                         index.Indexer,
 202                         cr[1, -2]                           // arguments
 203                     ),
 204                     cr[-1]                                  // value
 205                 );
 206             }
 207
 208             return cr.Finish(node);
 209         }
 210
 211         // BinaryExpression: AndAlso, OrElse
 212         private Result RewriteLogicalBinaryExpression(Expression expr, Stack stack) {
 213             BinaryExpression node = (BinaryExpression)expr;
 214
 215             // Left expression runs on a stack as left by parent
 216             Result left = RewriteExpression(node.Left, stack);
 217             // ... and so does the right one
 218             Result right = RewriteExpression(node.Right, stack);
 219             //conversion is a lambda. stack state will be ignored.
 220             Result conversion = RewriteExpression(node.Conversion, stack);
 221
 222             RewriteAction action = left.Action | right.Action | conversion.Action;
 223             if (action != RewriteAction.None) {
 224
 225                     // We don't have to worry about byref parameters here, because the
 226                     // factory doesn't allow it (it requires identical parameters and
 227                     // return type from the AndAlso/OrElse method)
 228
 229                 expr = BinaryExpression.Create(
 230                     node.NodeType,
 231                     left.Node,
 232                     right.Node,
 233                     node.Type,
 234                     node.Method,
 235                     (LambdaExpression)conversion.Node
 236                 );
 237             }
 238             return new Result(action, expr);
 239         }
 240
 241         private Result RewriteReducibleExpression(Expression expr, Stack stack) {
 242             Result result = RewriteExpression(expr.Reduce(), stack);
 243             // it's at least Copy because we reduced the node
 244             return new Result(result.Action | RewriteAction.Copy, result.Node);
 245         }
 246
 247         // BinaryExpression
 248         private Result RewriteBinaryExpression(Expression expr, Stack stack) {
 249             BinaryExpression node = (BinaryExpression)expr;
 250
 251             ChildRewriter cr = new ChildRewriter(this, stack, 3);
 252             // Left expression executes on the stack as left by parent
 253             cr.Add(node.Left);
 254             // Right expression always has non-empty stack (left is on it)
 255             cr.Add(node.Right);
 256             // conversion is a lambda, stack state will be ignored
 257             cr.Add(node.Conversion);
 258
 259             if (cr.Action == RewriteAction.SpillStack) {
 260                 RequireNoRefArgs(node.Method);
 261             }
 262
 263             return cr.Finish(cr.Rewrite ?
 264                                     BinaryExpression.Create(
 265                                             node.NodeType,
 266                                             cr[0],
 267                                             cr[1],
 268                                             node.Type,
 269                                             node.Method,
 270                                             (LambdaExpression)cr[2]) :
 271                                     expr);
 272         }
 273
 274         // variable assignment
 275         private Result RewriteVariableAssignment(BinaryExpression node, Stack stack) {
 276             // Expression is evaluated on a stack in current state
 277             Result right = RewriteExpression(node.Right, stack);
 278             if (right.Action != RewriteAction.None) {
 279                 node = Expression.Assign(node.Left, right.Node);
 280             }
 281             return new Result(right.Action, node);
 282         }
 283
 284         private Result RewriteAssignBinaryExpression(Expression expr, Stack stack) {
 285             var node = (BinaryExpression)expr;
 286
 287             switch (node.Left.NodeType) {
 288                 case ExpressionType.Index:
 289                     return RewriteIndexAssignment(node, stack);
 290                 case ExpressionType.MemberAccess:
 291                     return RewriteMemberAssignment(node, stack);
 292                 case ExpressionType.Parameter:
 293                     return RewriteVariableAssignment(node, stack);
 294                 case ExpressionType.Extension:
 295                     return RewriteExtensionAssignment(node, stack);
 296                 default:
 297                     throw Error.InvalidLvalue(node.Left.NodeType);
 298             }
 299         }
 300
 301         private Result RewriteExtensionAssignment(BinaryExpression node, Stack stack) {
 302             node = Expression.Assign(node.Left.ReduceExtensions(), node.Right);
 303             Result result = RewriteAssignBinaryExpression(node, stack);
 304             // it's at least Copy because we reduced the node
 305             return new Result(result.Action | RewriteAction.Copy, result.Node);
 306         }
 307
 308         // LambdaExpression
 309         [System.Diagnostics.CodeAnalysis.SuppressMessage("Microsoft.Usage", "CA1801:ReviewUnusedParameters", MessageId = "stack")]
 310         private static Result RewriteLambdaExpression(Expression expr, Stack stack) {
 311             LambdaExpression node = (LambdaExpression)expr;
 312
 313             // Call back into the rewriter
 314             expr = AnalyzeLambda(node);
 315
 316             // If the lambda gets rewritten, we don't need to spill the stack,
 317             // but we do need to rebuild the tree above us so it includes the new node.
 318             RewriteAction action = (expr == node) ? RewriteAction.None : RewriteAction.Copy;
 319
 320             return new Result(action, expr);
 321         }
 322
 323         // ConditionalExpression
 324         private Result RewriteConditionalExpression(Expression expr, Stack stack) {
 325             ConditionalExpression node = (ConditionalExpression)expr;
 326             // Test executes at the stack as left by parent
 327             Result test = RewriteExpression(node.Test, stack);
 328             // The test is popped by conditional jump so branches execute
 329             // at the stack as left by parent too.
 330             Result ifTrue = RewriteExpression(node.IfTrue, stack);
 331             Result ifFalse = RewriteExpression(node.IfFalse, stack);
 332
 333             RewriteAction action = test.Action | ifTrue.Action | ifFalse.Action;
 334             if (action != RewriteAction.None) {
 335                 expr = Expression.Condition(test.Node, ifTrue.Node, ifFalse.Node, node.Type);
 336             }
 337
 338             return new Result(action, expr);
 339         }
 340
 341         // member assignment
 342         private Result RewriteMemberAssignment(BinaryExpression node, Stack stack) {
 343             MemberExpression lvalue = (MemberExpression)node.Left;
 344
 345             ChildRewriter cr = new ChildRewriter(this, stack, 2);
 346
 347             // If there's an instance, it executes on the stack in current state
 348             // and rest is executed on non-empty stack.
 349             // Otherwise the stack is left unchaged.
 350             cr.Add(lvalue.Expression);
 351
 352             cr.Add(node.Right);
 353
 354             if (cr.Action == RewriteAction.SpillStack) {
 355                 RequireNotRefInstance(lvalue.Expression);
 356             }
 357
 358             if (cr.Rewrite) {
 359                 return cr.Finish(
 360                     new AssignBinaryExpression(
 361                         MemberExpression.Make(cr[0], lvalue.Member),
 362                         cr[1]
 363                     )
 364                 );
 365             }
 366             return new Result(RewriteAction.None, node);
 367         }
 368
 369         // MemberExpression
 370         private Result RewriteMemberExpression(Expression expr, Stack stack) {
 371             MemberExpression node = (MemberExpression)expr;
 372
 373             // Expression is emitted on top of the stack in current state
 374             Result expression = RewriteExpression(node.Expression, stack);
 375             if (expression.Action != RewriteAction.None) {
 376                 if (expression.Action == RewriteAction.SpillStack &&
 377                     node.Member.MemberType == MemberTypes.Property) {
 378                     // Only need to validate propreties because reading a field
 379                     // is always side-effect free.
 380                     RequireNotRefInstance(node.Expression);
 381                 }
 382                 expr = MemberExpression.Make(expression.Node, node.Member);
 383             }
 384             return new Result(expression.Action, expr);
 385         }
 386
 387         //RewriteIndexExpression
 388         private Result RewriteIndexExpression(Expression expr, Stack stack) {
 389             IndexExpression node = (IndexExpression)expr;
 390
 391             ChildRewriter cr = new ChildRewriter(this, stack, node.Arguments.Count + 1);
 392
 393             // For instance methods, the instance executes on the
 394             // stack as is, but stays on the stack, making it non-empty.
 395             cr.Add(node.Object);
 396             cr.Add(node.Arguments);
 397
 398             if (cr.Action == RewriteAction.SpillStack) {
 399                 RequireNotRefInstance(node.Object);
 400             }
 401
 402             if (cr.Rewrite) {
 403                 expr = new IndexExpression(
 404                     cr[0],
 405                     node.Indexer,
 406                     cr[1, -1]
 407                 );
 408             }
 409
 410             return cr.Finish(expr);
 411         }
 412
 413         // MethodCallExpression
 414         private Result RewriteMethodCallExpression(Expression expr, Stack stack) {
 415             MethodCallExpression node = (MethodCallExpression)expr;
 416
 417             ChildRewriter cr = new ChildRewriter(this, stack, node.Arguments.Count + 1);
 418
 419             // For instance methods, the instance executes on the
 420             // stack as is, but stays on the stack, making it non-empty.
 421             cr.Add(node.Object);
 422
 423             cr.AddArguments(node);
 424
 425             if (cr.Action == RewriteAction.SpillStack) {
 426                 RequireNotRefInstance(node.Object);
 427                 RequireNoRefArgs(node.Method);
 428             }
 429
 430             return cr.Finish(cr.Rewrite ? node.Rewrite(cr[0], cr[1, -1]) : expr);
 431         }
 432
 433         // NewArrayExpression
 434         private Result RewriteNewArrayExpression(Expression expr, Stack stack) {
 435             NewArrayExpression node = (NewArrayExpression)expr;
 436
 437             if (node.NodeType == ExpressionType.NewArrayInit) {
 438                 // In a case of array construction with element initialization
 439                 // the element expressions are never emitted on an empty stack because
 440                 // the array reference and the index are on the stack.
 441                 stack = Stack.NonEmpty;
 442             } else {
 443                 // In a case of NewArrayBounds we make no modifications to the stack
 444                 // before emitting bounds expressions.
 445             }
 446
 447             ChildRewriter cr = new ChildRewriter(this, stack, node.Expressions.Count);
 448             cr.Add(node.Expressions);
 449
 450             if (cr.Rewrite) {
 451                 Type element = node.Type.GetElementType();
 452                 if (node.NodeType == ExpressionType.NewArrayInit) {
 453                     expr = Expression.NewArrayInit(element, cr[0, -1]);
 454                 } else {
 455                     expr = Expression.NewArrayBounds(element, cr[0, -1]);
 456                 }
 457             }
 458
 459             return cr.Finish(expr);
 460         }
 461
 462         // InvocationExpression
 463         private Result RewriteInvocationExpression(Expression expr, Stack stack) {
 464             InvocationExpression node = (InvocationExpression)expr;
 465
 466             ChildRewriter cr;
 467
 468             // See if the lambda will be inlined
 469             LambdaExpression lambda = node.LambdaOperand;
 470             if (lambda != null) {
 471                 // Arguments execute on current stack
 472                 cr = new ChildRewriter(this, stack, node.Arguments.Count);
 473                 cr.Add(node.Arguments);
 474
 475                 if (cr.Action == RewriteAction.SpillStack) {
 476                     RequireNoRefArgs(Expression.GetInvokeMethod(node.Expression));
 477                 }
 478
 479                 // Lambda body also executes on current stack
 480                 var spiller = new StackSpiller(stack);
 481                 lambda = lambda.Accept(spiller);
 482
 483                 if (cr.Rewrite || spiller._lambdaRewrite != RewriteAction.None) {
 484                     node = new InvocationExpression(lambda, cr[0, -1], node.Type);
 485                 }
 486
 487                 Result result = cr.Finish(node);
 488                 return new Result(result.Action | spiller._lambdaRewrite, result.Node);
 489             }
 490
 491             cr = new ChildRewriter(this, stack, node.Arguments.Count + 1);
 492
 493             // first argument starts on stack as provided
 494             cr.Add(node.Expression);
 495
 496             // rest of arguments have non-empty stack (delegate instance on the stack)
 497             cr.Add(node.Arguments);
 498
 499             if (cr.Action == RewriteAction.SpillStack) {
 500                 RequireNoRefArgs(Expression.GetInvokeMethod(node.Expression));
 501             }
 502
 503             return cr.Finish(cr.Rewrite ? new InvocationExpression(cr[0], cr[1, -1], node.Type) : expr);
 504         }
 505
 506         // NewExpression
 507         private Result RewriteNewExpression(Expression expr, Stack stack) {
 508             NewExpression node = (NewExpression)expr;
 509
 510             // The first expression starts on a stack as provided by parent,
 511             // rest are definitely non-emtpy (which ChildRewriter guarantees)
 512             ChildRewriter cr = new ChildRewriter(this, stack, node.Arguments.Count);
 513             cr.AddArguments(node);
 514
 515             if (cr.Action == RewriteAction.SpillStack) {
 516                 RequireNoRefArgs(node.Constructor);
 517             }
 518
 519             return cr.Finish(cr.Rewrite ? new NewExpression(node.Constructor, cr[0, -1], node.Members) : expr);
 520         }
 521
 522         // TypeBinaryExpression
 523         private Result RewriteTypeBinaryExpression(Expression expr, Stack stack) {
 524             TypeBinaryExpression node = (TypeBinaryExpression)expr;
 525             // The expression is emitted on top of current stack
 526             Result expression = RewriteExpression(node.Expression, stack);
 527             if (expression.Action != RewriteAction.None) {
 528                 if (node.NodeType == ExpressionType.TypeIs) {
 529                     expr = Expression.TypeIs(expression.Node, node.TypeOperand);
 530                 } else {
 531                     expr = Expression.TypeEqual(expression.Node, node.TypeOperand);
 532                 }
 533             }
 534             return new Result(expression.Action, expr);
 535         }
 536
 537         // Throw
 538         private Result RewriteThrowUnaryExpression(Expression expr, Stack stack) {
 539             UnaryExpression node = (UnaryExpression)expr;
 540
 541             // Throw statement itself does not care about the stack
 542             // but it will empty the stack and it may cause stack misbalance
 543             // it so we need to restore stack after unconditional throw to make JIT happy
 544             // this has an effect of executing Throw on an empty stack.
 545
 546             Result value = RewriteExpressionFreeTemps(node.Operand, Stack.Empty);
 547             RewriteAction action = value.Action;
 548
 549             if (stack != Stack.Empty) {
 550                 action = RewriteAction.SpillStack;
 551             }
 552
 553             if (action != RewriteAction.None) {
 554                 expr = Expression.Throw(value.Node, node.Type);
 555             }
 556
 557             return new Result(action, expr);
 558         }
 559
 560         // UnaryExpression
 561         private Result RewriteUnaryExpression(Expression expr, Stack stack) {
 562             UnaryExpression node = (UnaryExpression)expr;
 563
 564             Debug.Assert(node.NodeType != ExpressionType.Quote, "unexpected Quote");
 565             Debug.Assert(node.NodeType != ExpressionType.Throw, "unexpected Throw");
 566
 567             // Operand is emitted on top of the stack as is
 568             Result expression = RewriteExpression(node.Operand, stack);
 569
 570             if (expression.Action == RewriteAction.SpillStack) {
 571                 RequireNoRefArgs(node.Method);
 572             }
 573
 574             if (expression.Action != RewriteAction.None) {
 575                 expr = new UnaryExpression(node.NodeType, expression.Node, node.Type, node.Method);
 576             }
 577             return new Result(expression.Action, expr);
 578         }
 579
 580         // RewriteListInitExpression
 581         private Result RewriteListInitExpression(Expression expr, Stack stack) {
 582             ListInitExpression node = (ListInitExpression)expr;
 583
 584             //ctor runs on initial stack
 585             Result newResult = RewriteExpression(node.NewExpression, stack);
 586             Expression rewrittenNew = newResult.Node;
 587             RewriteAction action = newResult.Action;
 588
 589             ReadOnlyCollection<ElementInit> inits = node.Initializers;
 590
 591             ChildRewriter[] cloneCrs = new ChildRewriter[inits.Count];
 592
 593             for (int i = 0; i < inits.Count; i++) {
 594                 ElementInit init = inits[i];
 595
 596                 //initializers all run on nonempty stack
 597                 ChildRewriter cr = new ChildRewriter(this, Stack.NonEmpty, init.Arguments.Count);
 598                 cr.Add(init.Arguments);
 599
 600                 action |= cr.Action;
 601                 cloneCrs[i] = cr;
 602             }
 603
 604             switch (action) {
 605                 case RewriteAction.None:
 606                     break;
 607                 case RewriteAction.Copy:
 608                     ElementInit[] newInits = new ElementInit[inits.Count];
 609                     for (int i = 0; i < inits.Count; i++) {
 610                         ChildRewriter cr = cloneCrs[i];
 611                         if (cr.Action == RewriteAction.None) {
 612                             newInits[i] = inits[i];
 613                         } else {
 614                             newInits[i] = Expression.ElementInit(inits[i].AddMethod, cr[0, -1]);
 615                         }
 616                     }
 617                     expr = Expression.ListInit((NewExpression)rewrittenNew, new TrueReadOnlyCollection<ElementInit>(newInits));
 618                     break;
 619                 case RewriteAction.SpillStack:
 620                     RequireNotRefInstance(node.NewExpression);
 621
 622                     ParameterExpression tempNew = MakeTemp(rewrittenNew.Type);
 623                     Expression[] comma = new Expression[inits.Count + 2];
 624                     comma[0] = Expression.Assign(tempNew, rewrittenNew);
 625
 626                     for (int i = 0; i < inits.Count; i++) {
 627                         ChildRewriter cr = cloneCrs[i];
 628                         Result add = cr.Finish(Expression.Call(tempNew, inits[i].AddMethod, cr[0, -1]));
 629                         comma[i + 1] = add.Node;
 630                     }
 631                     comma[inits.Count + 1] = tempNew;
 632                     expr = MakeBlock(comma);
 633                     break;
 634                 default:
 635                     throw ContractUtils.Unreachable;
 636             }
 637
 638             return new Result(action, expr);
 639         }
 640
 641         // RewriteMemberInitExpression
 642         private Result RewriteMemberInitExpression(Expression expr, Stack stack) {
 643             MemberInitExpression node = (MemberInitExpression)expr;
 644
 645             //ctor runs on original stack
 646             Result result = RewriteExpression(node.NewExpression, stack);
 647             Expression rewrittenNew = result.Node;
 648             RewriteAction action = result.Action;
 649
 650             ReadOnlyCollection<MemberBinding> bindings = node.Bindings;
 651             BindingRewriter[] bindingRewriters = new BindingRewriter[bindings.Count];
 652             for (int i = 0; i < bindings.Count; i++) {
 653                 MemberBinding binding = bindings[i];
 654                 //bindings run on nonempty stack
 655                 BindingRewriter rewriter = BindingRewriter.Create(binding, this, Stack.NonEmpty);
 656                 bindingRewriters[i] = rewriter;
 657                 action |= rewriter.Action;
 658             }
 659
 660             switch (action) {
 661                 case RewriteAction.None:
 662                     break;
 663                 case RewriteAction.Copy:
 664                     MemberBinding[] newBindings = new MemberBinding[bindings.Count];
 665                     for (int i = 0; i < bindings.Count; i++) {
 666                         newBindings[i] = bindingRewriters[i].AsBinding();
 667                     }
 668                     expr = Expression.MemberInit((NewExpression)rewrittenNew, new TrueReadOnlyCollection<MemberBinding>(newBindings));
 669                     break;
 670                 case RewriteAction.SpillStack:
 671                     RequireNotRefInstance(node.NewExpression);
 672
 673                     ParameterExpression tempNew = MakeTemp(rewrittenNew.Type);
 674                     Expression[] comma = new Expression[bindings.Count + 2];
 675                     comma[0] = Expression.Assign(tempNew, rewrittenNew);
 676                     for (int i = 0; i < bindings.Count; i++) {
 677                         BindingRewriter cr = bindingRewriters[i];
 678                         Expression initExpr = cr.AsExpression(tempNew);
 679                         comma[i + 1] = initExpr;
 680                     }
 681                     comma[bindings.Count + 1] = tempNew;
 682                     expr = MakeBlock(comma);
 683                     break;
 684                 default:
 685                     throw ContractUtils.Unreachable;
 686             }
 687             return new Result(action, expr);
 688         }
 689
 690         #endregion
 691
 692         #region Statements
 693
 694         // Block
 695         private Result RewriteBlockExpression(Expression expr, Stack stack) {
 696             BlockExpression node = (BlockExpression)expr;
 697
 698             int count = node.ExpressionCount;
 699             RewriteAction action = RewriteAction.None;
 700             Expression[] clone = null;
 701             for (int i = 0; i < count; i++) {
 702                 Expression expression = node.GetExpression(i);
 703                 // All statements within the block execute at the
 704                 // same stack state.
 705                 Result rewritten = RewriteExpression(expression, stack);
 706                 action |= rewritten.Action;
 707
 708                 if (clone == null && rewritten.Action != RewriteAction.None) {
 709                     clone = Clone(node.Expressions, i);
 710                 }
 711
 712                 if (clone != null) {
 713                     clone[i] = rewritten.Node;
 714                 }
 715             }
 716
 717             if (action != RewriteAction.None) {
 718                 // okay to wrap since we know no one can mutate the clone array
 719                 expr = node.Rewrite(null, clone);
 720             }
 721             return new Result(action, expr);
 722         }
 723
 724         // LabelExpression
 725         private Result RewriteLabelExpression(Expression expr, Stack stack) {
 726             LabelExpression node = (LabelExpression)expr;
 727
 728             Result expression = RewriteExpression(node.DefaultValue, stack);
 729             if (expression.Action != RewriteAction.None) {
 730                 expr = Expression.Label(node.Target, expression.Node);
 731             }
 732             return new Result(expression.Action, expr);
 733         }
 734
 735         // LoopStatement
 736         private Result RewriteLoopExpression(Expression expr, Stack stack) {
 737             LoopExpression node = (LoopExpression)expr;
 738
 739             // The loop statement requires empty stack for itself, so it
 740             // can guarantee it to the child nodes.
 741             Result body = RewriteExpression(node.Body, Stack.Empty);
 742
 743             RewriteAction action = body.Action;
 744
 745             // However, the loop itself requires that it executes on an empty stack
 746             // so we need to rewrite if the stack is not empty.
 747             if (stack != Stack.Empty) {
 748                 action = RewriteAction.SpillStack;
 749             }
 750
 751             if (action != RewriteAction.None) {
 752                 expr = new LoopExpression(body.Node, node.BreakLabel, node.ContinueLabel);
 753             }
 754             return new Result(action, expr);
 755         }
 756
 757         // GotoExpression
 758         // Note: goto does not necessarily need an empty stack. We could always
 759         // emit it as a "leave" which would clear the stack for us. That would
 760         // prevent us from doing certain optimizations we might want to do,
 761         // however, like the switch-case-goto pattern. For now, be conservative
 762         private Result RewriteGotoExpression(Expression expr, Stack stack) {
 763             GotoExpression node = (GotoExpression)expr;
 764
 765             // Goto requires empty stack to execute so the expression is
 766             // going to execute on an empty stack.
 767             Result value = RewriteExpressionFreeTemps(node.Value, Stack.Empty);
 768
 769             // However, the statement itself needs an empty stack for itself
 770             // so if stack is not empty, rewrite to empty the stack.
 771             RewriteAction action = value.Action;
 772             if (stack != Stack.Empty) {
 773                 action = RewriteAction.SpillStack;
 774             }
 775
 776             if (action != RewriteAction.None) {
 777                 expr = Expression.MakeGoto(node.Kind, node.Target, value.Node, node.Type);
 778             }
 779             return new Result(action, expr);
 780         }
 781
 782         // SwitchStatement
 783         private Result RewriteSwitchExpression(Expression expr, Stack stack) {
 784             SwitchExpression node = (SwitchExpression)expr;
 785
 786             // The switch statement test is emitted on the stack in current state
 787             Result switchValue = RewriteExpressionFreeTemps(node.SwitchValue, stack);
 788
 789             RewriteAction action = switchValue.Action;
 790             ReadOnlyCollection<SwitchCase> cases = node.Cases;
 791             SwitchCase[] clone = null;
 792             for (int i = 0; i < cases.Count; i++) {
 793                 SwitchCase @case = cases[i];
 794
 795                 Expression[] cloneTests = null;
 796                 ReadOnlyCollection<Expression> testValues = @case.TestValues;
 797                 for (int j = 0; j < testValues.Count; j++) {
 798                     // All tests execute at the same stack state as the switch.
 799                     // This is guarenteed by the compiler (to simplify spilling)
 800                     Result test = RewriteExpression(testValues[j], stack);
 801                     action |= test.Action;
 802
 803                     if (cloneTests == null && test.Action != RewriteAction.None) {
 804                         cloneTests = Clone(testValues, j);
 805                     }
 806
 807                     if (cloneTests != null) {
 808                         cloneTests[j] = test.Node;
 809                     }
 810                 }
 811
 812                 // And all the cases also run on the same stack level.
 813                 Result body = RewriteExpression(@case.Body, stack);
 814                 action |= body.Action;
 815
 816                 if (body.Action != RewriteAction.None || cloneTests != null) {
 817                     if (cloneTests != null) {
 818                         testValues = new ReadOnlyCollection<Expression>(cloneTests);
 819                     }
 820                     @case = new SwitchCase(body.Node, testValues);
 821
 822                     if (clone == null) {
 823                         clone = Clone(cases, i);
 824                     }
 825                 }
 826
 827                 if (clone != null) {
 828                     clone[i] = @case;
 829                 }
 830             }
 831
 832             // default body also runs on initial stack
 833             Result defaultBody = RewriteExpression(node.DefaultBody, stack);
 834             action |= defaultBody.Action;
 835
 836             if (action != RewriteAction.None) {
 837                 if (clone != null) {
 838                     // okay to wrap because we aren't modifying the array
 839                     cases = new ReadOnlyCollection<SwitchCase>(clone);
 840                 }
 841
 842                 expr = new SwitchExpression(node.Type, switchValue.Node, defaultBody.Node, node.Comparison, cases);
 843             }
 844
 845             return new Result(action, expr);
 846         }
 847
 848         // TryStatement
 849         private Result RewriteTryExpression(Expression expr, Stack stack) {
 850             TryExpression node = (TryExpression)expr;
 851
 852             // Try statement definitely needs an empty stack so its
 853             // child nodes execute at empty stack.
 854             Result body = RewriteExpression(node.Body, Stack.Empty);
 855             ReadOnlyCollection<CatchBlock> handlers = node.Handlers;
 856             CatchBlock[] clone = null;
 857
 858             RewriteAction action = body.Action;
 859             if (handlers != null) {
 860                 for (int i = 0; i < handlers.Count; i++) {
 861                     RewriteAction curAction = body.Action;
 862
 863                     CatchBlock handler = handlers[i];
 864
 865                     Expression filter = handler.Filter;
 866                     if (handler.Filter != null) {
 867                         // our code gen saves the incoming filter value and provides it as a varaible so the stack is empty
 868                         Result rfault = RewriteExpression(handler.Filter, Stack.Empty);
 869                         action |= rfault.Action;
 870                         curAction |= rfault.Action;
 871                         filter = rfault.Node;
 872                     }
 873
 874                     // Catch block starts with an empty stack (guaranteed by TryStatement)
 875                     Result rbody = RewriteExpression(handler.Body, Stack.Empty);
 876                     action |= rbody.Action;
 877                     curAction |= rbody.Action;
 878
 879                     if (curAction != RewriteAction.None) {
 880                         handler = Expression.MakeCatchBlock(handler.Test, handler.Variable, rbody.Node, filter);
 881
 882                         if (clone == null) {
 883                             clone = Clone(handlers, i);
 884                         }
 885                     }
 886
 887                     if (clone != null) {
 888                         clone[i] = handler;
 889                     }
 890                 }
 891             }
 892
 893             Result fault = RewriteExpression(node.Fault, Stack.Empty);
 894             action |= fault.Action;
 895
 896             Result @finally = RewriteExpression(node.Finally, Stack.Empty);
 897             action |= @finally.Action;
 898
 899             // If the stack is initially not empty, rewrite to spill the stack
 900             if (stack != Stack.Empty) {
 901                 action = RewriteAction.SpillStack;
 902             }
 903
 904             if (action != RewriteAction.None) {
 905                 if (clone != null) {
 906                     // okay to wrap because we aren't modifying the array
 907                     handlers = new ReadOnlyCollection<CatchBlock>(clone);
 908                 }
 909
 910                 expr = new TryExpression(node.Type, body.Node, @finally.Node, fault.Node, handlers);
 911             }
 912             return new Result(action, expr);
 913         }
 914
 915         private Result RewriteExtensionExpression(Expression expr, Stack stack) {
 916             Result result = RewriteExpression(expr.ReduceExtensions(), stack);
 917             // it's at least Copy because we reduced the node
 918             return new Result(result.Action | RewriteAction.Copy, result.Node);
 919         }
 920
 921         #endregion
 922
 923         #region Cloning
 924
 925         /// <summary>
 926         /// Will clone an IList into an array of the same size, and copy
 927         /// all vaues up to (and NOT including) the max index
 928         /// </summary>
 929         /// <returns>The cloned array.</returns>
 930         private static T[] Clone<T>(ReadOnlyCollection<T> original, int max) {
 931             Debug.Assert(original != null);
 932             Debug.Assert(max < original.Count);
 933
 934             T[] clone = new T[original.Count];
 935             for (int j = 0; j < max; j++) {
 936                 clone[j] = original[j];
 937             }
 938             return clone;
 939         }
 940
 941         #endregion
 942
 943         /// <summary>
 944         /// If we are spilling, requires that there are no byref arguments to
 945         /// the method call.
 946         ///
 947         /// Used for:
 948         ///   NewExpression,
 949         ///   MethodCallExpression,
 950         ///   InvocationExpression,
 951         ///   DynamicExpression,
 952         ///   UnaryExpression,
 953         ///   BinaryExpression.
 954         /// </summary>
 955         /// <remarks>
 956         /// We could support this if spilling happened later in the compiler.
 957         /// Other expressions that can emit calls with arguments (such as
 958         /// ListInitExpression and IndexExpression) don't allow byref arguments.
 959         /// </remarks>
 960         private static void RequireNoRefArgs(MethodBase method) {
 961             if (method != null && method.GetParametersCached().Any(p => p.ParameterType.IsByRef)) {
 962                 throw Error.TryNotSupportedForMethodsWithRefArgs(method);
 963             }
 964         }
 965
 966         /// <summary>
 967         /// Requires that the instance is not a value type (primitive types are
 968         /// okay because they're immutable).
 969         ///
 970         /// Used for:
 971         ///  MethodCallExpression,
 972         ///  MemberExpression (for properties),
 973         ///  IndexExpression,
 974         ///  ListInitExpression,
 975         ///  MemberInitExpression,
 976         ///  assign to MemberExpression,
 977         ///  assign to IndexExpression.
 978         /// </summary>
 979         /// <remarks>
 980         /// We could support this if spilling happened later in the compiler.
 981         /// </remarks>
 982         private static void RequireNotRefInstance(Expression instance) {
 983             // Primitive value types are okay because they are all readonly,
 984             // but we can't rely on this for non-primitive types. So we throw
 985             // NotSupported.
 986             if (instance != null && instance.Type.IsValueType && Type.GetTypeCode(instance.Type) == TypeCode.Object) {
 987                 throw Error.TryNotSupportedForValueTypeInstances(instance.Type);
 988             }
 989         }
 990     }
 991 }