ABSTRACT Next-generation space telescopes will observe the atmospheres of rocky planets orbiting nearby M-dwarfs. Understanding these observations will require well-developed theory in addition to numerical simulations. Here we present theoretical models for the temperature structure and atmospheric circulation of dry, tidally locked rocky exoplanets with gray radiative transfer and test them using a general circulation model (GCM). First, we develop a radiative-convective (RC) model that captures surface temperatures of slowly rotating and cool atmospheres. Second, we show that the atmospheric circulation acts as a global heat engine, which places strong constraints on large-scale wind speeds. Third, we develop an RC-subsiding model which extends our RC model to hot and thin atmospheres. We find that rocky planets develop large day-night temperature gradients at a ratio of wave-to-radiative timescales up to two orders of magnitude smaller than the value suggested by work on hot Jupiters. The small ratio is due to the heat engine inefficiency and asymmetry between updrafts and subsidence in convecting atmospheres. Fourth, we show, using GCM simulations, that rotation only has a strong effect on temperature structure if the atmosphere is hot or thin. Our models let us map out atmospheric scenarios for planets such as GJ 1132b, and show how thermal phase curves could constrain them. Measuring phase curves of short-period planets will require similar amounts of time on the James Webb Space Telescope as detecting molecules via transit spectroscopy, so future observations should pursue both techniques.