[Analyzer][NFCi] SValBuilder: Simlify a SymExpr to the absolute simplest form

[martong]

Summary

Move the SymExpr simplification fixpoint logic into SValBuilder.

Strictly speaking, this is not an NFC, however, I could not synthesize a test that could demonstrate any functional change. The only difference compared to the baseline is where the actual simplification happens.

[martong]

Measurement results are attached, I think there is no relevant difference.

stats.html92 KBDownload

[steakhal]

I don't think there is any time concern with this patch. It's NFC. You should retitle accordingly.

clang/lib/StaticAnalyzer/Core/SimpleSValBuilder.cpp

51

What about calling this simplifySValOnce()

1137

You can remove this comment. Not really useful anyway.

[martong]

• Rename simplifySValImpl to simplifySValOnce
• Remove a comment

[martong]

clang/lib/StaticAnalyzer/Core/SimpleSValBuilder.cpp

51

Sounds better!

1137

Ok.

[steakhal]

You mentioned in the summary that there are different places where simplification-like machinary kicks in, which hindered the test case synthesis. What places did you refer to exactly?

[martong]

In D114938#3174331, @steakhal wrote:

You mentioned in the summary that there are different places where simplification-like machinary kicks in, which hindered the test case synthesis. What places did you refer to exactly?

These are the places where we call SimpleSValBuilder::simplifySVal.

1. EquivalenceClass::simplify
2. SimpleSValBuilder::evalBinOpNN
3. SimpleSValBuilder::getKnownValue

clang/lib/StaticAnalyzer/Core/RangeConstraintManager.cpp

if (Constraint->encodesTrueRange()) {
     // Fall through, re-assume based on the range values as well.
   }
   // Overestimate the individual Ranges with the RangeSet' lowest and
   // highest values.
   return State->assumeInclusiveRange(DefinedVal, Constraint->getMinValue(),
                                      Constraint->getMaxValue(), true);
 }
 
-// Simplify the given symbol with the help of the SValBuilder. In
-// SValBuilder::symplifySval, we traverse the symbol tree and query the
-// constraint values for the sub-trees and if a value is a constant we do the
-// constant folding. Compound symbols might collapse to simpler symbol tree
-// that is still possible to further simplify. Thus, we do the simplification on
-// a new symbol tree until we reach the simplest form, i.e. the fixpoint.
-//
-// Consider the following symbol `(b * b) * b * b` which has this tree:
-//       *
-//      / \
-//     *   b
-//    /  \
-//   /    b
-// (b * b)
-// Now, if the `b * b == 1` new constraint is added then during the first
-// iteration we have the following transformations:
-//       *                  *
-//      / \                / \
-//     *   b     -->      b   b
-//    /  \
-//   /    b
-//  1
-// We need another iteration to reach the final result `1`.
-LLVM_NODISCARD
-static SVal simplifyUntilFixpoint(SValBuilder &SVB, ProgramStateRef State,
-                                  const SymbolRef Sym) {
-  SVal Val = SVB.makeSymbolVal(Sym);
-  SVal SimplifiedVal = SVB.simplifySVal(State, Val);
-  // Do the simplification until we can.
-  while (SimplifiedVal != Val) {
-    Val = SimplifiedVal;
-    SimplifiedVal = SVB.simplifySVal(State, Val);
-  }
-  return SimplifiedVal;
-}
-
 // Iterate over all symbols and try to simplify them. Once a symbol is
 // simplified then we check if we can merge the simplified symbol's equivalence
 // class to this class. This way, we simplify not just the symbols but the
 // classes as well: we strive to keep the number of the classes to be the
 // absolute minimum.
 LLVM_NODISCARD ProgramStateRef
 EquivalenceClass::simplify(SValBuilder &SVB, RangeSet::Factory &F,
                            ProgramStateRef State, EquivalenceClass Class) {
   SymbolSet ClassMembers = Class.getClassMembers(State);
   for (const SymbolRef &MemberSym : ClassMembers) {
 
-    const SVal SimplifiedMemberVal =
-        simplifyUntilFixpoint(SVB, State, MemberSym);
+    const SVal SimplifiedMemberVal = simplifyToSVal(State, MemberSym);
     const SymbolRef SimplifiedMemberSym = SimplifiedMemberVal.getAsSymbol();
 
     // The symbol is collapsed to a constant, check if the current State is
     // still feasible.
     if (const auto CI = SimplifiedMemberVal.getAs<nonloc::ConcreteInt>()) {
       const llvm::APSInt &SV = CI->getValue();
       const RangeSet *ClassConstraint = getConstraint(State, Class);
       // We have found a contradiction.

clang/lib/StaticAnalyzer/Core/SimpleSValBuilder.cpp

 #include "clang/StaticAnalyzer/Core/PathSensitive/ProgramState.h"
 #include "clang/StaticAnalyzer/Core/PathSensitive/SValVisitor.h"
 
 using namespace clang;
 using namespace ento;
 
 namespace {
 class SimpleSValBuilder : public SValBuilder {
+
+  // With one `simplifySValOnce` call, a compound symbols might collapse to
+  // simpler symbol tree that is still possible to further simplify. Thus, we
+  // do the simplification on a new symbol tree until we reach the simplest
+  // form, i.e. the fixpoint.
+  // Consider the following symbol `(b * b) * b * b` which has this tree:
+  //       *
+  //      / \
+  //     *   b
+  //    /  \
+  //   /    b
+  // (b * b)
+  // Now, if the `b * b == 1` new constraint is added then during the first
+  // iteration we have the following transformations:
+  //       *                  *
+  //      / \                / \
+  //     *   b     -->      b   b
+  //    /  \
+  //   /    b
+  //  1
+  // We need another iteration to reach the final result `1`.
+  SVal simplifyUntilFixpoint(ProgramStateRef State, SVal Val);
+
+  // Recursively descends into symbolic expressions and replaces symbols
+  // with their known values (in the sense of the getKnownValue() method).
+  // We traverse the symbol tree and query the constraint values for the
+  // sub-trees and if a value is a constant we do the constant folding.
+  SVal simplifySValOnce(ProgramStateRef State, SVal V);
+
 public:
   SimpleSValBuilder(llvm::BumpPtrAllocator &alloc, ASTContext &context,
                     ProgramStateManager &stateMgr)
       : SValBuilder(alloc, context, stateMgr) {}
   ~SimpleSValBuilder() override {}
 
   SVal evalMinus(NonLoc val) override;
   SVal evalComplement(NonLoc val) override;
   SVal evalBinOpNN(ProgramStateRef state, BinaryOperator::Opcode op,
                    NonLoc lhs, NonLoc rhs, QualType resultTy) override;
   SVal evalBinOpLL(ProgramStateRef state, BinaryOperator::Opcode op,
                    Loc lhs, Loc rhs, QualType resultTy) override;
   SVal evalBinOpLN(ProgramStateRef state, BinaryOperator::Opcode op,
                    Loc lhs, NonLoc rhs, QualType resultTy) override;
 
   /// getKnownValue - evaluates a given SVal. If the SVal has only one possible
   ///  (integer) value, that value is returned. Otherwise, returns NULL.
   const llvm::APSInt *getKnownValue(ProgramStateRef state, SVal V) override;
 
-  /// Recursively descends into symbolic expressions and replaces symbols
-  /// with their known values (in the sense of the getKnownValue() method).
   SVal simplifySVal(ProgramStateRef State, SVal V) override;
 
   SVal MakeSymIntVal(const SymExpr *LHS, BinaryOperator::Opcode op,
                      const llvm::APSInt &RHS, QualType resultTy);
 };
 } // end anonymous namespace
 
 SValBuilder *ento::createSimpleSValBuilder(llvm::BumpPtrAllocator &alloc,
if (Optional<nonloc::ConcreteInt> X = V.getAs<nonloc::ConcreteInt>())
     return &X->getValue();
 
   if (SymbolRef Sym = V.getAsSymbol())
     return state->getConstraintManager().getSymVal(state, Sym);
 
   return nullptr;
 }
 
+SVal SimpleSValBuilder::simplifyUntilFixpoint(ProgramStateRef State, SVal Val) {
+  SVal SimplifiedVal = simplifySValOnce(State, Val);
+  while (SimplifiedVal != Val) {
+    Val = SimplifiedVal;
+    SimplifiedVal = simplifySValOnce(State, Val);
+  }
+  return SimplifiedVal;
+}
+
 SVal SimpleSValBuilder::simplifySVal(ProgramStateRef State, SVal V) {
+  return simplifyUntilFixpoint(State, V);
+}
+
+SVal SimpleSValBuilder::simplifySValOnce(ProgramStateRef State, SVal V) {
   // For now, this function tries to constant-fold symbols inside a
   // nonloc::SymbolVal, and does nothing else. More simplifications should
   // be possible, such as constant-folding an index in an ElementRegion.
 
   class Simplifier : public FullSValVisitor<Simplifier, SVal> {
     ProgramStateRef State;
     SValBuilder &SVB;