An optimizing compiler includes a strength reduction mechanism that optimizes a computer program that includes conditional operations by analyzing the instructions in the computer program in a single pass, determining whether instruction substitution is profitable for original instructions in the code, and performing instruction substitution for one or more original instructions for which instruction substitution is deemed profitable, including conditional operations. The substituted instructions result in strength reduction in the computer program.