We studied the binary carbide systems Li2C2 and CaC2 at high pressure using an evolutionary and ab initio random structure search methodology for crystal structure prediction. At ambient pressure Li2C2 and CaC2 represent salt-like acetylides consisting of C-2(2-) dumbbell anions. The systems develop into semimetals (P (3) over bar m1-Li2C2) and metals (Cmcm-Li2C2, Cmcm-CaC2, and Immm-CaC2) with polymeric anions (chains, layers, strands) at moderate pressures (below 20 GPa). Cmcm-CaC2 is energetically closely competing with the ground, state structure. Polyanionic forms of carbon 4 stabilized by electrostatic interactions with surrounding cations add a new feature to carbon chemistry. SemimetallicP (3) over bar m1-Li2C2 displays an electronic structure close to that of graphene. The pi* band, however, is hybridized with Li-sp states and changed into a bonding valence band. Metallic forms are predicted to be superconductors. Calculated critical temperatures may exceed 10 K for equilibrium volume structures.