Formation of hyperstoichiometric uranium dioxide, UO2+x, derived from the fluorite structure was investigated by means of density functional theory (DFT) calculations. Oxidation was modeled by adding oxygen atoms to UO2 fluorite supercells. For each compound ab initio molecular dynamics simulations were performed to allow the ions to optimize their local geometry. A similar approach was used for studying the reduction of U3O8. In agreement with the experimental phase diagram we identify stable line compounds at the U4O9-y and U3O7 stoichiometries. Although the transition from fluorite to the layered U3O8 structure occurs at U3O7 (UO2.333) or U3O7.333 (UO2.444), our calculated low temperature phase diagram indicates that the fluorite derived compounds are favored up to UO2.5, that is, as long as the charge-compensation for adding oxygen atoms occurs via formation of U5+ ions, after which the U3O8-y phase becomes more stable. The most stable fluorite UO2+x phases at low temperature (0 K) are based on ordering of split quad-interstitial oxygen clusters. Most existing crystallographic models of U4O9 and U3O7, however, apply the cuboctahedral cluster. To better understand these discrepancies, the new structural models are analyzed in terms of existing neutron diffraction data. DFT calculations were also performed on the experimental cuboctahedral based U4O9-y structure, which enable comparisons between the properties of this phase with the quad-interstitial ones in detail.