mcs/class/dlr/Runtime/Microsoft.Scripting.Core/Compiler/LabelInfo.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.Diagnostics;
  19 using System.Dynamic.Utils;
  20 using System.Reflection.Emit;
  21
  22 #if !FEATURE_CORE_DLR
  23 namespace Microsoft.Scripting.Ast.Compiler {
  24 #else
  25 namespace System.Linq.Expressions.Compiler {
  26 #endif
  27 #if !FEATURE_CORE_DLR || SILVERLIGHT
  28     using ILGenerator = OffsetTrackingILGenerator;
  29 #endif
  30
  31     /// <summary>
  32     /// Contains compiler state corresponding to a LabelTarget
  33     /// See also LabelScopeInfo.
  34     /// </summary>
  35     internal sealed class LabelInfo {
  36         // The tree node representing this label
  37         private readonly LabelTarget _node;
  38
  39         // The IL label, will be mutated if Node is redefined
  40         private Label _label;
  41         private bool _labelDefined;
  42
  43         internal Label Label {
  44             get {
  45                 EnsureLabelAndValue();
  46                 return _label;
  47             }
  48         }
  49
  50         // The local that carries the label's value, if any
  51         private LocalBuilder _value;
  52
  53         // The blocks where this label is defined. If it has more than one item,
  54         // the blocks can't be jumped to except from a child block
  55         private readonly Set<LabelScopeInfo> _definitions = new Set<LabelScopeInfo>();
  56
  57         // Blocks that jump to this block
  58         private readonly List<LabelScopeInfo> _references = new List<LabelScopeInfo>();
  59
  60         // True if this label is the last thing in this block
  61         // (meaning we can emit a direct return)
  62         private readonly bool _canReturn;
  63
  64         // True if at least one jump is across blocks
  65         // If we have any jump across blocks to this label, then the
  66         // LabelTarget can only be defined in one place
  67         private bool _acrossBlockJump;
  68
  69         // Until we have more information, default to a leave instruction,
  70         // which always works. Note: leave spills the stack, so we need to
  71         // ensure that StackSpiller has guarenteed us an empty stack at this
  72         // point. Otherwise Leave and Branch are not equivalent
  73         private OpCode _opCode = OpCodes.Leave;
  74
  75         private readonly ILGenerator _ilg;
  76
  77         internal LabelInfo(ILGenerator il, LabelTarget node, bool canReturn) {
  78             _ilg = il;
  79             _node = node;
  80             _canReturn = canReturn;
  81         }
  82
  83         internal bool CanReturn {
  84             get { return _canReturn; }
  85         }
  86
  87         /// <summary>
  88         /// Indicates if it is legal to emit a "branch" instruction based on
  89         /// currently available information. Call the Reference method before
  90         /// using this property.
  91         /// </summary>
  92         internal bool CanBranch {
  93             get { return _opCode != OpCodes.Leave; }
  94         }
  95
  96         internal void Reference(LabelScopeInfo block) {
  97             _references.Add(block);
  98             if (_definitions.Count > 0) {
  99                 ValidateJump(block);
 100             }
 101         }
 102
 103         // Returns true if the label was successfully defined
 104         // or false if the label is now ambiguous
 105         internal void Define(LabelScopeInfo block) {
 106             // Prevent the label from being shadowed, which enforces cleaner
 107             // trees. Also we depend on this for simplicity (keeping only one
 108             // active IL Label per LabelInfo)
 109             for (LabelScopeInfo j = block; j != null; j = j.Parent) {
 110                 if (j.ContainsTarget(_node)) {
 111                     throw Error.LabelTargetAlreadyDefined(_node.Name);
 112                 }
 113             }
 114
 115             _definitions.Add(block);
 116             block.AddLabelInfo(_node, this);
 117
 118             // Once defined, validate all jumps
 119             if (_definitions.Count == 1) {
 120                 foreach (var r in _references) {
 121                     ValidateJump(r);
 122                 }
 123             } else {
 124                 // Was just redefined, if we had any across block jumps, they're
 125                 // now invalid
 126                 if (_acrossBlockJump) {
 127                     throw Error.AmbiguousJump(_node.Name);
 128                 }
 129                 // For local jumps, we need a new IL label
 130                 // This is okay because:
 131                 //   1. no across block jumps have been made or will be made
 132                 //   2. we don't allow the label to be shadowed
 133                 _labelDefined = false;
 134             }
 135         }
 136
 137         private void ValidateJump(LabelScopeInfo reference) {
 138             // Assume we can do a ret/branch
 139             _opCode = _canReturn ? OpCodes.Ret : OpCodes.Br;
 140
 141             // look for a simple jump out
 142             for (LabelScopeInfo j = reference; j != null; j = j.Parent) {
 143                 if (_definitions.Contains(j)) {
 144                     // found it, jump is valid!
 145                     return;
 146                 }
 147                 if (j.Kind == LabelScopeKind.Finally ||
 148                     j.Kind == LabelScopeKind.Filter) {
 149                     break;
 150                 }
 151                 if (j.Kind == LabelScopeKind.Try ||
 152                     j.Kind == LabelScopeKind.Catch) {
 153                     _opCode = OpCodes.Leave;
 154                 }
 155             }
 156
 157             _acrossBlockJump = true;
 158             if (_node != null && _node.Type != typeof(void)) {
 159                 throw Error.NonLocalJumpWithValue(_node.Name);
 160             }
 161
 162             if (_definitions.Count > 1) {
 163                 throw Error.AmbiguousJump(_node.Name);
 164             }
 165
 166             // We didn't find an outward jump. Look for a jump across blocks
 167             LabelScopeInfo def = _definitions.First();
 168             LabelScopeInfo common = Helpers.CommonNode(def, reference, b => b.Parent);
 169
 170             // Assume we can do a ret/branch
 171             _opCode = _canReturn ? OpCodes.Ret : OpCodes.Br;
 172
 173             // Validate that we aren't jumping across a finally
 174             for (LabelScopeInfo j = reference; j != common; j = j.Parent) {
 175                 if (j.Kind == LabelScopeKind.Finally) {
 176                     throw Error.ControlCannotLeaveFinally();
 177                 }
 178                 if (j.Kind == LabelScopeKind.Filter) {
 179                     throw Error.ControlCannotLeaveFilterTest();
 180                 }
 181                 if (j.Kind == LabelScopeKind.Try ||
 182                     j.Kind == LabelScopeKind.Catch) {
 183                     _opCode = OpCodes.Leave;
 184                 }
 185             }
 186
 187             // Valdiate that we aren't jumping into a catch or an expression
 188             for (LabelScopeInfo j = def; j != common; j = j.Parent) {
 189                 if (!j.CanJumpInto) {
 190                     if (j.Kind == LabelScopeKind.Expression) {
 191                         throw Error.ControlCannotEnterExpression();
 192                     } else {
 193                         throw Error.ControlCannotEnterTry();
 194                     }
 195                 }
 196             }
 197         }
 198
 199         internal void ValidateFinish() {
 200             // Make sure that if this label was jumped to, it is also defined
 201             if (_references.Count > 0 && _definitions.Count == 0) {
 202                 throw Error.LabelTargetUndefined(_node.Name);
 203             }
 204         }
 205
 206         internal void EmitJump() {
 207             // Return directly if we can
 208             if (_opCode == OpCodes.Ret) {
 209                 _ilg.Emit(OpCodes.Ret);
 210             } else {
 211                 StoreValue();
 212                 _ilg.Emit(_opCode, Label);
 213             }
 214         }
 215
 216         private void StoreValue() {
 217             EnsureLabelAndValue();
 218             if (_value != null) {
 219                 _ilg.Emit(OpCodes.Stloc, _value);
 220             }
 221         }
 222
 223         internal void Mark() {
 224             if (_canReturn) {
 225                 // Don't mark return labels unless they were actually jumped to
 226                 // (returns are last so we know for sure if anyone jumped to it)
 227                 if (!_labelDefined) {
 228                     // We don't even need to emit the "ret" because
 229                     // LambdaCompiler does that for us.
 230                     return;
 231                 }
 232
 233                 // Otherwise, emit something like:
 234                 // ret
 235                 // <marked label>:
 236                 // ldloc <value>
 237                 _ilg.Emit(OpCodes.Ret);
 238             } else {
 239
 240                 // For the normal case, we emit:
 241                 // stloc <value>
 242                 // <marked label>:
 243                 // ldloc <value>
 244                 StoreValue();
 245             }
 246             MarkWithEmptyStack();
 247         }
 248
 249         // Like Mark, but assumes the stack is empty
 250         internal void MarkWithEmptyStack() {
 251             _ilg.MarkLabel(Label);
 252             if (_value != null) {
 253                 // We always read the value from a local, because we don't know
 254                 // if there will be a "leave" instruction targeting it ("branch"
 255                 // preserves its stack, but "leave" empties the stack)
 256                 _ilg.Emit(OpCodes.Ldloc, _value);
 257             }
 258         }
 259
 260         private void EnsureLabelAndValue() {
 261             if (!_labelDefined) {
 262                 _labelDefined = true;
 263                 _label = _ilg.DefineLabel();
 264                 if (_node != null && _node.Type != typeof(void)) {
 265                     _value = _ilg.DeclareLocal(_node.Type);
 266                 }
 267             }
 268         }
 269     }
 270
 271     internal enum LabelScopeKind {
 272         // any "statement like" node that can be jumped into
 273         Statement,
 274
 275         // these correspond to the node of the same name
 276         Block,
 277         Switch,
 278         Lambda,
 279         Try,
 280
 281         // these correspond to the part of the try block we're in
 282         Catch,
 283         Finally,
 284         Filter,
 285
 286         // the catch-all value for any other expression type
 287         // (means we can't jump into it)
 288         Expression,
 289     }
 290
 291     //
 292     // Tracks scoping information for LabelTargets. Logically corresponds to a
 293     // "label scope". Even though we have arbitrary goto support, we still need
 294     // to track what kinds of nodes that gotos are jumping through, both to
 295     // emit property IL ("leave" out of a try block), and for validation, and
 296     // to allow labels to be duplicated in the tree, as long as the jumps are
 297     // considered "up only" jumps.
 298     //
 299     // We create one of these for every Expression that can be jumped into, as
 300     // well as creating them for the first expression we can't jump into. The
 301     // "Kind" property indicates what kind of scope this is.
 302     //
 303     internal sealed class LabelScopeInfo {
 304         private Dictionary<LabelTarget, LabelInfo> Labels; // lazily allocated, we typically use this only once every 6th-7th block
 305         internal readonly LabelScopeKind Kind;
 306         internal readonly LabelScopeInfo Parent;
 307
 308         internal LabelScopeInfo(LabelScopeInfo parent, LabelScopeKind kind) {
 309             Parent = parent;
 310             Kind = kind;
 311         }
 312
 313         /// <summary>
 314         /// Returns true if we can jump into this node
 315         /// </summary>
 316         internal bool CanJumpInto {
 317             get {
 318                 switch (Kind) {
 319                     case LabelScopeKind.Block:
 320                     case LabelScopeKind.Statement:
 321                     case LabelScopeKind.Switch:
 322                     case LabelScopeKind.Lambda:
 323                         return true;
 324                 }
 325                 return false;
 326             }
 327         }
 328
 329
 330         internal bool ContainsTarget(LabelTarget target) {
 331             if (Labels == null) {
 332                 return false;
 333             }
 334
 335             return Labels.ContainsKey(target);
 336         }
 337
 338         internal bool TryGetLabelInfo(LabelTarget target, out LabelInfo info) {
 339             if (Labels == null) {
 340                 info = null;
 341                 return false;
 342             }
 343
 344             return Labels.TryGetValue(target, out info);
 345         }
 346
 347         internal void AddLabelInfo(LabelTarget target, LabelInfo info) {
 348             Debug.Assert(CanJumpInto);
 349
 350             if (Labels == null) {
 351                 Labels = new Dictionary<LabelTarget, LabelInfo>();
 352             }
 353
 354             Labels.Add(target, info);
 355         }
 356     }
 357 }