The possible use of spin rather than charge as a state variable in devices for processing and storing information has been widely discussed(1,2), because it could allow low-power operation and might also have applications in quantum computing. However, spin-based experiments and proposals for logic applications typically use spin only as an internal variable, the terminal quantities for each individual logic gate still being charge-based(3-8). This requires repeated spin-to-charge conversion, using extra hardware that offsets any possible advantage. Here we propose a spintronic device that uses spin at every stage of its operation. Input and output information are represented by the magnetization of nanomagnets that communicate through spin-coherent channels. Based on simulations with an experimentally benchmarked model, we argue that the device is both feasible and shows the five essential characteristics(9,10) for logic applications: concatenability, non-linearity, feedback elimination, gain and a complete set of Boolean operations.