VLIW processors are statically scheduled processors and their performance depends on the quality of schedules generated by the compiler?s scheduler. We propose a new scheduling scheme where the application is first divided into decision trees and then further split into traces. Traces are speculatively scheduled on the processor based on their probability of execution. We have developed a tool "SpliTree" to generate traces automatically. Using dynamic branch prediction for scheduling traces our scheme achieves approximately 1.4x performance improvement over that using decision trees for Spec92 benchmarks simulated on TriMedia™.