The ELF stuff and assemblers should be simplified:

• Change buffer iterators to reader/writer types which can read/write anything implementing a Readable/Writable interface
• Give up on buffer-backed ELF objects - pretty but not useful
• POJO ELF things that are Readable/Writable
• Assembler should probably extend Writer, not delegate to it

Originally I was thinking we could define a universal notion of cross-compilation target, with multiple variable components. However, every tool has a slightly different interpretation of this concept and even the same tool can report different targets depending on how it was built.

We need to be able to:

• Specify the target that is being built for
• Identify the target of a single-target tool like gcc or clang, and compare it to the specified target
• Specify the target of a multi-target tool like lcc or opt, and/or
• Encode the target into LLVM bit code in the LLVM way to be the specified target

ObjRef.fields should contain only QType values, for instance.

Implement the native (C) plugin:

• Structure and type probes
• Constant probes
• Transform C-types-as-classes into corresponding Type instances
• CNative: addr_of operators
• CNative: alignof/offsetof/sizeof operators
• CNative: alloca
• CNative: ascii[z]ToJavaString/utf8[z]ToJavaString
• CNative: auto operator
• CNative: constant operator
• CNative: copy implementations
• CNative: defined operator
• CNative: elementCount operator
• CNative: isComplete/isSigned/isUnsigned operators
• CNative: word/uword/zero operators
• CNative: va_arg and related operators (new node types)

Generate configuration infrastructure. Needs #12 to detect config classes.

Defining a void method throws the following error:

<stdin>:3: error: /opt/llvm/bin/llc: instructions returning void cannot have a name
error: `llc` invocation has failed for ./main/output.ll: cc.quarkus.qcc.machine.tool.CompilationFailureException: Compiler terminated with exit code 1
Compilation failed with 2 error(s)

PR with fix available shortly.

Typically in node.getPredecessors().

The initial dispatch algorithm will amount to using comparisons against the numerical class ID of the target object. This implementation is simple to implement, while also aggressively favoring devirtualization. However there are many cases which might be better served by a more sophisticated solution.

This task is to identify different likely dispatch cases and their characteristics, to research possible dispatch strategies, and to determine the best strategy to use for each case and the tradeoffs therein.

There's really no need to clutter the final image with these annotations. But it does mean that all of the plugin classes that are looking for these annotations in the visible set will have to be adjusted to looking in the invisible set instead.

The graph API has evolved considerably over the period of this project. After #67 it should be considered whether the graph API should be extracted (again) into a separate package or even module. Included tasks are:

• Examine the possibility of establishing a separate interface hierarchy for leaf node types, so that every possible node type is easily enumerable and visitable without confusing sub/supertype relationships (e.g. TryInvocation extends Goto because the normal path works like Goto does; should there be a separate interface for Goto-the-behavior versus Goto-the-leaf-node-type?)
• Determine whether it is beneficial to have distinct leaf types for every Value type, even types with similar shape and properties (e.g. CommutativeBinaryVakue vs Add/Multiply/CmpEq/Xor/etc.)
• Determine whether the leaf node types should be interfaces with implementation classes, or implementation classes directly (complicated by the multiply-inherited node traits defined by the Value hierarchy)
• Crystalize the behavioral properties of the graph nodes, and strip away implementation which violates those properties:
  • BasicBlocks consist of two parts: the "label" (presently NodeHandle) and the terminator (i.e. Terminal instruction); since basic blocks form a control flow graph that may contain cycles, they necessarily must be allowed to be built thusly (in two stages)
  • Most nodes are not replaceable at any time, thus this functionality on Node is probably an attractive nuisance
  • Type ought not be a Node at all (this was an early design mistake when it was assumed that types would need to be substitutable, but this approach is not practical)
  • BasicBlock only extends Node for NodeHandle, and it is the only type that uses it; this should be cleaned up
• Clean up extraneous node types:
  • PinnedNode is an unnecessary intermediate, since PhiValue is the only possible subtype I've introduced a "block entry" node which is pinned to the block, and on which the block's terminator must depend; the optimizer will be tasked with moving dependencies around in order to hoist dependants of the pinned node (this was already a reality though it was hidden from view due to using null as a placeholder to mean block entry)
  • ValueTerminator is no longer needed (it was needed when GraphFactory returned the node instead of the terminated basic block for invoke-in-try nodes)

This list is not exhaustive.

The VM API and the type definition types need to converge; the former are effectively redundant after the class definition redesign.
Having both types adds complexity for no gain.

• JavaMethod → MethodElement
• JavaConstructor → ConstructorElement
• JavaField → FieldElement

Also let's look at:

• JavaClass → DefinedTypeDefinition

We need to install LLVM in our GitHub Actions CI configuration before CI can test LLVM-based code generation.

The sequential BasicBlockBuilder chain implementation is useful for getting us off the ground, but to support serious mutually-recursive optimization with a reasonable time complexity, we're eventually going to need a proper pattern matching engine. Fortunately Java lends itself fairly well to such things.

It should be possible to write methods like this:

@Rule
public Value add(BasicBlockBuilder self, Add v1, Value v1v1, Literal v1v2, Literal v2) {
    return self.add(v1v1, self.add(v1v2, v2));
}

And have a tool that can look at that method (and others like it) and combine them into a single BasicBlockBuilder implementation whose add method will:

• examine its first parameter "v1" (using a ValueVisitor implementation), and if it is an Add...
• examine the add's second parameter "v1v2" (using a ValueVisitor implementation), and if it's a Literal...
• example the outer add's second parameter "v2" (using a ValueVisitor implementation), and if it's a Literal...
• generate a method call to the given method, providing...
• itself as the first parameter
• the outer add's first value, cast as an Add, as the second parameter
• the inner add's first value as the third parameter
• the inner add's second value, cast as a Literal, as the fourth parameter
• the outer add's second value, cast as a Literal, as the fifth parameter

Furthermore, it would recognize that Add is commutative, and so generate matches for all four equivalent permutations automatically. The information above should be extracted from method name and return type along with the the types, names, and possibly order of the method parameters. It could be done as an annotation processor during the build of QCC, so that the entire data structure is ready to go when QCC runs.

It should be possible to inject BasicBlockBuilders that delegate back to the current pattern matcher (self) or to the next block builder (next), allowing pattern matches to terminate or recurse.

In addition to matching the type of the node and its values, it should also be possible to match value.getType(), for example:

@Rule
public Value add(BasicBlockBuilder self, Value v1, FloatType v1Type, Value v2, SignedIntegerType v2Type) {
    // ...
}

This would match calls to add with a value whose type is a FloatType and another value whose type is a SignedIntegerType,again recognizing commutativity to generate both permutations, again using a visitor to match the types. Note that there is no visitor interface for types yet, but this will be necessary and should be introduced regardless.

By using visitors for double dispatch and generating nested levels during build as needed (effectively a DFA), each pattern can be matched in effectively constant time relative to the number of rules or linear time relative to the rule depth (which is typically extremely small), and a pattern can match arbitrarily deep constructs, limited only by the maximum number of arguments on a method.

This feature could be implemented as an annotation processor or as a Maven mojo. The plugin or mojo would find all classes within a module with rule methods and assemble them into one single rule set during the build of that module. Merging rules between modules is probably not feasible and is not necessary at any rate.

It may be worth exploring using the same engine to produce handlers for the copying and visiting stages. A visitor pattern matcher would greatly simplify lowering to LLVM, for example, eliminating if/else constructs.

The current cc.quarkus.qcc.graph.schedule.Schedule implementation uses a textbook algorithm for determining the dominator tree, and then implements half (the easy half) of Cliff Click's GCM - the "schedule early" part. While this schedule will aggressively hoist variables out of loops, it is not an ideal as it is far too eager. As a result it relies heavily on LLVM coming up with something better. In addition, the virtual JVM will likely end up doing more work than needed with this schedule.

We should have a better scheduler which can strike a better balance between hoisting operations out of loops and delaying evaluation as much as possible. Click's GCM algorithm has a "schedule early" and "schedule late" stage; this could provide good results.

Footnote: what is the scheduler anyway....

The scheduler is essentially a piece of code that looks at the node graph of a method or function and assigns each node to a basic block. That assignment is then used by the generator to produce a sequential list of instructions to submit to the compiler.

Code generation may vary significantly based on the version of the toolchain installation. The API should have methods to compare the toolchain version against a version string or perhaps a major, minor pair. Use the SmallRye Common Version library to help with the string manipulation.

It would be nice to improve method lookup. Right now, this is what is necessary to find the standard main method:

        DefinedTypeDefinition stringClass = bcc.findDefinedType("java/lang/String");
        if (stringClass == null) {
            context.error("String class not found (missing JDK?)");
            return delegate;
        }
        TypeSystem ts = context.getTypeSystem();
        LiteralFactory lf = context.getLiteralFactory();
        ReferenceType stringArray = ts.getReferenceType(lf.literalOfArrayType(ts.getReferenceType(stringClass.validate().getTypeId())));
        int idx = userMainClass.validate().resolve().findMethodIndex("main", MethodDescriptor.of(ParameterizedExecutableDescriptor.of(stringArray), ts.getVoidType()));
        if (idx == -1) {
            context.error("No main method found on main class %s", mainClassName);
            return delegate; // bail out
        }
        final MethodElement userMain = userMainClass.validate().getMethod(idx);

(edited because it's actually even worse)

Certain functions will have to become core intrinsics in order to allow the JVM to function at all. Intrinsics are implemented as a delegating GraphFactory implementation which transforms certain method calls.

Note that only methods that cannot be implemented directly in Java should be made into intrinsics.

• Introduce intrinsics plugin, which includes the GraphFactory implementation along with an efficient registry (intrinsic lookup should be an O(1) operation)
• Thread.currentThread() should translate to a special Value, which will ultimately be read from an implicit parameter of every Java method
• java.lang.Class#cast
• java.lang.Class#isArray
• java.lang.Class#isAssignableFrom
• java.lang.Class#isInstance
• java.lang.Class#isInterface
• java.lang.Class#isPrimitive
• java.lang.Object#clone - custom Value probably
• java.lang.Object#getClass - could be native code?
• java.lang.Object#hashCode - could be native code?
• java.lang.Throwable#fillInStackTrace
• The operations within cc.quarkus.api.Values should be mapped to their corresponding Value implementations
• The operations in cc.quarkus.api.Tuning should be implemented to modify the likelihood of their corresponding operations
• cc.quarkus.c_native.api.Pin should be implemented by way of special Values and memory operations (todo: see if this can be done via the native API instead)

Add more required intrinsics here. Do not add things that should be implemented using c_native, or things which are intrinsics for optimization reasons. Most Unsafe methods should be implemented in Java to relay to Values or use c_native directly.

Exception in thread "main" java.lang.StackOverflowError
    at cc.quarkus.qcc.graph.literal.ClassTypeIdLiteral.isSubtypeOf(ClassTypeIdLiteral.java:21)
    at cc.quarkus.qcc.graph.literal.ClassTypeIdLiteral.isSubtypeOf(ClassTypeIdLiteral.java:21)
    at cc.quarkus.qcc.graph.literal.ClassTypeIdLiteral.isSubtypeOf(ClassTypeIdLiteral.java:21)
    at cc.quarkus.qcc.graph.literal.ClassTypeIdLiteral.isSubtypeOf(ClassTypeIdLiteral.java:16)
    at cc.quarkus.qcc.graph.literal.TypeIdLiteral.isSupertypeOf(TypeIdLiteral.java:37)
    at cc.quarkus.qcc.type.ReferenceType.join(ReferenceType.java:85)
    at cc.quarkus.qcc.type.ReferenceType.join(ReferenceType.java:95)
    at cc.quarkus.qcc.type.ReferenceType.join(ReferenceType.java:95)

ReferenceType computes new superclass types correctly but if nullable, it calls asNullable on the current type which results in an endless loop.

A fix to call asNullable on the computed superclass reference type seemed to work.

It is useful to combine probes whenever possible. CTypeProbe has already gained the ability (since b377612) to probe many types at once; it should also be able to probe symbol values as well.

One case for this is to probe the standard C symbol BYTE_BITS rather than assuming a value of 8; another case would be to probe the alignment of functions.

The virtual JVM needs to be able to relay objects from the host JVM. The following tasks are required:

• Instantiate and populate arrays
• Instantiate Strings

Simplify the project structure.

• Move the LLVM backend to plugins
• Eliminate the compiler/generator subtree
• Move the compiler/graph subtree back up to compiler
• Move native/crt to runtime

This gives us the following general structure:

• compiler
• driver
• machine
  • arch
  • file
    • bin
    • elf
    • macho
    • object
  • llvm (this is the ll generation API)
  • probe
  • tool
    • api
    • clang
    • gnu
    • llvm (this is the llc/opt invocation API)
• main
• native
  • api
  • a module for each native OS comprising necessary interfaces to that OS's library set
  • a module for each cross-OS library or logical grouping of libraries
• plugins
  • llvm
  • patcher
  • (soon) native
  • (later) various optimization and checking plugins
• runtime

To support invokedynamic, the first step must be to support the parsing of the bytecode. A few things are necessary for this to happen.

• Support the necessary constant types in ClassFileImpl
• Create InvokeDynamic (implementing Action) and possibly InvokeDynamicValue (implementing Value) node types
• Create a method or methods on BasicBlockBuilder to create the node type(s)

The initial interpreter is basically a graph iterator which keeps stack frames as hash maps mapping Value to boxed Objects. This might end up being good enough, but I doubt it. We will likely want to come up with a better interpreter that JIT-compiles code blocks into bytecode to run on the host JVM.

@headius and @enebo have taken some initial looks at what this might entail.

Since it is expected that the initial interpreter will suffice for the purposes of the initial implementation, there is no milestone on this issue.

For the second milestone, we need to fully implement local variable operations, and modify the method bytecode parser to generate the corresponding nodes. They are:

• Local variable create
• Load
• Store
• Get address (see also #61)
• End scope (but see footnote)

Footnote: the notion of a lexical scope exists at a Java level, and can exist at an LLVM level (see @llvm.stacksave and @llvm.stackrestore), however it does not exist at a bytecode level, wherein local variable lifespan is not necessarily nested or constrained by scope. Therefore, in many cases, it will be impossible to end the scope of some variables before the end of the corresponding method body. That said, detecting constrained scope may be useful in terms of conserving stack storage so it should remain a consideration, if only for later.

Plugins will generally need access to element annotations (which are currently supported, more or less), but they will also need access to the complete generic annotated types for some classes, variables, and values. The generic type (if valid) will have to flow through with the values in order for plugins to be able to evaluate and act on them. For example, the C native plugin will need to be able to evaluate @restrict ptr<size_t> and transform it into the appropriate Type.

There is a functional annotation abstraction, and a proof-of-concept implementation of type signatures, but type path evaluation remains unimplemented. It might be reasonable to implement a GenericType hierarchy that runs alongside of Type, and some provision to indicate that a value has no generic type, or the generic type is not valid (which is permissible but has consequences for reflection APIs), and so on.

Right now the toolchain provider lookup is based on finding toolchains in groups, preferring e.g. GCC first (all locations), then Clang, etc. This is not optimal because it's possible (for example) to have a GCC cross-compiler get selected before the main GCC or Clang installation.

Most configuration systems will look for cc first, then gcc, etc., identifying what the "actual" compiler is and testing it before moving on to the next option. We should do the same.

The only way to currently test QCC is to manually create a java.base Maven artifact and install it, which is a significant hurdle to onboarding.

We need JDK artifacts. A proof-of-something implementation is presented here, but this needs to be done better, to meet more requirements:

• Produce an OS independent artifact for each JDK module
• Include QCC patch code in each module

Some requisite tasks:

• Establish base project with a Git submodule for the corresponding JDK upstream
• Define Maven modules for each JDK build module
• Supplement or patch the JDK Makefile(s) in order to build OS-neutral (Java only) artifacts for each JDK module, which includes all of the platform-specific classes for each module
• Create source directories within each Maven module for classes which are duplicated (with modifications) between each OS (see below) and for patch and native implementation classes
• Create a process whereby the upstream repository can be tracked, such that changes to the upstream repository can be (at least manually, and later maybe partially automatically) applied to the corresponding downstream code

In order to find all source files in OpenJDK which have different variations based on platform, try the following command:

find `find \`find src -name share -or -name unix -or -name linux -or -name macosx -or -name windows -or -name aix -or -name solaris -or -name posix\` -name classes` -name \*.java -type f -printf '%P\n' | sort | uniq -c | sort -rn

Note: This epic should be transferred to a new repository which will meet these goals, with issues for each subtask.

ShrinkWrap Resolver is included as an easy way to bootstrap and test the project. This should probably be replaced with simple builder methods on the main driver which accept the paths of the bootstrap module JARs. ShrinkWrap Resolver could be used in tests, but it brings in numerous extraneous dependencies and complexity (and potential conflict with downstream project tests) so it should not be a part of the core API.

In order to unambiguously name an LLVM function that corresponds to a method, the name must be uniquely derived from the method's enclosing class (including its class loader), name, return type, and parameter type(s). This can result in very long names in some cases.

It would be nicer if there was a way to encode the names in a more compact manner. However it is difficult to imagine a scheme that results in shorter names without compromising readability or build reproducibility.

Research some possible strategies for a more terse name encoding scheme.

The basis of the QCC optimization system is that optimizations must run in either a single pass, or in two passes, in linear or near-linear time compared to the program size.

Collect a set of useful one-pass and two-pass optimizations that can be plausibly implemented. From there, determine which optimizations should be implemented and establish an issue with a design for each one.

Get the i18n rigging set up.

• Message module(s)
• LogManager setup for tests (in the parent POM?)

The type system is left over from two distinct experiments, and furthermore does not integrate @bobmcwhirter's work on constraints. Rework the type system as follows:

• Provide a TypeSystem type which can yield the target-/configuration-specific types for pointers, references, etc. with appropriate sizes and alignments
• Introduce relational types as types that are partially comparable
• Eliminate the old ClassType and friends in favor of class/interface/array runtime type identifiers which are relationally comparable and which can be lowered into (potentially small) integers
• Introduce a simple Reference type using constraints for type checks
• Move all type-related classes and interfaces back to the .type subpackage

We will need an inline assembly API. The LLVM backend can pass it through via (the LLVM asm capability)[https://llvm.org/docs/LangRef.html#inline-assembler-expressions].

Inline assembly would be used for:

• Emitting safepoint probes (to avoid a more expensive load)
• Trapping integer division-by-zero (to avoid a more expensive manual zero-check)
• Trapping null dereferencing (to avoid a more expensive manual null-check)

Since some (or all) of these would result in a signal handler throwing an exception, we'd need both Try and "normal" variants. Since some assembly could return a value, we'd also need both Value and "void" variants.

The implementation should be a static method or methods that are implemented as intrinsics, e.g. public static native void asmV(String opcode, String constraints, boolean sideEffect, object... arguments);.

The following code prints 1 as expected:

putchar(1 == 1 ? '1' : '0');

However, the following prints 01:

int a = 1;
int b = 1;
putchar(a == b ? '1' : '0');

We need a canonical strategy for object layouts, and some code (API & implementation) to implement that strategy. The backend must be able to query the object layout.

The following factors must be considered:

• Alignment requirements and directives
• Monitor support (and relation to stack-allocated objects, for which monitors are meaningless)
• GC or heap implementation specific bits (and interactions with stack allocations)
  (and more)

The graph class names do not reflect their more limited scope:

• GraphFactory → BasicBlockBuilder
• GraphVisitor → BasicBlockVisitor

During image build, the run-time-visible heap must be stored using some strategy that enables the heap to be quickly restored at run time.

The primary requirement is that heap restoration should be as fast as possible. This ties in tightly with #73.

Set up Jandex for our modules. Maybe activate a profile when a marker file is present...

There are several correctness transformations that are intended to be employed by a core plugin, in order to keep the bytecode parser as simple as possible. These transformations correspond to detection of run-time problems that would otherwise cause undefined behavior (UB) on the back end or a crash. We need a code correctness plugin which performs the following tasks:

• Automatic narrowing/widening/value cast/bitcast where type mismatches occur in operations
• Null checking of dereferences for methods, fields, and array accesses
• Zero divisor checking for integer divisions
• Range checking for array accesses
• Detect incompatible class changes (static invocation of instance method and vice-versa, etc) and replace such calls with IncompatibleClassChangeError throw
• Consider moving the validation logic around checkcast and instanceof out of the core bytecode parser and into this plugin
• Shift distance masking to 32 or 64 (and with 0x1f or 0x3f) (*shl,*shr,*ushr)
• Range checks (saturation) for fp-to-integer conversions where the result is out of the range of the target type
• Auto-boxing/unboxing of arguments to methods, values being stored in fields and arrays, values being read from fields and arrays

Additional tasks should only be as required; in particular, optimizations should be excluded from this plugin (at least for now) and implemented separately.

A number of very similar types have identical names between QCC and LLVM. This causes difficulty with regards to reading the code and debugging errors.

Resolve the conflict somehow (maybe add a prefix to the LLVM types e.g. LLValue, LLBasicBlock, etc.).

We will need an effective escape analysis algorithm. Escape analysis will be used to eliminate allocations and to determine whether objects can be stack-allocated. There are other applications as well.

In order to help people to get started on the project, add a docs directory containing a README.adoc as well as other files covering the design of the project.

Class definition is currently broken due to invalid recursion/stack overflow.

Implement a single method reference concept to replace method identifiers and method handles. Any time an invoke instruction is encountered, a method reference on the "owner" class is looked up or created. If the method is absent, a negative is cached, otherwise the method reference will directly reference the exact method body. Drop the virtual method body for now (this could be implemented on the back end and interpreter separately instead).

We need an overall garbage collection design proposal. We have certain requirements:

• Favor a heavily request-oriented usage profile
• Optimize for smaller (but not necessarily tiny) heaps
• Optimize for fast startup (i.e. minimize setup time)
• Optimize for minimal pausing

And non-requirements:

• QCC applications cannot unload classes; therefore a permanent "generation" is indicated and support for unloading classes is not required

In addition, the overall design should be able to support a "epsilon"/no-GC mode of operation.

This implies certain design parameters:

• Exploring stack allocation in conjunction with (closed-world) escape analysis
• Probably a generational copying collector as an implementation
• Support for compressed references on 64-bit platforms

The garbage collector design proposal must include an SPI that can be implemented by multiple heap+GC implementations. In addition, this may require tight backend integration (i.e. LLVM). It should also include a description of allocation strategy and reference encoding and format, along with any requirements that would apply to object layout (such as object header bits and things of that nature).

The diagnostics/error reporting API is a mess. It should:

• Be independent of logging
• Support error/warn/notice/info levels
• Be aware of source location (only one level is necessary; related messages can follow)
• Support error codes for each type of problem (likely reuse i18n infrastructure for this, see #11)
• Propagate through all stages in such a way that:
  • C probes may correspond to original source file/line in such a way that C probe errors may be relayed into the main diagnostic context
  • Backend compilation errors correspond to original source whenever possible
• Employ (or at least examine) best practices established by long-lived existent static compilers such as gcc, clang as well as modern languages like rust, go etc.
• Take advantage of diagnostic location information on nodes (?)

This piece is fundamental enough that an informal design proposal should be the first deliverable.

In order to ensure that we don't make any rule-breaking/trouble-causing naming mistakes, the VM types should exchange their unacceptable prefix in favor of e.g. VMThread, VM, VMObject, etc. or something equally neutral.

Already the complexity of wiring together dependent build stages from arbitrary plugins causes a familiar set of difficulties. To solve this, bring in the wiring infrastructure from Quarkus to assemble the pieces in a predictable and useful order instead of using an arbitrarily-ordered input list.

The subproject will be extracted from the Quarkus codebase and introduced as a standalone project. The project will then be consumed by QCC, and later by Quarkus itself. It is also possible that having the subproject in common will allow merging between the wiring stages of QCC and Quarkus when integrating QCC with Quarkus, but this is not a requirement.

The initial implementation of toolchain selection is fairly unpredictable. Presently on my Linux system it consistently chooses clang rather than gcc - and clang in turn selects the wrong gcc for linking operations, finding the cross-compiler which cannot produce working code in my case.

We need to rework the toolchain detection process. It should:

• Determine what toolchains are available
• Perform a minimal test to ensure the toolchain is functional
• Implement a better algorithm to detect the preferred compiler (e.g. first see what cc is, then gcc, then clang, in that order, for non-cross-compile situations)

Need an object file abstraction for probes that lets us treat ELF, MachO, COFF etc. similarly:

• Be able to get a symbol's value by name as a boolean, int, or long
• Other things? Maybe that's enough for probe