cloud9_root/src/third_party/stp/src/simplifier/simplifier.cpp
//Tries to simplify the input to TRUE/FALSE. if it fails, then
//return the constructed equality
Tries to simplify the input to TRUE/FALSE. if it fails, then
return the constructed equality
Tries to simplify the input to TRUE / FALSE . if it fails then return the constructed equality
ASTNode
  Simplifier::CreateSimplifiedEQ(const ASTNode& in1, const ASTNode& in2)
  {
    CountersAndStats("CreateSimplifiedEQ", _bm);
    const Kind k1 = in1.GetKind();
    const Kind k2 = in2.GetKind();
    if (in1 == in2)
      return ASTTrue;
    if (BVCONST == k1 && BVCONST == k2)
      return ASTFalse;
    const int constStart = std::min(mostSignificantConstants(in1), mostSignificantConstants(in2));
    for (int i = 0; i < constStart; i++)
      {
        const int a = getConstantBit(in1, i);
        const int b = getConstantBit(in2, i);
        assert(a==1 || a==0);
        assert(b==1 || b==0);
        if (a != b)
          return ASTFalse;
      }
    if (constStart > 0)
      {
        int newWidth = in1.GetValueWidth() - constStart;
        ASTNode zero = _bm->CreateZeroConst(32);
        ASTNode lhs = nf->CreateTerm(BVEXTRACT, newWidth, in1, _bm->CreateBVConst(32, newWidth - 1), zero);
        ASTNode rhs = nf->CreateTerm(BVEXTRACT, newWidth, in2, _bm->CreateBVConst(32, newWidth - 1), zero);
        ASTNode r = nf->CreateNode(EQ, lhs, rhs);
        assert(BVTypeCheck(r));
        return r;
      }
    if (k1 == BVCONCAT && k2 == BVCONCAT && in1[0].GetValueWidth() == in2[0].GetValueWidth())
      {
        return nf->CreateNode(AND, nf->CreateNode(EQ, in1[0], in2[0]), nf->CreateNode(EQ, in1[1], in2[1]));
      }
    if (k1 == BVCONST && k2 == BVCONCAT)
      {
        int width = in1.GetValueWidth();
        int bottomW = in2[1].GetValueWidth();
        ASTNode zero = _bm->CreateZeroConst(32);
        ASTNode top = nf->CreateTerm(BVEXTRACT, width - bottomW, in1, _bm->CreateBVConst(32, width - 1),
            _bm->CreateBVConst(32, bottomW));
        ASTNode bottom = nf->CreateTerm(BVEXTRACT, bottomW, in1, _bm->CreateBVConst(32, bottomW - 1), zero);
        assert(BVTypeCheck(top));
        assert(BVTypeCheck(bottom));
        ASTNode r = nf->CreateNode(AND, nf->CreateNode(EQ, top, in2[0]), nf->CreateNode(EQ, bottom, in2[1]));
        return r;
      }
    if ((k1 == ITE || k1 == BVCONST) && (k2 == ITE || k2 == BVCONST))
      {
        ASTNodeSet visited0, visited1;
        vector<ASTNode> l0, l1;
        if (getPossibleValues(in1, visited0, l0) && getPossibleValues(in2, visited1, l1))
          {
            sort(l0.begin(), l0.end());
            sort(l1.begin(), l1.end());
            vector<ASTNode> result(l0.size() + l1.size());
            vector<ASTNode>::iterator it = set_intersection(l0.begin(), l0.end(), l1.begin(), l1.end(), result.begin());
            if (it == result.begin())
              return ASTFalse;
            if (it == result.begin() + 1)
              {
                ASTNode lhs = replaceIteConst(in1, *result.begin(), nf);
                ASTNode rhs = replaceIteConst(in2, *result.begin(), nf);
                ASTNode result = nf->CreateNode(AND, lhs, rhs);
                return result;
              }
          }
      }
    return nf->CreateNode(EQ, in1, in2);
  }
ASTNode Simplifier :: CreateSimplifiedEQ ( const ASTNode & in1 , const ASTNode & in2 ) { CountersAndStats ( " " , _bm ) ; const Kind k1 = in1 . GetKind ( ) ; const Kind k2 = in2 . GetKind ( ) ; if ( in1 == in2 ) return ASTTrue ; if ( BVCONST == k1 && BVCONST == k2 ) return ASTFalse ; const int constStart = std :: min ( mostSignificantConstants ( in1 ) , mostSignificantConstants ( in2 ) ) ; for ( int i = 0 ; i < constStart ; i ++ ) { const int a = getConstantBit ( in1 , i ) ; const int b = getConstantBit ( in2 , i ) ; assert ( a == 1 || a == 0 ) ; assert ( b == 1 || b == 0 ) ; if ( a != b ) return ASTFalse ; } if ( constStart > 0 ) { int newWidth = in1 . GetValueWidth ( ) - constStart ; ASTNode zero = _bm -> CreateZeroConst ( 32 ) ; ASTNode lhs = nf -> CreateTerm ( BVEXTRACT , newWidth , in1 , _bm -> CreateBVConst ( 32 , newWidth - 1 ) , zero ) ; ASTNode rhs = nf -> CreateTerm ( BVEXTRACT , newWidth , in2 , _bm -> CreateBVConst ( 32 , newWidth - 1 ) , zero ) ; ASTNode r = nf -> CreateNode ( EQ , lhs , rhs ) ; assert ( BVTypeCheck ( r ) ) ; return r ; } if ( k1 == BVCONCAT && k2 == BVCONCAT && in1 [ 0 ] . GetValueWidth ( ) == in2 [ 0 ] . GetValueWidth ( ) ) { return nf -> CreateNode ( AND , nf -> CreateNode ( EQ , in1 [ 0 ] , in2 [ 0 ] ) , nf -> CreateNode ( EQ , in1 [ 1 ] , in2 [ 1 ] ) ) ; } if ( k1 == BVCONST && k2 == BVCONCAT ) { int width = in1 . GetValueWidth ( ) ; int bottomW = in2 [ 1 ] . GetValueWidth ( ) ; ASTNode zero = _bm -> CreateZeroConst ( 32 ) ; ASTNode top = nf -> CreateTerm ( BVEXTRACT , width - bottomW , in1 , _bm -> CreateBVConst ( 32 , width - 1 ) , _bm -> CreateBVConst ( 32 , bottomW ) ) ; ASTNode bottom = nf -> CreateTerm ( BVEXTRACT , bottomW , in1 , _bm -> CreateBVConst ( 32 , bottomW - 1 ) , zero ) ; assert ( BVTypeCheck ( top ) ) ; assert ( BVTypeCheck ( bottom ) ) ; ASTNode r = nf -> CreateNode ( AND , nf -> CreateNode ( EQ , top , in2 [ 0 ] ) , nf -> CreateNode ( EQ , bottom , in2 [ 1 ] ) ) ; return r ; } if ( ( k1 == ITE || k1 == BVCONST ) && ( k2 == ITE || k2 == BVCONST ) ) { ASTNodeSet visited0 , visited1 ; vector < ASTNode > l0 , l1 ; if ( getPossibleValues ( in1 , visited0 , l0 ) && getPossibleValues ( in2 , visited1 , l1 ) ) { sort ( l0 . begin ( ) , l0 . end ( ) ) ; sort ( l1 . begin ( ) , l1 . end ( ) ) ; vector < ASTNode > result ( l0 . size ( ) + l1 . size ( ) ) ; vector < ASTNode > :: iterator it = set_intersection ( l0 . begin ( ) , l0 . end ( ) , l1 . begin ( ) , l1 . end ( ) , result . begin ( ) ) ; if ( it == result . begin ( ) ) return ASTFalse ; if ( it == result . begin ( ) + 1 ) { ASTNode lhs = replaceIteConst ( in1 , * result . begin ( ) , nf ) ; ASTNode rhs = replaceIteConst ( in2 , * result . begin ( ) , nf ) ; ASTNode result = nf -> CreateNode ( AND , lhs , rhs ) ; return result ; } } } return nf -> CreateNode ( EQ , in1 , in2 ) ; }
Tries to simplify the input to TRUE/FALSE.
Tries to simplify the input to TRUE / FALSE .
//terms are syntactically the same //here the terms are definitely not syntactically equal but may be //semantically equal. // Check if some of the leading constant bits are different. Fancier code would check // each bit, not just the leading bits. // The above loop has determined that the leading bits are the same. // If both the children are concats split them apart. // nb. This doesn't cover the case when the children are organised differently: // (concat (concat A B) C) == (concat A (concat B C)) // If the rhs is a concat, and the lhs is a constant. Split. // split the constant. // If it can only evaluate to constants on the LHS and the RHS, and those constants are never equal, // then it must be false. e.g.   ite( f, 10 , 20 ) = ite (g, 30 ,12) // If there is just one value in common, then, set it to true whenever it equals that value. //last resort is to CreateNode