Low-cost branch folding for embedded applications with small tight loops

Many portable and embedded applications are characterized by spending a large fraction of execution time on small program loops. To improve performance many embedded systems use special instructions to handle program loop executions. These special instructions, however, consume opcode space, which is valuable in the embedded computing environments. In this paper, we propose a hardware technique for folding our branches when executing these small loops. This technique does not require any special branch instructions. It is based on the detection and utilization of certain short backward branch instructions (sbb). A sbb is any PC-relative branch instruction with a limited backward branch distance. Once an sbb is detected, its displacement field is used by the hardware to identify the actual program loop size. It does so by loading this negative displacement field into a counter and incrementing the counter for each instruction sequentially executed. As the count approaches zero, the hardware folds out the sbb by predicting that it is always taken. The hardware overhead for this technique is minimal. Using a 5-bit increment counter, the performance improvement over a set of embedded applications is about 7.5%