The many surface reconstructions of (110)-oriented lanthanum--strontium manganite (La$_{0.8}$Sr$_{0.2}$MnO$_3$, LSMO) were followed as a function of the oxygen chemical potential ($mu_text{O}$) and the surface cation composition. Decreasing $mu_text{O}$ causes Mn to migrate across the surface, enforcing phase separation into A-site-rich areas and a variety of composition-related, structurally diverse B-site-rich reconstructions. The composition of these phase-separated structures was quantified with scanning tunneling microscopy (STM), and these results were used to build a 2D phase diagram of the LSMO(110) equilibrium surface structures.