Tác giả giữ toàn bộ bản quyền (All Rights Reserved) — không phải giấy phép mở. Bạn vẫn xem và học miễn phí trên OpenER; muốn tái sử dụng cần xin phép tác giả.
[MUSIC PLAYING] PROFESSOR: Hey. Hello.
Welcome back to RISC-V Instruction Encoding. We have covered three types of instruction formats so far.
The first format that we covered was the R-format that covered R-type instructions, which are those instructions that operate between the registers and the microprocessor for arithmetic and logic instructions.
Then we covered the I-format that covered immediate operations with the immediates, and then we covered the S-format that covered stores.
Let's take a look at the B-format, which will be covering branches. And let's see what is a subtle detail why we needed yet another instruction format for branches.
First, let's take a look at what — let's recall what the branches do. Conditional branches evaluate a condition between the registers.
In this case, we will need two source registers, x1 and x2.
And this branch, if equal, will compare the values that are in registers x1 and x2 and branch the label, which is another address in the code, if that condition is met.
If the condition is not met, if the value in x1 is not equal to the value in x2, it will execute the next instruction in sequence.
So one thing that we notice — branch instructions could use the same or a similar format as the stores. Like the stores, branches need two source registers.
They don't need a destination register, and they need some immediate value to represent where is the label or some representation of the label is needed.
So the main question here is, how do we encode that value of a label? Where do we branch to?
In order to answer that, let's take a look at what do branches do and what are they usually being used for. So branches in our assembly code are a product often of loops.
We have seen that there are three types of loops — if, else, while, for — in C that tend to get translated into branches.
These loops, when translated to the assembly code, are relatively of a short length.
The number of instructions that are inside the loop is typically less than 50, maybe a few hundred at the maximum.
And if we need to go to some farther-away part of our code like a procedure, we would use a different type of an instruction, which would be a jump, which we'll see is of a J-format.
The other important observation is about where the code is. Generally, we know that the code resides in the memory. And it is in a separate location from the data.
So it is in a limited part of a memory, and it does not mix with the data.
In general, that code — or sometimes recently has been called text for some odd reasons — the code is a subset of our memory addresses, and the maximum reach of our branch should not exceed the size of the code.
Otherwise, you will be branching into a part of the memory where there is no program, so things will not make sense.
The other thing to keep in mind as we are executing these loops — the current address where the instruction is that we are executing points to the program counter.
And as we execute them in sequence, the program counter increments. And then when we hit the branch, it goes back to the original position. And then we keep executing, and that's our loop.
So the address of the instruction that is currently being executed is in the program counter. So it makes sense to use so-called PC-relative addressing for the branches.
What does that mean?
PC-relative means that we are going to use immediate value to point to the offset, to calculate the offset from the current instruction that is in the program counter.
So in which units should that offset be expressed?
First, if we are using very similar format to what we have used for stores, S-types, we know that we can use up to 12 bits to encode our offsets.
These 12 bits come from repurposing the destination register that we don't need. There are 5 bits there and 7 bits for the funct7 field.
So that gives us 12 bits or a total range of 2 to the 12 addresses or plus/minus 2 to the 11 addresses when we need to go both forwards and backwards.
So what should we use as the unit of addressing? Should we use bytes as we used in stores?
No, because we don't want to branch into a middle of an instruction somewhere in the code.
Remember, our code in the RB32 base instruction set consists of instructions that are always 32 bits wide.
So if we branch into an address that is not aligned with the start of an instruction, it would be branching into what looks like garbage to us.
So we don't want to branch into a middle of an instruction. So I think the other option is just to branch to the beginning of the instruction.
Always a branch should be divisible — branch value should be divisible by 4.
And that has also another benefit if we always branch the start of the word, is that we have now increased the reach of our branches.
It is 2 to the plus minus 2 to the 11 times the number of words, and each word is 4 bytes or 32 bits.
So that gives us tens of kilobytes of range for our branch, which is nice. So here is how the branch calculation would work.
If we don't take the branch, our program counter would point to the next instruction in the code. What is the next instruction in the code that follows in our code?
Well, it is in the next word, which is exactly 4 bytes away. We have seen that before.
If we do take the branch, we need to calculate the offset with respect to the program counter.
And that offset is going to be the immediate value, or 12-bit wide long immediate, times 4.
Because in this scenario, we would be calculating that offset in the unit of words.
And keep in mind that this immediate value can be positive or negative, making the branch go forwards or backwards.
But this is not really how we do it in RISC-V. Keep in mind this is not true. There is a quirk.
A network is in a feature of the ISA that supports so-called compressed instruction set. So what is that? Now, we haven't talked about that before.
Compressed instruction set is a subset of the ISA that has 16-bit instructions, not 32.
We have talked about 32, 64, 128, RV-32, RV-64, RV-128, all the instructions for 32 bits, except there is a subset that uses 16-bit instructions.
Why is that? Because in some applications, this code size really matters. So you want to have your code have the smallest possible footprint.
So that is usually for really inexpensive consumer devices. A good example of those are flash memory keys and things like those.
Over there, if you need to use more of a memory to store your code, you have to pay more for that. And people don't want to do that.
So the code compactness really matters. So that's why RISC-V supports so-called compressed instruction format, and those instructions are 16 bits wide.
And don't confuse that with these other RV types. All those are 32-bit instructions. Now, here is a catch.
We may have a code that has both 32-bit instructions and 16-bit instructions. So what do we do?
We need to be able to branch into 16-bit instructions that may be offset by 2 bytes from the start of the word.
So that's why RISC-V made a decision not to have two different types of branches.
You just have one type of a branch that is able to index by 2 bytes, that is able to calculate the offset by 2 bytes.
So by default, all these five branches use this unit that multiplies the immediate by 2.
So that is less of a reach than we would have had if we were calculating the offset with respect to words, but it is still good enough.
Keep in mind, though, that in this class, we are only using 32-bit instructions. We are not studying a complex instruction set.
That means that if we don't correctly specify that offset, we could branch into a middle of an instruction. And that will not be good.
That would, in our case, produce garbage, would read a garbage instruction.
So as a result, the range of our branches is plus-minus 1 kiloword or 4 kilobytes.
So let's take a look at now how does the actual branch calculation look like.
If we don't take the branch, we are going to execute the next extraction in the code, which is 4 bytes away.
If we do take the branch, we are loading a new value in the program counter that equals to the value of the immediate times 2.
Remember that it is always times 2. So those offsets are always going to be even numbers. Well, let's see an example just in a second.
But we have arrived to — so we can see how does the B-format actually look like.
So our B format looks really complicated, the most complicated format that we have seen so far, but it actually is not.
It is pretty much the same as the S-format because we'll find the opcode in a familiar place, then we'll find funct3 in a familiar place which will specify the type of a branch that we are going to execute.
And it has rs1 and rs2 in the familiar places.
The rest — the former space that we use for the destination register and the funct7 fields — are basically taken by the bits that specify the immediate values, except that these immediate bits are shuffled all over the place.
And initially, that does not quite make that much sense.
But we'll see in the next slide how does it make sense.
Now, keep in mind that these 12 bits represent a 13-bit value because that 13-bit value always has the least significant bit equal to 0, as you have specified before.
So we don't need to store that last bit, the least significant bit, because we know that it is always equal to 0. We just need to store 12 bits for a 13-bit representational offset.
Let's take a look at an example here. So here is our RISC-V code that executes a loop.
In the beginning of that loop, there is an instruction branch of equal contents of two registers to the end.
So it would branch if the contents of the values in x19 and x10 are equal to each other. It would branch to the instruction that is specified by the label end.
What is the end? Right there. So this instruction is at the value of PC, Program Counter. This instruction is 4 bytes away, PC plus 4.
This one is at PC plus 8, PC plus 12. What is the instruction that end points to? This target instruction. What should be inside the end?
Plus 16 bytes.
So branch offset is — we calculated by calculating a number of instructions that we have from the branch and multiplying that by the number of bits or the number of bytes that we need to branch forward.
So that is 16 bytes.
One notice here — if we accidentally put a 0 here as the value for the offset, we are always going to be branching to ourselves.
And that is an unfortunate situation of so-called infinite loop that we don't have a way to exit out of.
And also, keep in mind that the infinite loop was the old address of Apple Computer — 1 Infinite Loop, Cupertino, California.
Plenty of funny names like this one in the Silicon Valley.
Okay. So offset here is 16 bytes. And let's see how we should represent that. So let's make a first pass at this instruction encoding.
We have our instruction, and it is supposed to branch forward by 4 bytes.
And we're going to determine this number for the compilation time. Branch does have a new opcode — 1100011.
And then we'll find out that the funct3 field specified the type of a branch if equal.
And then we need to put the numbers of the registers that are in rs1 and rs2.
rs1 is x19, so we are going to have a binary value of 19 in the field that specifies rs1.
And then we are going to have binary value for 10 in this field that specifies rs2.
So the last thing that we need to do is to figure out, how does this immediate get placed in there?
So we do want to specify immediate of 16 bytes — or actually, what will turn out to be 8 byte pairs. Remember, I don't need to keep that least significant bit.
So 16 bytes is the same as 8 byte pairs, right?
Before we go and figure out exactly what would be the value of the immediate, let's figure out the reasoning for this kind of strange immediate encoding.
So here are the four types of instructions that we have seen so far.
And three of them use — you have to encode immediates, so I-type encoding immediates in the upper bits from a bit position of 20 to 31.
And that would translate into the immediate value that would be placed in the bottom 12 bits, and the top bit would always end up being sign extended.
Remember, we always have to extend the value of the immediate to fill all 32 bits. Now, the next type was the S-type.
In here, immediate was spread into two places, into two fields.
The former rd field had lower 5 bits, and former funct7 field had the upper 7 bits.
So we would put together the S-type of immediate by taking bits 7 through 11, the lower 5 and the upper 7 over here.
And we would extend the one that was in bit position 31.
Now, B-type, when you take a look at it here, is almost identical to the encoding that we've used for the S-immediate.
So all the bits are exactly in the same places. And most importantly, the 31st bit is in the topmost position, the most valuable position.
So that's the one that is going to be sine extended. We always will find that one that needs to be sine extended in the topmost bit position.
And what we see here — what has happened is we have moved a bit in 7 bit from — in 7 bit from this bit position over there in our encoding.
The reason why this looks kind of strange is because we are humans, and it look strange to us. It's totally normal.
To a processor, it is a lot easier because we are helping processor figure out where the immediates are by keeping them mostly in the same place.
So our registers are going to be in the same place, and most of our immediates are going to be found in the same place as well. We'll see there is a benefit to that.
Let's finish our example that we started some time ago.
So we're going to finish encoding this branch of equal instruction with an offset that should specify 16 bytes or 8 pairs of bytes.
So we are going to encode this value of the immediate with — an actual value of 16 will be placed in the immediate and appropriate bit positions.
So first thing that we'll notice — since we are always branching by pairs of bytes, we don't need to store the least significant bit. It is always 0.
There is no reason to waste our precious instruction space to encode 0's. So I'll throw that one away.
Then we'll take the next least significant 4 bits and place them in this bit position that was previously partially occupied by rd.
Then we'll take the next ones, place them in the lower 6 bits of the funct7 field, add this immediate 11 in the least significant bit position where rd was, and finally, put the most significant immediate bit into the 31st bit of the instruction.
And that's it. So then we can find out exactly what is our value. Well, this bit is discarded.
We need to take these 4 and place them down there, and that is our immediate. This wraps up a somewhat lengthy discussion on how the branch instructions look like.
Here is a summary of all six branch instructions that we have had. They have an opcode here. It is the same for all six of them.
And the funct3 field specified which branch type it is.
One thing that I want you to notice — you might have seen that the last two bits in the opcode are always 11. And so far, the next two bits are 00.
This is a feature. We are only really using the top three bits in the funct field to specify the type of the instruction that we are working with.
The bottom 4 bits are essentially used to encode the other parts of the ISA and two RD extensions.
We don't need to pay attention to that now. This is just for your information. But I'll pause here. See you after a break.
Đăng nhập để đánh giá học liệu này.
Đăng nhập để bình luận — chưa ai bình luận về học liệu này.
Không có khóa học liên quan.