CS433: Computer System OrganizationDesign of Conditional Test / Branch MechanismsHolding Conditional Test OutcomesConditional BranchingWhat’s a Branch?Non-Branch InstructionsUnconditional BranchesWhat’s a Conditional Branch?Conditional Branches are ExpensiveDesign of Conditional Test / Branch MechanismsConditionsCondition: Overflow (V)Condition: OverflowOverflow ExamplesMore on OverflowCondition: Sign or Negative (N)Condition: Zero (Z)Condition: Carry (C)Carry and Higher Precision ArithmeticExtra Precision AddOverflow and Carry-OutSigned Comparisons and Condition CodesUnsigned Comparison from Condition CodesSigned and Unsigned ConditionsWhere Are Conditional Test Outcomes Held?PowerPC Condition Register (CR)Moto 88K CMP ResultCondition Codes (“CC bits”)Conditional BranchesSwitch StatementsArithmetic BranchingIndirect BranchingJump TablesArithmetic Branches Using Simple Indirect BranchComparing Early, Branching LateComparing Early, Branching LateCC Bits and Code MotionCC Bits and Code MotionCC Bits and Code MotionCC Bits and Code MotionBranch Prediction and Conditional NegationAssemblers, Linkers, and Limited Branch DisplacementLinker Resolution of Branch OffsetsLinker Patching of BranchesIf We Can’t Negate cond1/18/2007 CS433 Luddy Harrison 1CS433: Computer System OrganizationLuddy HarrisonSpring 2007Conditionals and Booleans1/18/2007 CS433 Luddy Harrison 2Design of Conditional Test / Branch Mechanismsz Two fundamental questionsz Where will conditional test outcomes be held?z What will a conditional branch test for?z Naturally these two are closely relatedz Nevertheless there is surprising variation, even among machines who, say, perform comparisons the same way.1/18/2007 CS433 Luddy Harrison 3Holding Conditional Test Outcomesz CC = (Ra ? Rb)z Hold the comparison result in a single Condition Code registerz X86 uses this architecturez CR3 = (Ra ? Rb)z Hold the result in one of several CC bitsz ADI Blackfin uses this architecturez Rc = (Ra <= Rb)z Hold an individual comparison outcome (<= here) in a GPRz Alpha uses this architecturez Rc = COMPARE Ra, Rbz The individual bits of a GPR are set according to ==, <=, >=, etc.z The Motorola 88000 uses this architecturez The PowerPC has (in effect) 8 condition code registers, and it records multiple comparison outcomes in them, like the 880001/18/2007 CS433 Luddy Harrison 4Conditional Branchingz Branch if a GPR is zeroz BZ Ra, Lz Alpha has this kind of conditional branchz Branch if an individual bit of a GPR is zeroz BNZ Ra, #31, Lz 88K uses this kind of branch architecturez Branch if a combination of condition codesz BGE Lz Branches on the disjunction of zero and greater thancondition codesz X86 uses this kind of branch architecture1/18/2007 CS433 Luddy Harrison 5What’s a Branch?z I will refer to the computer’s program counter as the “PC”z It is a registerz It holds an address in instruction memoryz At the end of every instruction execution, PC holds the address of the next instruction to be executedz By default, PC is incremented by the number of bytes in the instruction being executedz If the instruction has k bytes, we write PC = PC + k to indicate the default update of PCz A branch may changes the PC is some way other than the default updatez It may unconditionally change the PC to another code addressz It may conditional change the PC to another code addressz It may branch to the code address held in a registerz It may compute the next code address by performing arithmeticz These are the only possibilities we consider1/18/2007 CS433 Luddy Harrison 6Non-Branch InstructionsADD R1, R2, R3Semantics:R1 = R2 + R3 || PC = PC + kwhere the ADD instruction has k bytes1/18/2007 CS433 Luddy Harrison 7Unconditional Branchesz BR LABELz We must be able to compute LABEL from the PC of the branch (BR) instructionz One way is simply to encode LABEL in the instructionz Another is to make branches PC-relativez Instructions are usually alignedz I’ve assumed 2Kbyte aligned instructionsz I will assume that BR instructions can branch anywhere (to any code address).1/18/2007 CS433 Luddy Harrison 8What’s a Conditional Branch?z A branch whose destination is not constantz BC cond, LABELz If cond is true, branch to LABELz Otherwise fall through to next instructionz if (cond) PC = LABEL else PC = PC + k z where k is # bytes in an insnz Determined at run-timez Might be different every time the branch is takenz May bez Based on a boolean condition (true / false)z In this case it’s a 2-way branch Divided into “taken” and “fall-through” casesz Based on an arithmetic conditionz In this case it’s a multi-way branchz To an instruction address held in a registerz For example, indirect function call1/18/2007 CS433 Luddy Harrison 9Conditional Branches are Expensivez They throw a wrench into instruction fetchz For this reason, they are a primary contributor to latency in instruction execution (along with memory access)z In fact, conditional branches are loads (to instruction memory instead of data memory)z An instruction fetch is just another name for a load from instruction memory.z A conditional branch is therefore a load from a non-constant address in instruction memoryz Like memory accesses, the less predictable they are, the more ofa performance problem they createz From this point of view, we could say that random access to memory is theperformance issue for modern processors!1/18/2007 CS433 Luddy Harrison 10Design of Conditional Test / Branch Mechanismsz Fundamental questionsz What conditions will be tested for?z Architecture of comparison and condition typesz Where will conditional test outcomes be held?z Architecture of condition code registersz What will a conditional branch test for?z Architecture of conditional branchesz Naturally these questions are closely related.1/18/2007 CS433 Luddy Harrison 11Conditionsz Overflowz Zero, Non-Zeroz Sign (-, +)z Equality, Inequalityz ≠, =z Magnitude / Orderingz <, >, ≤, ≥All of the above apply to signed and unsigned integer and fractional as well as floating point typesz Carry, Borrow Outz Bit Set / Clearz if ((x & 0x20) != 0) …z if ((x & 0x20) == 0)z IEEE 754 (Floating Point)z NaNz Unorderedz DenormalizedThe underlined conditions are the most widely used1/18/2007 CS433 Luddy Harrison 12Condition: Overflow (V)N-1 N-2 0MSB LSBN-1 N-2 0NN+KINTERMEDIATE RESULT,with EXTRA PRECISION:RESULT TYPE:TRUNCATIONOverflow occurs if bits N… N+K are significant.1/18/2007 CS433