1 // Licensed to the .NET Foundation under one or more agreements. 2 // The .NET Foundation licenses this file to you under the MIT license. 3 // See the LICENSE file in the project root for more information. 4 5 using System.Collections.Generic; 6 using System.Collections.ObjectModel; 7 using System.Diagnostics; 8 using System.Dynamic.Utils; 9 using System.Reflection; 10 11 namespace System.Linq.Expressions.Compiler 12 { 13 internal partial class StackSpiller 14 { 15 /// <summary> 16 /// Rewrites child expressions, spilling them into temps if needed. The 17 /// stack starts in the initial state, and after the first subexpression 18 /// is added it is changed to non-empty. 19 /// 20 /// When all children have been added, the caller should rewrite the 21 /// node if Rewrite is true. Then, it should call Finish with either 22 /// the original expression or the rewritten expression. Finish will call 23 /// Expression.Block if necessary and return a new Result. 24 /// </summary> 25 private sealed class ChildRewriter 26 { 27 /// <summary> 28 /// The parent stack spiller, used to perform rewrites of expressions 29 /// and to allocate temporary variables. 30 /// </summary> 31 private readonly StackSpiller _self; 32 33 /// <summary> 34 /// The child expressions being rewritten. 35 /// </summary> 36 private readonly Expression[] _expressions; 37 38 /// <summary> 39 /// The index of the next expression to rewrite in <see cref="_expressions"/>. 40 /// </summary> 41 private int _expressionsCount; 42 43 /// <summary> 44 /// The index of the last expression that requires a SpillStack action. 45 /// </summary> 46 private int _lastSpillIndex; 47 48 /// <summary> 49 /// The comma of expressions that will evaluate the parent expression 50 /// using temporary variables introduced by stack spilling. This field 51 /// is populated in <see cref="EnsureDone"/> which gets called upon 52 /// the first access to an indexer or the <see cref="Rewrite"/> method 53 /// on the child rewriter instance. A comma only gets built if the 54 /// rewrite action in <see cref="_action"/> is set to SpillStack. 55 /// </summary> 56 /// <example> 57 /// When stack spilling the following expression: 58 /// <c> 59 /// bar.Foo(try { 42 } finally { ; }) 60 /// </c> 61 /// the resulting comma will contain three expressions: 62 /// <c> 63 /// $temp$0 = bar 64 /// $temp$1 = try { 42 } finally { ; } 65 /// $temp$0.Foo($temp$1) 66 /// </c> 67 /// These get wrapped in a Block in the <see cref="Rewrite"/> method. 68 /// </example> 69 private List<Expression> _comma; 70 71 /// <summary> 72 /// The current computed rewrite action, obtained by OR-ing together 73 /// the rewrite actions returned from rewriting the child expressions 74 /// in calls to <see cref="Add"/>. 75 /// </summary> 76 private RewriteAction _action; 77 78 /// <summary> 79 /// The current computed evaluation stack state. After adding the first 80 /// child expression through <see cref="Add"/>, the state changes from 81 /// the initial state (provided to the constructor) to non-empty. 82 /// </summary> 83 private Stack _stack; 84 85 /// <summary> 86 /// Indicates whether the rewrite has completed. This flag is toggled 87 /// upon the first access to an indexer or the <see cref="Finish"/> 88 /// method on the child rewriter instance. Once set to <c>true</c>, 89 /// calls to <see cref="Add"/> are no longer allowed. 90 /// </summary> 91 private bool _done; 92 93 /// <summary> 94 /// Indicates whether a child expression represents a ByRef value and 95 /// requires use of a <see cref="ByRefAssignBinaryExpression" /> node 96 /// to perform spilling. 97 /// </summary> 98 private bool[] _byRefs; 99 100 /// <summary> 101 /// Creates a new child rewriter instance using the specified initial 102 /// evaluation <see cref="stack"/> state and the number of child 103 /// expressions specified in <see cref="count"/>. 104 /// </summary> 105 /// <param name="self">The parent stack spiller.</param> 106 /// <param name="stack">The initial evaluation stack state.</param> 107 /// <param name="count">The number of child expressions that will be added.</param> ChildRewriter(StackSpiller self, Stack stack, int count)108 internal ChildRewriter(StackSpiller self, Stack stack, int count) 109 { 110 _self = self; 111 _stack = stack; 112 _expressions = new Expression[count]; 113 } 114 115 /// <summary> 116 /// Adds a child <paramref name="expression"/> to the rewriter, causing 117 /// it to be rewritten using the parent stack spiller, and the evaluation 118 /// stack state and rewrite action to be updated accordingly. 119 /// </summary> 120 /// <param name="expression">The child expression to add.</param> Add(Expression expression)121 internal void Add(Expression expression) 122 { 123 Debug.Assert(!_done); 124 125 if (expression == null) 126 { 127 _expressions[_expressionsCount++] = null; 128 return; 129 } 130 131 Result exp = _self.RewriteExpression(expression, _stack); 132 _action |= exp.Action; 133 _stack = Stack.NonEmpty; 134 135 if (exp.Action == RewriteAction.SpillStack) 136 { 137 _lastSpillIndex = _expressionsCount; 138 } 139 140 // Track items in case we need to copy or spill stack. 141 _expressions[_expressionsCount++] = exp.Node; 142 } 143 144 /// <summary> 145 /// Adds child <paramref name="expressions"/> to the rewriter, causing 146 /// them to be rewritten using the parent stack spiller, and the evaluation 147 /// stack state and rewrite action to be updated accordingly. 148 /// </summary> 149 /// <param name="expressions">The child expressions to add.</param> Add(ReadOnlyCollection<Expression> expressions)150 internal void Add(ReadOnlyCollection<Expression> expressions) 151 { 152 for (int i = 0, count = expressions.Count; i < count; i++) 153 { 154 Add(expressions[i]); 155 } 156 } 157 158 /// <summary> 159 /// Adds child <paramref name="expressions"/> provided through an argument 160 /// provider to the rewriter, causing them to be rewritten using the parent 161 /// stack spiller, and the evaluation stack state and rewrite action to be 162 /// updated accordingly. 163 /// </summary> 164 /// <param name="expressions"> 165 /// The argument provider containing the child expression to add. 166 /// </param> AddArguments(IArgumentProvider expressions)167 internal void AddArguments(IArgumentProvider expressions) 168 { 169 for (int i = 0, count = expressions.ArgumentCount; i < count; i++) 170 { 171 Add(expressions.GetArgument(i)); 172 } 173 } 174 175 /// <summary> 176 /// Called after all child expressions have been added using <see cref="Add"/> 177 /// invocations, causing the comma to be populated with the rewritten child 178 /// expressions and necessary assignments to temporary variables. A comma is 179 /// only built when the rewrite action is <see cref="RewriteAction.SpillStack"/>. 180 /// </summary> 181 /// <example> 182 /// When stack spilling the following expression: 183 /// <c> 184 /// bar.Foo(try { 42 } finally { ; }) 185 /// </c> 186 /// this method will populate the comma with the rewritten child expressions: 187 /// <c> 188 /// $temp$0 = bar 189 /// $temp$1 = try { 42 } finally { ; } 190 /// </c> 191 /// The final expression evaluating <c>bar.Foo(...)</c> will get added by the 192 /// <see cref="Finish"/> method prior to wrapping the comma in a block 193 /// expression. 194 /// </example> EnsureDone()195 private void EnsureDone() 196 { 197 // Done adding child expressions, build the comma if necessary. 198 if (!_done) 199 { 200 _done = true; 201 202 if (_action == RewriteAction.SpillStack) 203 { 204 Expression[] clone = _expressions; 205 int count = _lastSpillIndex + 1; 206 List<Expression> comma = new List<Expression>(count + 1); 207 for (int i = 0; i < count; i++) 208 { 209 Expression current = clone[i]; 210 if (ShouldSaveToTemp(current)) 211 { 212 Expression temp; 213 clone[i] = _self.ToTemp(current, out temp, _byRefs?[i] ?? false); 214 comma.Add(temp); 215 } 216 } 217 comma.Capacity = comma.Count + 1; 218 _comma = comma; 219 } 220 } 221 } 222 223 /// <summary> 224 /// Checks whether the given <paramref name="expression"/> representing a 225 /// child expression should be saved in a temporary variable upon spilling 226 /// the stack. If the expression has no have side-effects, the introduction 227 /// of a temporary variable can be avoided, reducing the number of locals. 228 /// </summary> 229 /// <param name="expression">The expression to check for side-effects.</param> 230 /// <returns> 231 /// <c>true</c> if the expression should be saved to a temporary variable; 232 /// otherwise, <c>false</c>. 233 /// </returns> ShouldSaveToTemp(Expression expression)234 private static bool ShouldSaveToTemp(Expression expression) 235 { 236 if (expression == null) 237 return false; 238 239 // Some expressions have no side-effects and don't have to be 240 // stored into temporaries, e.g. 241 // 242 // xs[0] = try { ... } 243 // | 244 // v 245 // t0 = xs 246 // t1 = 0 // <-- this is redundant 247 // t2 = try { ... } 248 // t0[t1] = t2 249 // | 250 // v 251 // t0 = xs 252 // t1 = try { ... } 253 // t0[0] = t1 254 255 switch (expression.NodeType) 256 { 257 // Emits ldnull, ldc, initobj, closure constant access, etc. 258 case ExpressionType.Constant: 259 case ExpressionType.Default: 260 return false; 261 262 // Emits calls to pure RuntimeOps methods with immutable arguments 263 case ExpressionType.RuntimeVariables: 264 return false; 265 266 case ExpressionType.MemberAccess: 267 var member = (MemberExpression)expression; 268 var field = member.Member as FieldInfo; 269 if (field != null) 270 { 271 // Emits ldc for the raw value of the field 272 if (field.IsLiteral) 273 return false; 274 275 // For read-only fields we could save the receiver, but 276 // that's more involved, so we'll just handle static fields 277 if (field.IsInitOnly && field.IsStatic) 278 return false; 279 } 280 break; 281 } 282 283 // NB: We omit Lambda because it may interfere with the Invoke/Lambda 284 // inlining optimizations. Parameter is out too because we don't 285 // have any sophisticated load/store analysis. 286 287 // NB: We omit Quote because the emitted call to RuntimeOps.Quote will 288 // trigger reduction of extension nodes which can cause the timing 289 // of exceptions thrown from Reduce methods to change. 290 291 return true; 292 } 293 294 /// <summary> 295 /// Gets a Boolean value indicating whether the parent expression should be 296 /// rewritten by using <see cref="Finish"/>. 297 /// </summary> 298 internal bool Rewrite => _action != RewriteAction.None; 299 300 /// <summary> 301 /// Gets the rewrite action computed from rewriting child expressions during 302 /// calls to <see cref="Add"/>. 303 /// </summary> 304 internal RewriteAction Action => _action; 305 306 /// <summary> 307 /// Marks the child expression representing the instance as a ByRef value. 308 /// </summary> 309 /// <param name="expression"> 310 /// The child expression representing the instance. 311 /// </param> MarkRefInstance(Expression expr)312 internal void MarkRefInstance(Expression expr) 313 { 314 if (IsRefInstance(expr)) 315 { 316 MarkRef(0); 317 } 318 } 319 320 /// <summary> 321 /// Marks child expressions representing arguments bound to parameters of 322 /// the specified <paramref name="method"/> as ByRef values if needed. 323 /// </summary> 324 /// <param name="method"> 325 /// The method containing the parameters bound to the arguments held by 326 /// child expressions tracked by this rewriter. 327 /// </param> 328 /// <param name="startIndex"> 329 /// The index of the child expression representing the first argument. This 330 /// value is typically 0 for static methods and 1 for instance methods. 331 /// </param> MarkRefArgs(MethodBase method, int startIndex)332 internal void MarkRefArgs(MethodBase method, int startIndex) 333 { 334 var parameters = method.GetParametersCached(); 335 336 for (int i = 0, n = parameters.Length; i < n; i++) 337 { 338 if (parameters[i].ParameterType.IsByRef) 339 { 340 MarkRef(startIndex + i); 341 } 342 } 343 } 344 345 /// <summary> 346 /// Marks the child expression in at the specified <paramref name="index"/> 347 /// as having a ByRef value. 348 /// </summary> 349 /// <param name="index"> 350 /// The index of the child expression holding a ByRef value. 351 /// </param> MarkRef(int index)352 private void MarkRef(int index) 353 { 354 if (_byRefs == null) 355 { 356 _byRefs = new bool[_expressions.Length]; 357 } 358 359 _byRefs[index] = true; 360 } 361 362 /// <summary> 363 /// Rewrites the parent <paramref name="expression"/> where any stack spilled 364 /// child expressions have been substituted for temporary variables, and returns 365 /// the rewrite result to the caller. 366 /// </summary> 367 /// <param name="expression"> 368 /// The parent expression after substituting stack spilled child expressions 369 /// for temporary variables using the indexers on the child rewriter. 370 /// </param> 371 /// <returns> 372 /// The result of rewriting the parent <paramref name="expression"/>, which 373 /// includes the rewritten expression and the rewrite action. If stack spilling 374 /// has taken place, the resulting expression is a block expression containing 375 /// the expressions kept in <see cref="_comma"/>. 376 /// </returns> Finish(Expression expression)377 internal Result Finish(Expression expression) 378 { 379 EnsureDone(); 380 381 if (_action == RewriteAction.SpillStack) 382 { 383 Debug.Assert(_comma.Capacity == _comma.Count + 1); 384 _comma.Add(expression); 385 expression = MakeBlock(_comma); 386 } 387 388 return new Result(_action, expression); 389 } 390 391 /// <summary> 392 /// Gets the rewritten child expression at the specified <paramref name="index"/>, 393 /// used to rewrite the parent expression. In case stack spilling has taken place, 394 /// the returned expression will be a temporary variable. 395 /// </summary> 396 /// <param name="index"> 397 /// The index of the child expression to retrieve. Negative values indicate -1-based 398 /// offsets from the end of the child expressions array. Positive values indicate 399 /// 0-based offsets from the start of the child expressions array. 400 /// </param> 401 /// <returns> 402 /// The rewritten child expression at the specified <paramref name="index"/>. 403 /// </returns> 404 internal Expression this[int index] 405 { 406 get 407 { 408 EnsureDone(); 409 410 if (index < 0) 411 { 412 index += _expressions.Length; 413 } 414 415 return _expressions[index]; 416 } 417 } 418 419 /// <summary> 420 /// Gets the rewritten child expressions between the specified <paramref name="first"/> 421 /// and <paramref name="last"/> (inclusive) indexes, used to rewrite the parent 422 /// expression. In case stack spilling has taken place, the returned expressions will 423 /// contain temporary variables. 424 /// </summary> 425 /// <param name="first"> 426 /// The index of the first child expression to retrieve. This value should always be 427 /// positive. 428 /// </param> 429 /// <param name="last"> 430 /// The (inclusive) index of the last child expression to retrieve. Negative values 431 /// indicate -1-based offsets from the end of the child expressions array. Positive values 432 /// indicate 0-based offsets from the start of the child expressions array. 433 /// </param> 434 /// <returns> 435 /// The rewritten child expressions between the specified <paramref name="first"/> 436 /// and <paramref name="last"/> (inclusive) indexes. 437 /// </returns> 438 internal Expression[] this[int first, int last] 439 { 440 get 441 { 442 EnsureDone(); 443 444 if (last < 0) 445 { 446 last += _expressions.Length; 447 } 448 449 int count = last - first + 1; 450 ContractUtils.RequiresArrayRange(_expressions, first, count, nameof(first), nameof(last)); 451 452 if (count == _expressions.Length) 453 { 454 Debug.Assert(first == 0); 455 456 // If the entire array is requested just return it so we don't make a new array. 457 return _expressions; 458 } 459 460 Expression[] clone = new Expression[count]; 461 Array.Copy(_expressions, first, clone, 0, count); 462 return clone; 463 } 464 } 465 } 466 } 467 } 468