Predicting phase stabilities of crystal polymorphs is central to computational materials science and chemistry. Such predictions are challenging because they first require searching for potential energy minima and then performing arduous free-energy calculations to account for entropic effects at finite temperatures. Here, we develop a framework that facilitates such predictions by exploiting all the information obtained from random searches of crystal structures. This framework combines automated clustering, classification and visualisation of crystal structures with machine-learning estimation of their enthalpy and entropy. We demonstrate the framework on the technologically important system of TiO2, which has many polymorphs, without relying on prior knowledge of known phases. We find a number of new phases and predict the phase diagram and metastabilities of crystal polymorphs at 1600 K, benchmarking the results against full free-energy calculations.