Tin sulfides, SnxSy, are an important class of materials that are actively investigated as novel photovoltaic and water splitting materials. A first-principles evolutionary crystal structure search is performed with the goal of constructing the complete phase diagram of SnxSy and discovering new phases as well as new compounds of varying stoichiometry at ambient conditions and pressures up to 100 GPa. The ambient phase of SnS2 with P3¯m1 symmetry remains stable up to 28 GPa. Another ambient phase, SnS, experiences a series of phase transformations including α-SnS to β-SnS at 9 GPa, followed by β-SnS to γ-SnS at 40 GPa. γ-SnS is a new high-pressure metallic phase with Pm3¯m space group symmetry stable up to 100 GPa, which becomes a superconductor with a maximum Tc = 9.74 K at 40 GPa. Another new metallic compound, Sn3S4 with I4¯3d space group symmetry, is predicted to be stable at pressures above 15 GPa, which also becomes a superconductor with relatively high Tc = 21.9 K at 30 GPa.