Some embodiments provide a system that executes a native code module. During operation, the system obtains the native code module. Next, the system loads the native code module into a secure runtime environment. Finally, the system safely executes the native code module in the secure runtime environment by using a set of software fault isolation (SFI) mechanisms that use predicated store instructions and predicated control flow instructions, wherein each predicated instruction from the predicated store instructions and the predicated control flow instructions is executed if a mask condition associated with the predicated instruction is met.