The relationships among predicates can be analyzed over the scope of an entire procedure. The system scans a block of predicated code and collects a set of predicates used in the code to form a basis set. The system then allocates a bit-vector for each predicate in the basis set to form a live set. Each bit-vector represent a liveness of each predicate. The system then builds an interference graph that symbolizes interferences between registers during allocation of registers.