core/vm: added JIT segmenting / optimisations

* multi-push segments
* static jumps segments

8 files changed, 202 insertions, 5 deletions

diff --git a/core/vm/doc.go b/core/vm/doc.go
index ab87bf934..debbdb35e 100644
--- a/core/vm/doc.go
+++ b/core/vm/doc.go
@@ -24,9 +24,12 @@ invokes the JIT VM in a seperate goroutine and compiles the byte code in JIT
 instructions.
 
 The JIT VM, when invoked, loops around a set of pre-defined instructions until
-it either runs of gas, causes an internal error, returns or stops. At a later
-stage the JIT VM will see some additional features that will cause sets of
-instructions to be compiled down to segments. Segments are sets of instructions
-that can be run in one go saving precious time during execution.
+it either runs of gas, causes an internal error, returns or stops.
+
+The JIT optimiser attempts to pre-compile instructions in to chunks or segments
+such as multiple PUSH operations and static JUMPs. It does this by analysing the
+opcodes and attempts to match certain regions to known sets. Whenever the
+optimiser finds said segments it creates a new instruction and replaces the
+first occurrence in the sequence.
 */
 package vm
diff --git a/core/vm/instructions.go b/core/vm/instructions.go
index 5dcab6e08..2e868521e 100644
--- a/core/vm/instructions.go
+++ b/core/vm/instructions.go
@@ -73,7 +73,7 @@ func (instr instruction) do(program *Program, pc *uint64, env Environment, contr
 	// Resize the memory calculated previously
 	memory.Resize(newMemSize.Uint64())
 
-	// These opcodes return an argument and are thefor handled
+	// These opcodes return an argument and are therefor handled
 	// differently from the rest of the opcodes
 	switch instr.op {
 	case JUMP:
diff --git a/core/vm/jit.go b/core/vm/jit.go
index 8cb95b860..1aa7d7ef2 100644
--- a/core/vm/jit.go
+++ b/core/vm/jit.go
@@ -290,6 +290,8 @@ func CompileProgram(program *Program) (err error) {
 		}
 	}
 
+	optimiseProgram(program)
+
 	return nil
 }
 
diff --git a/core/vm/jit_optimiser.go b/core/vm/jit_optimiser.go
new file mode 100644
index 000000000..4823cc1a0
--- /dev/null
+++ b/core/vm/jit_optimiser.go
@@ -0,0 +1,90 @@
+package vm
+
+import (
+	"math/big"
+	"time"
+
+	"github.com/ethereum/go-ethereum/logger"
+	"github.com/ethereum/go-ethereum/logger/glog"
+)
+
+// optimeProgram optimises a JIT program creating segments out of program
+// instructions. Currently covered are multi-pushes and static jumps
+func optimiseProgram(program *Program) {
+	var load []instruction
+
+	var (
+		statsJump = 0
+		statsPush = 0
+	)
+
+	if glog.V(logger.Debug) {
+		glog.Infof("optimising %x\n", program.Id[:4])
+		tstart := time.Now()
+		defer func() {
+			glog.Infof("optimised %x done in %v with JMP: %d PSH: %d\n", program.Id[:4], time.Since(tstart), statsJump, statsPush)
+		}()
+	}
+
+	for i := 0; i < len(program.instructions); i++ {
+		instr := program.instructions[i].(instruction)
+
+		switch {
+		case instr.op.IsPush():
+			load = append(load, instr)
+		case instr.op.IsStaticJump():
+			if len(load) == 0 {
+				continue
+			}
+			// if the push load is greater than 1, finalise that
+			// segment first
+			if len(load) > 2 {
+				seg, size := makePushSeg(load[:len(load)-1])
+				program.instructions[i-size-1] = seg
+				statsPush++
+			}
+			// create a segment consisting of a pre determined
+			// jump, destination and validity.
+			seg := makeStaticJumpSeg(load[len(load)-1].data, program)
+			program.instructions[i-1] = seg
+			statsJump++
+
+			load = nil
+		default:
+			// create a new N pushes segment
+			if len(load) > 1 {
+				seg, size := makePushSeg(load)
+				program.instructions[i-size] = seg
+				statsPush++
+			}
+			load = nil
+		}
+	}
+}
+
+// makePushSeg creates a new push segment from N amount of push instructions
+func makePushSeg(instrs []instruction) (pushSeg, int) {
+	var (
+		data []*big.Int
+		gas  = new(big.Int)
+	)
+
+	for _, instr := range instrs {
+		data = append(data, instr.data)
+		gas.Add(gas, instr.gas)
+	}
+
+	return pushSeg{data, gas}, len(instrs)
+}
+
+// makeStaticJumpSeg creates a new static jump segment from a predefined
+// destination (PUSH, JUMP).
+func makeStaticJumpSeg(to *big.Int, program *Program) jumpSeg {
+	gas := new(big.Int)
+	gas.Add(gas, _baseCheck[PUSH1].gas)
+	gas.Add(gas, _baseCheck[JUMP].gas)
+
+	contract := &Contract{Code: program.code}
+	pos, err := jump(program.mapping, program.destinations, contract, to)
+	return jumpSeg{pos, err, gas}
+}
diff --git a/core/vm/jit_test.go b/core/vm/jit_test.go
index cb09e179d..aa97e5184 100644
--- a/core/vm/jit_test.go
+++ b/core/vm/jit_test.go
@@ -26,6 +26,49 @@ import (
 
 const maxRun = 1000
 
+func TestSegmenting(t *testing.T) {
+	prog := NewProgram([]byte{byte(PUSH1), 0x1, byte(PUSH1), 0x1, 0x0})
+	err := CompileProgram(prog)
+	if err != nil {
+		t.Fatal(err)
+	}
+
+	if instr, ok := prog.instructions[0].(pushSeg); ok {
+		if len(instr.data) != 2 {
+			t.Error("expected 2 element width pushSegment, got", len(instr.data))
+		}
+	} else {
+		t.Errorf("expected instr[0] to be a pushSeg, got %T", prog.instructions[0])
+	}
+
+	prog = NewProgram([]byte{byte(PUSH1), 0x1, byte(PUSH1), 0x1, byte(JUMP)})
+	err = CompileProgram(prog)
+	if err != nil {
+		t.Fatal(err)
+	}
+	if _, ok := prog.instructions[1].(jumpSeg); ok {
+	} else {
+		t.Errorf("expected instr[1] to be jumpSeg, got %T", prog.instructions[1])
+	}
+
+	prog = NewProgram([]byte{byte(PUSH1), 0x1, byte(PUSH1), 0x1, byte(PUSH1), 0x1, byte(JUMP)})
+	err = CompileProgram(prog)
+	if err != nil {
+		t.Fatal(err)
+	}
+	if instr, ok := prog.instructions[0].(pushSeg); ok {
+		if len(instr.data) != 2 {
+			t.Error("expected 2 element width pushSegment, got", len(instr.data))
+		}
+	} else {
+		t.Errorf("expected instr[0] to be a pushSeg, got %T", prog.instructions[0])
+	}
+	if _, ok := prog.instructions[2].(jumpSeg); ok {
+	} else {
+		t.Errorf("expected instr[1] to be jumpSeg, got %T", prog.instructions[1])
+	}
+}
+
 func TestCompiling(t *testing.T) {
 	prog := NewProgram([]byte{0x60, 0x10})
 	err := CompileProgram(prog)
diff --git a/core/vm/opcodes.go b/core/vm/opcodes.go
index 986c35ef8..46905baac 100644
--- a/core/vm/opcodes.go
+++ b/core/vm/opcodes.go
@@ -23,6 +23,18 @@ import (
 // OpCode is an EVM opcode
 type OpCode byte
 
+func (op OpCode) IsPush() bool {
+	switch op {
+	case PUSH1, PUSH2, PUSH3, PUSH4, PUSH5, PUSH6, PUSH7, PUSH8, PUSH9, PUSH10, PUSH11, PUSH12, PUSH13, PUSH14, PUSH15, PUSH16, PUSH17, PUSH18, PUSH19, PUSH20, PUSH21, PUSH22, PUSH23, PUSH24, PUSH25, PUSH26, PUSH27, PUSH28, PUSH29, PUSH30, PUSH31, PUSH32:
+		return true
+	}
+	return false
+}
+
+func (op OpCode) IsStaticJump() bool {
+	return op == JUMP
+}
+
 const (
 	// 0x0 range - arithmetic ops
 	STOP OpCode = iota
diff --git a/core/vm/segments.go b/core/vm/segments.go
new file mode 100644
index 000000000..fd4065149
--- /dev/null
+++ b/core/vm/segments.go
@@ -0,0 +1,44 @@
+package vm
+
+import "math/big"
+
+type jumpSeg struct {
+	pos uint64
+	err error
+	gas *big.Int
+}
+
+func (j jumpSeg) do(program *Program, pc *uint64, env Environment, contract *Contract, memory *Memory, stack *stack) ([]byte, error) {
+	if !contract.UseGas(j.gas) {
+		return nil, OutOfGasError
+	}
+	if j.err != nil {
+		return nil, j.err
+	}
+	*pc = j.pos
+	return nil, nil
+}
+func (s jumpSeg) halts() bool { return false }
+func (s jumpSeg) Op() OpCode  { return 0 }
+
+type pushSeg struct {
+	data []*big.Int
+	gas  *big.Int
+}
+
+func (s pushSeg) do(program *Program, pc *uint64, env Environment, contract *Contract, memory *Memory, stack *stack) ([]byte, error) {
+	// Use the calculated gas. When insufficient gas is present, use all gas and return an
+	// Out Of Gas error
+	if !contract.UseGas(s.gas) {
+		return nil, OutOfGasError
+	}
+
+	for _, d := range s.data {
+		stack.push(new(big.Int).Set(d))
+	}
+	*pc += uint64(len(s.data))
+	return nil, nil
+}
+
+func (s pushSeg) halts() bool { return false }
+func (s pushSeg) Op() OpCode  { return 0 }
diff --git a/core/vm/stack.go b/core/vm/stack.go
index 009ac9e1b..0046edec2 100644
--- a/core/vm/stack.go
+++ b/core/vm/stack.go
@@ -42,6 +42,9 @@ func (st *stack) push(d *big.Int) {
 	//st.data = append(st.data, stackItem)
 	st.data = append(st.data, d)
 }
+func (st *stack) pushN(ds ...*big.Int) {
+	st.data = append(st.data, ds...)
+}
 
 func (st *stack) pop() (ret *big.Int) {
 	ret = st.data[len(st.data)-1]