1 /* ****************************************************************************
3 * Copyright (c) Microsoft Corporation.
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.
11 * You must not remove this notice, or any other, from this software.
14 * ***************************************************************************/
17 using System.Collections.Generic;
18 using System.Collections.ObjectModel;
19 using System.Diagnostics;
20 using System.Dynamic.Utils;
23 namespace Microsoft.Scripting.Ast.Compiler {
25 namespace System.Linq.Expressions.Compiler {
28 internal partial class StackSpiller {
30 private class TempMaker {
32 /// Current temporary variable
37 /// List of free temporary variables. These can be recycled for new temps.
39 private List<ParameterExpression> _freeTemps;
42 /// Stack of currently active temporary variables.
44 private Stack<ParameterExpression> _usedTemps;
47 /// List of all temps created by stackspiller for this rule/lambda
49 private List<ParameterExpression> _temps = new List<ParameterExpression>();
51 internal List<ParameterExpression> Temps {
52 get { return _temps; }
55 internal ParameterExpression Temp(Type type) {
56 ParameterExpression temp;
57 if (_freeTemps != null) {
58 // Recycle from the free-list if possible.
59 for (int i = _freeTemps.Count - 1; i >= 0; i--) {
61 if (temp.Type == type) {
62 _freeTemps.RemoveAt(i);
67 // Not on the free-list, create a brand new one.
68 temp = Expression.Variable(type, "$temp$" + _temp++);
73 private ParameterExpression UseTemp(ParameterExpression temp) {
74 Debug.Assert(_freeTemps == null || !_freeTemps.Contains(temp));
75 Debug.Assert(_usedTemps == null || !_usedTemps.Contains(temp));
77 if (_usedTemps == null) {
78 _usedTemps = new Stack<ParameterExpression>();
80 _usedTemps.Push(temp);
84 private void FreeTemp(ParameterExpression temp) {
85 Debug.Assert(_freeTemps == null || !_freeTemps.Contains(temp));
86 if (_freeTemps == null) {
87 _freeTemps = new List<ParameterExpression>();
93 return _usedTemps != null ? _usedTemps.Count : 0;
96 // Free temporaries created since the last marking.
97 // This is a performance optimization to lower the overall number of tempories needed.
98 internal void Free(int mark) {
99 // (_usedTemps != null) ==> (mark <= _usedTemps.Count)
100 Debug.Assert(_usedTemps == null || mark <= _usedTemps.Count);
101 // (_usedTemps == null) ==> (mark == 0)
102 Debug.Assert(mark == 0 || _usedTemps != null);
104 if (_usedTemps != null) {
105 while (mark < _usedTemps.Count) {
106 FreeTemp(_usedTemps.Pop());
111 [Conditional("DEBUG")]
112 [System.Diagnostics.CodeAnalysis.SuppressMessage("Microsoft.Performance", "CA1822:MarkMembersAsStatic")]
113 internal void VerifyTemps() {
114 Debug.Assert(_usedTemps == null || _usedTemps.Count == 0);
120 /// Rewrites child expressions, spilling them into temps if needed. The
121 /// stack starts in the inital state, and after the first subexpression
122 /// is added it is change to non-empty. This behavior can be overridden
123 /// by setting the stack manually between adds.
125 /// When all children have been added, the caller should rewrite the
126 /// node if Rewrite is true. Then, it should call Finish with etiher
127 /// the orignal expression or the rewritten expression. Finish will call
128 /// Expression.Comma if necessary and return a new Result.
130 private class ChildRewriter {
131 private readonly StackSpiller _self;
132 private readonly Expression[] _expressions;
133 private int _expressionsCount;
134 private List<Expression> _comma;
135 private RewriteAction _action;
136 private Stack _stack;
139 internal ChildRewriter(StackSpiller self, Stack stack, int count) {
142 _expressions = new Expression[count];
145 internal void Add(Expression node) {
146 Debug.Assert(!_done);
149 _expressions[_expressionsCount++] = null;
153 Result exp = _self.RewriteExpression(node, _stack);
154 _action |= exp.Action;
155 _stack = Stack.NonEmpty;
157 // track items in case we need to copy or spill stack
158 _expressions[_expressionsCount++] = exp.Node;
161 internal void Add(IList<Expression> expressions) {
162 for (int i = 0, count = expressions.Count; i < count; i++) {
167 internal void AddArguments(IArgumentProvider expressions) {
168 for (int i = 0, count = expressions.ArgumentCount; i < count; i++) {
169 Add(expressions.GetArgument(i));
173 private void EnsureDone() {
174 // done adding arguments, build the comma if necessary
178 if (_action == RewriteAction.SpillStack) {
179 Expression[] clone = _expressions;
180 int count = clone.Length;
181 List<Expression> comma = new List<Expression>(count + 1);
182 for (int i = 0; i < count; i++) {
183 if (clone[i] != null) {
185 clone[i] = _self.ToTemp(clone[i], out temp);
189 comma.Capacity = comma.Count + 1;
195 internal bool Rewrite {
196 get { return _action != RewriteAction.None; }
199 internal RewriteAction Action {
200 get { return _action; }
203 internal Result Finish(Expression expr) {
206 if (_action == RewriteAction.SpillStack) {
207 Debug.Assert(_comma.Capacity == _comma.Count + 1);
209 expr = MakeBlock(_comma);
212 return new Result(_action, expr);
215 internal Expression this[int index] {
219 index += _expressions.Length;
221 return _expressions[index];
225 internal Expression[] this[int first, int last] {
229 last += _expressions.Length;
231 int count = last - first + 1;
232 ContractUtils.RequiresArrayRange(_expressions, first, count, "first", "last");
234 if (count == _expressions.Length) {
235 Debug.Assert(first == 0);
236 // if the entire array is requested just return it so we don't make a new array
240 Expression[] clone = new Expression[count];
241 Array.Copy(_expressions, first, clone, 0, count);
248 private ParameterExpression MakeTemp(Type type) {
249 return _tm.Temp(type);
256 private void Free(int mark) {
260 [Conditional("DEBUG")]
261 [System.Diagnostics.CodeAnalysis.SuppressMessage("Microsoft.Performance", "CA1822:MarkMembersAsStatic")]
262 private void VerifyTemps() {
268 /// save: temp = expression
269 /// return value: temp
271 private ParameterExpression ToTemp(Expression expression, out Expression save) {
272 ParameterExpression temp = MakeTemp(expression.Type);
273 save = Expression.Assign(temp, expression);
278 /// Creates a special block that is marked as not allowing jumps in.
279 /// This should not be used for rewriting BlockExpression itself, or
280 /// anything else that supports jumping.
282 private static Expression MakeBlock(params Expression[] expressions) {
283 return MakeBlock((IList<Expression>)expressions);
287 /// Creates a special block that is marked as not allowing jumps in.
288 /// This should not be used for rewriting BlockExpression itself, or
289 /// anything else that supports jumping.
291 private static Expression MakeBlock(IList<Expression> expressions) {
292 return new SpilledExpressionBlock(expressions);
297 /// A special subtype of BlockExpression that indicates to the compiler
298 /// that this block is a spilled expression and should not allow jumps in.
300 internal sealed class SpilledExpressionBlock : BlockN {
301 internal SpilledExpressionBlock(IList<Expression> expressions)
302 : base(expressions) {
304 internal override BlockExpression Rewrite(ReadOnlyCollection<ParameterExpression> variables, Expression[] args) {
305 throw ContractUtils.Unreachable;