Topic: code optimization by instruction reordering or scheduling

topics > computer science > programming > Group: code generation

code optimization by special case analysis
machine code and assembly language
Subtopic: branch chaining up

Quote: branch chaining: instead of two long jumps, can have short jump to a long jump [»leveB7_1980]
Quote: length of a span-dependent instruction depends on distance to operand; e.g., branches
Quote: algorithm for branch chaining which is linear in program length but exponentional in short jump length [»leveB7_1980]

Subtopic: branch prediction up

Quote: developed heuristics for static branch prediction of loop and non-loop branches; average miss rate of 20%, best possible is about 10% [»ballT6_1993]

Subtopic: instruction reordering up

Quote: use reordering to eliminate load and store operations; preceded or followed by duplicate operations [»maesJW10_2000]
Quote: many optimizations depend on copies creating equal values while not affecting other values; if not enforced, user types can not be optimized [»dehnJC4_1998]

Subtopic: pipeline optimization up

Quote: survey of heuristics for code optimization of instruction level parallelism in pipelined processors [»krisSM7_1990]
Quote: branches reduce the ability of a processor to prefetch instructions; especially when taken [»rymaJW3_1982]
Quote: sometimes pipeline gaps can be used for anticipatory prefetching into fast buffer registers [»rymaJW3_1982]
Quote: an address generation interlock occurs when a register is needed for address calculation but it hasn't been set yet [»rymaJW3_1982]
Quote: an operand fetch interlock occurs when a memory location is needed but it is still being updated [»rymaJW3_1982]

Subtopic: instruction scheduling up

Quote: instruction scheduling moves loads away from stores; conditions from branch; etc. [»auslM6_1982]
Quote: perform instruction scheduling before and after register allocation
Quote: register allocation and instruction scheduling can conflict; schedule dependency information can reduce interference in register coloring [»ambrW3_1994]
Quote: optimal instruction schedules by integer programming; up to 1000 instructions; 4x improvements at 14% cost [»wilkK6_2000]
Quote: the MIPS compiler reorganizes codes or inserts no-ops to avoid pipeline interlocks; uses follow sets

Related Topics up

Topic: code optimization by special case analysis (22 items)
Topic: machine code and assembly language
(49 items)

Updated barberCB 4/04
Copyright © 2002-2008 by C. Bradford Barber. All rights reserved.
Thesa is a trademark of C. Bradford Barber.