The lack of memory safety in many popular programming languages, including C and C++, has been a cause for great concern in the realm of software reliability, verification, and more recently, system security. A major portion of known security attacks against software systems can be attributed to this shortcoming, including the well-known stack overflow, heap overflow, and format string attacks. Despite their limitations, the flexibility, performance, and ease of use of these languages have made them the choice of most embedded software developers. Researchers have proposed various techniques to enhance programs for memory safety; however, they are all subject to severe performance penalties, making their use impractical in most scenarios. In this paper, we present architectural enhancements to enable efficient, memory-safe execution of software on embedded processors. The key insight behind our approach is to extend embedded processors with hardware that significantly accelerates the execution of the additional computations involved in memory-safe execution. Specifically, we design custom instructions to perform various kinds of memory-safety checks and augment the instruction set of a state-of-the-art extensible processor (Xtensa from Tensilica, Inc.) to implement them. We demonstrate the application of the proposed architectural enhancements using CCured, an existing tool for type-safe retrofitting of C programs. The tool uses a type-inferencing engine that is built around strong type-safety theory and is provably safe. Simulations of memory-safe versions of popular embedded benchmarks on a cycle-accurate simulator modeling a typical embedded system configuration indicate an average performance improvement of 2.3x, and a maximum of 4.6x when using the proposed architecture. These enhancements entail minimal (less than 10%) hardware overhead to the base processor. Our approach is completely automated, and applicable to any C program, making it a promising and practical approach for addressing the growing security and reliability concerns in embedded software.