A method and system for compiling a program written in a type-safe language. Instructions are reordered for speculative execution while reducing the execution time of the program. A dependency graph is generated wherein exception dependent arcs are discriminated from arcs of other dependency types. Determination is made whether earliest execution start time of the H-PEI will be earlier when executed with or without a constraint by the exception dependent arc. If it is determined that it will be earlier in the latter case, the instruction sequence including the H-PEI is reordered for speculative execution.