Change memory address bit widths to max(ceil(log2(n)), 1)

[sampsyo]

I feel like I might be doing something incredibly dumb, but I was just trying to write a program (compiling to FuTIL) and found myself confused about the appropriate width for memory index subscripts. This program type-checks and compiles just fine:

decl arr: ubit<32>[4];
arr[(1 as ubit<3>)] := 0;

And just for completeness, this program, of course, emits the "zero-padding not supported" error message I would expect in these scenarios:

decl arr: ubit<32>[4];
arr[(1 as ubit<2>)] := 0;

But here's my confusion: I thought a 4-element memory would have 2-bit addresses. That is, 2 bits is enough to express addresses 0b00 through 0b11, covering the whole memory. We never need the address 0b100 (i.e., 4). In general, I would have thought that the type-checker would want to use log2(size) as the address width, not log2(size)+1.

Like I said above, I feel like I am missing something incredibly obvious, but I'd be ever so grateful if somebody could point out what's going wrong here.

[rachitnigam]

For what it's worth, you can just write:

decl arr: ubit<32>[4];
arr[1] := 0;

and run ./fuse -b futil --lower <file>. There is a pass that annotates programs with the right bitwidths (which you can observe by passing --pass-debug)

The culprit for the bits needed calculation is here: https://github.com/cucapra/dahlia/blob/master/src/main/scala/Utils.scala#L14

It compute ceil(log2(n + 1)) because log2(1) = 0. Maybe it should instead be calculating max(log2(n), 1) to make sure that all numbers are at least bit<1>?

[sampsyo]

Great; thanks for clarifying. Yeah, I think max(ceil(log2(n)), 1) is probably the right thing. Then a 32-entry memory has a 5-bit address port, exactly the same as a 31-entry memory. Things turn over at a 33-entry memory, where you need 6 bits. I'll change the title of this issue to reflect a request to change that. But it is not a high priority.

To expand a bit, I think the ideal thing to do here would probably be ceil(log2(n)) with no modifiers, but that of course has the unpleasant side effect of making the type of addresses for 1-bit memories ubit<0>, as you noted, which seems troublesome. On the other hand, that is morally the right thing to do, because a 1-entry memory (a.k.a. a register) does not actually need an address port! You can just say "I want to read this memory" or "I want to write this memory" and the memory already automatically knows what element you're talking about. But dealing with ubit<0> is probably too annoying so we should defer that—hence the max to sidestep the unpleasantness.

[sampsyo]

(Oh right, I meant to add that I was just using the weird 1 as ubit<2> thing to write the smallest possible complete-compilable-program litmus tests to show off the behavior, not because that is actually a good thing to do. 😃)