Graph based code generation #32

0x7CFE · 2013-10-05T11:06:53Z

Current JIT compiler implementation does not parse Smalltalk instructions in any way. Instructions are processed directly in a switch-case blocks.

This is simple but not beautiful. Currently we need to traverse the method instruction array at least 3 times. One pass per scanForBranches() and scanForBlockReturn() and one in the main processing loop in writeFunctionBody().

The idea is to make a single pass which will then parse bytecodes and convert them into TSmalltalkInstruction entities which will hold all corresponding info. The same approach is used in LLVM itself.

This will help us write clean code and perform various operations with the instructions much like it is done with LLVM IR code.

Base API stuff:

Convinient abstraction for Smalltalk instructions
Abstractions for BasicBlock, ParsedMethod & ParsedBlock
Iterators over instructions, basic blocks and smalltalk blocks
Visitors that make iteration easy
~~Protect TMethod* pointer in parsed entities~~
~~Provide a way to compare relative position of basic blocks and instructions~~

Control graph:

Base datatypes for graph node, graph domain, etc.
Graph generation code
Node and Domain Visitors
Recursive argument access through empty domain
Create and link tau nodes (related to type inference)

Refactoring stuff:

Tests:

Name	Written	Passed
TSmalltalkInstruction	✅	✅
InstructionDecoder	✅	✅
ABAB (#2)	✅	✅
Stack semantics	✅	✅
Stack underflow	✅	❌
Decode all methods	✅	✅
Visitors	❌	❌
Method visualization	❌	❌
ControlGraph visualization	❌	❌

Commit provides basic data structures for operating Smalltalk bytecodes in a friendly way. Base concept is stolen drom the LLVM and other software which deals with basic blocks and so on. Currently only very simple read-only interface is provided. Issue: #32

Issue: #32

Commit provides basic data structures for operating Smalltalk bytecodes in a friendly way. Base concept is stolen drom the LLVM and other software which deals with basic blocks and so on. Issue: #32

Parse method provides a way for translating compiled Smalltalk method into intermediate form convinient for analysis and modification. After method is parsed, one may traverse it using basic block or instruction iterators. Issue: #32

Issue: #32

This pass may be used to find the location of the very first temporary assignment within the provided method. Typically such writes are used to initialize the counters or instantiate temporary objects that are used in method later. This information may be used by type inference system to provide more accurate result. Issue: #32

Issue: #32

This allows reuse of TSmalltalkInstruction which was allocated once act as an instruction storage for current operation in VM. Issue: #32

Issue: #32

Previous implementation of soft VM decoded instructions manually. Parts of instructions were parsed in the actual code being executed. This was not clean and error prone. Current commit removes all pointer arithmetic because all is done within decoder of TSmalltalkInstruction. Issue: #32

Redundant fields will be refactored later Issue: #32

Issue: #32

* feature/32/stapi_tests: (39 commits) Disables stack underflow test Adds test to check whether all incomings of Phi are unique Fixes unregistered methods in image Fixes tests due to new requirements Fixes ABAB test due to new requirements Fixes ControlGraphVisualizer 1. It throws exception if file can't be created 2. It escapes chars in filename 3. If literals can't be accessed, it generates a name for the node by default Adds test to check behaviour of graph builder on stack underflow Fixes the correct order of arguments for EXPECT_* Fixes segfault in stack_semantics Removes check whether branch should jump on branches Adds tests for duplicate opcode Fixes TSmalltalkInstruction::isValueProvider (primitives provide values) Fixes test for TSmalltalkInstruction (primitives are value providers) Fixes TSmalltalkInstruction::isValueConsumer (selfReturn doesn't consume value) Fixes test for TSmalltalkInstruction (selfReturn doesn't consume value) Adds tests which checks whether branches jump not on terminators Adds test to check whether instructions linked with value providers Adds newline at EOF in ParsedBytecode.cpp Adds fixes after rebase Removes stringstream(to format message) from tests ... Conflicts: CMakeLists.txt image/imageSource.st tests/CMakeLists.txt Issue: #32

* feature/32/codegen_into_ir_func: Forces IR functions to be inlined Rewrites doAssignInstance with `@setInstanceInContext' Rewrites doAssignInstance using cached `@getObjectFieldPtr' Fixes using of `@getTempsFromContext' Rewrites primitive::arrayAtPut using cached `@getObjectFieldPtr' Rewrites doPushInstance using cached `@getInstanceFromContext' Rewrites doPushArgument using cached `@getArgFromContext' Rewrites doPushLiteral using TJITContext::getLiteral Rewrites TJITContext::getLiteral using cached `@getLiteralFromContext' Rewrites doAssignTemporary with `@setTemporaryInContext' Rewrites doPushArgument with `@getTemporaryFromContext' Adds function to_string to format names of llvm values Removes extra space in `@setObjectField' Rewrites `@getObjectFields' using `@getObjectFieldPtr' Issue: #32

* feature/32/stapi_tests: (39 commits) Disables stack underflow test Adds test to check whether all incomings of Phi are unique Fixes unregistered methods in image Fixes tests due to new requirements Fixes ABAB test due to new requirements Fixes ControlGraphVisualizer 1. It throws exception if file can't be created 2. It escapes chars in filename 3. If literals can't be accessed, it generates a name for the node by default Adds test to check behaviour of graph builder on stack underflow Fixes the correct order of arguments for EXPECT_* Fixes segfault in stack_semantics Removes check whether branch should jump on branches Adds tests for duplicate opcode Fixes TSmalltalkInstruction::isValueProvider (primitives provide values) Fixes test for TSmalltalkInstruction (primitives are value providers) Fixes TSmalltalkInstruction::isValueConsumer (selfReturn doesn't consume value) Fixes test for TSmalltalkInstruction (selfReturn doesn't consume value) Adds tests which checks whether branches jump not on terminators Adds test to check whether instructions linked with value providers Adds newline at EOF in ParsedBytecode.cpp Adds fixes after rebase Removes stringstream(to format message) from tests ... Conflicts: CMakeLists.txt image/imageSource.st tests/CMakeLists.txt Issue: #32

* feature/32/codegen_into_ir_func: Forces IR functions to be inlined Rewrites doAssignInstance with `@setInstanceInContext' Rewrites doAssignInstance using cached `@getObjectFieldPtr' Fixes using of `@getTempsFromContext' Rewrites primitive::arrayAtPut using cached `@getObjectFieldPtr' Rewrites doPushInstance using cached `@getInstanceFromContext' Rewrites doPushArgument using cached `@getArgFromContext' Rewrites doPushLiteral using TJITContext::getLiteral Rewrites TJITContext::getLiteral using cached `@getLiteralFromContext' Rewrites doAssignTemporary with `@setTemporaryInContext' Rewrites doPushArgument with `@getTemporaryFromContext' Adds function to_string to format names of llvm values Removes extra space in `@setObjectField' Rewrites `@getObjectFields' using `@getObjectFieldPtr' Issue: #32

* feature/32/stapi_tests: (39 commits) Disables stack underflow test Adds test to check whether all incomings of Phi are unique Fixes unregistered methods in image Fixes tests due to new requirements Fixes ABAB test due to new requirements Fixes ControlGraphVisualizer 1. It throws exception if file can't be created 2. It escapes chars in filename 3. If literals can't be accessed, it generates a name for the node by default Adds test to check behaviour of graph builder on stack underflow Fixes the correct order of arguments for EXPECT_* Fixes segfault in stack_semantics Removes check whether branch should jump on branches Adds tests for duplicate opcode Fixes TSmalltalkInstruction::isValueProvider (primitives provide values) Fixes test for TSmalltalkInstruction (primitives are value providers) Fixes TSmalltalkInstruction::isValueConsumer (selfReturn doesn't consume value) Fixes test for TSmalltalkInstruction (selfReturn doesn't consume value) Adds tests which checks whether branches jump not on terminators Adds test to check whether instructions linked with value providers Adds newline at EOF in ParsedBytecode.cpp Adds fixes after rebase Removes stringstream(to format message) from tests ... Conflicts: CMakeLists.txt image/imageSource.st tests/CMakeLists.txt Issue: #32

* feature/32/codegen_into_ir_func: Forces IR functions to be inlined Rewrites doAssignInstance with `@setInstanceInContext' Rewrites doAssignInstance using cached `@getObjectFieldPtr' Fixes using of `@getTempsFromContext' Rewrites primitive::arrayAtPut using cached `@getObjectFieldPtr' Rewrites doPushInstance using cached `@getInstanceFromContext' Rewrites doPushArgument using cached `@getArgFromContext' Rewrites doPushLiteral using TJITContext::getLiteral Rewrites TJITContext::getLiteral using cached `@getLiteralFromContext' Rewrites doAssignTemporary with `@setTemporaryInContext' Rewrites doPushArgument with `@getTemporaryFromContext' Adds function to_string to format names of llvm values Removes extra space in `@setObjectField' Rewrites `@getObjectFields' using `@getObjectFieldPtr' Issue: #32

0x7CFE · 2015-04-19T07:30:02Z

In order to increase granularity and maitainability, remaining tasks from the list should be processed in separate tasks.

Among them, base functionality is considered to be working.

Issue: #32