In this paper, we present a systematic approach that transforms the program execution trace into the frequency domain and precisely identifies program phases. The analyzed results can be embedded into program code to mark the starting point and execution characteristics, such as CPI (Cycles per Instruction), of each phase. The so generated information can be applied to runtime program phase prediction. With the precise program phase information, more intelligent software and system optimization techniques can be further explored and developed.