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