Lifetime-optimal Speculative Partial Redundancy Elimination (LOSPRE) is one of the most classical, ubiquitous and effective techniques used by compilers for redundancy elimination, i.e. avoiding unnecessary recomputations of the same expression. State-of-the-art methods for LOSPRE over structured programs are based on treewidth, i.e. they first compute a tree decomposition of the control-flow graph of the program and then perform dynamic programming on this decomposition. In this work, we consider a different decomposition approach which is called series-parallel-loop (SPL) and was recently introduced in [8]. We present an efficient linear-time LOSPRE algorithm that builds upon SPL decompositions. We then provide extensive experimental results over the Small Device C Compiler (SDCC) benchmarks, demonstrating that our algorithm outperforms the highly-optimized treewidth-based approach of SDCC.