Use Sitecore Content Search (Lucene) Index to retrieve all items from index that include a specific rendering. Don't forget to allow/include "__Renderings" in your index. Cleaner solution could be achieved using ComputedField to index renderings by ID type (for example)

GetAllItemsBasedOnRendering.cs

/// <summary>
/// Use Sitecore Content Search (Lucene) Index to retrieve all items from index that include a specific rendering
/// </summary>
/// <param name="templateID"></param>
/// <param name="database"></param>
/// <param name="indexName"></param>
/// <returns></returns>
private List<Item> GetAllItemsBasedOnRendering(ID renderingID, string database, string indexName)
{
	List<Item> resultList = new List<Item>();
	var index = ContentSearchManager.GetIndex(indexName);

	Database db = Sitecore.Configuration.Factory.GetDatabase(database);
	if (db == null)
	{
		return resultList;
	}

	using (var context = index.CreateSearchContext())
	{
		string renderingStr = renderingID.ToString().ToLowerInvariant();
		var results = context.GetQueryable<SearchResult>().Where(x => x.Renderings.Contains(renderingStr)).GetResults().Hits;
		if (results != null && results.Count() > 0)
		{
			resultList = results.Select(x => x.Document.GetItem()).ToList();
		}
	}
	return resultList;
}

public class SearchResult : SearchResultItem
{
	[IndexField("__Renderings")]
	public string Renderings { get; set; }
}