Solids deform and fluids flow, but soft glassy materials, such as emulsions, foams, suspensions, and pastes, exhibit an intricate mix of solid- and liquid-like behavior. While much progress has been made to understand their elastic (small strain) and flow (infinite strain) properties, such understanding is lacking for the softening and yielding phenomena that connect these asymptotic regimes. Here we present a comprehensive framework for softening and yielding of soft glassy materials, based on extensive numerical simulations of oscillatory rheological tests, and show that two distinct scenarios unfold depending on the material's packing density. For dense systems, there is a single, pressure-independent strain where the elastic modulus drops and the particle motion becomes diffusive. In contrast, for weakly jammed systems, a two-step process arises: at an intermediate softening strain, the elastic and loss moduli both drop down and then reach a new plateau value, whereas the particle motion becomes diffusive at the distinctly larger yield strain. We show that softening is associated with an extensive number of microscopic contact changes leading to a non-analytic rheological signature. Moreover, the scaling of the softening strain with pressure suggest the existence of a novel pressure scale above which softening and yielding coincide, and we verify the existence of this crossover scale numerically. Our findings thus evidence the existence of two distinct classes of soft glassy materials – jamming dominated and dense – and show how these can be distinguished by their rheological fingerprint.