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