Binary tin sulfides are appealing because of their simple stoichiometry and semiconducting properties and are potentially cost-effective optoelectronic materials. The multivalency of Sn allows yet more intermediate compositions, Sn$_x$S$_y$, whose structures and properties are of interest.Sn$_2$S$_3$ is already under consideration as a mixed-valence semiconductor. Other intermediate compositions have remained elusive. Here we report a comprehensive study of phase stability of the Sn$_x$S$_y$ series compounds, utilizing swarm-intelligence crystal structure search method combined with first-principles energetic calculations. We find that the stability of mixed-valence Sn$_x$S$_y$ compounds with respect to decomposition into pure-valence SnS and SnS$_2$ is in general weaker than the Sn$_x$O$_y$ counterparts, likely due to differences in chemical bonding. Besides identifying the experimentally discovered stable phases of Sn$_2$S$_3$, our calculations indicate that the Sn$_3$S$_4$ phase is another mixed-valence composition which shows marginal stability with respect to decomposition into SnS and SnS$_2$. Other studied compositions may be metastable under ambient conditions, with slightly positive formation enthalpies. We find two structures of Sn$_3$S$_4$ having comparably low energies, both of which feature one-dimensional chain-like fragments obtained by breaking up the edge-connected octahedral layers of SnS$_2$. Both structures indicate lattice phonon stability and one shows quasi-direct band gap with a calculated value of 1.43 eV, ideal for solar absorbers. A further analysis of the composition-structure-property relationship supports the notion that lowdimensional Sn-S motifs and van der Waals interaction may lead to diverse structure types and chemical compositions, having functional properties that are yet to be identified in the Sn$_x$S$_y$ series with mixed valency.