Switch-implementation.

frog/leg/ssa/builder.dart

 // Copyright (c) 2012, the Dart project authors.  Please see the AUTHORS file
 // for details. All rights reserved. Use of this source code is governed by a
 // BSD-style license that can be found in the LICENSE file.
 
 class Interceptors {
   Compiler compiler;
   Interceptors(Compiler this.compiler);
 
   SourceString mapOperatorToMethodName(Operator op) {
     String name = op.source.stringValue;
@@ skipping 602 matching lines @@
   final HBreak breakInstruction;
   final LocalsHandler locals;
   BreakHandlerEntry(this.breakInstruction, this.locals);
 }
 
 interface BreakHandler default BreakHandlerImpl {
   BreakHandler(SsaBuilder builder, StatementElement target);
   void addBreak(HBreak breakInstruction);
   void forEachBreak(Function action);
   void close();
-  List<SourceString> labels();
+  List<LabelElement> labels();
 }
 
 // Inert break handler used to avoid null checks when a loop isn't
 // used as the target of a break, and therefore doesn't need a break
 // handler associated with it.
 class NullBreakHandler implements BreakHandler {
   const NullBreakHandler();
   void addBreak(HBreak breakInstruction) { unreachable(); }
   void forEachBreak(Function ignored) { }
   void close() { }
-  List<SourceString> labels() => const <SourceString>[];
+  List<LabelElement> labels() => const <LabelElement>[];
 }
 
 // Records breaks until a target block is available.
 // Breaks are always forward jumps.
 class BreakHandlerImpl implements BreakHandler {
   final BreakHandler previous;
   final SsaBuilder builder;
   final StatementElement target;
   final List<BreakHandlerEntry> breaks;
   BreakHandlerImpl(SsaBuilder builder, this.target)
@@ skipping 16 matching lines @@
     }
   }
 
   void close() {
     assert(builder.currentBreakHandler === this);
     // The mapping from StatementElement to BreakHandler is no longer needed.
     builder.breakTargets.remove(target);
     builder.currentBreakHandler = previous;
   }
 
-  List<SourceString> labels() {
-    List<SourceString> result = null;
+  List<LabelElement> labels() {
+    List<LabelElement> result = null;
     for (LabelElement element in target.labels) {
       if (element.isBreakTarget) {
-        if (result === null) result = <SourceString>[];
-        result.add(element.label.source);
+        if (result === null) result = <LabelElement>[];
+        result.add(element);
       }
     }
-    return (result === null) ? const <SourceString>[] : result;
+    return (result === null) ? const <LabelElement>[] : result;
   }
 }
 
 class SsaBuilder implements Visitor {
   final Compiler compiler;
   TreeElements elements;
   final Interceptors interceptors;
   final WorkItem work;
   bool methodInterceptionEnabled;
   HGraph graph;
   LocalsHandler localsHandler;
   HInstruction rethrowableException;
 
   Map<StatementElement, BreakHandler> breakTargets;
 
   // We build the Ssa graph by simulating a stack machine.
   List<HInstruction> stack;
 
   // The current block to add instructions to. Might be null, if we are
   // visiting dead code.
   HBasicBlock current;
   // The most recently opened block. Has the same value as [current] while
   // the block is open, but unlike [current], it isn't cleared when the current
   // block is closed.
   HBasicBlock lastOpenedBlock;
 
   // Linked list of active break-handlers. Will be removed in the order
   // they are added.
   BreakHandler currentBreakHandler = const NullBreakHandler();
-  // The break handler to use for an upcoming loop statement (temporarily set
-  // if a labeled statement is labeling a loop).
-  BreakHandler loopBreakHandler = null;
 
   SsaBuilder(Compiler compiler, WorkItem work)
     : this.compiler = compiler,
       this.work = work,
       interceptors = compiler.builder.interceptors,
       methodInterceptionEnabled = true,
       elements = work.resolutionTree,
       graph = new HGraph(),
       stack = new List<HInstruction>(),
       breakTargets = new Map<StatementElement, BreakHandler>() {
@@ skipping 278 matching lines @@
   }
 
   /**
    * Creates a new loop-header block. The previous [current] block
    * is closed with an [HGoto] and replaced by the newly created block.
    * Also notifies the locals handler that we're entering a loop.
    */
   BreakHandler beginLoopHeader(Node node) {
     assert(!isAborted());
     HBasicBlock previousBlock = close(new HGoto());
-    BreakHandler breakHandler = getLoopBreakHandler(node);
+    BreakHandler breakHandler = getBreakHandler(node);
     HBasicBlock loopEntry = graph.addNewLoopHeaderBlock(breakHandler.labels());
     previousBlock.addSuccessor(loopEntry);
     open(loopEntry);
 
     localsHandler.beginLoopHeader(node, loopEntry);
     return breakHandler;
   }
 
   /**
    * Ends the loop:
@@ skipping 301 matching lines @@
     assert(op.token.kind !== PLUS_TOKEN);
     HInstruction operand = pop();
     // See if we can constant-fold right away. This avoids rewrites later on.
     if (operand is HConstant) {
       HConstant typedOperand = operand;
       Constant constant = typedOperand.constant;
       Constant folded = constant.unaryFold(op.source.stringValue);
       if (folded !== null) {
         stack.add(graph.addConstant(folded));
         return;
-      }      
+      }
     }
     HInstruction target =
         new HStatic(interceptors.getPrefixOperatorInterceptor(op));
     add(target);
     switch (op.source.stringValue) {
       case "-": push(new HNegate(target, operand)); break;
       case "~": push(new HBitNot(target, operand)); break;
       default: unreachable();
     }
   }
@@ skipping 294 matching lines @@
           SourceString name = selector.namedArguments[i];
           if (name == parameter.name) {
             foundIndex = i;
             break;
           }
         }
         if (foundIndex != -1) {
           list.add(namedArguments[foundIndex]);
         } else {
           Constant constant = compiler.compileVariable(parameter);
-          list.add(graph.addConstant(constant)); 
+          list.add(graph.addConstant(constant));
         }
       }
     }
   }
 
   void addGenericSendArgumentsToList(Link<Node> link, List<HInstruction> list) {
     for (; !link.isEmpty(); link = link.tail) {
       visit(link.head);
       list.add(pop());
     }
@@ skipping 446 matching lines @@
     work.allowSpeculativeOptimization = false;
     assert(!isAborted());
     StatementElement target = elements[node];
     assert(target !== null);
     BreakHandler handler = breakTargets[target];
     assert(handler !== null);
     LocalsHandler savedLocals = new LocalsHandler.from(localsHandler);
     HBreak breakInstruction;
     if (node.target === null) {
       breakInstruction = new HBreak();
-    }  else {
-      breakInstruction = new HBreak(node.target.source);
+    } else {
+      LabelElement label = elements[node.target];
+      breakInstruction = new HBreak(label);
     }
     close(breakInstruction);
     handler.addBreak(breakInstruction, savedLocals);
   }
 
   visitContinueStatement(ContinueStatement node) {
     // TODO(lrn): Replace this with a real implementation of continue.
     compiler.reportWarning(node, 'continue not implemented');
     generateUnimplemented('continue not implemented');
   }
 
-  BreakHandler getLoopBreakHandler(Node node) {
+  BreakHandler getBreakHandler(Node node) {
     StatementElement element = elements[node];
-    BreakHandler handler;
-    if (loopBreakHandler === null) {
-      if (element === null) return const NullBreakHandler();
-      handler = new BreakHandler(this, element);
-    } else {
-      handler = loopBreakHandler;
-      loopBreakHandler = null;
-      if (element === null) return handler;
-    }
-    return handler;
+    if (element === null) return const NullBreakHandler();
+    return new BreakHandler(this, element);
   }
 
   visitForInStatement(ForInStatement node) {
     // Generate a structure equivalent to:
     //   Iterator<E> $iter = <iterable>.iterator()
     //   while ($iter.hasNext()) {
     //     E <declaredIdentifier> = $iter.next();
     //     <body>
     //   }
     localsHandler.startLoop(node);
@@ skipping 141 matching lines @@
     visit(node.value);
     visit(node.key);
   }
 
   visitNamedArgument(NamedArgument node) {
     visit(node.expression);
   }
 
   visitSwitchStatement(SwitchStatement node) {
     work.allowSpeculativeOptimization = false;
+    LocalsHandler savedLocals = new LocalsHandler.from(localsHandler);
     visit(node.expression);
     HInstruction expression = pop();
+    if (node.cases.isEmpty()) {
+      return;
+    }
     Link<Node> cases = node.cases.nodes;
-    int count = 0;
-    handleThen() {
-      if (cases.head.statements.nodes.isEmpty()) {
-        compiler.unimplemented('fall-through', node: cases.head);
+    Element equalsHelper = interceptors.getEqualsInterceptor();
+    HInstruction target = new HStatic(equalsHelper);
+    add(target);
+
+    BreakHandler breakHandler = getBreakHandler(node);
+
+    void buildCompare(Expression caseExpression) {
+      visit(caseExpression);
+      push(new HEquals(target, pop(), expression));
+    }
+    buildSwitchCases(cases, buildCompare);
+
+    // Create merge block for break targets.
+    HBasicBlock joinBlock = new HBasicBlock();
+    List<LocalsHandler> caseLocals = <LocalsHandler>[];
+    breakHandler.forEachBreak((HBreak instruction, LocalsHandler locals) {
+      instruction.block.addSuccessor(joinBlock);
+      caseLocals.add(locals);
+    });
+    if (caseLocals.length == 0) return;
+    if (!isAborted()) {
+      caseLocals.add(localsHandler);
+      goto(current, joinBlock);
+    }
+    graph.addBlock(joinBlock);
+    open(joinBlock);
+    if (caseLocals.length == 1) {
+      localsHandler = caseLocals[0];
+    } else {
+      localsHandler = savedLocals.mergeMultiple(caseLocals, joinBlock);
+    }
+  }
+
+
+  // Recursively build an if/else structure to match the cases.
+  buildSwitchCases(Link<Node> cases, Function buildCompare) {
+    SwitchCase node = cases.head;
+    // TODO(lrn): Handle labels and continues.
+
+    void visitStatementsAndAbort() {
+      visit(node.statements);
+      if (!isAborted()) {
+        compiler.cancel('Missing break at end of switch case', node: node);
+        HBreak breakInstruction = new HBreak();
+        close(breakInstruction);
+        currentBreakHandler.addBreak(breakInstruction, localsHandler);
       }
-      visit(cases.head.statements);
-      cases = cases.tail;
-    }
-    handleElse() {
-      if (cases.isEmpty()) return;
-      if (cases.head.asDefaultCase() !== null) {
-        stack.add(graph.addConstantBool(true));
-        if (!cases.tail.isEmpty()) {
-          compiler.unimplemented('default case not last', node: cases.head);
-        }
-      } else {
-        SwitchCase switchCase = cases.head;
-        visit(switchCase.expression);
-        HInstruction caseExpression = pop();
-        Element equalsHelper = interceptors.getEqualsInterceptor();
-        HInstruction target = new HStatic(equalsHelper);
-        add(target);
-        push(new HEquals(target, caseExpression, expression));
-      }
-      handleIf(handleThen, handleElse);
     }
 
-    localsHandler.startLoop(node);
-    BreakHandler breakHandler = beginLoopHeader(node);
-    HBasicBlock loopEntryBlock = current;
-    localsHandler.enterLoopBody(node);
-
-    handleElse();
-
-    if (isAborted()) {
-      compiler.unimplemented("SsaBuilder for loop with aborting body",
-                             node: node);
+    Link<Node> expressions = node.expressions.nodes;
+    if (expressions.isEmpty()) {
+      // Default case with no expressions.
+      if (!node.isDefaultCase) {
+        compiler.internalError("Case with no expression and not default");
+      }
+      visitStatementsAndAbort();
+      return;
     }
 
-    HBasicBlock bodyExitBlock = close(new HGoto());
-    HBasicBlock conditionBlock = addNewBlock();
-    bodyExitBlock.addSuccessor(conditionBlock);
-    open(conditionBlock);
-    stack.add(graph.addConstantBool(false));
+    // Recursively build the test conditions.
+    HInstruction buildTests(Link<Node> expressions, HInstruction left) {
+      // previous is a boolean instruction.

[floitsch, 2012/03/08 16:35:14]

P

[Lasse Reichstein Nielsen, 2012/03/08 18:35:40]

Whoops, 'previous'->'left'.

+      if (expressions.isEmpty()) return left;
+      push(new HNot(left));
 
-    conditionBlock = close(new HLoopBranch(popBoolified(),
-                                           HLoopBranch.DO_WHILE_LOOP));
+      HIf branch = new HIf(pop(), false);
+      HBasicBlock leftBlock = close(branch);
+      LocalsHandler savedLocals = new LocalsHandler.from(localsHandler);
 
-    conditionBlock.addSuccessor(loopEntryBlock);  // The back-edge.
-    loopEntryBlock.postProcessLoopHeader();
+      HBasicBlock rightBlock = addNewBlock();
+      leftBlock.addSuccessor(rightBlock);
+      open(rightBlock);
 
-    endLoop(loopEntryBlock, conditionBlock, breakHandler);
+      buildCompare(expressions.head);
+      HInstruction right = buildTests(expressions.tail, popBoolified());
+
+      SubGraph rightGraph = new SubGraph(rightBlock, current);
+
+      rightBlock = close(new HGoto());
+      HBasicBlock joinBlock = addNewBlock();
+      leftBlock.addSuccessor(joinBlock);
+      rightBlock.addSuccessor(joinBlock);
+      open(joinBlock);
+
+      branch.blockInformation =
+          new HIfBlockInformation(branch, rightGraph, null, joinBlock);
+
+      localsHandler.mergeWith(savedLocals, joinBlock);
+      HPhi result = new HPhi.manyInputs(null, [left, right]);
+      joinBlock.addPhi(result);
+      return result;
+    }
+
+    buildCompare(expressions.head);
+    HInstruction result = buildTests(expressions.tail, popBoolified());
+
+    if (node.isDefaultCase) {
+      // Don't actually use the condition result.
+      visitStatementsAndAbort();
+    } else {
+      stack.add(result);
+      handleIf(() { visitStatementsAndAbort(); },
+               cases.tail.isEmpty() ?
+                   null :
+                   () { buildSwitchCases(cases.tail, buildCompare); });
+    }
+  }
+
+  visitSwitchCase(SwitchCase node) {
+    unreachable();
   }
 
   visitTryStatement(TryStatement node) {
     work.allowSpeculativeOptimization = false;
     assert(!work.isBailoutVersion());
     HBasicBlock enterBlock = graph.addNewBlock();
     close(new HGoto()).addSuccessor(enterBlock);
     open(enterBlock);
     HTry tryInstruction = new HTry();
     List<HBasicBlock> blocks = <HBasicBlock>[];
@@ skipping 111 matching lines @@
     // Normally, we would call [close] here. However, then we hit
     // another unimplemented feature: aborting loop body. Simply
     // calling [add] does not work as it asserts that the instruction
     // isn't a control flow instruction. So we inline parts of [add].
     current.addAfter(current.last, new HThrow(message));
     if (isExpression) {
       stack.add(graph.addConstantNull());
     }
   }
 }