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?