5

The control flow graph below is from a single function in Notepad (Win7 64-bit). Why is the linker (or the compiler) separating the basic blocks of a single function into multiple, discontinuous chunks?

Function CFG

  • Look into Working-Set Tuning, and this semi-related answer of mine. – DCoder Feb 13 '14 at 8:40
  • 1
    @CarstenC4: why do you consider these separate address ranges? Can you elaborate? From your question they all appear to use the exact same address range, which makes your question a bit unclear. – 0xC0000022L Feb 13 '14 at 10:23
  • @CarstenC4: you mean why the function is not contiguous in memory? I.e. why it is chunked? – 0xC0000022L Feb 13 '14 at 13:09
  • @0xC..22L: 'not contiguous' is the better wording, thanks – CarstenC4 Feb 13 '14 at 17:42
  • 1
    This is done for cache locality. They try to keep the "hot paths" of functions in one cache line, while "cold paths" are in another cache line. – Jonathon Reinhart Feb 14 '14 at 1:38
4

DCoder already referenced his own answer in a comment.

The chunks in the control flow graph are usually referred to as basic blocks or extended basic blocks. The reason why they are being reordered has to with optimizations performed by the compiler.

There are several terms for what you are asking about:

  • function chunking
  • basic block reordering
  • partition interleaving

I strongly suggest that if you are interested in this topic, you read up on compiler design. In particular I would suggest reading "the dragon book" ("Compilers - Principles, Techniques, & Tools" by Aho, Lam, Sethi and Ullman) and there the parts about optimization. Here I refer to the second edition from 2007 (ISBN: 0-321-48681-1).

Check out the sections 8.4 ("Basic Blocks and Flow Graphs") and 8.5 ("Optimization of Basic Blocks") and in the latter 8.5.7 ("Reassembling Basic Blocks From DAGs"). But that's only the beginning. Chapter 9 is equally important as a whole and so is section 11.10 ("Locality Optimizations"). Quoting one of the reasons for the kind of optimization you're asking about from the introductory paragraph of the subsection on partition interleaving:

11.10.3 Partition Interleaving

Different partitions in a loop often read the same data, or read and write the same cache lines. [...]

quoted from "Compilers - Principles, Techniques, & Tools" by Aho, Lam, Sethi and Ullman.

This boils down to what DCoder has already mentioned in his/her comment to your question.

Oh and the book "Reversing: Secrets of Reverse Engineering" is also a good read that discusses this in part. However, it's more focused on the "how does it look" than the "why is it done".

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.