1.1 --- a/src/Code.h	Sat Dec 22 16:42:20 2012 -0800
     1.2 +++ b/src/Code.h	Sat Dec 22 18:22:14 2012 -0800
     1.3 @@ -44,6 +44,7 @@
     1.4      Barriered<ByteArray> sourcemap_;
     1.5      unsigned maxStackDepth_;
     1.6      unsigned lineNumber_;
     1.7 +    unsigned maxLoopDepth_;
     1.8  
     1.9    public:
    1.10      static inline size_t BytesPerSafepoint(size_t stackDepth) {
    1.11 @@ -53,7 +54,7 @@
    1.12    public:
    1.13      static Code *New(Zone *zone, Handle<ByteArray> bytecode, Handle<FixedArray> locals,
    1.14                       Handle<FixedArray> objects, Handle<FixedArray> strings, unsigned maxStackDepth,
    1.15 -                     Handle<ByteArray> safepoints, Handle<ByteArray> sourcemap);
    1.16 +                     unsigned maxLoopDepth, Handle<ByteArray> safepoints, Handle<ByteArray> sourcemap);
    1.17  
    1.18      Module *module() {
    1.19          return module_;
    1.20 @@ -73,6 +74,9 @@
    1.21      unsigned maxStackDepth() {
    1.22          return maxStackDepth_;
    1.23      }
    1.24 +    unsigned maxLoopDepth() {
    1.25 +        return maxLoopDepth_;
    1.26 +    }
    1.27      Map *map(size_t index) {
    1.28          return Map::cast(objects_->at(index));
    1.29      }

     2.1 --- a/src/Interpreter.cpp	Sat Dec 22 16:42:20 2012 -0800
     2.2 +++ b/src/Interpreter.cpp	Sat Dec 22 18:22:14 2012 -0800
     2.3 @@ -446,8 +446,18 @@
     2.4  }
     2.5  
     2.6  case OP_JUMP:
     2.7 +{
     2.8      top.pc += READ_INT32(top.pc);
     2.9      continue;
    2.10 +}
    2.11 +
    2.12 +case OP_BREAK:
    2.13 +case OP_CONTINUE:
    2.14 +{
    2.15 +    top.fp->leaveLoop(zone);
    2.16 +    top.pc += READ_INT32(top.pc);
    2.17 +    continue;
    2.18 +}
    2.19  
    2.20  case OP_GETLOCAL:
    2.21  {
    2.22 @@ -1065,6 +1075,18 @@
    2.23      break;
    2.24  }
    2.25  
    2.26 +case OP_ENTERLOOP:
    2.27 +{
    2.28 +    top.fp->enterLoop(zone);
    2.29 +    break;
    2.30 +}
    2.31 +
    2.32 +case OP_LEAVELOOP:
    2.33 +{
    2.34 +    top.fp->leaveLoop(zone);
    2.35 +    break;
    2.36 +}
    2.37 +
    2.38  default:
    2.39      assert(false);
    2.40      return false;

     3.1 --- a/src/Opcodes.cpp	Sat Dec 22 16:42:20 2012 -0800
     3.2 +++ b/src/Opcodes.cpp	Sat Dec 22 18:22:14 2012 -0800
     3.3 @@ -40,7 +40,7 @@
     3.4  Code *
     3.5  Code::New(Zone *zone, Handle<ByteArray> bytecode, Handle<FixedArray> locals,
     3.6            Handle<FixedArray> objects, Handle<FixedArray> strings, unsigned maxStackDepth,
     3.7 -          Handle<ByteArray> safepoints, Handle<ByteArray> sourcemap)
     3.8 +          unsigned maxLoopDepth, Handle<ByteArray> safepoints, Handle<ByteArray> sourcemap)
     3.9  {
    3.10      Local<Code> code(zone, Code::cast(zone->allocate(MapKind_Code, sizeof(Code), Heap::Tenure_Old)));
    3.11      if (!code)
    3.12 @@ -55,6 +55,7 @@
    3.13      code->sourcemap_ = sourcemap;
    3.14      code->lineNumber_ = 0;
    3.15      code->strings_ = strings;
    3.16 +    code->maxLoopDepth_ = maxLoopDepth;
    3.17      return code;
    3.18  }
    3.19  
    3.20 @@ -160,6 +161,7 @@
    3.21            case OP_MUL_F:
    3.22            case OP_DIV_F:
    3.23            case OP_CVT_I2F:
    3.24 +          case OP_CVT_I2B:
    3.25            case OP_POP:
    3.26            case OP_GETELEM:
    3.27            case OP_SETELEM:
    3.28 @@ -207,6 +209,12 @@
    3.29            case OP_FALSE:
    3.30            case OP_SIZEOF:
    3.31            case OP_PUBLIC:
    3.32 +          case OP_LEAVELOOP:
    3.33 +            break;
    3.34 +
    3.35 +          case OP_ENTERLOOP:
    3.36 +            if (pc[1])
    3.37 +              fprintf(fp, "; lifo region");
    3.38              break;
    3.39  
    3.40            case OP_STOP:
    3.41 @@ -224,6 +232,8 @@
    3.42            case OP_JT:
    3.43            case OP_JF:
    3.44            case OP_JUMP:
    3.45 +          case OP_CONTINUE:
    3.46 +          case OP_BREAK:
    3.47              fprintf(fp, "%u (%+d)", unsigned((pc + READ_INT32(pc)) - code->start()), READ_INT32(pc));
    3.48              break;
    3.49  

     4.1 --- a/src/Opcodes.tbl	Sat Dec 22 16:42:20 2012 -0800
     4.2 +++ b/src/Opcodes.tbl	Sat Dec 22 18:22:14 2012 -0800
     4.3 @@ -43,6 +43,10 @@
     4.4  // Unconditional jump.
     4.5  OPDEF(OP_JUMP,          "jump",         5,      0,  0)
     4.6  
     4.7 +// Aliases for JUMP, that automatically leave LR regions.
     4.8 +OPDEF(OP_BREAK,         "break",        5,      0,  0)
     4.9 +OPDEF(OP_CONTINUE,      "continue",     5,      0,  0)
    4.10 +
    4.11  // Gets or sets the value of a local variable onto the stack. The local
    4.12  // variable is given by an immediate index.
    4.13  OPDEF(OP_GETLOCAL,      "getlocal",     5,      0,  1)
    4.14 @@ -243,4 +247,12 @@
    4.15  OPDEF(OP_SIZEOF,        "sizeof",       1,      1, 1)
    4.16  
    4.17  // Registers a function as a publicly exported name.
    4.18 -OPDEF(OP_PUBLIC,        "public",       1,      1, 0)
    4.19 \ No newline at end of file
    4.20 +OPDEF(OP_PUBLIC,        "public",       1,      1, 0)
    4.21 +
    4.22 +// Enter and leave loop bodies. This is to track positions in the LIFO stack.
    4.23 +// This is only used for the outermost scope inside loop bodies. BREAK and
    4.24 +// CONTINUE implicitly perform a LEAVELOOP.
    4.25 +//
    4.26 +// If the second byte to ENTERLOOP is 0, then no LIFO region is needed.
    4.27 +OPDEF(OP_ENTERLOOP,     "enterloop",    2,      0, 0)
    4.28 +OPDEF(OP_LEAVELOOP,     "leaveloop",    1,      0, 0)
    4.29 \ No newline at end of file

     5.1 --- a/src/Stack.cpp	Sat Dec 22 16:42:20 2012 -0800
     5.2 +++ b/src/Stack.cpp	Sat Dec 22 18:22:14 2012 -0800
     5.3 @@ -67,7 +67,9 @@
     5.4  static inline size_t
     5.5  SizeForCodeFrame(Code *code)
     5.6  {
     5.7 -    return sizeof(Frame) + sizeof(LocalSlot) * (code->nlocals() + code->maxStackDepth());
     5.8 +    return sizeof(Frame) + 
     5.9 +           sizeof(void *) * (code->maxLoopDepth()) +
    5.10 +           sizeof(LocalSlot) * (code->nlocals() + code->maxStackDepth());
    5.11  }
    5.12  
    5.13  bool
    5.14 @@ -199,6 +201,22 @@
    5.15      top_.fp = top_.fp->prev();
    5.16  }
    5.17  
    5.18 +void
    5.19 +Frame::enterLoop(Zone *zone)
    5.20 +{
    5.21 +    assert(loopDepth_ < code_->maxLoopDepth());
    5.22 +    loopStack()[loopDepth_] = zone->heap().lifoPosition();
    5.23 +    loopDepth_++;
    5.24 +}
    5.25 +
    5.26 +void
    5.27 +Frame::leaveLoop(Zone *zone)
    5.28 +{
    5.29 +    assert(loopDepth_ > 0);
    5.30 +    loopDepth_--;
    5.31 +    zone->heap().unwindLifo(loopStack()[loopDepth_]);
    5.32 +}
    5.33 +
    5.34  void
    5.35  Frame::accept(VirtualObjectVisitor *visitor)
    5.36  {

     6.1 --- a/src/Stack.h	Sat Dec 22 16:42:20 2012 -0800
     6.2 +++ b/src/Stack.h	Sat Dec 22 18:22:14 2012 -0800
     6.3 @@ -66,7 +66,14 @@
     6.4          Object *callee_;
     6.5      };
     6.6      Code *code_;
     6.7 +
     6.8 +    // Position of the LIFO stack at function entry.
     6.9      Address lifoPosition_;
    6.10 +    
    6.11 +    // Loop nesting level, for LIFO stack balancing. LIFO stack balancing
    6.12 +    // is not strictly required, but it helps to avoid unnecessary waste,
    6.13 +    // since once the LIFO stack is depleted, we must use the heap instead.
    6.14 +    unsigned loopDepth_;
    6.15  
    6.16    public:
    6.17      Frame(Frame *prev, bytecode *prevpc, Function *fun, Code *code, Address lifoPosition)
    6.18 @@ -74,7 +81,8 @@
    6.19          prevpc_(prevpc),
    6.20          fun_(fun),
    6.21          code_(code),
    6.22 -        lifoPosition_(lifoPosition)
    6.23 +        lifoPosition_(lifoPosition),
    6.24 +        loopDepth_(0)
    6.25      {
    6.26      }
    6.27  
    6.28 @@ -87,8 +95,11 @@
    6.29      {
    6.30      }
    6.31  
    6.32 +    Address *loopStack() {
    6.33 +        return reinterpret_cast<Address *>(this + 1);
    6.34 +    }
    6.35      LocalSlot *locals() {
    6.36 -        return reinterpret_cast<LocalSlot *>(this + 1);
    6.37 +        return reinterpret_cast<LocalSlot *>(loopStack() + code_->maxLoopDepth());
    6.38      }
    6.39      LocalSlot *stackBase() {
    6.40          return locals() + code_->nlocals();
    6.41 @@ -124,6 +135,8 @@
    6.42          assert(slot < fun()->nargs());
    6.43          return *(reinterpret_cast<LocalSlot *>(this) - slot - 1);
    6.44      }
    6.45 +    void enterLoop(Zone *zone);
    6.46 +    void leaveLoop(Zone *zone);
    6.47      void accept(VirtualObjectVisitor *visitor);
    6.48  };
    6.49  

     7.1 --- a/src/compiler/BytecodeEmitter.cpp	Sat Dec 22 16:42:20 2012 -0800
     7.2 +++ b/src/compiler/BytecodeEmitter.cpp	Sat Dec 22 18:22:14 2012 -0800
     7.3 @@ -90,7 +90,9 @@
     7.4      buffer_pos_(buffer_),
     7.5      buffer_end_(buffer_pos_ + ARRAY_LENGTH(inline_buffer_)),
     7.6      oom_(false),
     7.7 -    maxStackDepth_(0)
     7.8 +    maxStackDepth_(0),
     7.9 +    loopDepth_(0),
    7.10 +    maxLoopDepth_(0)
    7.11  {
    7.12      lastCodePosition_ = 0;
    7.13      firstLine_ = 1;
    7.14 @@ -377,6 +379,7 @@
    7.15                       objects,
    7.16                       strings,
    7.17                       maxStackDepth(),
    7.18 +                     maxLoopDepth_,
    7.19                       safepoints,
    7.20                       sourcemap);
    7.21  

     8.1 --- a/src/compiler/BytecodeEmitter.h	Sat Dec 22 16:42:20 2012 -0800
     8.2 +++ b/src/compiler/BytecodeEmitter.h	Sat Dec 22 18:22:14 2012 -0800
     8.3 @@ -137,6 +137,8 @@
     8.4      StringTable strings_;
     8.5      Vector<Symbol *> locals_;
     8.6      Vector<Object *> objects_;
     8.7 +    unsigned loopDepth_;
     8.8 +    unsigned maxLoopDepth_;
     8.9  
    8.10    private:
    8.11      // The maximum size of a code object must be such that the distance between
    8.12 @@ -342,7 +344,8 @@
    8.13          if (oom())
    8.14              return;
    8.15  
    8.16 -        assert(op == OP_JT || op == OP_JF || op == OP_JUMP);
    8.17 +        assert(op == OP_JT || op == OP_JF || op == OP_JUMP ||
    8.18 +               op == OP_CONTINUE || op == OP_BREAK);
    8.19          ensure(OP_JUMP_LENGTH);
    8.20  
    8.21          if (label->bound()) {
    8.22 @@ -433,43 +436,30 @@
    8.23              markOop(1);
    8.24      }
    8.25  
    8.26 -#if 0
    8.27 -    void getglobal(Variable *var) {
    8.28 -        ensure(OP_GETGLOBAL_F_LENGTH);
    8.29 -        if (var->type()->isPrimitive()) {
    8.30 -            switch (var->type()->primitive()) {
    8.31 -              case PrimitiveType_Float:
    8.32 -                writeOp(OP_GETGLOBAL_F);
    8.33 -                break;
    8.34 -              default:
    8.35 -                assert(var->type()->primitive() == PrimitiveType_Int32);
    8.36 -                writeOp(OP_GETGLOBAL_I);
    8.37 -                break;
    8.38 -            }
    8.39 -        } else {
    8.40 -            writeOp(OP_GETGLOBAL_O);
    8.41 -            markOop(1);
    8.42 -        }
    8.43 -        writeUint32(var->slot());
    8.44 +    int enterloop() {
    8.45 +        int offset = position();
    8.46 +
    8.47 +        ensure(OP_ENTERLOOP);
    8.48 +        writeOp(OP_ENTERLOOP);
    8.49 +        writeUint8(0);
    8.50 +
    8.51 +        loopDepth_++;
    8.52 +        if (loopDepth_ > maxLoopDepth_)
    8.53 +            maxLoopDepth_ = loopDepth_;
    8.54 +
    8.55 +        return offset;
    8.56      }
    8.57 -    void setglobal(Variable *var) {
    8.58 -        ensure(OP_SETGLOBAL_F_LENGTH);
    8.59 -        if (var->type()->isPrimitive()) {
    8.60 -            switch (var->type()->primitive()) {
    8.61 -              case PrimitiveType_Float:
    8.62 -                writeOp(OP_SETGLOBAL_F);
    8.63 -                break;
    8.64 -              default:
    8.65 -                assert(var->type()->primitive() == PrimitiveType_Int32);
    8.66 -                writeOp(OP_SETGLOBAL_I);
    8.67 -                break;
    8.68 -            }
    8.69 -        } else {
    8.70 -            writeOp(OP_SETGLOBAL_O);
    8.71 -        }
    8.72 -        writeUint32(var->slot());
    8.73 +    void leaveloop() {
    8.74 +        singleByteOp(OP_LEAVELOOP);
    8.75 +
    8.76 +        assert(loopDepth_);
    8.77 +        loopDepth_--;
    8.78      }
    8.79 -#endif
    8.80 +    void setLoopUsesLifoStack(int pos) {
    8.81 +        assert(pos >= 0 && pos < position());
    8.82 +        assert(*(buffer() + pos) == OP_ENTERLOOP);
    8.83 +        *(buffer() + pos + 1) = 1;
    8.84 +    }
    8.85  
    8.86      void float_(float value) {
    8.87          ensure(OP_FLOAT_LENGTH);

     9.1 --- a/src/compiler/SemanticAnalysis.cpp	Sat Dec 22 16:42:20 2012 -0800
     9.2 +++ b/src/compiler/SemanticAnalysis.cpp	Sat Dec 22 18:22:14 2012 -0800
     9.3 @@ -242,6 +242,36 @@
     9.4  }
     9.5  
     9.6  void
     9.7 +SemanticAnalysis::requireLifoStack()
     9.8 +{
     9.9 +    if (!loop_)
    9.10 +        return;
    9.11 +
    9.12 +    loop_->setUsesLifoStack();
    9.13 +}
    9.14 +
    9.15 +void
    9.16 +SemanticAnalysis::visitLoopBody(Statement *stmt)
    9.17 +{
    9.18 +    // We always mark off a loop body, so on each edge, we can balance the
    9.19 +    // LIFO stack. Right now, we don't have the ability to budget the LIFO
    9.20 +    // stack ahead of time. If we turn out to never need the LIFO stack, we
    9.21 +    // mark it as unnecessary. (The interpreter can't really make use of this,
    9.22 +    // but the JIT can).
    9.23 +    //
    9.24 +    // Note that balancing the LIFO stack isn't even necessary, so this
    9.25 +    // feature may be removed. All this mechanism does is mitigate the
    9.26 +    // possibility that a long-running loop will overflow the LIFO region
    9.27 +    // and therefore start requiring nursery allocations.
    9.28 +    int pos = __ enterloop();
    9.29 +    stmt->accept(this);
    9.30 +    __ leaveloop();
    9.31 +
    9.32 +    if (loop_->usesLifoStack())
    9.33 +        __ setLoopUsesLifoStack(pos);
    9.34 +}
    9.35 +
    9.36 +void
    9.37  SemanticAnalysis::visitForStatement(ForStatement *node)
    9.38  {
    9.39      AutoEnterScope scope(&scope_, node->scope());
    9.40 @@ -259,7 +289,7 @@
    9.41          __ jump(&test);
    9.42  
    9.43      __ bind(&header);
    9.44 -    node->body()->accept(this);
    9.45 +    visitLoopBody(node->body());
    9.46  
    9.47      __ bind(&update);
    9.48      if (node->update())
    9.49 @@ -291,10 +321,10 @@
    9.50      if (node->token() == TOK_WHILE) {
    9.51          Label body;
    9.52          visitForTest(node->condition(), &body, &join, &body);
    9.53 -        node->body()->accept(this);
    9.54 +        visitLoopBody(node->body());
    9.55          __ jump(&header);
    9.56      } else {
    9.57 -        node->body()->accept(this);
    9.58 +        visitLoopBody(node->body());
    9.59          visitForTest(node->condition(), &header, &join, &join);
    9.60      }
    9.61  
    9.62 @@ -308,7 +338,12 @@
    9.63  {
    9.64      if (sym->scope()->kind() == Scope::GLOBAL)
    9.65          return Heap::Tenure_Old;
    9.66 -    // :TODO: need to use LIFO!
    9.67 +
    9.68 +    // SP2's array semantics allow any array kind to escape, so we must use
    9.69 +    // the normal heap. (Hopefully escape analysis can ease this pain later).
    9.70 +    if (sym->type()->isArray())
    9.71 +        return Heap::Tenure_Default;
    9.72 +
    9.73      return Heap::Tenure_Default;
    9.74  }
    9.75  
    9.76 @@ -531,8 +566,11 @@
    9.77              mustComputeReference = actual->isReference() && !given->isReference();
    9.78          }
    9.79  
    9.80 -        if (mustComputeReference)
    9.81 +        if (mustComputeReference) {
    9.82 +            // Refs always use the LIFO stack if they can.
    9.83              arg = new (pool_) HToRef(arg->node(), arg->type(), arg);
    9.84 +            requireLifoStack();
    9.85 +        }
    9.86  
    9.87          if (!args->append(arg))
    9.88              return;
    9.89 @@ -563,8 +601,7 @@
    9.90          return;
    9.91      }
    9.92  
    9.93 -    // Note, if we re-introduce LIFO allocs, we need to unwind here.
    9.94 -    __ jump(loop_->break_());
    9.95 +    __ j(OP_BREAK, loop_->break_());
    9.96  }
    9.97  
    9.98  void
    9.99 @@ -575,8 +612,7 @@
   9.100          return;
   9.101      }
   9.102  
   9.103 -    // Note, if we re-introduce LIFO allocs, we need to unwind here.
   9.104 -    __ jump(loop_->continue_());
   9.105 +    __ j(OP_CONTINUE, loop_->continue_());
   9.106  }
   9.107  
   9.108  void

    10.1 --- a/src/compiler/SemanticAnalysis.h	Sat Dec 22 16:42:20 2012 -0800
    10.2 +++ b/src/compiler/SemanticAnalysis.h	Sat Dec 22 18:22:14 2012 -0800
    10.3 @@ -88,6 +88,8 @@
    10.4          Coerce_Assign
    10.5      };
    10.6  
    10.7 +    void requireLifoStack();
    10.8 +    void visitLoopBody(Statement *stmt);
    10.9      void visitForTest(Expression *expr,
   10.10                        BytecodeEmitter::Label *trueBranch,
   10.11                        BytecodeEmitter::Label *falseBranch,
   10.12 @@ -114,6 +116,7 @@
   10.13          BytecodeEmitter::Label *ct_;
   10.14          LoopScope **prevp_;
   10.15          LoopScope *prev_;
   10.16 +        bool usesLifoStack_;
   10.17  
   10.18        public:
   10.19          LoopScope(Scope *scope, BytecodeEmitter::Label *bk, BytecodeEmitter::Label *ct,
   10.20 @@ -122,7 +125,8 @@
   10.21              bk_(bk),
   10.22              ct_(ct),
   10.23              prevp_(prevp),
   10.24 -            prev_(*prevp)
   10.25 +            prev_(*prevp),
   10.26 +            usesLifoStack_(false)
   10.27          {
   10.28              *prevp_ = this;
   10.29          }
   10.30 @@ -141,6 +145,12 @@
   10.31          Scope *scope() {
   10.32              return scope_;
   10.33          }
   10.34 +        void setUsesLifoStack() {
   10.35 +            usesLifoStack_ = true;
   10.36 +        }
   10.37 +        bool usesLifoStack() const {
   10.38 +            return usesLifoStack_;
   10.39 +        }
   10.40      };
   10.41      
   10.42    private:

    11.1 --- /dev/null	Thu Jan 01 00:00:00 1970 +0000
    11.2 +++ b/tests/manual/lifo.sp	Sat Dec 22 18:22:14 2012 -0800
    11.3 @@ -0,0 +1,16 @@
    11.4 +native PrintNum(num);
    11.5 +
    11.6 +q(&a)
    11.7 +{
    11.8 +    return 5;
    11.9 +}
   11.10 +
   11.11 +public main()
   11.12 +{
   11.13 +    // This isn't a real test, yet. The diassembly should have
   11.14 +    // LIFO save/restore functions.
   11.15 +    for (new i = 0; i < 100; i++) {
   11.16 +        q(i);
   11.17 +    }
   11.18 +}
   11.19 +

    12.1 --- a/tests/prototype/lifo.sp	Sat Dec 22 16:42:20 2012 -0800
    12.2 +++ /dev/null	Thu Jan 01 00:00:00 1970 +0000
    12.3 @@ -1,13 +0,0 @@
    12.4 -q(&a)
    12.5 -{
    12.6 -    return 5;
    12.7 -}
    12.8 -
    12.9 -main()
   12.10 -{
   12.11 -    for (new i = 0; i < 100; i++) {
   12.12 -        q(i);
   12.13 -    }
   12.14 -    return 5;
   12.15 -}
   12.16 -