TRACE GENERATION METHOD, TRACE GENERATION DEVICE, TRACE GENERATION PROGRAM PRODUCT, AND MULTI-LEVEL COMPILATION USING TRACE GENERATION METHOD

A trace generation device including a directed graph generator configured to generate a directed graph in accordance with execution of compiled traces whose maximum length is limited to a certain length or shorter and that have been generated at a low optimization level, the directed graph representing transitions of execution between the compiled traces; a directed graph updater configured to traverse edges in the directed graph backward from a start point in timer-based sampling, the start point being a node corresponding to a trace in which a timer tick has occurred, and configured to increment a recompilation counter of a trace that the backward traversal has reached when stopping in front of a cyclic trace or at a trace not having any further edge; and a generator configured to determine the head of a corresponding trace as a head of a new trace.