From b19627804400901ba003f6e401366cb7d3c4290f Mon Sep 17 00:00:00 2001 From: Jeffrey Wilcke Date: Tue, 6 Oct 2015 23:39:43 +0200 Subject: core/vm: added JIT segmenting / optimisations * multi-push segments * static jumps segments --- core/vm/doc.go | 11 +++--- core/vm/instructions.go | 2 +- core/vm/jit.go | 2 ++ core/vm/jit_optimiser.go | 90 ++++++++++++++++++++++++++++++++++++++++++++++++ core/vm/jit_test.go | 43 +++++++++++++++++++++++ core/vm/opcodes.go | 12 +++++++ core/vm/segments.go | 44 +++++++++++++++++++++++ core/vm/stack.go | 3 ++ 8 files changed, 202 insertions(+), 5 deletions(-) create mode 100644 core/vm/jit_optimiser.go create mode 100644 core/vm/segments.go (limited to 'core/vm') 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] -- cgit v1.2.3