google/souper — pull request #82 by chenyang78 (2014-10-09 04:19:29+00:00)
Title: Improvements to getUBInstCondition

The original implementation has some performance issues and also
a large memory footprint when the number of phi instructions is large.
There are some subtle problems:

Presumably I guess the purpose of UsedPhis is for avoiding processing
a phi instruction multiple times. However, it doesn't really make effect
(I actually put an assertion there, i.e., assert(UsedPhis.count(I) == 0),
and it never failed during my testing on gzip and some llvm files. )
To better understand that, let's look at the following example,

%34:i1 = phi %33, 0:i1, %29
%35:i1 = phi %32, %29, %34
%36:i1 = phi %31, %29, %35

Let's say we the current phi is %34, then we get into getUBPhiPaths.
Because getUBPhiPaths doesn't have a mechanism to determine
if a phi has been processed or not, we will recursively process
%34 and %29. After we return from the recursive call, let's assume
we add %34 and %29 into UsedPhis. Then, we move to %35, because %35 is
not in UsedPhis, we will go into getUBPhiPaths. This time we will
process %35, %29, (%34, %29) (visitations between the parentheses
repeat what we have done when processing %34). Similarly, for
%36, we do %36, %29, (%35, %29, %34, %29). When the phi-chain
is long, we will redo a very large amount of work. Also, since
for each phi path, we `new' some memory for it and end up with
a large memory footprint. Consequently, when the required memory
is smaller than the memory provided by the system, we failed to
handle some files.

----------

The path addresses these issues using the following approach.

The basic algorithm is:

(1) for a given phi instruction, we first collect all paths that start
from the phi. For each path, we also keep the the phi instructions
along the path and the UB instructions associated with these phi
instructions;
(2) then for each path, we generate a corresponding KLEE expression
based on the facts that we collected in step (1), including:
* UB instructions;
* Phi predicates;

With the algorithm, it is easy to get into the path explosion problem,
i.e., the number of paths is increased exponentially. Under some
circumstances, e.g., the number of phis is too large, we will suffer
with large performance overhead. In some extreme cases, we will fail
to process some file due to the large memory footprint, i.e., `newing'
too many PhiPaths. Two tricks are used to relief the penalty of the
path explosion problem:
(1) caching the KLEE expresions for each processed phi, where each
KLEE expression encodes the path that starts from one of the phi's
values. For example, when processing a sample souper IR below

%0 = block
%1 = block
%2:i32 = var
%3:i32 = shl 0:i32, %2
%4:i32 = var
%5:i32 = shl 0:i32, %4
%6 = block
%11:i32 = phi %1, %3, %5
%12:i32 = phi %0, %6, %11

we first encounter phi %11. The generated KLEE expression
for this phi encodes two paths, i.e., %3 and %5. We cache
these two into CachedPhis. Then we move to process phi %12.
At this point, rather than recursively re-contruct %11 (through
%12's value), we just re-used the cached path-expressions.
For each path-expression, we append it with %12's own predicate
and also cache them with %12 for future use. After finishing
%12, we will have three entries for phi %12.
(2) The first trick increases the performance, but we still suffer
with large memory consumption, i.e., it's easy to cache too
many paths. The second trick is to reduce the memory footprint
by only caching "useful" path that has UB Insts. For example,
in the example in (1), for phi %12, we don't need to cache
the path starting from %6, because this path doesn't have any
UB Insts.

These tricks basically relies on the dependency chain of instructions
generated by souper. For example, if we say %12 depends on %11, then
%12 would never appear earlier than %11.