28-08-2013, 04:18 PM
Control Dependences
Control Dependences.ppt (Size: 364.5 KB / Downloads: 17)
Two strategies to deal with control dependences:
If-conversion: expose by converting to data dependences. Used for vectorization
Explicitly expose as control dependences. Used for automatic parallelization
Branch Classification
Forward Branch: transfers control to a target that occurs lexically after the branch but at the same level of nesting
Backward Branch: transfers control to a statement occurring lexically before the branch but at the same level of nesting
Exit Branch: terminates one or more loops by transferring control to a target outside a loop nest
Branch removal
Basic idea:
Make a pass through the program.
Maintain a Boolean expression cc that represents the condition that must be true for the current expression to be executed
On encountering a branch, conjoin the controlling expression into cc
On encountering a target of a branch is encountered, its controlling expression is disjoined into cc
Branch Removal: Forward Branches
To show correctness we must establish:
the guard for statement instance in the new program is true if and only if the corresponding statement in the old program is executed, unless the statement has been introduced to capture a guard variable value, which must be executed at the point the conditional expression would have been evaluated
the order of execution of statements in the new program with true guards is the same as the order of execution of those statements in the original program
Any expression with side effects is evaluated exactly as many times in the new program as in the old program
Complete Forward Branch Removal
Statement is branch target: combine (disjoin) set of conditions associated with branches to that target with the current condition passed from the lexical predecessor
Statement is any type except DO, ENDDO, CONTINUE: the current condition is conjoined to the guard for the current statement
Statement is a DO: invoke relocate_branches to remove exit branches. Recur on body of the loop. May generate some statements before the loop which should be guarded by the current condition