Computational searches for structures of solid oxygen under high pressures in the multi-TPa range are carried out using density-functional-theory methods. We find that molecular oxygen persists to about 1.9 TPa at which it transforms into a semiconducting square-spiral-like polymeric structure (I4(1)/acd) with a band gap of ~3.0 eV. Solid oxygen forms a metallic zigzag chainlike structure (Cmcm) at about 3.0 TPa, but the chains in each layer gradually merge as the pressure is increased and a structure of Fmmm symmetry forms at about 9.3 TPa in which each atom has four nearest neighbors. The superconducting properties of molecular oxygen do not vary much with compression, although the structure becomes more symmetric. The electronic properties of oxygen have a complex evolution with pressure, swapping between insulating, semiconducting, and metallic.