Support for intrinsics cttz, ctlz, ctpop and bswap
tell sclang, using an environment var, to get Souper to print stats
Merge pull request #78 from jubitaneja/intrinsics-final

Support for intrinsics cttz, ctlz, ctpop and bswap
Rename all flags containing the substring -souper to have -souper at the start

This has bugged me for a while. It's pretty clear at this point that we
should be more consistent about this as we add more flags.
Merge pull request #83 from regehr/sclang-stats

tell sclang, using an environment var, to get Souper to print stats
Added a new flag -souper-debug-level to control the verbose level of debug information

* Added one more cmdline option -souper-debug-level which
controls the verbose level of debug message. The larger
the number is, the more verbose message is generated.
The default level is 1.

* When the souper-debug-level is larger than 1, then dump all
replacements that collected by souper before they are processed
by KLEE. The existing debug-souper behavior will not be affected
if we do not pass a level higher than 1.
Fixed issue 26

The idea is that when we build an instruction, if the instruction is a phi-node with multiple incoming edges, we do DFS from the basic block containing the phi-node and check if we will revisit the basic block. If yes, we know that this phi-node is the merge point of loop iterations.
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 patch 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 = var
  %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.
Merge pull request #79 from chenyang78/debug_info

More control over debug information
Merge pull request #74 from chenyang78/issue_26

A fix to address issue 26
Merge pull request #82 from chenyang78/getUBInstCondition

Improvements to getUBInstCondition
Add Yang Chen (individual CLA)
implement infer(), a Solver method that replaces isValid() for some important
use cases, such as the opt Pass and the main souper tool. infer() finds a RHS
for a Souper LHS, avoiding the need to guess what the RHS looks like. infer()
provides memory-based and Redis-based caching, and isValid() calls are no longer
cached at all. also, turn the CandidateMap data structure into a simple vector.

this patchset leaves the following changes for subsequent work:

- add an end-to-end test of the Redis subsystem

- possibly rename the CandidateMap data structure

- place the static profiling code properly (currently it is below the RAM cache,
causing it to undercount)

- possibly remove the isTriviallyValid() checker, as it does not measureably
affect performance
Merge pull request #87 from regehr/infer

implement infer()
Merge branch 'master' into tools
tool improvements
print warnings to stderr
don't warn in raw mode