  Applying program analyses to Software Product Lines (SPLs) has been a
fundamental research problem at the intersection of Product Line Engineering
and software analysis. Different attempts have been made to "lift" particular
product-level analyses to run on the entire product line. In this paper, we
tackle the class of Datalog-based analyses (e.g., pointer and taint analyses),
study the theoretical aspects of lifting Datalog inference, and implement a
lifted inference algorithm inside the Souffl\'e Datalog engine. We evaluate our
implementation on a set of benchmark product lines. We show significant savings
in processing time and fact database size (billions of times faster on one of
the benchmarks) compared to brute-force analysis of each product individually.
