cloud9_root/src/third_party/stp/src/simplifier/constantBitP/ConstantBitPropagation.cpp
// NB: This expects that the constructor was called with the same node. Sorry.
This expects that the constructor was called with the same node. Sorry.
This expects that the constructor was called with the same node . Sorry .
ASTNode
    ConstantBitPropagation::topLevelBothWays(const ASTNode& top, bool setTopToTrue, bool conjoinToTop)
    {
      assert(top.GetSTPMgr()->UserFlags.bitConstantProp_flag);
      assert (BOOLEAN_TYPE == top.GetType());
      propagate();
      status = NO_CHANGE;
      ASTNodeMap fromTo = getAllFixed();
      if (debug_cBitProp_messages)
        {
          cerr << "Number removed by bottom UP:" << fromTo.size() << endl;
        }
      if (setTopToTrue)
    	  setNodeToTrue(top);
      if (debug_cBitProp_messages)
        {
          cerr << "starting propagation" << endl;
          printNodeWithFixings();
          cerr << "Initial Tree:" << endl;
          cerr << top;
        }
      propagate();
      if (debug_cBitProp_messages)
        {
          cerr << "status:" << status <<endl;
          cerr << "ended propagation" << endl;
          printNodeWithFixings();
        }
      if (CONFLICT == status)
          return top.GetSTPMgr()->CreateNode(FALSE);
      ASTVec toConjoin;
      for (NodeToFixedBitsMap::NodeToFixedBitsMapType::iterator it = fixedMap->map->begin(); it != fixedMap->map->end(); it++) 
        {
          const FixedBits& bits = *it->second;
          const ASTNode& node = (it->first);
          if (false && node.GetKind() == SYMBOL && !bits.isTotallyFixed() && bits.countFixed() > 0)
            {
              int leastFixed = bits.leastUnfixed();
              int mostFixed = bits.mostUnfixed();
              const int width = node.GetValueWidth();
              int new_width = mostFixed - leastFixed +1;
              assert(new_width > 0);
              ASTNode fresh = node.GetSTPMgr()->CreateFreshVariable(0,new_width,"STP_REPLACE");
              ASTNode a,b;
              if (leastFixed > 0)
                a= node.GetSTPMgr()->CreateBVConst(bits.GetBVConst( leastFixed-1,  0), leastFixed);
              if (mostFixed != width-1)
                b =  node.GetSTPMgr()->CreateBVConst(bits.GetBVConst( width-1,  mostFixed+1),width-1-mostFixed);
              if (!a.IsNull())
                fresh = nf->CreateTerm(BVCONCAT, a.GetValueWidth() + fresh.GetValueWidth(), fresh, a);
              if (!b.IsNull())
                fresh = nf->CreateTerm(BVCONCAT, b.GetValueWidth() + fresh.GetValueWidth(), b, fresh);
              assert(fresh.GetValueWidth() == node.GetValueWidth());
              bool r = simplifier->UpdateSubstitutionMap(node, fresh);
              assert(r);
            }
          if (!bits.isTotallyFixed())
            continue;
          if (node.isConstant())
            continue;
          if (BVEXTRACT == node.GetKind() || BVCONCAT == node.GetKind())
            continue;
          ASTNode propositionToAssert;
          ASTNode constantToReplaceWith;
          bool doAssign = false;
            {
              if (fromTo.find(node) != fromTo.end())
                continue;
              ASTNode constNode = bitsToNode(node,bits);
              if (node.GetType() == BOOLEAN_TYPE)
                {
                  if (SYMBOL == node.GetKind())
                    {
                      bool r = simplifier->UpdateSubstitutionMap(node, constNode);
                      assert(r);
                      doAssign = false;
                    }
                  else if (conjoinToTop && bits.getValue(0))
                    {
                      propositionToAssert = node;
                      constantToReplaceWith = constNode;
                      doAssign=true;
                    }
                  else if (conjoinToTop)
                    {
                      propositionToAssert = nf->CreateNode(NOT, node);
                      constantToReplaceWith = constNode;
                      doAssign=true;
                    }
                }
              else if (node.GetType() == BITVECTOR_TYPE)
                {
                  assert(((unsigned)bits.getWidth()) == node.GetValueWidth());
                  if (SYMBOL == node.GetKind())
                    {
                      bool r = simplifier->UpdateSubstitutionMap(node, constNode);
                      assert(r);
                      doAssign = false;
                    }
                  else if (conjoinToTop)
                    {
                      propositionToAssert = nf->CreateNode(EQ, node, constNode);
                      constantToReplaceWith = constNode;
                      doAssign=true;
                    }
                }
              else
                FatalError("sadf234s");
            }
          if (doAssign && top != propositionToAssert
              && !dependents->nodeDependsOn(top, propositionToAssert))
            {
              assert(!constantToReplaceWith.IsNull());
              assert(constantToReplaceWith.isConstant());
              assert(propositionToAssert.GetType() == BOOLEAN_TYPE);
              assert(node.GetValueWidth() == constantToReplaceWith.GetValueWidth());
              fromTo.insert(make_pair(node, constantToReplaceWith));
              toConjoin.push_back(propositionToAssert);
              assert(conjoinToTop);
            }
        }
      ASTNodeMap cache;
      ASTNode result = SubstitutionMap::replace(top, fromTo, cache,nf);
      if (0 != toConjoin.size())
        {
          ASTNode conjunct = (1 == toConjoin.size())? toConjoin[0]: nf->CreateNode(AND,toConjoin);
          conjunct = simplifier->applySubstitutionMap(conjunct);
          result = nf->CreateNode(AND, result, conjunct); 
        }
  	if (debug_print_graph_after)
		{
			ofstream file;
			file.open("afterCbitp.gdl");
			PrintingHackfixedMap = fixedMap;
			printer::GDL_Print(file,top,&toString);
			file.close();
		}
      assert(BVTypeCheck(result));
      assert(status != CONFLICT); 
      return result;
    }
ASTNode ConstantBitPropagation :: topLevelBothWays ( const ASTNode & top , bool setTopToTrue , bool conjoinToTop ) { assert ( top . GetSTPMgr ( ) -> UserFlags . bitConstantProp_flag ) ; assert ( BOOLEAN_TYPE == top . GetType ( ) ) ; propagate ( ) ; status = NO_CHANGE ; ASTNodeMap fromTo = getAllFixed ( ) ; if ( debug_cBitProp_messages ) { cerr << " " << fromTo . size ( ) << endl ; } if ( setTopToTrue ) setNodeToTrue ( top ) ; if ( debug_cBitProp_messages ) { cerr << " " << endl ; printNodeWithFixings ( ) ; cerr << " " << endl ; cerr << top ; } propagate ( ) ; if ( debug_cBitProp_messages ) { cerr << " " << status << endl ; cerr << " " << endl ; printNodeWithFixings ( ) ; } if ( CONFLICT == status ) return top . GetSTPMgr ( ) -> CreateNode ( FALSE ) ; ASTVec toConjoin ; for ( NodeToFixedBitsMap :: NodeToFixedBitsMapType :: iterator it = fixedMap -> map -> begin ( ) ; it != fixedMap -> map -> end ( ) ; it ++ ) { const FixedBits & bits = * it -> second ; const ASTNode & node = ( it -> first ) ; if ( false && node . GetKind ( ) == SYMBOL && ! bits . isTotallyFixed ( ) && bits . countFixed ( ) > 0 ) { int leastFixed = bits . leastUnfixed ( ) ; int mostFixed = bits . mostUnfixed ( ) ; const int width = node . GetValueWidth ( ) ; int new_width = mostFixed - leastFixed + 1 ; assert ( new_width > 0 ) ; ASTNode fresh = node . GetSTPMgr ( ) -> CreateFreshVariable ( 0 , new_width , " " ) ; ASTNode a , b ; if ( leastFixed > 0 ) a = node . GetSTPMgr ( ) -> CreateBVConst ( bits . GetBVConst ( leastFixed - 1 , 0 ) , leastFixed ) ; if ( mostFixed != width - 1 ) b = node . GetSTPMgr ( ) -> CreateBVConst ( bits . GetBVConst ( width - 1 , mostFixed + 1 ) , width - 1 - mostFixed ) ; if ( ! a . IsNull ( ) ) fresh = nf -> CreateTerm ( BVCONCAT , a . GetValueWidth ( ) + fresh . GetValueWidth ( ) , fresh , a ) ; if ( ! b . IsNull ( ) ) fresh = nf -> CreateTerm ( BVCONCAT , b . GetValueWidth ( ) + fresh . GetValueWidth ( ) , b , fresh ) ; assert ( fresh . GetValueWidth ( ) == node . GetValueWidth ( ) ) ; bool r = simplifier -> UpdateSubstitutionMap ( node , fresh ) ; assert ( r ) ; } if ( ! bits . isTotallyFixed ( ) ) continue ; if ( node . isConstant ( ) ) continue ; if ( BVEXTRACT == node . GetKind ( ) || BVCONCAT == node . GetKind ( ) ) continue ; ASTNode propositionToAssert ; ASTNode constantToReplaceWith ; bool doAssign = false ; { if ( fromTo . find ( node ) != fromTo . end ( ) ) continue ; ASTNode constNode = bitsToNode ( node , bits ) ; if ( node . GetType ( ) == BOOLEAN_TYPE ) { if ( SYMBOL == node . GetKind ( ) ) { bool r = simplifier -> UpdateSubstitutionMap ( node , constNode ) ; assert ( r ) ; doAssign = false ; } else if ( conjoinToTop && bits . getValue ( 0 ) ) { propositionToAssert = node ; constantToReplaceWith = constNode ; doAssign = true ; } else if ( conjoinToTop ) { propositionToAssert = nf -> CreateNode ( NOT , node ) ; constantToReplaceWith = constNode ; doAssign = true ; } } else if ( node . GetType ( ) == BITVECTOR_TYPE ) { assert ( ( ( unsigned ) bits . getWidth ( ) ) == node . GetValueWidth ( ) ) ; if ( SYMBOL == node . GetKind ( ) ) { bool r = simplifier -> UpdateSubstitutionMap ( node , constNode ) ; assert ( r ) ; doAssign = false ; } else if ( conjoinToTop ) { propositionToAssert = nf -> CreateNode ( EQ , node , constNode ) ; constantToReplaceWith = constNode ; doAssign = true ; } } else FatalError ( " " ) ; } if ( doAssign && top != propositionToAssert && ! dependents -> nodeDependsOn ( top , propositionToAssert ) ) { assert ( ! constantToReplaceWith . IsNull ( ) ) ; assert ( constantToReplaceWith . isConstant ( ) ) ; assert ( propositionToAssert . GetType ( ) == BOOLEAN_TYPE ) ; assert ( node . GetValueWidth ( ) == constantToReplaceWith . GetValueWidth ( ) ) ; fromTo . insert ( make_pair ( node , constantToReplaceWith ) ) ; toConjoin . push_back ( propositionToAssert ) ; assert ( conjoinToTop ) ; } } ASTNodeMap cache ; ASTNode result = SubstitutionMap :: replace ( top , fromTo , cache , nf ) ; if ( 0 != toConjoin . size ( ) ) { ASTNode conjunct = ( 1 == toConjoin . size ( ) ) ? toConjoin [ 0 ] : nf -> CreateNode ( AND , toConjoin ) ; conjunct = simplifier -> applySubstitutionMap ( conjunct ) ; result = nf -> CreateNode ( AND , result , conjunct ) ; } if ( debug_print_graph_after ) { ofstream file ; file . open ( " " ) ; PrintingHackfixedMap = fixedMap ; printer :: GDL_Print ( file , top , & toString ) ; file . close ( ) ; } assert ( BVTypeCheck ( result ) ) ; assert ( status != CONFLICT ) ; return result ; }
NB: This expects that the constructor was called with the same node.
NB : This expects that the constructor was called with the same node .
//Determine what must always be true. // propagate may have stopped with a conflict. // go through the fixedBits. If a node is entirely fixed. // "and" it onto the top. Creates redundancy. Check that the // node doesn't already depend on "top" directly. // iterates through all the pairs of node->fixedBits. // replace partially known variables with new variables. // Don't constrain nodes we already know all about. // other nodes will contain the same information (the extract doesn't change the fixings). // toAssign: conjoin it with the top level. // toReplace: replace all references to it (except the one conjoined to the top) with this. // skip the assigning and replacing. // If it is already contained in the fromTo map, then it's one of the values // that have fully been determined (previously). Not conjoined. // Write the constants into the main graph. // It doesn't happen very often. But the "toConjoin" might contain a variable // that was added to the substitution map (because the value was determined just now // during propagation. // conjoin the new conditions. // conflict should have been seen earlier.