Constant propagation (CP) is a powerful, practically relevant optimization of sequential programs. However, systematic adaptions to the parallel setting are still missing. In fact, because of the computational complexity paraphrased by the catch-phrase “state explosion problem”, the successful transfer of sequential techniques is currently restricted to bitvector-based optimizations, which because of their structural simplicity can be enhanced to parallel programs at almost no costs on the implementation and computation side. CP, however, is beyond this class. Here, we show how to enhance the framework underlying the transfer of bitvector problems obtaining the basis for developing a powerful algorithm for parallel constant propagation (PCP). This algorithm can be implemented as easily and as efficiently as its sequential counterpart for simple constants computed by state-of-the-art sequential optimizers.