5 ms·

In a modern CPU, instruction selection is much more complicated than, "Oh, addl (or sll) is faster than umul," and depends on the micro-architecture/pipeline, s

In a modern CPU, instruction selection is much more complicated than, "Oh, addl (or sll) is faster than umul," and depends on the micro-architecture/pipeline, surrounding code, etc. Addition usually takes one cycle, while multiplication might take several cycles (although, by pipelining, you can generally execute a multiply per cycle per multiplier) But, if all the other adders are full and the result isn't needed for a few cycles, it might be fastest to use the multiplier. (I'm thinking of a statically scheduled pipeline. Things get harder when the CPU does dynamic instruction reordering.)

_delirium 16y ago
Do any compilers attempt to take those sorts of concerns into account? It seems like it'd be an interesting experiment, but it breaks some of the nice abstractions--- afaik, strength-reduction is usually done before scheduling, with the only architecture dependency being a table of costs assigned to each operation. Letting scheduling constraints have input on those decisions seems ideal but tricky, unless I'm missing something.
- wwalker3 16y ago
  It would be very hard to accurately account for a microprocessor's out-of-order instruction issue in a compiler. A modern desktop-class microprocessor can have scores of instructions "in flight" at once. Each new instruction that's decoded gets reordered or stalled differently depending on the status of all of those previous instructions and their hardware requirements. A compiler could try to model the processor's microarchitecture and simulate how it would execute the program, but that simulation would be inaccurate because of data-dependent branching, interrupts, and other unpredictable behaviors. Plus, the microarchitectural details you'd need to create such a simulation are usually not available. That said, compilers can still tailor code to the microarchitecture in a general way. For example, if you know a processor can only decode one branch instruction per cycle, you can try to reorder the compiled code to avoid back-to-back branches in the instruction stream.
  - mian2zi3 16y ago
    > It would be very hard to accurately account for a microprocessor's out-of-order instruction issue in a compiler. This is true. However, a lot of modern processors do in-order execution, they just aren't made by Intel or AMD for desktops: GPUs, network processors, SIMD DSPs, etc. When I was hacking compilers (6 years ago), compiling for these processors presented difficult challenges and there was a real market for new compiler technology. One project was for a network processor that was not only in-order, but it was not interlocked: correctness depended on the compiler having an exact model of the processor's pipeline. Some registers were not registers, but latches. They got new values every cycle, so if you didn't gab a value on the right cycle, it was gone forever.
- mian2zi3 16y ago
  The phase ordering problem in compilers is notoriously hard. You wouldn't worry about the interaction between strength reduction and scheduling, but in other cases you do need to take these interactions into account. In my compiler (aka a compiler I worked on), the software pipeliner estimated register pressure, since you don't want to over-pipeline to expose parallelism if you blow the register set and cause the allocator to spill. Often register allocation is sensitive to the schedule (and there have been attempts to combine them into one pass.) For x+x vs x*2 vs x<<1, the trick is to represent them in a uniform way and let the scheduler decide what instruction to emit based.
  - 1amzave 16y ago
    > Often register allocation is sensitive to the schedule (and there have been attempts to combine them into one pass.) Yes -- for what it's worth, the compiler I'm working on at the moment has a pre-allocation scheduling pass and a post-allocation scheduling pass, and will also sometimes reschedule during allocation to shorten live ranges and thus ease register pressure.

_delirium 16y ago

Do any compilers attempt to take those sorts of concerns into account? It seems like it'd be an interesting experiment, but it breaks some of the nice abstractions--- afaik, strength-reduction is usually done before scheduling, with the only architecture dependency being a table of costs assigned to each operation. Letting scheduling constraints have input on those decisions seems ideal but tricky, unless I'm missing something.

wwalker3 16y ago
It would be very hard to accurately account for a microprocessor's out-of-order instruction issue in a compiler. A modern desktop-class microprocessor can have scores of instructions "in flight" at once. Each new instruction that's decoded gets reordered or stalled differently depending on the status of all of those previous instructions and their hardware requirements. A compiler could try to model the processor's microarchitecture and simulate how it would execute the program, but that simulation would be inaccurate because of data-dependent branching, interrupts, and other unpredictable behaviors. Plus, the microarchitectural details you'd need to create such a simulation are usually not available. That said, compilers can still tailor code to the microarchitecture in a general way. For example, if you know a processor can only decode one branch instruction per cycle, you can try to reorder the compiled code to avoid back-to-back branches in the instruction stream.
- mian2zi3 16y ago
  > It would be very hard to accurately account for a microprocessor's out-of-order instruction issue in a compiler. This is true. However, a lot of modern processors do in-order execution, they just aren't made by Intel or AMD for desktops: GPUs, network processors, SIMD DSPs, etc. When I was hacking compilers (6 years ago), compiling for these processors presented difficult challenges and there was a real market for new compiler technology. One project was for a network processor that was not only in-order, but it was not interlocked: correctness depended on the compiler having an exact model of the processor's pipeline. Some registers were not registers, but latches. They got new values every cycle, so if you didn't gab a value on the right cycle, it was gone forever.
mian2zi3 16y ago
The phase ordering problem in compilers is notoriously hard. You wouldn't worry about the interaction between strength reduction and scheduling, but in other cases you do need to take these interactions into account. In my compiler (aka a compiler I worked on), the software pipeliner estimated register pressure, since you don't want to over-pipeline to expose parallelism if you blow the register set and cause the allocator to spill. Often register allocation is sensitive to the schedule (and there have been attempts to combine them into one pass.) For x+x vs x*2 vs x<<1, the trick is to represent them in a uniform way and let the scheduler decide what instruction to emit based.
- 1amzave 16y ago
  > Often register allocation is sensitive to the schedule (and there have been attempts to combine them into one pass.) Yes -- for what it's worth, the compiler I'm working on at the moment has a pre-allocation scheduling pass and a post-allocation scheduling pass, and will also sometimes reschedule during allocation to shorten live ranges and thus ease register pressure.