This paper introduces an optimization-based locomotion control framework, CAFE-MPC, for on-the-fly synthesis of complex dynamic maneuvers in legged robots. The core of CAFE-MPC is a cascaded-fidelity model predictive controller (CAFE-MPC) that strategically relaxes the planning problem along the prediction horizon, using finer integration time steps and progressively relaxed constraints for computational and performance gains. An efficient customized multiple-shooting iLQR (MS-iLQR) solver is used to numerically solve the relaxed problem. The action-value function from CAFE-MPC is then used as the basis for a new value-function-based whole-body control (VWBC) technique, which avoids additional tuning for the WBC. This unifies the whole-body MPC and conventional whole-body quadratic programming (QP), which were previously treated as separate components. The paper studies the effects of cascaded relaxations in CAFE-MPC on tracking performance and computation time, showing that it advances the performance of whole-body MPC without increasing computational cost. The proposed framework enables the first real-time synthesis of a gymnastic-style running barrel roll on the MIT Mini Cheetah, demonstrating superior performance over the Riccati feedback controller in constraint handling.This paper introduces an optimization-based locomotion control framework, CAFE-MPC, for on-the-fly synthesis of complex dynamic maneuvers in legged robots. The core of CAFE-MPC is a cascaded-fidelity model predictive controller (CAFE-MPC) that strategically relaxes the planning problem along the prediction horizon, using finer integration time steps and progressively relaxed constraints for computational and performance gains. An efficient customized multiple-shooting iLQR (MS-iLQR) solver is used to numerically solve the relaxed problem. The action-value function from CAFE-MPC is then used as the basis for a new value-function-based whole-body control (VWBC) technique, which avoids additional tuning for the WBC. This unifies the whole-body MPC and conventional whole-body quadratic programming (QP), which were previously treated as separate components. The paper studies the effects of cascaded relaxations in CAFE-MPC on tracking performance and computation time, showing that it advances the performance of whole-body MPC without increasing computational cost. The proposed framework enables the first real-time synthesis of a gymnastic-style running barrel roll on the MIT Mini Cheetah, demonstrating superior performance over the Riccati feedback controller in constraint handling.