Control-Flow Integrity (CFI) is a popular technique to de- fend against State-of-the-Art exploits, by ensuring that every (indirect) control-flow transfer points to a legitimate address and it is part of the Control-flow Graph (CFG) of a program. Enabling CFI in real systems is not straightforward, since in many cases the actual CFG of a program can only be approximated. Even in the case where there is perfect knowl- edge of the CFG, ensuring that all return instructions will return to their actual call sites, without employing a shadow stack, is questionable. In this work, we explore the implementation of a full-featured CFI- enabled Instruction Set Architecture (ISA) on actual hardware. Our new instructions provide the finest possible granularity for both intra-function and inter-function Control-Flow Integrity. We implement hardware-based CFI (HCFI) by modifying a SPARC SoC and evaluate the prototype on an FPGA board by running SPECInt benchmarks instrumented with a fine-grained CFI policy. HCFI can effectively protect applications from code-reuse attacks, while adding less than 1% average runtime and 2% power consumption overhead, making it particularly suitable for embed- ded systems.