How profiling is done in trace scheduling?
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.