Searches for the stable compounds and structures were performed using evolutionary algorithm, as implemented in the USPEX code4; 79; 185. The most significant feature of USPEX we used in this work is the capability of searching for a specific area of the composition space - as opposed to the more usual structure predictions at fixed chemical composition. The desired composition space is described via building blocks (for example, search for all compositions in a form of [xAlO+yMgO] or [xMg+yO]). During the initialization, USPEX samples the whole range of compositions of interest randomly and sparsely. Chemistry-preserving constraints in the variation operators are lifted and replaced by block-correction scheme which ensures that a child structure is within the desired area of compositional space, and a new “chemical transmutation" operator is introduced 23. Stable compositions are determined using the convex hull construction: a compound is thermodynamically stable if the enthalpy of its decomposition into any other compounds is positive. Structure prediction was done in conjunction with ab initio structure relaxations based on density functional theory (DFT) within the Perdew-Burke-Ernzerhof (PBE) generalized gradient approximation (GGA)43, as implemented in the VASP code64. For structural relaxation, we used the all-electron projector-augmented wave (PAW) method 57 and plane wave basis set with the 600 eV kinetic energy cutoff; Brillouin zone was sampled by Monkhorst-Pack meshes with the resolution 2 0.06 . Such calculations provide an excellent description of the known structures (Mg, O, MgO) and their energetics. To ensure that the obtained structures are dynamically stable, we calculated phonon frequencies throughout the Brillouin zone using the finite-displacement approach as implemented in the Phonopy code67. Phonon calculations also allowed us to explore the effects of temperature using the quasiharmonic approximation; for each structure, phonons were calculated at 10 - 15 different volumes.