How profiling is done in trace scheduling? I'm trying to understand how trace scheduling works. The book that I'm reading, Engineering a Compiler by Keith D. Cooper &amp; 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?
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.