(The Morgan Kaufmann Series in Computer Architecture and Design) David A. Patterson, John L. Hennessy - Computer Organization and Design RISC-V Edition_ The Hardware Software Interface-Morgan Kaufmann-102-258-pages-7.pdf

98 Chapter 2 Instructions: Language of the Computer Elaboration: C allows bit fields or fields to be defined within words, both allowing objects to be packed within a word and to match an externally enforced in...

98 Chapter 2 Instructions: Language of the Computer Elaboration: C allows bit fields or fields to be defined within words, both allowing objects to be packed within a word and to match an externally enforced interface such as an I/O device. All fields must fit within a single word. Fields are unsigned integers that can be as short as 1 bit. C compilers insert and extract fields using logical instructions in RISC-V: andi, ori, slli, and srli. Check Which operations can isolate a field in a word? Yourself 1. AND 2. A shift left followed by a shift right The utility of an automatic computer lies in the possibility of using a given sequence of instructions repeatedly, the number of times it is iterated being dependent upon the results of the 2.7 Instructions for Making Decisions computation.… This choice can be made What distinguishes a computer from a simple calculator is its ability to make to depend upon the decisions. Based on the input data and the values created during computation, sign of a number (zero different instructions execute. Decision making is commonly represented in being reckoned as plus programming languages using the if statement, sometimes combined with go to for machine purposes). statements and labels. RISC-V assembly language includes two decision-making Consequently, instructions, similar to an if statement with a go-to. The first instruction is we introduce an beq rs1, rs2, L1 [instruction] (the conditional transfer This instruction means go to the statement labeled L1 if the value in register rs1 [instruction]) which equals the value in register rs2. The mnemonic beq stands for branch if equal. The will, depending on the second instruction is sign of a given number, cause the proper one bne rs1, rs2, L1 of two routines to be It means go to the statement labeled L1 if the value in register rs1 does not equal executed. the value in register rs2. The mnemonic bne stands for branch if not equal. These Burks, Goldstine, and two instructions are traditionally called conditional branches. von Neumann, 1946 conditional branch An instruction that tests a value and that allows for a subsequent transfer of control to a new address in the program based on the outcome of the test.  2.7 Instructions for Making Decisions 99 Compiling if-then-else into Conditional Branches EXAMPLE In the following code segment, f, g, h, i, and j are variables. If the five variables f through j correspond to the five registers x19 through x23, what is the compiled RISC-V code for this C if statement? if (i == j) f = g + h; else f = g − h; Figure 2.9 shows a flowchart of what the RISC-V code should do. The first expression compares for equality between two variables in registers. It would ANSWER seem that we would want to branch if I and j are equal (beq). In general, the code will be more efficient if we test for the opposite condition to branch over the code that branches if the values are not equal (bne). Here is the code: bne x22, x23, Else   // go to Else if i ≠ j The next assignment statement performs a single operation, and if all the operands are allocated to registers, it is just one instruction: add x19, x20, x21     // f = g + h (skipped if i ≠ j) We now need to go to the end of the if statement. This example introduces another kind of branch, often called an unconditional branch. This instruction says that the processor always follows the branch. One way to express an unconditional branch in RISC-V is to use a conditional branch whose condition is always true: beq x0, x0, Exit     // if 0 == 0, go to Exit The assignment statement in the else portion of the if statement can again be compiled into a single instruction. We just need to append the label Else to this instruction. We also show the label Exit that is after this instruction, showing the end of the if-then-else compiled code: Else:sub x19, x20, x21   // f = g − h (skipped if i = j) Exit: Notice that the assembler relieves the compiler and the assembly language programmer from the tedium of calculating addresses for branches, just as it does for calculating data addresses for loads and stores (see Section 2.12). 100 Chapter 2 Instructions: Language of the Computer i=j ij i= =j? Else: f=g+h f=g–h Exit: FIGURE 2.9 Illustration of the options in the if statement above. The left box corresponds to the then part of the if statement, and the right box corresponds to the else part. Hardware/ Compilers frequently create branches and labels where they do not appear in the programming language. Avoiding the burden of writing explicit labels and Software branches is one benefit of writing in high-level programming languages and is a Interface reason coding is faster at that level. Loops Decisions are important both for choosing between two alternatives—found in if statements—and for iterating a computation—found in loops. The same assembly instructions are the building blocks for both cases. Compiling a while Loop in C EXAMPLE Here is a traditional loop in C: while (save[i] == k)     i += 1; Assume that i and k correspond to registers x22 and x24 and the base of the array save is in x25. What is the RISC-V assembly code corresponding to this C code? The first step is to load save[i] into a temporary register. Before we can load ANSWER save[i] into a temporary register, we need to have its address. Before we can add i to the base of array save to form the address, we must multiply the index i by 4 due to the byte addressing issue. Fortunately, we can use shift left, since shifting left by 2 bits multiplies by 22 or 4 (see page 96 in the prior  2.7 Instructions for Making Decisions 101 section). We need to add the label Loop to it so that we can branch back to that instruction at the end of the loop: Loop: slli x10, x22, 2    // Temp reg x10 = i * 4 To get the address of save[i], we need to add x10 and the base of save in x25: add x10, x10, x25     // x10 = address of save[i] Now we can use that address to load save[i] into a temporary register: lw x9, 0(x10)     // Temp reg x9 = save[i] The next instruction performs the loop test, exiting if save[i] ≠ k: bne x9, x24, Exit    // go to Exit if save[i] ≠ k The following instruction adds 1 to i: addi x22, x22, 1     // i = i + 1 The end of the loop branches back to the while test at the top of the loop. We just add the Exit label after it, and we’re done: beq x0, x0, Loop     // go to Loop Exit: (See Self Study in Section 2.25 for an optimization of this sequence.) Such sequences of instructions that end in a branch are so fundamental to compiling Hardware/ that they are given their own buzzword: a basic block is a sequence of instructions without branches, except possibly at the end, and without branch targets or branch Software labels, except possibly at the beginning. One of the first early phases of compilation Interface is breaking the program into basic blocks. basic block A sequence of instructions without branches (except possibly The test for equality or inequality is probably the most popular test, but there are at the end) and without many other relationships between two numbers. For example, a for loop may want branch targets or branch to test to see if the index variable is less than 0. The full set of comparisons is less labels (except possibly at than (), greater than or equal (≥), equal the beginning). (=), and not equal (≠). Comparison of bit patterns must also deal with the dichotomy between signed and unsigned numbers. Sometimes a bit pattern with a 1 in the most significant bit represents a negative number and, of course, is less than any positive number, which must have a 0 in the most significant bit. With unsigned integers, on the other hand, a 1 in the most significant bit represents a number that is larger than any that begins 102 Chapter 2 Instructions: Language of the Computer with a 0. (We’ll soon take advantage of this dual meaning of the most significant bit to reduce the cost of the array bounds checking.) RISC-V provides instructions that handle both cases. These instructions have the same form as beq and bne, but perform different comparisons. The branch if less than (blt) instruction compares the values in registers rs1 and rs2 and takes the branch if the value in rs1 is smaller, when they are treated as two’s complement numbers. Branch if greater than or equal (bge) takes the branch in the opposite case, that is, if the value in rs1 is at least the value in rs2. Branch if less than, unsigned (bltu) takes the branch if the value in rs1 is smaller than the value in rs2 when the values are treated as unsigned numbers. Finally, branch if greater than or equal, unsigned (bgeu) takes the branch in the opposite case. An alternative to providing these additional branch instructions is to set a register based upon the result of the comparison, then branch on the value in that temporary register with the beq or bne instructions. This approach, used by the MIPS instruction set, can make the processor datapath slightly simpler, but it takes more instructions to express a program. Yet another alternative, used by ARM’s instruction sets, is to keep extra bits that record what occurred during an instruction. These additional bits, called condition codes or flags, indicate, for example, if the result of an arithmetic operation was negative, or zero, or resulted in overflow. Conditional branches then use combinations of these condition codes to perform the desired test. One downside to condition codes is that if many instructions always set them, it will create dependencies that will make it difficult for pipelined execution (see Chapter 4). Bounds Check Shortcut Treating signed numbers as if they were unsigned gives us a low-cost way of checking if 0 ≤ x < y, which matches the index out-of-bounds check for arrays. The key is that negative integers in two’s complement notation look like large numbers in unsigned notation; that is, the most significant bit is a sign bit in the former notation but a large part of the number in the latter. Thus, an unsigned comparison of x < y checks if x is negative as well as if x is less than y. Use this shortcut to reduce an index-out-of-bounds check: branch to EXAMPLE IndexOutOfBounds if x20 ≥ x11 or if x20 is negative. The checking code just uses unsigned greater than or equal to do both checks: ANSWER bgeu x20, x11, IndexOutOfBounds // if x20 >= x11 or x20 < 0, goto IndexOutOfBounds  2.7 Instructions for Making Decisions 103 Case/Switch Statement Most programming languages have a case or switch statement that allows the programmer to select one of many alternatives depending on a single value. The simplest way to implement switch is via a sequence of conditional tests, turning the switch statement into a chain of if-then-else statements. Sometimes the alternatives may be more efficiently encoded as a table of addresses of alternative instruction sequences, called a branch address table or branch address branch table, and the program needs only to index into the table and then branch table Also called to the appropriate sequence. The branch table is therefore just an array of double- branch table. A table of words containing addresses that correspond to labels in the code. The program addresses of alternative instruction sequences. loads the appropriate entry from the branch table into a register. It then needs to branch using the address in the register. To support such situations, computers like RISC-V include an indirect jump instruction, which performs an unconditional branch to the address specified in a register. In RISC-V, the jump-and-link register instruction (jalr) serves this purpose. We’ll see an even more popular use of this versatile instruction in the next section. Although there are many statements for decisions and loops in programming Hardware/ languages like C and Java, the bedrock statement that implements them at the instruction set level is the conditional branch. Software Interface I. C has many statements for decisions and loops, while RISC-V has few. Check Which of the following does or does not explain this imbalance? Why? Yourself 1. More decision statements make code easier to read and understand. 2. Fewer decision statements simplify the task of the underlying layer that is responsible for execution. 3. More decision statements mean fewer lines of code, which generally reduces coding time. 4. More decision statements mean fewer lines of code, which generally results in the execution of fewer operations. II. Why does C provide two sets of operators for AND (& and &&) and two sets of operators for OR (| and ||), while RISC-V doesn’t? 1. Logical operations AND and OR implement & and |, while conditional branches implement && and ||. 2. The previous statement has it backwards: && and || correspond to logical operations, while & and | map to conditional branches. 3. They are redundant and mean the same thing: && and || are simply inherited from the programming language B, the predecessor of C.