I'm trying to understand how trace scheduling works. The book that I'm reading, Engineering a Compiler by Keith D. Cooper & Linda Torczon, states that this method is using profiling. Profiling ranks each edge if the CFG by its frequency of execution. In other words the more a particular edge is followed the higher rank it has. So basically first the algorithm profiles the CFG and then runs trace scheduling. The only way (in my view) to do profiling is to run the code so that each edge of the CFG can be ranked. Somehow I don't think this is being done.

Here are my questions:

So how is profiling done?
Does the compiler guess the rank of each edge?
If it does, then what is the foundation for the guess?

  • 1
    $\begingroup$ Yes, profile-guided optimization uses data from running the program. However, it is possible to use heuristics to predict the likely direction of branches. E.g., Ball & Larus' "Branch Prediction for Free" (1993) uses some simple heuristics to generate static branch prediction hints. In range values and non-null pointers are generally more likely; specificity can also be a hint (under equal distribution, equality is less likely). $\endgroup$
    – user4577
    Jul 16, 2015 at 20:55
  • $\begingroup$ Why specifically do you think that they're not running the code? Yes, running the code is normally the way we do profiling. Without knowing why you think they're not running the code, the best answer we can give you is "I think you have a mistaken premise". I encourage you you to edit the question to provide us more background so we can provide you a better answer. $\endgroup$
    – D.W.
    Jul 16, 2015 at 23:48

1 Answer 1


Yes, profiling is normally done by running the program. Yes, running the program and then gathering information about execution frequencies is how this is normally done. As Paul A. Clayton suggests, read more about profile-guided optimization to learn more about techniques commonly used in this field -- there's a rich literature on profile-guided optimization.

There are alternatives based on various heuristics or static analysis algorithms, but profiling normally implies running the program, and profiling will usually be considerably more accurate than any static technique.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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