If it's true that a C program doesn't have control of the stack, what does that mean for supporting the stack switching in Wastrel? Can you not reify the stack and replace it with another from a suspended async function? Do you need some kind of userland stack for all stacks once you support WASM stack switching?
2 additional points,
1: The article mentions DWARF, even without it you can use #line directives to give line-numbers in your generated code (and this goes a very long way when debugging), the other part is local variables and their contents.
For variables one can get a good distance by using a C++ subset(a subset that doesn't affect compile time, so avoid any std:: namespaced includes) instead and f.ex. "root/gc/smart" ptr's,etc (depending on language semantics), since the variables will show up in a debugger when you have your #line directives (so "sane" name mangling of output variables is needed).
2: The real sore point of C as a backend is GC, the best GC's are intertwined with the regular stack-frame so normal stack-walking routines also gives everything needed for accuracte GC (required for any moving GC designs, even if more naive generation collectors are possible without it).
Now if you want accurate somewhat fast portable stack-scanning the most sane way currently is to maintain a shadow-stack, where you pass prev-frame ptrs in calls and the prev-frame ptr is a ptr to the end of a flat array that is pre-pended by a magic ptr and the previous prev-frame ptr (forming a linked list with the cost of a few writes, one extra argument with no cleanup cost).
Sadly, the performant linked shadow-stack will obfuscate all your pointers for debugging since they need to be clumped into one array instead of multiple named variables (and restricts you from on-stack complex objects).
Hopefully, one can use the new C++ reflection support for shadow-stacks without breaking compile times, but that's another story.
There's also the issue in that the following two things don't have the same semantics in C:
float v = a * b + c;
static_inline float get_thing(float a, float b) {
return a*b;
}
float v = get_thing(a, b) + c;
uintptr_t's don't actually have the same semantics as pointers either. Eg if you write:
void my_func(strong_type1* a, strong_type2* b);
void my_func(some_type_that_has_a_uintptr_t1 ap, some_type_that_has_a_uintptr_t2 bp) {
float* a = get(ap);
float* b = get(bp);
}
I like compiler backends, but truth be told, I grow weary of compiler backends.
I have considered generating LLVM IR but it's too quirky and unstable. Given the Virgil wasm backend already has a shadow stack, it should now be possible for me to go back to square one and generate C code, but manage roots on the stack for a precise GC.
Hmm....
I think emitting something like
#line 12 "source.wasm"
I was thinking about how to embed custom high level language into my backend application written in C++. Each individual script would compile to native shared lib loadable on demand so that the performance stays high. For this I was contemplating exactly this approach. Compile this high level custom language with very limited feature set to plain C and then have compiler that comes with Linux finish the job.
(My experience with "compile to C" is with cfront, the original C++ implementation that compiled to C. The generated code was just terrible to read.)
Often times virtual functions are implemented in C to provide an interface (such as filesystem code in the Linux kernel) via function pointers—-just like C++ vtable lookups, these cannot be inlined at compile time.
What I wonder is whether code generated in C can be JIT-optimized by WASM runtimes with similar automatic inlining.
Yet you trust it to generate the frame for this leviathan in the first place. Sometimes C is about writing quality code, apparently, sometimes it's about spending all day trying to outsmart the compiler rather than take advantage of it.
You could put each stack frame into a struct, and have the first field be a pointer to a const static stack-map data structure or function that enumerates the pointers within the frame.
BTW, the passed pointer to this struct could also be used to implement access to the calling function's variables, for when you have nested functions and closures.
I really wish someone on the C language/compiler/linker level took a real look at the problem and actually tried to solve it in a way that isn't a pain to deal with for people that integrate with the code.
I’ve done a few such things for compiling ML models, but in the end I always regretted it.
float v = (float) ((float) a) * ((float) b) + c;
float v = ((float) a) * ((float) b) + c;
You can find all the possible tricks in making it debuggable by reading the y.tab.c
Including all the corner cases for odd compilers.
Re2c is a bit more modern if you don't need all the history of yacc.
Then, we have both a precise semantics and tools to help produce robust output.
I found this Reddit thread that gives a bit more detail:
https://www.reddit.com/r/haskell/comments/1pbbon/c_as_a_proj...
and the project link:
We used this in production with Nim for embedded firmware engineering at my previous job doing industrial IoT systems, which let us write a much nicer language than C (and much faster, much safer), with code-sharing between the network server (and its comms protocol) and the firmware code itself.
All can be done with C itself of course, but this let us achieve it faster and in a much nicer fashion
(though it is fine if GC can only happen inside a function call and the call takes the shadow stack as an argument)
Not necessarily! Floating-point contraction is allowable essentially within statements but not across them. By assigning the result of a * b into a value, you prohibit contraction from being able to contract with the addition into an FMA.
In practice, every compiler has fast-math flags which says stuff it and allows all of these optimizations to occur across statements and even across inline boundaries.
(Then there's also the issue of FLT_EVAL_METHOD, another area where what the standard says and what compilers actually do are fairly diametrically opposed.)
But yes, you can put a line-oriented breakpoint on your action code and step through it.
I'd have to do an actual project to see how annoying it is to lower semantics to unsafe Rust to know for sure, but my guess is you'd be slightly better off because you don't have to work around implicit conversions in C, the more gratuitous UBs in C, and I think I'd prefer the slightly more complete intrinsic support in Rust over C.
A floating expression may be contracted, that is, evaluated as though it were a single opera- tion, thereby omitting rounding errors implied by the source code and the expression evalua- tion method.86) The FP_CONTRACT pragma in <math.h> provides a way to disallow contracted expressions. Otherwise, whether and how expressions are contracted is implementation-defined.
If you're making a language that generates C, it's probably a good idea to pin down which C compilers are supported, and control the options passed to them. Then you can more or less maintain the upper hand on issues like this.
// a.c
int f( int x ) {
return x + 1;
}
// b.c
extern int f(int x );
int main() {
int y = f(41);
}
Not easy, but there are compilers that do it.
Lobster [0] started out with automatic reference counting. It has inferred static typing, specialising functions based on type, reminiscent of how Javascript JIT compilers do it. Then the type inference engine was expanded to also specialise functions based on ownership/borrowing type of its arguments. RC is still done for variables that don't fit into the ownership system but the executed ops overall got greatly reduced. The trade-off is increased code size.
I have read a few older papers about eliding reference counting ops which seem to be resulting in similar elisions, except that those had not been expressed in terms of ownership/borrowing.
I think newer versions of the Swift compiler too infer lifetimes to some extent.
When emitting Rust you could now also use reference counting smart pointers, even with cycle detection [1]. Personally I'm interested in how ownership information could be used to optimise tracing GC.
[0]:https://aardappel.github.io/lobster/memory_management.html
[1]:https://www.semanticscholar.org/paper/Breadth-first-Cycle-Co...
The whole point of using "static" in that way is to prevent people from using it outside of the file.
If you need to call a static function (inline or otherwise) from outside of the compilation unit to use the API, then it's a bug in the API, not a problem with static.
I agree with you about pre-processor macros, though.
Just because you can use the information you have to call a given function, doesn't mean you aren't violating an interface.
Tangentially, i was experimenting with a runtime library to expose such "borrow-first" semantics, such "lents" can be easily copied on a new thread stack to access shared memory, and are not involved in RC . Race-conditions detection helps to share memory without any explicit move to a new thread. It seems to work well for simpler data-structures like sequence/vectors/strings/dictionary, but have not figured a proper way to handle recursive/dynamic data-structures!
Snark aside, the output targets of compilers need to be unsafe languages typically, since the point of a high level compiler in general is to verify difficult proofs, then emit constructs consistent with those proof results, but simplified so that they cannot be verified anymore, but can run fast since those proofs aren't needed at runtime anymore. (Incidentally this is both a strength and weakness of C, since it provides very little ability for the compiler to do proofs, the output is generally close to the input, while other languages typically have much more useful compilers since they do much more proof work at compile time to make runtime faster, while C just makes the programmer specify exactly what must be done, and leaves the proof of correctness up to the programmer)
So I work in compilers, which means that I write programs that translate programs to programs. Sometimes you will want to target a language at a higher level than just, like, assembler, and oftentimes C is that language. Generating C is less fraught than writing C by hand, as the generator can often avoid the undefined-behavior pitfalls that one has to be so careful about when writing C by hand. Still, I have found some patterns that help me get good results.
Today’s note is a quick summary of things that work for me. I won’t be so vain as to call them “best practices”, but they are my practices, and you can have them too if you like.
When I learned C, in the early days of GStreamer (oh bless its heart it still has the same web page!), we used lots of preprocessor macros. Mostly we got the message over time that many macro uses should have been inline functions; macros are for token-pasting and generating names, not for data access or other implementation.
But what I did not appreciate until much later was that always-inline functions remove any possible performance penalty for data abstractions. For example, in Wastrel, I can describe a bounded range of WebAssembly memory via a memory struct, and an access to that memory in another struct:
struct memory { uintptr_t base; uint64_t size; }; struct access { uint32_t addr; uint32_t len; };
And then if I want a writable pointer to that memory, I can do so:
#define static_inline \ static inline __attribute__((always_inline))
static_inline void* write_ptr(struct memory m, struct access a) { BOUNDS_CHECK(m, a); char *base = __builtin_assume_aligned((char *) m.base_addr, 4096); return (void *) (base + a.addr); }
(Wastrel usually omits any code for BOUNDS_CHECK, and just relies on memory being mapped into a PROT_NONE region of an appropriate size. We use a macro there because if the bounds check fails and kills the process, it’s nice to be able to use __FILE__ and __LINE__.)
Regardless of whether explicit bounds checks are enabled, the static_inline attribute ensures that the abstraction cost is entirely burned away; and in the case where bounds checks are elided, we don’t need the size of the memory or the len of the access, so they won’t be allocated at all.
If write_ptr wasn’t static_inline, I would be a little worried that somewhere one of these struct values would get passed through memory. This is mostly a concern with functions that return structs by value; whereas in e.g. AArch64, returning a struct memory would use the same registers that a call to void (*)(struct memory) would use for the argument, the SYS-V x64 ABI only allocates two general-purpose registers to be used for return values. I would mostly prefer to not think about this flavor of bottleneck, and that is what static inline functions do for me.
C has an odd set of default integer conversions, for example promoting uint8_t to signed int, and also has weird boundary conditions for signed integers. When generating C, we should probably sidestep these rules and instead be explicit: define static inline u8_to_u32, s16_to_s32, etc conversion functions, and turn on -Wconversion.
Using static inline cast functions also allows the generated code to assert that operands are of a particular type. Ideally, you end up in a situation where all casts are in your helper functions, and no cast is in generated code.
Whippet is a garbage collector written in C. A garbage collector cuts across all data abstractions: objects are sometimes viewed as absolute addresses, or ranges in a paged space, or offsets from the beginning of an aligned region, and so on. If you represent all of these concepts with size_t or uintptr_t or whatever, you’re going to have a bad time. So Whippet has struct gc_ref, struct gc_edge, and the like: single-member structs whose purpose it is to avoid confusion by partitioning sets of applicable operations. A gc_edge_address call will never apply to a struct gc_ref, and so on for other types and operations.
This is a great pattern for hand-written code, but it’s particularly powerful for compilers: you will often end up compiling a term of a known type or kind and you would like to avoid mistakes in the residualized C.
For example, when compiling WebAssembly, consider struct.set‘s operational semantics: the textual rendering states, “Assert: Due to validation, val is some ref.struct structaddr.” Wouldn’t it be nice if this assertion could translate to C? Well in this case it can: with single-inheritance subtyping (as WebAssembly has), you can make a forest of pointer subtypes:
typedef struct anyref { uintptr_t value; } anyref; typedef struct eqref { anyref p; } eqref; typedef struct i31ref { eqref p; } i31ref; typedef struct arrayref { eqref p; } arrayref; typedef struct structref { eqref p; } structref;
So for a (type $type_0 (struct (mut f64))), I might generate:
typedef struct type_0ref { structref p; } type_0ref;
Then if I generate a field setter for $type_0, I make it take a type_0ref:
static inline void type_0_set_field_0(type_0ref obj, double val) { ... }
In this way the types carry through from source to target language. There is a similar type forest for the actual object representations:
typedef struct wasm_any { uintptr_t type_tag; } wasm_any; typedef struct wasm_struct { wasm_any p; } wasm_struct; typedef struct type_0 { wasm_struct p; double field_0; } type_0; ...
And we generate little cast routines to go back and forth between type_0ref and type_0* as needed. There is no overhead because all routines are static inline, and we get pointer subtyping for free: if a struct.set $type_0 0 instruction is passed a subtype of $type_0, the compiler can generate an upcast that type-checks.
In WebAssembly, accesses to linear memory are not necessarily aligned, so we can’t just cast an address to (say) int32_t* and dereference. Instead we memcpy(&i32, addr, sizeof(int32_t)), and trust the compiler to just emit an unaligned load if it can (and it can). No need for more words here!
So, GCC finally has __attribute__((musttail)): praise be. However, when compiling WebAssembly, it could be that you end up compiling a function with, like 30 arguments, or 30 return values; I don’t trust a C compiler to reliably shuffle between different stack argument needs at tail calls to or from such a function. It could even refuse to compile a file if it can’t meet its musttail obligations; not a good characteristic for a target language.
Really you would like it if all function parameters were allocated to registers. You can ensure this is the case if, say, you only pass the first n values in registers, and then pass the rest in global variables. You don’t need to pass them on a stack, because you can make the callee load them back to locals as part of the prologue.
What’s fun about this is that it also neatly enables multiple return values when compiling to C: simply go through the set of function types used in your program, allocate enough global variables of the right types to store all return values, and make a function epilogue store any “excess” return values—those beyond the first return value, if any—in global variables, and have callers reload those values right after calls.
Generating C is a local optimum: you get the industrial-strength instruction selection and register allocation of GCC or Clang, you don’t have to implement many peephole-style optimizations, and you get to link to to possibly-inlinable C runtime routines. It’s hard to improve over this design point in a marginal way.
There are drawbacks, of course. As a Schemer, my largest source of annoyance is that I don’t have control of the stack: I don’t know how much stack a given function will need, nor can I extend the stack of my program in any reasonable way. I can’t iterate the stack to precisely enumerate embedded pointers (but perhaps that’s fine). I certainly can’t slice a stack to capture a delimited continuation.
The other major irritation is about side tables: one would like to be able to implement so-called zero-cost exceptions, but without support from the compiler and toolchain, it’s impossible.
And finally, source-level debugging is gnarly. You would like to be able to embed DWARF information corresponding to the code you residualize; I don’t know how to do that when generating C.
(Why not Rust, you ask? Of course you are asking that. For what it is worth, I have found that lifetimes are a frontend issue; if I had a source language with explicit lifetimes, I would consider producing Rust, as I could machine-check that the output has the same guarantees as the input. Likewise if I were using a Rust standard library. But if you are compiling from a language without fancy lifetimes, I don’t know what you would get from Rust: fewer implicit conversions, yes, but less mature tail call support, longer compile times... it’s a wash, I think.)
Oh well. Nothing is perfect, and it’s best to go into things with your eyes wide open. If you got down to here, I hope these notes help you in your generations. For me, once my generated C type-checked, it worked: very little debugging has been necessary. Hacking is not always like this, but I’ll take it when it comes. Until next time, happy hacking!