Unstacker.cs

// Licensed to the .NET Foundation under one or more agreements.
// The .NET Foundation licenses this file to you under the MIT license.
// See the LICENSE file in the project root for more information. 

#if !MinimalReader && !CodeContracts
using System;
using System.Collections;
using System.Diagnostics;

#if CCINamespace
namespace Microsoft.Cci{
#else
namespace System.Compiler{
#endif
  /// <summary>
  /// Walks a normalized IR, removing push, pop and dup instructions, replacing them with references to local variables.
  /// Requires all Blocks to be basic blocks. I.e. any transfer statement is always the last statement in a block.
  /// (This precondition is established by Reader but not by Normalizer.)
  /// </summary>
  public class Unstacker : StandardVisitor{
    private TrivialHashtable/*!*/ SucessorBlock = new TrivialHashtable();
    private TrivialHashtable/*!*/ StackLocalsAtEntry = new TrivialHashtable();
    private LocalsStack/*!*/ localsStack = new LocalsStack();

    public Unstacker(){
      //^ base();
    }

    public override Statement VisitAssignmentStatement(AssignmentStatement assignment){
      if (assignment == null) return null;
      assignment.Source = this.VisitExpression(assignment.Source);
      assignment.Target = this.VisitTargetExpression(assignment.Target);
      return assignment;
    }
    public override Expression VisitBinaryExpression(BinaryExpression binaryExpression){
      if (binaryExpression == null) return null;
      binaryExpression.Operand2 = this.VisitExpression(binaryExpression.Operand2);
      binaryExpression.Operand1 = this.VisitExpression(binaryExpression.Operand1);
      if (binaryExpression.Type == null) binaryExpression.Type = binaryExpression.Operand1.Type; //Hack: need proper inferencing
      return binaryExpression;
    }
    public override Block VisitBlock(Block block){
      if (block == null) return null;
      LocalsStack stackLocalsAtEntry = (LocalsStack)this.StackLocalsAtEntry[block.UniqueKey];
      if (stackLocalsAtEntry == null){
        //Unreachable code, or the very first block
        stackLocalsAtEntry = new LocalsStack();
      }
      this.localsStack = stackLocalsAtEntry.Clone();
      base.VisitBlock(block);
      Block successor = (Block)this.SucessorBlock[block.UniqueKey];
      if (successor != null) {
        //Dropping off into successor.
        LocalsStack targetStack = (LocalsStack)this.StackLocalsAtEntry[successor.UniqueKey];
        if (targetStack != null && targetStack.top >= 0) {
          //Another predecessor block has already decided what the stack for the successor block is going to look like.
          //Reconcile the stack from this block with the stack expected by the successor block.
          this.localsStack.Transfer(targetStack, block.Statements);
        }
        else {
          this.StackLocalsAtEntry[successor.UniqueKey] = this.localsStack;
        }
      }
      return block;
    }
    public override Statement VisitBranch(Branch branch){
      if (branch == null) return null;
      if (branch.Target == null) return null;
      branch.Condition = this.VisitExpression(branch.Condition);
      int n = this.localsStack.top+1;
      LocalsStack targetStack = (LocalsStack)this.StackLocalsAtEntry[branch.Target.UniqueKey];
      if (targetStack == null){
        this.StackLocalsAtEntry[branch.Target.UniqueKey] = this.localsStack.Clone();
        return branch;
      }
      //Target block has an entry stack that is different from the current stack. Need to copy stack before branching.
      if (n <= 0) return branch; //Empty stack, no need to copy
      StatementList statements = new StatementList(n+1);
      this.localsStack.Transfer(targetStack, statements);
      statements.Add(branch);
      return new Block(statements);
    }
    public override Statement VisitSwitchInstruction(SwitchInstruction switchInstruction) {
      if (switchInstruction == null) return null;
      switchInstruction.Expression = this.VisitExpression(switchInstruction.Expression);
      for (int i = 0, n = switchInstruction.Targets == null ? 0 : switchInstruction.Targets.Count; i < n; i++){
        Block target = switchInstruction.Targets[i];
        if (target == null) continue;
        this.StackLocalsAtEntry[target.UniqueKey] = this.localsStack.Clone();
      }
      return switchInstruction;
    }
    public override ExpressionList VisitExpressionList(ExpressionList expressions) {
      if (expressions == null) return null;
      for (int i = expressions.Count-1; i >= 0; i--)
        expressions[i] = this.VisitExpression(expressions[i]);
      return expressions;
    }
    public override Statement VisitExpressionStatement(ExpressionStatement statement){
      if (statement == null) return null;
      Expression e = statement.Expression = this.VisitExpression(statement.Expression);
      if (e == null || e.Type == CoreSystemTypes.Void) return statement;
      if (e.NodeType == NodeType.Dup) return this.localsStack.Dup();
      return this.localsStack.Push(e);
    }
    public override Expression VisitExpression(Expression expression){
      if (expression == null) return null;
      switch(expression.NodeType){
        case NodeType.Dup: 
        case NodeType.Arglist:
          return expression;
        case NodeType.Pop:
          UnaryExpression uex = expression as UnaryExpression;
          if (uex != null){
            Expression e = uex.Operand = this.VisitExpression(uex.Operand);
            if (e == null) return null;
            uex.Type = CoreSystemTypes.Void;
            return uex;
          }
          return this.localsStack.Pop();
        default:
          return (Expression)this.Visit(expression);
      }
    }
    public override Expression VisitIndexer(Indexer indexer){
      if (indexer == null) return null;
      indexer.Operands = this.VisitExpressionList(indexer.Operands);
      indexer.Object = this.VisitExpression(indexer.Object);
      return indexer;
    }
    public override Method VisitMethod(Method method){
      // body might not have been materialized, so make sure we do that first!
      Block body = method.Body;

      if (method == null) return null;
      BlockSorter blockSorter = new BlockSorter();
      BlockList sortedBlocks = blockSorter.SortedBlocks;
      this.SucessorBlock = blockSorter.SuccessorBlock;
      this.StackLocalsAtEntry = new TrivialHashtable();
      this.localsStack = new LocalsStack();
      ExceptionHandlerList ehandlers = method.ExceptionHandlers;
      for (int i = 0, n = ehandlers == null ? 0 : ehandlers.Count; i < n; i++){
        ExceptionHandler ehandler = ehandlers[i];
        if (ehandler == null) continue;
        Block handlerStart = ehandler.HandlerStartBlock;
        if (handlerStart == null) continue;
        LocalsStack lstack = new LocalsStack();
        this.StackLocalsAtEntry[handlerStart.UniqueKey] = lstack;
        if (ehandler.HandlerType == NodeType.Catch) {
          lstack.exceptionHandlerType = CoreSystemTypes.Object;
          if (ehandler.FilterType != null) lstack.exceptionHandlerType = ehandler.FilterType;
        } else if (ehandler.HandlerType == NodeType.Filter) {
          lstack.exceptionHandlerType = CoreSystemTypes.Object;
          if (ehandler.FilterExpression != null) {
            lstack = new LocalsStack();
            lstack.exceptionHandlerType = CoreSystemTypes.Object;
            this.StackLocalsAtEntry[ehandler.FilterExpression.UniqueKey] = lstack;
          }
        }
      }
      blockSorter.VisitMethodBody(body);
      for (int i = 0, n = sortedBlocks.Count; i < n; i++) {
        Block b = sortedBlocks[i];
        if (b == null) { Debug.Assert(false); continue; }
        this.VisitBlock(b);
      }
      return method;
    }
    public override Expression VisitMethodCall(MethodCall call){
      if (call == null) return null;
      call.Operands = this.VisitExpressionList(call.Operands);
      call.Callee = this.VisitExpression(call.Callee);
      return call;
    }
    public override Expression VisitTernaryExpression(TernaryExpression expression){
      if (expression == null) return null;
      expression.Operand3 = this.VisitExpression(expression.Operand3);
      expression.Operand2 = this.VisitExpression(expression.Operand2);
      expression.Operand1 = this.VisitExpression(expression.Operand1);
      return expression;
    }

    private class LocalsStack{
      private Local[]/*!*/ elements;
      internal int top = -1;
      internal TypeNode exceptionHandlerType;

      private void Grow(){
        int n = this.elements.Length;
        Local[] newElements = new Local[n+8];
        for (int i = 0; i < n; i++) newElements[i] = this.elements[i];
        this.elements = newElements;
      }
      internal LocalsStack(){
        this.elements = new Local[8];
        //^ base();
      }
      private LocalsStack(LocalsStack/*!*/ other) {
        this.top = other.top;
        this.exceptionHandlerType = other.exceptionHandlerType;
        Local[] otherElements = other.elements;
        int n = otherElements.Length;
        Local[] elements = this.elements = new Local[n];
        //^ base();
        n = this.top+1;
        for (int i = 0; i < n; i++)
          elements[i] = otherElements[i];
      }
      internal LocalsStack/*!*/ Clone(){
        return new LocalsStack(this);
      }
      internal AssignmentStatement Dup(){
        int i = this.top;
        Expression topVal;
        if (this.top == -1 && this.exceptionHandlerType != null) {
          topVal = new Expression(NodeType.Dup, this.exceptionHandlerType);
        }else{
          Debug.Assert(i >= 0 && i < this.elements.Length);
          topVal = this.elements[i];
          //^ assume topVal != null;
        }
        Local dup = new Local(topVal.Type);
        if ((i = ++this.top) >= this.elements.Length) this.Grow();
        this.elements[i] = dup;
        return new AssignmentStatement(dup, topVal);
      }
      internal AssignmentStatement Push(Expression/*!*/ expr) {
        //Debug.Assert(expr != null && expr.Type != null);
        int i = ++this.top;
        Debug.Assert(i >= 0);
        if (i >= this.elements.Length) this.Grow();
        Local loc = this.elements[i];
        if (loc == null || loc.Type != expr.Type)
          this.elements[i] = loc = new Local(expr.Type);
        return new AssignmentStatement(loc, expr);
      }
      internal Expression Pop(){
        if (this.top == -1 && this.exceptionHandlerType != null){
          TypeNode t = this.exceptionHandlerType;
          this.exceptionHandlerType = null;
          return new Expression(NodeType.Pop, t);
        }
        int i = this.top--;
        Debug.Assert(i >= 0 && i < this.elements.Length);
        return this.elements[i];
      }
      internal void Transfer(LocalsStack/*!*/ targetStack, StatementList/*!*/ statements) {
        Debug.Assert(targetStack != null);
        if (targetStack == this) return;
        int n = this.top;
        Debug.Assert(n == targetStack.top);
        for (int i = 0; i <= n; i++){
          Local sloc = this.elements[i];
          Local tloc = targetStack.elements[i];
          if (sloc == tloc) continue;
          Debug.Assert(sloc != null && tloc != null);
          statements.Add(new AssignmentStatement(tloc, sloc));
        }
      }
    }
    private class BlockSorter : StandardVisitor{
      private TrivialHashtable/*!*/ VisitedBlocks = new TrivialHashtable();
      private TrivialHashtable/*!*/ BlocksThatDropThrough = new TrivialHashtable();
      private bool lastBranchWasUnconditional = false;
      internal BlockList/*!*/ SortedBlocks = new BlockList();
      internal TrivialHashtable/*!*/ SuccessorBlock = new TrivialHashtable();

      internal BlockSorter(){
        //^ base();
      }

      internal void VisitMethodBody(Block body) {
        if (body == null) return;
        StatementList statements = body.Statements;
        if (statements == null) return;
        Block previousBlock = null;
        for (int i = 0, n = statements.Count; i < n; i++) {
          Block b = statements[i] as Block;
          if (b == null) { Debug.Assert(false); continue; }
          if (previousBlock != null && this.BlocksThatDropThrough[previousBlock.UniqueKey] != null) {
            this.SuccessorBlock[previousBlock.UniqueKey] = b;
          }
          this.VisitBlock(b);
          previousBlock = b;
        }
      }
      public override Block VisitBlock(Block block) {
        if (block == null) return null;
        if (this.VisitedBlocks[block.UniqueKey] != null) {
          return block;
        }
        this.VisitedBlocks[block.UniqueKey] = block;
        this.SortedBlocks.Add(block);
        this.lastBranchWasUnconditional = false;
        base.VisitBlock(block);
        if (!this.lastBranchWasUnconditional)
          this.BlocksThatDropThrough[block.UniqueKey] = block;
        return block;
      }
      public override Statement VisitBranch(Branch branch){
        if (branch == null) return null;
        if (branch.Target == null) return null;
        this.VisitBlock(branch.Target);
        this.lastBranchWasUnconditional = branch.Condition == null;
        return branch;
      }
      public override Statement VisitEndFilter(EndFilter endFilter) {
        endFilter.Value = this.VisitExpression(endFilter.Value);
        this.lastBranchWasUnconditional = true;
        return endFilter;
      }
      public override Statement VisitEndFinally(EndFinally endFinally) {
        this.lastBranchWasUnconditional = true;
        return endFinally;
      }
      public override Statement VisitReturn(Return ret) {
        this.lastBranchWasUnconditional = true;
        return ret;
      }
      public override Statement VisitSwitchInstruction(SwitchInstruction switchInstruction) {
        if (switchInstruction == null) return null;
        switchInstruction.Expression = this.VisitExpression(switchInstruction.Expression);
        for (int i = 0, n = switchInstruction.Targets == null ? 0 : switchInstruction.Targets.Count; i < n; i++){
          Block target = switchInstruction.Targets[i];
          if (target == null) continue;
          this.VisitBlock(target);
        }
        return switchInstruction;
      }
      public override Statement VisitThrow(Throw Throw) {
        this.lastBranchWasUnconditional = true;
        return Throw;
      }
    }
  }
}
#endif