// Copyright Microsoft Corporation.
// This source file is subject to the Microsoft Permissive License.
// See http://www.microsoft.com/resources/sharedsource/licensingbasics/sharedsourcelicenses.mspx.
// All other rights reserved.
#if !MinimalReader || !NoWriter
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;
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 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
|