Compression of branch trace messaging information differs for a mode employed for software debug or optimization, in which the information is tightly packed, than for a mode employed for hardware debug, in which executed instruction addresses are more frequently included to better support detection of incorrect branch jumps. In addition, compression of branch trace messaging information may be selectively adapted in at least one of the two modes to provide executed instruction addresses at greater frequency, up to an address for each instruction executed within a particular code segment.