4 ms·
interesting! only 18 bytes! all compressed instructions! i'd thought of doing that (in general it can be a very tricky transformation for a compiler to make
by kragen 3y ago
interesting! only 18 bytes! all compressed instructions! i'd thought of doing that (in general it can be a very tricky transformation for a compiler to make safely, since it requires the loop reduction to be commutative, which of course it is in this case) but had come to the conclusion that it wouldn't help. incorrectly, it seems
in this case it's doing a tricky thing: because it's done the strength-reduction on the pointer arithmetic, it's free to do whatever it wants with the loop counter—not just eliminate it, but also, say, reverse it. that means it doesn't have to care about the loop reduction being commutative or not
https://godbolt.org/z/M14rdfzq3 https://godbolt.org/z/M14rdfzq3 has the trailing semicolon removed, for the convenience of hypothetical other readers of this thread
here's my untested, hopefully uncorrupted reformatting of it:
.globl sumarray
sumarray: li a2, 0 # total := 0
beqz a1, 1f # skip loop if array empty
2: lw a3, (a0) # load *a
addw a2, a2, a3 # add it to total
addi a1, a1, -1 # decrement n-i (previously initialized to n)
addi a0, a0, 4 # a++
bnez a1, 2b # repeat loop unless n-i == 0
1: mv a0, a2 # move total into return value slot
ret
that's 9 instructions, 5 inside the loop, but the only output from one instruction used as an input to another is the output of the lw; plausibly a sufficiently superscalar implementation of risc-v could run an iteration of the loop per cycle? kind of funny instruction scheduling, though, with those two dependent instructions being right next to each other, which would stall a naïve pipeline. macro-op fusion won't help in this case, you really need superscalar
this is an instruction shorter than my version because it doesn't need the slli or the extra instruction to compute the loop end, though it does need the extra addi in the loop. because it's only using beqz and bnez, its branches can all be compressed. i think the main thing i wasn't appreciating was how much space i was wasting on the array end computation, because that's the kind of thing that never matters
the 'pulp' core (now core-v) got a significant speedup on dsp loops by adding special zero-overhead looping registers, so you don't have to waste cycles on decrementing and testing loop counters (on your two inner levels of looping, anyway); part of their claim was that in-order scalar execution took more time per instruction but less picojoules, so if you're limited by energy consumption rather than transistor budgets or nonparallelizable algorithms, you're better off with more, slower in-order cores. from https://docs.openhwgroup.org/projects/cv32e40p-user-manual/en/latest/instruction_set_extensions.html#hardware-loops-operations https://docs.openhwgroup.org/projects/cv32e40p-user-manual/e... i think that would make the loop look like this:
.balign 4 # must be 4-byte aligned
.option norvc # no compressed insns!
cv.setup 0, 1f, a1 # loop starts on next insn
lw a3, (a0) # load *a
addw a2, a2, a3 # add it to total
addi a0, a0, 4 # a++
but for larger loops the loop setup can take three instructions
this is also the kind of thing that the vector extensions ought to help with, of course!