The execution time of an instruction depends on its adjacent instructions and I/O activities. Our method first iteratively determines the set of all possible execution times of each instruction. We next construct a set of linear constraints on their execution counts. The maximum value of the cost function is an upper bound of the worst-case execution time. We demonstrate the capability of this method on a machine model where a processor has an instruction cache and pipeline, and cycle-stealing DMA I/O is concurrently executing. The experimental results show that our method safely and tightly bounds the worst-case execution time.