afonso360 edited PR #3038 from fuzz-gen
to main
.
cfallin submitted PR review.
cfallin created PR review comment:
Tiny nit, but I personally prefer doc-comments to end in periods (e.g. "Compilation Error when compiling a function.").
cfallin submitted PR review.
cfallin created PR review comment:
Should there be an error-case for "timeout", i.e. ran too long? I'll keep reading to see how infinite loops are caught but this seems like a separate logical case from explicit trap.
cfallin created PR review comment:
Ah, it seems we might want a "run for max N steps" method on the interpreter here. Otherwise, if we have an infinite loop (when fuzz-case generation becomes sophisticated enough for that, if it's not already?), we tie up a core indefinitely.
There's a question whether we step for N steps on both sides (interp and compiled) and then compare state at the end, or if we just reject inputs that run that long. I suspect probably the latter is good enough; the former would require instrumentation in the compiler to count ops and stop. We have "fuel" at the Wasmtime level but it's not built-in to Cranelift itself. And, anything a testcase could do to run indefinitely would be tested by other valid test cases as well, so I think it's fine to avoid these inputs altogether.
cfallin created PR review comment:
I'd prefer for the fuzz target to be integrated into the toplevel Wasmtime fuzzer crate, I think: while Cranelift is logically separate, it lives in the same repository, is already fuzzed by other fuzz targets there, and it is somewhat confusing to have two different
fuzz
directories.
cfallin created PR review comment:
For now (a first version), we could just reject inputs that trap in the interpreter too, right? This of course means we don't cover edge-cases like "divide should trap in exactly these cases".
I think that trap functionality is also generally handled by the runtime, e.g. Wasmtime, so we would have to build out another Cranelift-level implementation for this to be tested properly; that strikes me as disproportionate effort for the given reward, since trap cases are covered by Wasm tests and Wasm-level fuzzing as well.
cfallin created PR review comment:
If we implement
Arbitrary
for the testcase type, can we just take that type in thefuzz_target!
's lambda directly? I'd prefer that both as it's a little more idiomatic and for the specific reason that this gives us a properDebug
-print of failing test cases.
cfallin created PR review comment:
Taking the
Arbitrary
type directly (comment above) also means we don't have to manually handle this case.
cfallin created PR review comment:
End sentence with
.
, and capitalize "Cranelift" here and below.
cfallin created PR review comment:
s/util/utility/
cfallin created PR review comment:
This is already supported by
cargo fuzz
(e.g.,cargo fuzz run fuzzgen ./fuzz/artifacts/...
-- do we need a separate implementation of it?
cfallin created PR review comment:
This "available variables" approach is nice, but gets somewhat complicated with control flow, and you can see e.g. in the regalloc2 SSA generator there's a two-staged approach where we decide what values are defined in each block first, then (i) pick among values defined in blocks that dominate us for uses, (ii) ensure we define all vars we said we would in a given block.
So, in this implementation, what happens if the variable is defined, but only in one predecessor? Do we unconditionally re-define it (and let the frontend handle the SSA fixup for that)?
Another workaround is to decide at the top of the function which variables will exist, and assign initial values to all of them. Then all the rest of the instruction outputs are just redefinitions. This is actually probably the easiest and least buggy (which is what we want for a fuzztest generator!) and still shouldn't sacrifice any coverage, since it can turn into arbitrary SSA.
cfallin created PR review comment:
As an aside, I very much like that this is designed to support multiple test inputs per function; this lets us get the most out of the cost of one compilation. Maybe a comment to this effect here?
cfallin created PR review comment:
We could, in theory, extend the codegen in the
cranelift-meta
crate to generate something like this table. I think it would be generally useful to have such a table for other table-driven code, too.
cfallin created PR review comment:
As mentioned above, I think that this binary is probably not necessary.
One use-case that you mentioned in the readme is to use this to quickly test the generator in an ad-hoc way. But a better idea might be to have a separate fuzz target that only runs the fuzztest generator, and then checks that the result passes the CLIF validator. In this way, you can test that we're generating valid CLIF. This is what e.g. the
ssagen
target in regalloc2 does.
afonso360 submitted PR review.
afonso360 created PR review comment:
No, The main reason I built this was to produce an easily sharable test case, but i see that
cargo-fuzz fmt
with theArbitrary
impl provides us with that already. I'm going to remove this.
afonso360 submitted PR review.
afonso360 created PR review comment:
Yeah, lets add this to the TODO queue to be revisited later.
afonso360 submitted PR review.
afonso360 created PR review comment:
Sounds like a good idea, I've added a new fuzz target that just validates the generated function
afonso360 submitted PR review.
afonso360 created PR review comment:
when fuzz-case generation becomes sophisticated enough for that, if it's not already?
It isn't simply because we limit the number of generated instructions up to a maximum of 16. Otherwise I think we are simply limited by the input length. On a related note, I moved all of the arbitrary restrictions that we place on the generator into a
Config
module so that this become more obvious (and so that we can eventually do swarm fuzzing).There's a question whether we step for N steps on both sides (interp and compiled) and then compare state at the end, or if we just reject inputs that run that long. I suspect probably the latter is good enough
Rejecting inputs that run that long on the interpreter seems like the way to go for me.
afonso360 submitted PR review.
afonso360 created PR review comment:
I think it makes sense. I'm not seeing a quick way to constrain the interpreter to run just N instructions, so lets add that when we implement branches and control flow.
afonso360 submitted PR review.
afonso360 created PR review comment:
Great! Lets add this one to the TODO list as well.
afonso360 created PR review comment:
The idea here was that this set of "available variables" is defined per block not per function (its not currently separated because we generate just one block), when branching or calling
return
we choose a random number of variables from the current block to transfer onto the next block (depending on the block "signature").I don't think we have issues with picking variables defined in predecessors because we never do that, and I don't think we can do that with clif? (I may be wrong here)
Another workaround is to decide at the top of the function which variables will exist, and assign initial values to all of them.
Ah! I didn't know that we could transform non SSA code into SSA code. This might be something that we actually want to fuzz as well. In that case I think this is a good way to go.
Let me know if you want me to change this into the non SSA from.
afonso360 submitted PR review.
afonso360 edited PR review comment.
afonso360 edited PR review comment.
afonso360 updated PR #3038 from fuzz-gen
to main
.
afonso360 edited PR review comment.
cfallin submitted PR review.
cfallin created PR review comment:
when branching ... we choose a random number of variables ... to transfer onto the next block
This definitely works for a straightline sequence of blocks, but how does this work for loops? More generally, if you decide at the end of a block which variables to see as "defined" in the next block, you need to see all in-edges to a block before you know for sure that a variable is defined on every in-edge.
This is the origin of the two-stage approach -- it breaks the cycle: if you pin down what should be defined in each location, you can then, in parallel, both rely on that (in uses) and ensure that (in defs).
I think the easiest answer is to rely on the SSA-builder algorithm built into the variable helper layer which you're using here, and def everything at the top first, then select any variable for each use. The key thing (which I think may be flying under the radar here given the "transfer to the next block" phrasing above) is that "variables" as you're using them are not SSA values or blockparams; the latter are defined by the former depending on where you place the one or more definitions of a variable. (And indeed, a variable can have more than one def.) It's always correct to use a variable that has been defined at least once on every path from the entry block (has some dominating def), so the trivially correct thing to do is define everything (for the first time) in the entry block :-)
afonso360 updated PR #3038 from fuzz-gen
to main
.
afonso360 created PR review comment:
I've updated the fuzzer to perform this upfront allocation of variables. I'm slightly concerned that it now seems to be reusing the same variable a lot consecutively, but I think this may be the fuzzer exploring the non ssa to ssa code?
afonso360 submitted PR review.
afonso360 requested cfallin for a review on PR #3038.
afonso360 submitted PR review.
afonso360 created PR review comment:
I hadn't seen your reply when writing my previous comment. I've changed it to the upfront allocation and i think it should be better because we are probably going to stress the variable helper a bit more with the fuzzer.
But i'm still not sure i'm following what you are saying.
This definitely works for a straightline sequence of blocks, but how does this work for loops? More generally, if you decide at the end of a block which variables to see as "defined" in the next block, you need to see all in-edges to a block before you know for sure that a variable is defined on every in-edge.
The way I'm thinking about this is as if every block is sort of a function.
function %test(i32, i32) -> i32 { block0(v0: i32, v1: i32): v2 = iconst.i32 10 jump block1(v1) ; Here we can choose any of v0, v1, v2 block1(v4: i32): v5 = iconst.i32 12 return v4 ; Here we can choose either v4 or v5 but never v0,v1,v2 }
So in a sense, what I was thinking was: We generate the next block (or reuse an existing one) see what types it has in its signature and choose variables available in the current block to "call" it with (either block params or values locally defined by us).
This way, we don't need to know who called this block, because we never use variables defined by anyone else.
This is more of a curiosity now, because I've changed into the other approach and think it is better, but I'd like to understand why it wouldn't work.
afonso360 edited PR review comment.
cfallin created PR review comment:
We generate the next block (or reuse an existing one) see what types it has in its signature and choose variables available in the current block to "call" it with (either block params or values locally defined by us).
Ah, I see! The key thing here, I think, is that "what types it has in its signature" is decided before code is generated, and so breaks the cycle: this is the equivalent to the pre-pass I mentioned that decides where to define things so that defs and uses can both rely on those decisions. So this approach would also work.
Given that the
cranelift-frontend
logic is built to accept multi-def vars and generate SSA, I think that the approach this PR takes now (upfront initializations) is still the right one, but your approach would work well for generating the SSA directly, if we decide to do that instead at some point.
cfallin submitted PR review.
afonso360 submitted PR review.
afonso360 created PR review comment:
Now that I'm looking at this again, I don't think its quite right, we probably should be assigning the block params to the pool of variables instead of creating new ones.
I'll look at this again tommorow
cfallin submitted PR review.
cfallin submitted PR review.
cfallin created PR review comment:
I think this should be right? At least, my understanding is that the blockparams are SSA values while the variables are a higher-level abstraction; it would be more confusing to have a pool of both and then selectively lower vars to SSA values or use an SSA value directly, I think.
afonso360 updated PR #3038 from fuzz-gen
to main
.
afonso360 created PR review comment:
Ah, this works only because the first block is special and has the function params. I think for the other blocks we have to associate the block params to existing variables? Otherwise we run into the issue you were pointing out earlier where we may not have defined a variable depending on where we came from.
Anyway, I'll probably start working on the control flow improvements today, and should be in a more informed position to address this when I submit the next PR.
afonso360 submitted PR review.
afonso360 edited PR review comment.
abrown merged PR #3038.
Last updated: Nov 22 2024 at 16:03 UTC