A program execution control device for causing a processor to execute a program composed of one or more sets of bytecodes including a bytecode for invoking a bytecode set, comprising: an instruction execution processing unit that executes: a first judgment, for each execution of an invocation bytecode during execution of the program, of judging whether a bytecode set targeted for invocation is already compiled to native code specific to the processor, characterized in that the instruction execution processing unit further executes a second judgment, when the first judgment determines that the target bytecode set is uncompiled, of judging whether the target bytecode set is currently under compilation to native code; a compilation request, when the second judgment determines that the target bytecode set is not currently under compilation, instructing the processor so that the target bytecode set is sequentially interpreted and executed, and issuing a request to compile the target bytecode set to native code; a first instruction execution, when the first judgment determines that the target bytecode set is already compiled to native code specific to the processor, of instructing the processor to execute native code resulting from the compilation; a compilation process, instructing the processor to i) compile, in parallel with the sequential interpretation and execution of the target bytecode set performed by said compilation request, the target bytecode set indicated by the compilation request, or ii) compile, in parallel with the native code execution performed by said first instruction execution, a bytecode set that is indicated by another compilation request, the bytecode set indicated by the other compilation request being different from the target bytecode set corresponding to the native code being executed in parallel: and a second instruction execution, when the second judgment determines that the target bytecode set is currently under compilation, of instructing the processor to wait until the compilation is done and subsequently execute native code resulting from the compilation. a first judgment, for each execution of an invocation bytecode during execution of the program, of judging whether a bytecode set targeted for invocation is already compiled to native code specific to the processor, characterized in that the instruction execution processing unit further executes a second judgment, when the first judgment determines that the target bytecode set is uncompiled, of judging whether the target bytecode set is currently under compilation to native code; a compilation request, when the second judgment determines that the target bytecode set is not currently under compilation, instructing the processor so that the target bytecode set is sequentially interpreted and executed, and issuing a request to compile the target bytecode set to native code; a first instruction execution, when the first judgment determines that the target bytecode set is already compiled to native code specific to the processor, of instructing the processor to execute native code resulting from the compilation; a compilation process, instructing the processor to i) compile, in parallel with the sequential interpretation and execution of the target bytecode set performed by said compilation request, the target bytecode set indicated by the compilation request, or ii) compile, in parallel with the native code execution performed by said first instruction execution, a bytecode set that is indicated by another compilation request, the bytecode set indicated by the other compilation request being different from the target bytecode set corresponding to the native code being executed in parallel: and i) compile, in parallel with the sequential interpretation and execution of the target bytecode set performed by said compilation request, the target bytecode set indicated by the compilation request, or ii) compile, in parallel with the native code execution performed by said first instruction execution, a bytecode set that is indicated by another compilation request, the bytecode set indicated by the other compilation request being different from the target bytecode set corresponding to the native code being executed in parallel: and a second instruction execution, when the second judgment determines that the target bytecode set is currently under compilation, of instructing the processor to wait until the compilation is done and subsequently execute native code resulting from the compilation.