We develop Chime, a set of mechanisms and methodologies that enable long-running computations on low power IoT devices with scarce and intermittent energy sources. We address the power transiency and unpredictability problem by optimally inserting checkpoints that save the intermediate states. Chime automatically locates and embeds checkpoints at the register-transfer level. We define an objective function that aims to find low-overhead checkpoints which minimize the recomputation energy cost. We develop and exploit a dynamic programming technique to solve the optimization problem. For real time operation, Chime adaptively adjusts the checkpointing rate based on the available energy level in the system. Chime is deployed and evaluated on algebraic, data transformation, and cryptographic benchmark circuits. For storage of checkpoint data, we evaluate and compare the effectiveness of various non-volatile memories including NAND Flash, PCM, and STTM. Extensive evaluations show that Chime reliably enables execution of long computations under different source power patterns with low overhead. Our benchmark evaluations demonstrate that the area and energy overheads corresponding to the checkpoints are less than 9% and 11% respectively.