WIP: redesign interp #2655

niaow · 2022-02-27T14:37:25Z

This is an attempt to redesign interp. It is still relatively early on, but the main goals are to track side-effects more accurately and keep time complexity down.

niaow · 2022-02-27T14:38:22Z

This is still a bit more complex than I want (especially with errRuntime vs reverts)

niaow · 2022-03-01T13:25:15Z

There is one known problem right now: the memory management assumes that a store of a non-byte-multiple integer (mainly i1) is zero extended when storing and truncated when loading. This is not really correct, but should not actually be a problem. I don't really have a better idea for this.

aykevl · 2022-03-01T13:55:03Z

There is one known problem right now: the memory management assumes that a store of a non-byte-multiple integer (mainly i1) is zero extended when storing and truncated when loading. This is not really correct, but should not actually be a problem. I don't really have a better idea for this.

Why would that not be correct? All modern general-purpose ISAs are byte addressable, not bit addressable. LLVM backends lower i1 to i8. I think this assumption is correct.

niaow · 2022-03-01T14:03:21Z

From the LLVM docs for store:

When writing a value of a type like i20 with a size that is not an integral number of bytes, it is unspecified what happens to the extra bits that do not belong to the type, but they will typically be overwritten.

If I understand what this is saying, this is unspecified behavior. However, yes I expect that this is at least generally correct.

niaow · 2022-03-01T23:07:42Z

Now most of the base tests pass. The main exceptions are:

The reflect.go and json.go tests fail (this failure can be replicated by completely turning interp off, so it does not seem to be a bug in interp)
The WASM target doesn't really work right now because of bugs in ExternalInt64AsPtr (wasi is fine)
env.go, stdlib.go, and testing.go fail on emulated Cortex-M3 and RISC-V

niaow · 2022-03-03T16:01:42Z

The env.go issue is caused by internal/testlog.logger is getting corrupted. So far it is difficult to track down why.

niaow · 2022-03-03T16:39:22Z

Well I found the problem: it was a stack overflow in unicode.init, since it was not interpreted due to the allocas.

aykevl · 2022-03-13T00:10:25Z

The reflect.go and json.go tests fail (this failure can be replicated by completely turning interp off, so it does not seem to be a bug in interp)

This is probably because those rely on OptimizeReflectImplements, which in turn relies on interp.
...yes, that's a bit fragile.

niaow · 2022-03-13T01:06:28Z

The remaining issue with env.go now is that maps and other special data structures do not have attached type information (which causes the allocation to be left on the heap). I think that we do need to pass type information to these through the constructors, which implies getting the frontend to emit the compound type info.

niaow · 2022-03-19T17:16:45Z

With the latest commit, the reflect and json tests pass.

Use the existing compilerContext.createObjectLayout on the channel's underlying element to create a layout value that can be passed to the channel buffer's allocation.

Split compilerContext.createObjectLayout into two parts in preparation for calling the second part by the map creation layout function.

A Bits type for manipulating a size and a bitmap as one. Probably overkill for the needs coming up of building the layout for a hashmap but it can be shrunk down or replaced. For now, it makes the building of a bucket layout straightfoward in the next commit. Also the unit tests are a bit much given the limited use of the type.

Modify build.createMapUpdate to take the element type. Define the compilerContext.createMapLayout for creating a hashmap bucket layout. Pass the hashmap layout to the hashmapMake and hashmapSet functions. Define a hashmapBucketLayout function that takes sizes and bitmaps for the key and element types of a map and returns the size and bitmap for the bucket type. This is the function that needs to be kept in sync with the bucket layout implemented by src/runtime/hashmap.go. In src/runtime/hashmap.go, modifies arguments to hashmapMake and the hashmapSet family of functions to take the layout parameter in order to get the layout value passed to the alloc call.

FrankReh

Given my confusion regarding pointerAlign vs pointerSize, the first parameter name to createObjectLayout1 is then a misnomer. Maybe both should be passed to createObjectLayout1 or maybe createObjectLayout1 should should compute those two values again on its own.

FrankReh · 2022-03-20T21:21:03Z

compiler/llvm.go

@@ -102,6 +101,70 @@ func (c *compilerContext) createObjectLayout(t llvm.Type, pos token.Pos) llvm.Va
 		layout := (uint64(1) << 1) | 1
 		return llvm.ConstIntToPtr(llvm.ConstInt(c.uintptrType, layout, false), c.i8ptrType)
 	}
+	return c.createObjectLayout1(pointerSize, objectSizeBytes, bitmap, pos)


My version passed a pointerSize. But with the change to line 163, this should also be the alignment. Maybe better to pass both or pass neither and just recompute them in createObjectLayout1.

FrankReh · 2022-03-20T21:22:18Z

compiler/llvm.go

+	// We know there are pointers, we added one ourself for the bucket overhead
+	// so no check for that.
+
+	return c.createObjectLayout1(pointerAlign, mSizeBytes, mbitmap, pos)


This shouldn't pass the alignment unless the earlier call does too.

FrankReh · 2022-03-20T21:23:43Z

compiler/llvm.go

+}
+
+func (c *compilerContext) createObjectLayout1(pointerSize, objectSizeBytes uint64, bitmap *big.Int, pos token.Pos) llvm.Value {
+	pointerAlignment := c.targetData.PrefTypeAlignment(c.i8ptrType)


This is one of the causes of confusion. I got the alignment here, without passing it from the caller.

Fix the bucket size for the case of a key or value or both being smaller than a pointer. Fix the layout construction when the pointer alignment is smaller than the pointer width.

niaow · 2022-03-25T14:20:25Z

I am not really sure how I feel about this. I have gotten a lot working so far, but this is just way too big and complicated right now.

niaow · 2022-06-11T17:17:39Z

Some things that went right with this attempt:

The fixed-shape tree used for memory works quite well and has predictable overhead
The bit cat and slice mechanisms simplify memory handling a lot
Side-effect calculation is fairly accurate
The structure of each instruction using offsets into a list to get inputs and then appending its outputs to that list works well
The structure of the constructed representation works well, and the depth-first traversal of the dominator tree simplifies the construction of the internal interp representation
It is relatively easy to debug behavior
The "resolve" process on arguments is effective and flexible

Some things that went wrong with this attempt:

The whole distinction between errRuntime and errRevert is very confusing
There are still a few cases where repeated reverts can result in O(bad) overhead with repeated restoration of memory state
Memory lifetimes get stretched when they are used at runtime
Structs in interfaces are quite heavy, so functions use more memory than they really need to
The lack of access to the bodies of functions from imported packages (e.g. errors.New) forces extra work to be done after linking
The process of implementing an instruction is excessively complicated
The bit-concatenation type is not properly comparable
Its just too big, although this might be necessary
The "resolve" process on arguments is unnecessarily slow

ZauberNerd mentioned this pull request Mar 5, 2022

Replace initialization code for decode ifaceType go-yaml/yaml#828

Closed

niaow force-pushed the newer-interp branch 2 times, most recently from a0df4b9 to ac5f18f Compare March 18, 2022 21:22

FrankReh added 4 commits March 19, 2022 19:12

alloc layout: chanMake

a3e247c

Use the existing compilerContext.createObjectLayout on the channel's underlying element to create a layout value that can be passed to the channel buffer's allocation.

alloc layout: split compiler/createObjectLayout

277c4d2

Split compilerContext.createObjectLayout into two parts in preparation for calling the second part by the map creation layout function.

niaow force-pushed the newer-interp branch from 85be64b to 934adce Compare March 20, 2022 12:59

FrankReh reviewed Mar 20, 2022

View reviewed changes

FrankReh and others added 10 commits March 20, 2022 18:26

alloc layout: fix small buckets and alignment

607a771

Fix the bucket size for the case of a key or value or both being smaller than a pointer. Fix the layout construction when the pointer alignment is smaller than the pointer width.

wip

49a3967

change flush ordering to ascending order

50abd55

implement alignment handling

84a724f

[ci skip] escape runtime inputs

8dfefcf

[ci skip] do not try to interp noinline functions

212770f

[ci skip] implement runtime.alloc as an interp intrinsic

8f7e36e

[ci skip] discard trackPointer/debug/lifetime

dee134f

[ci skip] misc

3848f90

[ci skip] parse metadata

3e7300d

niaow added 16 commits March 21, 2022 09:03

[ci skip] fix calculation of side-effects

59f31e1

[ci skip] fix heap initialization on wasm and switch

ab07ba5

[ci skip] add context to errors

2a304e8

[ci skip] intrinsic runtime.runtimePanic

74f1e6b

[ci skip] misc

24523a9

[ci skip] implement alloca

d4c1bbd

[ci skip] implement shifts

3b9886a

[ci skip] implement bitwise ops

37e2808

[ci skip] implement the select instruction

89cfb06

[ci skip] fix udiv and add sdiv

92ff39e

[ci skip] cleanup

cd83345

[ci skip] implement memset intrinsic

c719d42

[ci skip] implement memcpy and memmove

7edd0fe

[ci skip] misc reflection

26b310e

[ci skip] move alloc layout parse to exec

65d90e7

[ci skip] memory management fixes

c58ad78

niaow force-pushed the newer-interp branch from 1e820c2 to c58ad78 Compare March 21, 2022 13:06

niaow added 5 commits March 21, 2022 11:27

[ci skip] redo layout to increase type alignment

d6b4d3f

[ci skip] fix heap initialization on Windows and Unix

af973bd

[ci skip] implement urem and srem

ba65ffc

[ci skip] initial floating point support

fd1f6e0

[ci skip] fix srem and urem support

20918c0

Provide feedback

Saved searches

Use saved searches to filter your results more quickly

WIP: redesign interp #2655

WIP: redesign interp #2655

niaow commented Feb 27, 2022

niaow commented Feb 27, 2022

niaow commented Mar 1, 2022

aykevl commented Mar 1, 2022

niaow commented Mar 1, 2022

niaow commented Mar 1, 2022

niaow commented Mar 3, 2022 •

edited

Loading

niaow commented Mar 3, 2022

aykevl commented Mar 13, 2022 •

edited

Loading

niaow commented Mar 13, 2022

niaow commented Mar 19, 2022

FrankReh left a comment

FrankReh Mar 20, 2022

FrankReh Mar 20, 2022

FrankReh Mar 20, 2022

niaow commented Mar 25, 2022 •

edited

Loading

niaow commented Jun 11, 2022 •

edited

Loading

WIP: redesign interp #2655

Are you sure you want to change the base?

WIP: redesign interp #2655

Conversation

niaow commented Feb 27, 2022

niaow commented Feb 27, 2022

niaow commented Mar 1, 2022

aykevl commented Mar 1, 2022

niaow commented Mar 1, 2022

niaow commented Mar 1, 2022

niaow commented Mar 3, 2022 • edited Loading

niaow commented Mar 3, 2022

aykevl commented Mar 13, 2022 • edited Loading

niaow commented Mar 13, 2022

niaow commented Mar 19, 2022

FrankReh left a comment

Choose a reason for hiding this comment

FrankReh Mar 20, 2022

Choose a reason for hiding this comment

FrankReh Mar 20, 2022

Choose a reason for hiding this comment

FrankReh Mar 20, 2022

Choose a reason for hiding this comment

niaow commented Mar 25, 2022 • edited Loading

niaow commented Jun 11, 2022 • edited Loading

niaow commented Mar 3, 2022 •

edited

Loading

aykevl commented Mar 13, 2022 •

edited

Loading

niaow commented Mar 25, 2022 •

edited

Loading

niaow commented Jun 11, 2022 •

edited

Loading