A microprocessor may include a trace cache and a trace generator. The trace cache includes several trace cache entries. Each trace cache entry is configured to store several operations and a respective set of liveness indications. The operations are generated by at least partially decoding several instructions. The trace generator may be configured to generate the respective plurality of liveness indications for the operations stored in each trace cache entry. Each liveness indication identifies whether its respective operation depends on a branch operation stored within that trace cache entry.