The paper presents a novel software-pipelining algorithm suitable for optimizing compilers targeting embedded VLIW processors. The proposed algorithm is different from previous approaches in that it can effectively handle code size constraints along with latency and resource constraints. Experimental results are presented showing that FDRA's solutions to the “traditional” software-pipelining problem, which considers latency minimization under resource constraints only, have similar quality to those produced by the best state-of-the-art algorithms. Additionally, it is argued that FDRA's novel ability to explicitly consider code size constraints allows embedded system designers to explore performance vs. code size tradeoffs, both unquestionably important figures of merit for embedded software.