A general semiclassical expression for quantum fidelity (Loschmidt echo) of arbitrary pure and mixed states is derived. It expresses fidelity as an interference sum of dephasing trajectories weighed by the Wigner function of the initial state, and does not require that the initial state be localized in position or momentum. This general dephasing representation is special in that, counterintuitively, all of fidelity decay is due to dephasing and none is due to the decay of classical overlaps. Surprising accuracy of the approximation is justified by invoking the shadowing theorem: twice—both for physical perturbations and for numerical errors. Beyond justifying the approximation, the shadowing theorem makes the dephasing representation practical: without shadowing it would be impossible to find numerically the precise trajectories needed in a semiclassical approximation. It is shown how the general expression reduces to the previously known special forms for localized states. The superiority of the general over the specialized forms is explained and supported by numerical tests for wave packets, nonlocal pure states, and for simple and random mixed states. The tests are done in nonuniversal regimes in mixed phase space where detailed features of fidelity are important. Although semiclassically motivated, the present approach is valid for abstract systems with a finite Hilbert basis provided that the discrete Wigner transform is used. This makes the method applicable, via a phase-space approach, to problems of quantum computation.