Code Generation Used in Compiler Design (Coursework Sample)

COMPILER DESIGN
1.Using relevant examples, explain the code generation for RISC machines, delay slots, instruction scheduling, in lining, loop unrolling as used in compiler design.
RISC Architectures
The pipeline structure of modern architectures requires careful instruction scheduling. If instruction I1 creates a value, there may be a latency that has to elapse before another instruction I2 can use this value.•If an instruction awaits the result of a previous computation, the pipeline may have to stall until the results becomes available.•A (conditional) branch instruction is time consuming and affects the contents of the instruction cache. Execution cannot start at destination before one or more cycles have elapsed. DelaySlots •Instruction in delay slot is executed while jump is in progress. What if jump is not taken? Need mechanism to annul instruction.•Branch prediction: assume target is known, fill delay slot with first instruction in target block.•If both destinations start with same instruction, ideal choice for delay slot.•Good heuristics for loops: assume that a backwards conditional jump is usually taken. Move first instruction in loop to delay slot for branch at end.•Call instruction has delay slot filled with parameter push.
Instruction Scheduling
•Purpose: minimize stalls and delays. Fill delay slots with useful computations, minimize execution time of basic block.•Tool: dependency analysis. Uncover legal reordering of instructions, available parallelism in basic blocks and beyond• Applications: • Filling delay slots is important for all programs. • Dependency analysis is critical for reordering of loop computations on vector processors and others.
In lining
•Calls make optimizations harder. There is a large payoff to local optimizations over large basic blocks: in lining subprogram bodies is often very effective: •It exposes the values of the actuals in the body •It creates larger basic blocks •It saves the cost of the call•Can be done at the tree level or at the RTL level. In both cases it can enable other optimizations.•Possible disadvantages: code size increases, debugging is harder.
In lining as a Tree Transformation
•Treat body of subprogram as a generic unit•Each in lined body needs its own local variables•Global references are captured at the point of definition• In lining works like instantiation: replace formals with actuals, complete analysis and expansion of inserted body• Replace multiple return statements where needed•Introduce temporary to hold return value of function
Loop Unrolling
•Create successive copies of body of loop: saves tests, makes bigger basic block, increases instruction-level parallelism for j in 1..N loop loop_body; end loop;•Becomes for k in 1..N/r loop––unroll r times loop_body; loop_body[j→ j+1];–– replace loop variable for each unrolling ··· loop_body[j→ j+r-1]; end loop; for k in N/r+1..N loop loop_body end loop;––left over iterations
2.Explain the VLIW/EPIC Architectures and Software Pipelining
VLIW/EPIC Architectures•Very Long Instruction Word (VLIW).• Processor can initiate multiple operations per cycle• Specified completely by compiler (unlike super scalar machines).• Explicitly Parallel Instruction Computing (EPIC).•VLIW + New features• predication, rotating registers, speculations, etc.
Control Speculation Support•Control speculation is the execution of instructions that may not have been executed in an un optimized code.•Generally occurs due to code motion across conditional branches•These instructions are speculative•Safe if the effect of the speculative instruction can be ignored or undone if the other branch is taken.
Speculative Operations• Speculative operations are written identically to their non-speculative counterparts, but with an "E" appended to the operation name.•e.g. DIVE ADDE PBRE•If an exceptional condition occurs during a speculative operation, the exception is not raised.•A bit is set in the result register to indicate that such a condition occurred.• Speculative bits are simply propagated by speculative instructions.•When a non-speculative operation encounters a register with the speculative bit set, an exception is raised.
Predication in HPL- PD•In HPL- PD, most operations can be predicated•They can have an extra operand that is a one-bit predicate register r2=ADDr1, r3 if p2•If the predicate register contains 0, the operation is not performed.•The values of predicate registers are typically set by a compare-to-predicate operations: p1=CMPP. <= r4, r5Uses of Predication•Predication, in its simplest form, is used with•if-conversion•A use of predication is to aid code motion by instruction scheduler•e.g. hyper-blocks•With more complex compare-to-predicate operations, we get• height reduction of control dependencies
The HPL- PD Memory HierarchyHPL- PD's memory hierarchy is unusual in that it is visible to the compiler.•In store instructions, compiler can specify in which cache the data should be placed.•In load instructions, the compiler can specify in which cache the data is expected to be found and in which cache the data should be left. This supports static scheduling of load/store operations with reasonable expectations that the assumed latencies will be correct.
Software Pipelining•Software pipelining is the technique of scheduling instructions across several iterations