What nonlocal effects can change the performance of a basic block?

Question

A Basic Block is an assembly snippet with only one entrance point and one exit point (the Wikipedia link also has a more rigorous definition). Many compiler optimization passes rely on the compiler breaking the user's code down into basic blocks before giving them to the optimizer.

I'm curious to know what nonlocal effects can affect performance of a basic block itself. By nonlocal effects I mean how code outside the basic block run before it may affect its running time, or how where the code is laid out in memory may affect it. This is a bit more restrictive than worrying about performance of arbitrary programs with looping, branching, etc.

Off the top of my head cache use by other parts of the program, both memory and instruction cache, seems like the biggest possible nonlocal effect. Also the state of the pipeline setup by previously executed instructions or earlier instructions currently in flight. I'm interested in x86/x86-64 specifically but effects on other architectures seem worth knowing too. Are there other nonlocal effects?

Answer 1

Here's a short list:

• Location of code and data in memory heirarchy
• Cache line effects
• Other threads executing in parallel
• Locks and other synchronization
• Interrupts (from I/O devices or OS trap calls)
• Page faults due to access patterns
• Data access dependencies (same vs. not same memory address)
• Write serialization/coherency

Have fun with these.