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