360 Assembly/Branch Instructions
From Wikibooks, the open-content textbooks collection
Contents |
[edit] Unconditional branch
An unconditional branch instruction causes the Program location counter (PSW) to be set to the address specified in the register or the register plus a 12-bit offset , or the register & offset plus the value of an additional "index" register and thus may be one of the following types:-
(R1,R14,R15 are labels "equated" to the equivalent registers in these examples to provide a cross reference listing. The examples would function equally well without the R prefixes)
- Register to register (RR)
Example BR R15 Branch to the location whose address is in Register 15 Example BALR R14,R15 Branch to the location whose address is in Register 15, put return address in R14
- Storage (RS)
Example B 4(R15) Branch to the location in R15 plus the (16 bit) decimal displacement of 4 Example B X'010'(R15) Branch to the location in R15 plus the (16 bit) hex displacement of decimal 16 Example B LABEL1 Branch to the location with the specified address (Base & displacement set by Asmblr.) Example BAL R14,X'010'(R15) Branch to location in (R15 plus displacement), put return address in R14 . LABEL1 EQU * A location (within the range of the base register for the program)
- Indexed (RX)
Example B 4(R15,R1) Branch to location whose address is calculated from R15 plus 4 plus R1
[edit] Conditional branch
An conditional branch instruction causes the Program location counter (PSW) to be set to the address specified in the register or the register plus a 12-bit offset , if a condition is satisfied and thus may be one of the following types:-
- Storage (RS)
Example BE 4(R15) Branch to the location in (R15 plus 4), if previous comparison gave "Equal" condtion (8)
Example BC 8,4(R15) Branch to the location in (R15 plus 4), if previous comparison gave "Equal" condtion (8)
(same as above but specifying actual condition code value = 8)
Example BC 7,X'010'(R15) Branch to the location in (R15 plus X'010') if previous comparison gave "Unequal" condtion (7)
- Indexed (RX)
Example BCT R1,4(R15) Reduce value in R1 by 1 and, if it is then zero, branch to location in (R15 plus 4 )
- Register to register (RR)
Example BCTR R1,R15 Reduce value in R1 by 1 and, if it is then zero, branch to address in R15
[edit] Branch Table (technique)
A branch table is a literally a set of contiguous unconditional branch instructions which are of equal length (usually 4 bytes), that are used to very efficiently branch directly to one of this set, using an index. This index is often generated from some source input value that may itself be non-sequential as in the example below. This method is considerably faster than using either a binary search or sequential table lookup for example. Lookups involve compare instructions and a subsequent conditional branch. Only 5 instructions are used in the example (2 of which are unconditional branch) that perform the following:-
- 1. Validate the input (translates any input values, other than A,S,M,D, to a null index value
- 2. Translate the input value (using an INSERT CHARACTER 'IC' instruction with an index) to one of 0,4,8,12 or 16 (= the index)
(earlier versions of this technique used 'TR'& 'IC' instructions, which was 4-5 times slower than using two 'IC' instructions)
- 3. Branch unconditionally to the appropriate unconditional branch instruction using the index - a zero value results in branching to an error routine.
(unconditional branches do not rely on previous character or numeric comparison instructions)
- Example Consider an input variable that is a single byte character in the range A-Z , where specific values such as A,S,M,D decide the processing logic within the program. In this case A=Add,S=Subtract,M=Multiply and D=Divide.
In the following two examples, the time taken to perform validity and go to the appropriate label is fixed, irrespective of the number of different valid one byte input characters.
[edit] Example using a table of branch instructions
SR R15,R15 Clear index register to zero (32 bits)
IC R15,INPUT Insert input byte into low order bits of R15 (bits 24-31 - forming X'000000C1' for "A")
IC R15,TABLE2(R15) Use R15 as Index to extract a 0,4,8,12 or 16 from the 2nd Table
B TABLE1(R15) Branch using the index now in R15
TABLE1 EQU * ---Start of Branch table--- (each branch instruction is 4 bytes long and unconditional)
B ERROR 00 = Invalid input value (that is , any byte not = A,S,M or D)
B ADD 04 = Input value was "A"
B SUBTRACT 08 = Input value was "S"
B MULTIPLY 12 = Input value was "M"
B DIVIDE 16 = Input value was "D"
* ---End of Branch table
ERROR EQU *
* print or display error message or similar
ADD EQU *
* perform addition and continue with rest of program
B NEXT
SUBTRACT EQU *
* etc
INPUT DS C The input character is in this byte.
TABLE2 DC Al1(00,00,00,00,00,00,00,00,00,00,00,00,00,00,00,00) X'00'-X'10'
DC Al1(00,00,00,00,00,00,00,00,00,00)00,00,00,00,00,00) ...
DC Al1(00,00,00,00,00,00,00,00,00,00)00,00,00,00,00,00)
DC Al1(00,00,00,00,00,00,00,00,00,00)00,00,00,00,00,00)
DC Al1(00,00,00,00,00,00,00,00,00,00)00,00,00,00,00,00)
DC Al1(00,00,00,00,00,00,00,00,00,00)00,00,00,00,00,00)
DC Al1(00,00,00,00,00,00,00,00,00,00)00,00,00,00,00,00)
DC Al1(00,00,00,00,00,00,00,00,00,00)00,00,00,00,00,00)
DC Al1(00,00,00,00,00,00,00,00,00,00)00,00,00,00,00,00)
DC Al1(00,00,00,00,00,00,00,00,00,00)00,00,00,00,00,00)
DC Al1(00,00,00,00,00,00,00,00,00,00)00,00,00,00,00,00)
DC Al1(00,00,00,00,00,00,00,00,00,00)00,00,00,00,00,00)
DC Al1(00,04,00,00,16,00,00,00,00,00,00)00,00,12,00,00) x'C0' - X'CF' (04 is at offset X'c1')
DC Al1(00,00,00,08,00,00,00,00,00,00)00,00,00,00,00,00) x'D0' - X'DF'
DC Al1(00,00,00,00,00,00,00,00,00,00)00,00,00,00,00,00)
DC Al1(00,00,00,00,00,00,00,00,00,00)00,00,00,00,00,00)
* the above table can be automated if the Assembler is allowed to calculate & place the index values but it is not shown here
* for simplicity. If validation is not required, the size of this translate table need only be the size of the range of all possible input values - in this case A through to M (18 bytes).
[edit] Example using a table of 2-byte offsets
Another very similar technique to the above branch table can be used. Instead of a table of branch instructions, a table of absolute or relative addresses (offsets) can be built by the Assembler. This requires just one extra instruction but increases the branch range to 64K without need for additional base register coverage and halves the size of the Table.
SR R15,R15 Clear index register to zero (32 bits)
IC R15,INPUT Insert input byte into low order bits of R15 (bits 24-31 - forming X'000000C1' for "A")
IC R15,TABLE2(R15) Use R15 as Index to extract a 0,2,4,6 or 8 from the 2nd Table
ICM R15,3,TABLE1(R15) extract two byte offset into low order bits of R15
B TABLE1(R15) Branch using the table address plus offset now in R15
TABLE1 DS 0H ---Start of Offset table--- (each is 2 bytes long)
DC Al2(ERROR-TABLE1) 00 = Invalid input value
DC AL2(ADD-TABLE1) 02 = Input value was "A"
DC AL2(SUBTRACT-TABLE1) 04 = Input value was "S"
DC AL2(MULTIPLY-TABLE1) 06 = Input value was "M"
DC AL2(DIVIDE-TABLE1) 08 = Input value was "D"
* ---End of Branch table
ERROR EQU *
* print or display error message or similar
ADD EQU *
* perform addition and continue with rest of program
B NEXT
SUBTRACT EQU *
* etc
INPUT DS C The input character is in this byte.
TABLE2 DC Al1(00,00,00,00,00,00,00,00,00,00,00,00,00,00,00,00) X'00'-X'10'
DC Al1(00,00,00,00,00,00,00,00,00,00)00,00,00,00,00,00) ...
DC Al1(00,00,00,00,00,00,00,00,00,00)00,00,00,00,00,00)
DC Al1(00,00,00,00,00,00,00,00,00,00)00,00,00,00,00,00)
DC Al1(00,00,00,00,00,00,00,00,00,00)00,00,00,00,00,00)
DC Al1(00,00,00,00,00,00,00,00,00,00)00,00,00,00,00,00)
DC Al1(00,00,00,00,00,00,00,00,00,00)00,00,00,00,00,00)
DC Al1(00,00,00,00,00,00,00,00,00,00)00,00,00,00,00,00)
DC Al1(00,00,00,00,00,00,00,00,00,00)00,00,00,00,00,00)
DC Al1(00,00,00,00,00,00,00,00,00,00)00,00,00,00,00,00)
DC Al1(00,00,00,00,00,00,00,00,00,00)00,00,00,00,00,00)
DC Al1(00,00,00,00,00,00,00,00,00,00)00,00,00,00,00,00)
DC Al1(00,02,00,00,08,00,00,00,00,00,00)00,00,06,00,00) x'C0' - X'CF' (02 is at offset X'c1')
DC Al1(00,00,00,04,00,00,00,00,00,00)00,00,00,00,00,00) x'D0' - X'DF'
DC Al1(00,00,00,00,00,00,00,00,00,00)00,00,00,00,00,00)
DC Al1(00,00,00,00,00,00,00,00,00,00)00,00,00,00,00,00)
* An alternative approach here is to have the two-byte branch offsets within TABLE2
* (it then also uses one less instruction and eliminates the need for TABLE1 but this may require twice the size of TABLE2
* (depending upon the need for validation, and also on the range of the input character).
An alternative method of defining TABLE2 above, letting the Assembler automate the placement of the index bytes, is as follows (example shown for "A" and "D" only for brevity).
TABLE2 DC 256AL1(0) define 256 bytes of nulls
ORG TABLE2+C'A' * repeat these two lines for each valid input character
DC AL1(02) * (The 'ORG' Assembler statement above resets to correct position)
ORG TABLE2+C'D' *
DC AL1(08) *
ORG * At end, reset to earlier position after end of 256 byte table
[edit] Example using a table of 4-byte absolute addresses
A table of absolute addresses can be built by the Assembler. This requires just one extra instruction but increases the branch range to 2 gigabytes (i.e the whole address space for 31 bit processors).
SR R15,R15 Clear index register to zero (32 bits)
IC R15,INPUT Insert input byte into low order bits of R15 (bits 24-31 - forming X'000000C1' for EBCDIC "A")
IC R15,TABLE2(R15) Use R15 as Index to extract a 0,4,8,12 or 16 from the 2nd Table
ICM R15,15,TABLE1(R15) extract absolute address into all 32 bits of R15
BR R15 Branch using the address in R15
TABLE1 DS 0H ---Start of Offset table--- (each is 2 bytes long)
DC A(ERROR) 00 = Invalid input value
DC A(ADD) 04 = Input value was "A"
DC A(SUBTRACT) 08 = Input value was "S"
DC A(MULTIPLY) 12 = Input value was "M"
DC A(DIVIDE) 16 = Input value was "D"
* ---End of Branch table
ERROR EQU * Label for Errors - could be different CSECT (R15=Entry point address)
* print or display error message or similar
ADD EQU * Label for 'Add' - could be different CSECT
* perform addition and continue with rest of program
B NEXT
SUBTRACT EQU * Label for 'Subtract' - could be in different CSECT
* etc
INPUT DS C The input character is in this byte.
TABLE2 DC Al1(00,00,00,00,00,00,00,00,00,00,00,00,00,00,00,00) X'00'-X'10'
DC Al1(00,00,00,00,00,00,00,00,00,00)00,00,00,00,00,00) ...
DC Al1(00,00,00,00,00,00,00,00,00,00)00,00,00,00,00,00)
DC Al1(00,00,00,00,00,00,00,00,00,00)00,00,00,00,00,00)
DC Al1(00,00,00,00,00,00,00,00,00,00)00,00,00,00,00,00)
DC Al1(00,00,00,00,00,00,00,00,00,00)00,00,00,00,00,00)
DC Al1(00,00,00,00,00,00,00,00,00,00)00,00,00,00,00,00)
DC Al1(00,00,00,00,00,00,00,00,00,00)00,00,00,00,00,00)
DC Al1(00,00,00,00,00,00,00,00,00,00)00,00,00,00,00,00)
DC Al1(00,00,00,00,00,00,00,00,00,00)00,00,00,00,00,00)
DC Al1(00,00,00,00,00,00,00,00,00,00)00,00,00,00,00,00)
DC Al1(00,00,00,00,00,00,00,00,00,00)00,00,00,00,00,00)
DC Al1(00,04,00,00,16,00,00,00,00,00,00)00,00,12,00,00) x'C0' - X'CF' (04 is at offset X'c1')
DC Al1(00,00,00,08,00,00,00,00,00,00)00,00,00,00,00,00) x'D0' - X'DF'
DC Al1(00,00,00,00,00,00,00,00,00,00)00,00,00,00,00,00)
DC Al1(00,00,00,00,00,00,00,00,00,00)00,00,00,00,00,00)
[edit] See also
- [1] Wikipedia Index (information technology)
[edit] External links
- [2] System/360 Instruction Timing Information
