In one embodiment, a method for controlling an instruction cache including a least-recently-used bits array, a tag array, and a data array, includes looking up, in the least-recently-used bits array, least-recently-used bits for each of a plurality of cacheline sets in the instruction cache, determining a most-recently-used way in a designated cacheline set of the plurality of cacheline sets based on the least-recently-used bits for the designated cacheline, looking up, in the tag array, tags for one or more ways in the designated cacheline set, looking up, in the data array, data stored in the most-recently-used way in the designated cacheline set, and if there is a cache hit in the most-recently-used way, retrieving the data stored in the most-recently-used way from the data array.