SimpleSValBuilder.cpp

Go to the documentation of this file.

// SimpleSValBuilder.cpp - A basic SValBuilder -----------------------*- C++ -*-
//
// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
// See https://llvm.org/LICENSE.txt for license information.
// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
//
//===----------------------------------------------------------------------===//
//
//  This file defines SimpleSValBuilder, a basic implementation of SValBuilder.
//
//===----------------------------------------------------------------------===//
 
#include "clang/StaticAnalyzer/Core/PathSensitive/APSIntPtr.h"
#include "clang/StaticAnalyzer/Core/PathSensitive/APSIntType.h"
#include "clang/StaticAnalyzer/Core/PathSensitive/ExprEngine.h"
#include "clang/StaticAnalyzer/Core/PathSensitive/ProgramState.h"
#include "clang/StaticAnalyzer/Core/PathSensitive/SValBuilder.h"
#include "clang/StaticAnalyzer/Core/PathSensitive/SValVisitor.h"
#include <optional>
 
using namespace clang;
using namespace ento;
 
namespace {
class SimpleSValBuilder : public SValBuilder {
 
  // Query the constraint manager whether the SVal has only one possible
  // (integer) value. If that is the case, the value is returned. Otherwise,
  // returns NULL.
  // This is an implementation detail. Checkers should use `getKnownValue()`
  // instead.
  static const llvm::APSInt *getConstValue(ProgramStateRef state, SVal V);
 
  // Helper function that returns the value stored in a nonloc::ConcreteInt or
  // loc::ConcreteInt.
  static const llvm::APSInt *getConcreteValue(SVal V);
 
  // 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 getConstValue() 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 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;
 
  /// Evaluates a given SVal by recursively evaluating and
  /// simplifying the children SVals. 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;
 
  /// Evaluates a given SVal by recursively evaluating and simplifying the
  /// children SVals, then returns its minimal possible (integer) value. If the
  /// constraint manager cannot provide a meaningful answer, this returns NULL.
  const llvm::APSInt *getMinValue(ProgramStateRef state, SVal V) override;
 
  /// Evaluates a given SVal by recursively evaluating and simplifying the
  /// children SVals, then returns its maximal possible (integer) value. If the
  /// constraint manager cannot provide a meaningful answer, this returns NULL.
  const llvm::APSInt *getMaxValue(ProgramStateRef state, SVal V) override;
 
  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,
                                           ASTContext &context,
                                           ProgramStateManager &stateMgr) {
  return new SimpleSValBuilder(alloc, context, stateMgr);
}
 
// Checks if the negation the value and flipping sign preserve
// the semantics on the operation in the resultType
static bool isNegationValuePreserving(const llvm::APSInt &Value,
                                      APSIntType ResultType) {
  const unsigned ValueBits = Value.getSignificantBits();
  if (ValueBits == ResultType.getBitWidth()) {
    // The value is the lowest negative value that is representable
    // in signed integer with bitWith of result type. The
    // negation is representable if resultType is unsigned.
    return ResultType.isUnsigned();
  }
 
  // If resultType bitWith is higher that number of bits required
  // to represent RHS, the sign flip produce same value.
  return ValueBits < ResultType.getBitWidth();
}
 
//===----------------------------------------------------------------------===//
// Transfer function for binary operators.
//===----------------------------------------------------------------------===//
 
SVal SimpleSValBuilder::MakeSymIntVal(const SymExpr *LHS,
                                    BinaryOperator::Opcode op,
                                    const llvm::APSInt &RHS,
                                    QualType resultTy) {