Patent ID: 8191057

Claim:
A method for aggressive safe load speculation for a compiler in a computer system, the method consisting of: building a control flow graph; identifying both countable and non-countable loops; gathering a set of candidate loops for load speculation; for each candidate loop in the set of candidate loops gathered for load speculation performing: computing an estimate of the iteration count, total delay cycles in a loop, and code size; performing a profitability analysis and determining an unroll factor based on the total delay cycles in the loop, estimated register pressure, and estimated loop iteration count, wherein the unroll factor is at least smaller than half of the estimate loop iteration count and the code size; transforming the loop by generating a prologue loop to achieve data alignment and an unrolled main loop with loop directives, indicating which loads can safely be executed speculatively, wherein loop directives are implemented to reorder loads with branches; and performing low-level instruction scheduling on the generated unrolled main loop, wherein a loop with an early exit is a candidate loop for load speculation and has stride-one accesses to memory, for a leading load with a data element size, that is aligned with its data alignment, that is bigger than the data element size, there are a number of subsequent data accesses equal to a quotient of the data alignment and the data element size, minus one, which are safe for load speculation; for a loop with early exit and with unit-stride accesses of a contiguous storage, performing: determining whether a storage accessed by a first load has an alignment greater than its own data element size; determining whether the alignment amount is less than the size of one memory page; and responsive to a determination that the storage accessed by the first load has an alignment greater than its own data element size and that the alignment amount is less than the size of one memory page, generating a pre-loop having exactly enough of a number of iterations of the original loop so that when the original loop is executed, the data for the first load is strongly aligned in storage so that the main loop can be unrolled and the first load has strong enough alignment so that all of the subsequent loads in that unrolled iteration can be safely executed ahead of all of the early exit branches in that iteration.