This paper presents the design and evaluation of GreenDrive, a smartphone-based system that helps drivers save fuel by judiciously advising on driving speed to match the signal phase and timing (SPAT) of upcoming signalized traffic intersections. In the absence of such advice, the default driver behavior is usually to accelerate to (near) the maximum legally allowable speed, traffic conditions permitting. This behavior is suboptimal if the traffic light ahead will turn red just before the vehicle arrives at the intersection. GreenDrive uses collected real-time vehicle mobility data to predict exact signal timing a few tens of seconds ahead, which allows it to offer advice on speed that saves fuel by avoiding unnecessary acceleration that leads to arriving too soon and stopping at red lights. Our work differs from previous work in three respects. First and most importantly, we tackle the more challenging scenario, where some phases (such as left-turn arrows) are added or skipped dynamically, in accordance with real-time traffic demand. Second, our approach can accommodate a low system penetration rate and low vehicle density. Third, GreenDrive treats user-specified travel time requirements as soft deadlines and chooses appropriate speed adaptation strategies according to the user time budget. Using SUMO traffic simulator with real and large-scale road network, we show that GreenDrive learns phase durations with an average error below 2s, and reduces fuel consumption by up to 23.9%. Realworld experiments confirm 31.2% fuel saving and the ability to meet end-to-end travel time requirements.