allocas are emitted in reverse order. this is unintentional; can we fix?

[Birch-san]

CreateAllocaBPF hoists allocas to the start of the entry block.

I believe CreateAllocaBPF employs hoisting because it wishes to "ensure that a variable's storage is declared before any of its uses". probably to support a pathological case that you can get into with conditions (see #1787).

but one thing that's confusing about the generated code, is that variable allocations are emitted in reverse:

https://github.com/iovisor/bpftrace/blob/master/tests/codegen/builtin_arg.cpp

kprobe:f {
  @x = arg0;
  @y = arg2
}

https://github.com/iovisor/bpftrace/blob/master/tests/codegen/llvm/builtin_arg.ll#L11-L14

define i64 @"kprobe:f"(i8*) section "s_kprobe:f_1" {
entry:
  %"@y_val" = alloca i64
  %"@y_key" = alloca i64
  %"@x_val" = alloca i64
  %"@x_key" = alloca i64

if you call CreateAllocaBPF once, it hoists an alloca to the start of your program.
if you call CreateAllocaBPF again, it hoists another alloca to the start of your program, declaring it earlier even though we asked for it later.

this is not inherently a problem, but is a caveat that the reader needs to understand when reviewing the LLVM IR.
moreover it can make it hard to intuit how the BPF stack is laid out.

allocas are reversed because we put them at "the start of the entry block".
the only reason we do that is because it's an easy way to ensure that it's declared before any code accesses it.

there's a way to create the same guarantee (declared before access), but without the downsides of "everything's in reverse".

my proposal is "a block to put allocas into". we'd emit allocas into the end of that block (which fixes the ordering). this block would be the first block that runs in our probe. it neatly separates "hoisted declarations" and "everything else" into different, labelled blocks.

the reason I'm raising this is because I believe it's one piece needed for "big strings".

[danobi]

the only reason we do that is because it's an easy way to ensure that it's declared before any code accesses it.

Right, I think the only reason it's like this is b/c it was the easiest way to implement it.

my proposal is "a block to put allocas into". we'd emit allocas into the end of that block (which fixes the ordering). this block would be the first block that runs in our probe. it neatly separates "hoisted declarations" and "everything else" into different, labelled blocks.

Sounds reasonable to me

the reason I'm raising this is because I believe it's one piece needed for "big strings".

👍

[Birch-san]

I think #1792 is a good step towards this.

it introduces a hoist() helper to unify how both CreateAllocaBPF and CreateAllocaBPFInit hoist allocas.

after that's in, "emitting allocas into a block and in the right order" becomes a bit easier (modify how hoist() is implemented).

is there anything I can do to assist in getting that PR over the line?

[fbs]

I think having the allocas on top is also a requirement for the mem2reg pass (which transforms allocas in Phi when possible)

[Birch-san]

yes, as you say: I think the rule is "allocas need to be at the top of their Function"; I tried CreateAlloca (i.e. non-hoisted) in the middle of a Function and got an error, which I was able to resolve by hoisting via CreateAllocaBPF. think it was this line:
master...Birch-san:printf-off-stack-4#diff-3d80d60dba9cfc34c2fe79c01df26172886685f76475c9b53b372136e49f1af0R394

I have used CreateAlloca successfully in functions I control fully (i.e. when I can guarantee its first instructions will be allocas):
master...Birch-san:printf-off-stack-4#diff-3d80d60dba9cfc34c2fe79c01df26172886685f76475c9b53b372136e49f1af0R1277

[Birch-san]

if we want to emit the allocas at the top of the function but in correct order (i.e. not reversed) I do have some code that demonstrates how to split the entry block into "entry" and "posthoist":

Birch-san@078c5f0 (split the block)
Birch-san@e4a5d6a (macro to support older LLVM)

this would enable us to change CreateAllocaBPF such that it emits allocas to the bottom of the entry block, whilst the rest of the program writes into the "posthoist" block that follows afterward.

[Birch-san]

it also feels to me like CreateAllocaBPF should return a ScopedExpr to do the lifetime end for you. it would make CodegenLLVM::getMapKey() more cohesive:
https://github.com/iovisor/bpftrace/blob/93b6da21e10f82283e2bab783558c1e87eb53714/src/ast/passes/codegen_llvm.cpp#L2474-L2475

i.e. it would no longer need knowledge of "how/whether to clean up".

the same can be said of CodegenLLVM::visit(Map &map)'s relationship with IRBuilderBPF::CreateMapLookupElem:
https://github.com/iovisor/bpftrace/blob/master/src/ast/passes/codegen_llvm.cpp#L1093-L1094