DOC PREVIEW
UD CISC 672 - Code Shape III Booleans, Relationals, & Control flow

This preview shows page 1-2-3-4-5 out of 15 pages.

Save
View full document
View full document
Premium Document
Do you want full access? Go Premium and unlock all 15 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 15 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 15 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 15 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 15 pages.
Access to all documents
Download any document
Ad free experience
Premium Document
Do you want full access? Go Premium and unlock all 15 pages.
Access to all documents
Download any document
Ad free experience

Unformatted text preview:

Code Shape III Booleans, Relationals, & Control flowBoolean & Relational ValuesSlide 3Slide 4Slide 5Slide 6Slide 7Slide 8Slide 9Control FlowSlide 11Loop Implementation CodeBreak statementsSlide 14Slide 15Code Shape IIIBooleans, Relationals, & Control flowCopyright 2003, Keith D. Cooper, Ken Kennedy & Linda Torczon, all rights reserved.Boolean & Relational ValuesHow should the compiler represent them?•Answer depends on the target machineTwo classic approaches•Numerical representation•Positional (implicit) representationCorrect choice depends on both context and ISABoolean & Relational ValuesNumerical representation•Assign values to TRUE and FALSE•Use hardware AND, OR, and NOT operations•Use comparison to get a boolean from a relational expressionExamplesx < y becomescmp_LT rx,ry ⇒ r1if (x < y) then stmt1becomes else stmt2cmp_LT rx,ry ⇒ r1cbr r1→ _stmt1,_stmt2Boolean & Relational ValuesWhat if the ISA uses a condition code? •Must use a conditional branch to interpret result of compare•Necessitates branches in the evaluationExample:This “positional representation” is much more complexcmp rx, ry⇒ cc1cbr_LT cc1→ LT,LFx < ybecomesLT:loadI 1 ⇒ r2br → LELF:loadI 0 ⇒ r2LE:…other stmts…Boolean & Relational ValuesWhat if the ISA uses a condition code? •Must use a conditional branch to interpret result of compare•Necessitates branches in the evaluationExample:This “positional representation” is much more complexcmp rx, ry⇒ cc1cbr_LT cc1→ LT,LFx < ybecomesLT:loadI 1 ⇒ r2br → LELF:loadI 0 ⇒ r2LE:…other stmts…Condition codes• are an architect’s hack• allow ISA to avoid some comparisons• complicates code for simple casesBoolean & Relational ValuesThe last example actually encodes result in the PCIf result is used to control an operation, this may be enoughCondition code version does not directly produce (x < y)Boolean version doesStill, there is no significant difference in the code producedVARIATIONS ON THE ILOC BRANCH STRUCTURE Straight Condition Codes Boolean Compares comp rx,ry⇒ cc1 cmp_LT rx,ry⇒ r1 cbr_LT cc1 → L1,L2 cbr r1 → L1,L2 L1: add rc,rd⇒ ra L1: add rc,rd⇒ ra br → LOUT br → LOUT L2: add re,rf ⇒ ra L2: add re,rf ⇒ ra br → LOUT br → LOUT LOUT: nop LOUT: nop if (x < y) then a  c + d else a  e + fExampleBoolean & Relational ValuesConditional move & predication both simplify this codeBoth versions avoid the branchesBoth are shorter than CCs or Boolean-valued compareAre they better?OTHER ARCHITECTURAL VARIATIONSConditional MovePredicated Executioncomprx,ry⇒ cc1cmp_LTrx,ry⇒ r1addrc,rd⇒ r1(r1)?addrc,rd⇒ raaddre,rf ⇒ r2(¬r1)?addre,rf ⇒ rai2i_<cc1,r1,r2⇒ raif (x < y) then a  c + d else a  e + fExampleBoolean & Relational ValuesConsider the assignment x  a  b  c  dHere, the boolean compare produces much better code VARIATIONS ON THE ILOC BRANCH STRUCTUREStraight Condition CodesBoolean Comparecompra,rb⇒ cc1cmp_LTra,rb⇒ r1cbr_LTcc1 → L1,L2cmp_LTrc,rd⇒ r2L1:comprc,rd⇒ cc2andr1,r2⇒ rxcbr_LTcc2 → L3,L2L2:loadI0 ⇒ rxbr → LOUTL3:loadI1 ⇒ rxbr → LOUTLOUT:nopBoolean & Relational ValuesConditional move & predication help here, tooConditional move is worse than Boolean comparesPredication is identical to Boolean comparesContext & hardware determine the appropriate choicex  a  b  c  dControl FlowIf-then-else•Follow model for evaluating relationals & booleans with branchesBranching versus predication (e.g., IA-64)•Frequency of executionUneven distribution  do what it takes to speed common case•Amount of code in each caseUnequal amounts means predication may waste issue slots•Control flow inside the constructAny branching activity within the case base complicates the predicates and makes branches attractiveControl FlowLoops•Evaluate condition before loop (if needed)•Evaluate condition after loop •Branch back to the top (if needed)Merges test with last block of loop bodywhile, for, do, & until all fit this basic modelPre-testLoop bodyPost-testNext blockLoop Implementation Code loadI 1  r1loadI 1  r2loadI 100  r3cmp_GE r1, r3 r4cbr r4 L2, L1 L1: body add r1, r2 r1 cmp_LT r1, r3 r5 cbr r5 L1, L2L2: next statementfor (i = 1; i< 100; i++) { body }next statementPre-testPost-testInitializationBreak statementsMany modern programming languages include a break•Exits from the innermost control-flow statementOut of the innermost loopOut of a case statementTranslates into a jump•Targets statement outside control-flow construct•Creates multiple-exit construct•Skip in loop goes to next iterationOnly make sense if loop has > 1 blockPre-testLoop headPost-testNext blockB 1 B 2Break in B 1Skip in B 2Control FlowCase Statements1Evaluate the controlling expression2Branch to the selected case3Execute the code for that case4Branch to the statement after the caseParts 1, 3, & 4 are well understood, part 2 is the keyControl FlowCase Statements1Evaluate the controlling expression2Branch to the selected case3Execute the code for that case4Branch to the statement after the case (use break)Parts 1, 3, & 4 are well understood, part 2 is the keyStrategies•Linear search (nested if-then-else constructs)•Build a table of case expressions & binary search it•Directly compute an address (requires dense case set)Surprisingly many compilers do this for all


View Full Document

UD CISC 672 - Code Shape III Booleans, Relationals, & Control flow

Documents in this Course
Syllabus

Syllabus

18 pages

Load more
Download Code Shape III Booleans, Relationals, & Control flow
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...
Login

Join to view Code Shape III Booleans, Relationals, & Control flow and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view Code Shape III Booleans, Relationals, & Control flow 2 2 and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?