VariableIdSet SPRAY::IntervalPropertyState::allVariableIds() {
  VariableIdSet set;
  for(IntervalMapType::iterator i=intervals.begin();i!=intervals.end();++i) {
    set.insert((*i).first);
  }
  return set;
}

/*! 
  * \author Markus Schordan
  * \date 2014.
 */
void SPRAY::IntervalTransferFunctions::transferFunctionExit(Label lab, SgFunctionDefinition* funDef, VariableIdSet& localVariablesInFunction, Lattice& element) {
  // remove all declared variables at function exit (including function parameter variables)
  for(VariableIdSet::iterator i=localVariablesInFunction.begin();i!=localVariablesInFunction.end();++i) {
    VariableId varId=*i;
    IntervalPropertyState* ips=dynamic_cast<IntervalPropertyState*>(&element);
    ips->removeVariable(varId);
  }
}

VariableIdSet PState::getVariableIds() const {
  VariableIdSet varIdSet;
  for(PState::const_iterator i=begin();i!=end();++i) {
    VariableId varId=(*i).first;
    varIdSet.insert(varId);
  }
  return varIdSet;
}

/*! 
  * \author Markus Schordan
  * \date 2013.
 */
void RDTransferFunctions::transferFunctionExit(Label lab, SgFunctionDefinition* callExp, VariableIdSet& localVariablesInFunction, Lattice& element0) {
  RDLattice& element=dynamic_cast<RDLattice&>(element0);

  // remove all declared variable at function exit (including function parameter variables)
  for(VariableIdSet::iterator i=localVariablesInFunction.begin();i!=localVariablesInFunction.end();++i) {
    VariableId varId=*i;
    element.removeAllPairsWithVariableId(varId);
  }
}

VariableIdSet 
AnalysisAbstractionLayer::usedVariablesInsideFunctions(SgProject* project, VariableIdMapping* variableIdMapping) {
  list<SgVarRefExp*> varRefExpList=SgNodeHelper::listOfUsedVarsInFunctions(project);
  VariableIdSet setOfUsedVars;
  for(list<SgVarRefExp*>::iterator i=varRefExpList.begin();i!=varRefExpList.end();++i) {
    setOfUsedVars.insert(variableIdMapping->variableId(*i));
  }
  return setOfUsedVars;
}

/*! 
  * \author Markus Schordan
  * \date 2012.
 */
VariableIdMapping::VariableIdSet VariableIdMapping::getVariableIdSet() {
  VariableIdSet set;
  for(map<SgSymbol*,size_t>::iterator i=mappingSymToVarId.begin();i!=mappingSymToVarId.end();++i) {
    size_t t=(*i).second;
    VariableId id;
    id.setIdCode(t);
    set.insert(id);
  }
  return set;
}

VariableIdSet AnalysisAbstractionLayer::defVariables(SgNode* node, VariableIdMapping& vidm) {
  VariableIdSet resultSet;
  VarsInfo defVarsInfo=getDefUseVarsInfo(node, vidm).getDefVarsInfo();
  //cout<<"DEFISEVARSINFO: "<<DefUseVarsInfo::varsInfoPrettyPrint(defVarsInfo,vidm)<<endl;
  //cout<<"VariableIdInfoMap-size:"<<defVarsInfo.first.size()<<endl;
  extractVariableIdSetFromVarsInfo(resultSet,defVarsInfo);
  ROSE_ASSERT(defVarsInfo.first.size()==resultSet.size());
  ROSE_ASSERT(defVarsInfo.first.size()<=1);
  return resultSet;
}

std::string SPRAY::VariableIdSetPrettyPrint::str(VariableIdSet& vset, VariableIdMapping& vidm)
{
  std::ostringstream ostr;
  ostr << "[";
  VariableIdSet::iterator it = vset.begin();
  for( ; it != vset.end(); )
  {
    ostr << "<" << (*it).toString() << ", " << vidm.variableName(*it)  << ">";
    it++;
    if(it != vset.end())
      ostr << ", ";
  }
  ostr << "]";
  return ostr.str();
}

VariableIdSet Threadification::determineVariablesOfInterest(SgNode* root) {
  VariableIdSet varIdSet;
  RoseAst ast(root);
  for(RoseAst::iterator i=ast.begin();i!=ast.end();++i) {
    if(SgVariableDeclaration* varDecl=isSgVariableDeclaration(*i)) {
      VariableId varId=_variableIdMapping->variableId(varDecl);
      // specifically exclude array variable declarations
      if( (_variableIdMapping->hasPointerType(varId)||_variableIdMapping->hasIntegerType(varId)) 
            && _variableIdMapping->variableName(varId) != "stdout" 
            && _variableIdMapping->variableName(varId) != "__PRETTY_FUNCTION__" ) {
        varIdSet.insert(varId);
      }
    }
  }
  return varIdSet;
}

VariableIdMapping::VariableIdSet VariableIdMapping::variableIdsOfAstSubTree(SgNode* node) {
  VariableIdSet vset;
  RoseAst ast(node);
  for(RoseAst::iterator i=ast.begin();i!=ast.end();++i) {
    VariableId vid; // default creates intentionally an invalid id.
    if(SgVariableDeclaration* varDecl=isSgVariableDeclaration(*i)) {
      vid=variableId(varDecl);
    } else if(SgVarRefExp* varRefExp=isSgVarRefExp(*i)) {
      vid=variableId(varRefExp);
    } else if(SgInitializedName* initName=isSgInitializedName(*i)) {
      vid=variableId(initName);
    }
    if(vid.isValid())
      vset.insert(vid);
  }
  return vset;
}

void FIConstAnalysis::filterVariables(VariableIdSet& variableIdSet) {
    VariableIdSet toBeRemoved;
    for(VarConstSetMap::iterator i=_varConstSetMap.begin(); i!=_varConstSetMap.end(); ++i) {
        VariableId varId=(*i).first;
        if(variableIdSet.find(varId)==variableIdSet.end()) {
            toBeRemoved.insert(varId);
        }
    }
    for(VariableIdSet::iterator i=toBeRemoved.begin(); i!=toBeRemoved.end(); ++i) {
        _varConstSetMap.erase(*i);
    }
}

void SPRAY::set_union(const VariableIdSet& set1, const VariableIdSet& set2, VariableIdSet& rset)
{
  VariableIdSet::const_iterator it1 = set1.begin();
  VariableIdSet::const_iterator it2 = set2.begin();
  VariableIdSet::iterator rit = rset.begin();
  
  // // re-implementation of set-union
  while(true)
  {
    if(it1 == set1.end())
    {
      rset.insert(it2, set2.end());
      break;
    }
    if(it2 == set2.end())
    {
      rset.insert(it1, set1.end());
      break;
    }
    
    if(*it1 < *it2)
    {
      rset.insert(rit, *it1); ++it1; ++rit;
    }
    else if(*it2 < *it1)
    {
      rset.insert(rit, *it2); ++it2; ++rit;
    }
    else
    {
      rset.insert(rit, *it1); ++it1; ++it2; ++rit;
    }
  }
}

// returns the number of race conditions detected (0 or 1 as of now)
int Specialization::verifyUpdateSequenceRaceConditions(LoopInfoSet& loopInfoSet, ArrayUpdatesSequence& arrayUpdates, VariableIdMapping* variableIdMapping) {
  int cnt=0;
  stringstream ss;
  cout<<"STATUS: checking race conditions."<<endl;
  cout<<"INFO: number of parallel loops: "<<numParLoops(loopInfoSet,variableIdMapping)<<endl;

  VariableIdSet allIterVars;
  for(LoopInfoSet::iterator lis=loopInfoSet.begin();lis!=loopInfoSet.end();++lis) {
    allIterVars.insert((*lis).iterationVarId);
  }
  for(LoopInfoSet::iterator lis=loopInfoSet.begin();lis!=loopInfoSet.end();++lis) {
    if((*lis).iterationVarType==ITERVAR_PAR) {
      VariableId parVariable;
      parVariable=(*lis).iterationVarId;
      cout<<"INFO: checking parallel loop: "<<variableIdMapping->variableName(parVariable)<<endl;

      // race check
      // intersect w-set_i = empty
      // w-set_i intersect r-set_j = empty, i!=j.

      IndexToReadWriteDataMap indexToReadWriteDataMap;
      for(ArrayUpdatesSequence::iterator i=arrayUpdates.begin();i!=arrayUpdates.end();++i) {
        const EState* estate=(*i).first;
        const PState* pstate=estate->pstate();
        SgExpression* exp=(*i).second;
        IndexVector index;
        // use all vars for indexing or only outer+par loop variables
#ifdef USE_ALL_ITER_VARS
        for(VariableIdSet::iterator ol=allIterVars.begin();ol!=allIterVars.end();++ol) {
          VariableId otherVarId=*ol;
          ROSE_ASSERT(otherVarId.isValid());
          if(!pstate->varValue(otherVarId).isTop()) {
            int otherIntVal=pstate->varValue(otherVarId).getIntValue();
            index.push_back(otherIntVal);
          }
        }
#else
        for(VariableIdSet::iterator ol=(*lis).outerLoopsVarIds.begin();ol!=(*lis).outerLoopsVarIds.end();++ol) {
          VariableId otherVarId=*ol;
          ROSE_ASSERT(otherVarId.isValid());
          if(!pstate->varValue(otherVarId).isTop()&&pstate->varValue(otherVarId).isConstInt()) {
            int otherIntVal=pstate->varValue(otherVarId).getIntValue();
            index.push_back(otherIntVal);
          }
        }
        if(!pstate->varValue(parVariable).isTop()&&pstate->varValue(parVariable).isConstInt()) {
          int parIntVal=pstate->varValue(parVariable).getIntValue();
          index.push_back(parIntVal);
        }
#endif
        if((*lis).isInAssociatedLoop(estate)) {
          SgExpression* lhs=isSgExpression(SgNodeHelper::getLhs(exp));
          SgExpression* rhs=isSgExpression(SgNodeHelper::getRhs(exp));
          ROSE_ASSERT(isSgPntrArrRefExp(lhs)||SgNodeHelper::isFloatingPointAssignment(exp));
        
          //cout<<"EXP: "<<exp->unparseToString()<<", lhs:"<<lhs->unparseToString()<<" :: "<<endl;
          // read-set
          RoseAst rhsast(rhs);
          for(RoseAst::iterator j=rhsast.begin();j!=rhsast.end();++j) {
            if(SgPntrArrRefExp* useRef=isSgPntrArrRefExp(*j)) {
              j.skipChildrenOnForward();
              ArrayElementAccessData access(useRef,variableIdMapping);
              indexToReadWriteDataMap[index].readArrayAccessSet.insert(access);
            } else if(SgVarRefExp* useRef=isSgVarRefExp(*j)) {
              ROSE_ASSERT(useRef);
              j.skipChildrenOnForward();
              VariableId varId=variableIdMapping->variableId(useRef);
              indexToReadWriteDataMap[index].readVarIdSet.insert(varId);
            } else {
              //cout<<"INFO: UpdateExtraction: ignored expression on rhs:"<<(*j)->unparseToString()<<endl;
            }
          }
          if(SgPntrArrRefExp* arr=isSgPntrArrRefExp(lhs)) {
            ArrayElementAccessData access(arr,variableIdMapping);
            indexToReadWriteDataMap[index].writeArrayAccessSet.insert(access);
          } else if(SgVarRefExp* var=isSgVarRefExp(lhs)) {
            VariableId varId=variableIdMapping->variableId(var);
            indexToReadWriteDataMap[index].writeVarIdSet.insert(varId);
          } else {
            cerr<<"Error: SSA Numbering: unknown LHS."<<endl;
            exit(1);
          }
        
          ss<<"UPD"<<cnt<<":"<<pstate->toString(variableIdMapping)<<" : "<<exp->unparseToString()<<endl;
          ++cnt;
        }
      } // array sequence iter

      // to be utilized later for more detailed output
#if 0
      for(IndexToReadWriteDataMap::iterator imap=indexToReadWriteDataMap.begin();
          imap!=indexToReadWriteDataMap.end();
          ++imap) {
        //        cout<<"DEBUG: INDEX: "<<(*imap).first<<" R-SET: ";
        IndexVector index=(*imap).first;

        cout<<"DEBUG: INDEX: ";
        for(IndexVector::iterator iv=index.begin();iv!=index.end();++iv) {
          if(iv!=index.begin())
//.........这里部分代码省略.........

//.........这里部分代码省略.........
    tin.inlineFunctions(root);
    DeadCodeElimination dce;
    // eliminate non called functions
    int numEliminatedFunctions=dce.eliminateNonCalledTrivialFunctions(root);
    cout<<"STATUS: eliminated "<<numEliminatedFunctions<<" functions."<<endl;
  } else {
    cout<<"INFO: Inlining: turned off."<<endl;
  }

  if(boolOptions["eliminate-empty-if"]) {
    DeadCodeElimination dce;
    cout<<"STATUS: Eliminating empty if-statements."<<endl;
    size_t num=0;
    size_t numTotal=num;
    do {
      num=dce.eliminateEmptyIfStmts(root);
      cout<<"INFO: Number of if-statements eliminated: "<<num<<endl;
      numTotal+=num;
    } while(num>0);
    cout<<"STATUS: Total number of empty if-statements eliminated: "<<numTotal<<endl;
  }

  if(boolOptions["normalize"]) {
    cout <<"STATUS: Normalization started."<<endl;
    RewriteSystem rewriteSystem;
    rewriteSystem.resetStatistics();
    rewriteSystem.rewriteCompoundAssignmentsInAst(root,&variableIdMapping);
    cout <<"STATUS: Normalization finished."<<endl;

  }
 
  cout<<"STATUS: performing flow-insensitive const analysis."<<endl;
  VarConstSetMap varConstSetMap;
  VariableIdSet variablesOfInterest;
  FIConstAnalysis fiConstAnalysis(&variableIdMapping);
  fiConstAnalysis.setOptionMultiConstAnalysis(global_option_multiconstanalysis);
  fiConstAnalysis.setDetailedOutput(detailedOutput);
  fiConstAnalysis.runAnalysis(root, mainFunctionRoot);
  variablesOfInterest=fiConstAnalysis.determinedConstantVariables();
  cout<<"INFO: variables of interest: "<<variablesOfInterest.size()<<endl;
  if(detailedOutput)
    printResult(variableIdMapping,varConstSetMap);

  if(csvConstResultFileName) {
    VariableIdSet setOfUsedVarsInFunctions=AnalysisAbstractionLayer::usedVariablesInsideFunctions(root,&variableIdMapping);
    VariableIdSet setOfUsedVarsGlobalInit=AnalysisAbstractionLayer::usedVariablesInGlobalVariableInitializers(root,&variableIdMapping);
    VariableIdSet setOfAllUsedVars = setOfUsedVarsInFunctions;
    setOfAllUsedVars.insert(setOfUsedVarsGlobalInit.begin(), setOfUsedVarsGlobalInit.end());
    cout<<"INFO: number of used vars inside functions: "<<setOfUsedVarsInFunctions.size()<<endl;
    cout<<"INFO: number of used vars in global initializations: "<<setOfUsedVarsGlobalInit.size()<<endl;
    cout<<"INFO: number of vars inside functions or in global inititializations: "<<setOfAllUsedVars.size()<<endl;
    fiConstAnalysis.filterVariables(setOfAllUsedVars);
    fiConstAnalysis.writeCvsConstResult(variableIdMapping, string(csvConstResultFileName));
  }

  if(args.count("generate-conversion-functions")) {
    string conversionFunctionsFileName="conversionFunctions.C";
    ConversionFunctionsGenerator gen;
    set<string> varNameSet;
    std::list<SgVariableDeclaration*> globalVarDeclList=SgNodeHelper::listOfGlobalVars(root);
    for(std::list<SgVariableDeclaration*>::iterator i=globalVarDeclList.begin();i!=globalVarDeclList.end();++i) {
      SgInitializedNamePtrList& initNamePtrList=(*i)->get_variables();
      for(SgInitializedNamePtrList::iterator j=initNamePtrList.begin();j!=initNamePtrList.end();++j) {
	      SgInitializedName* initName=*j;
        if ( true || isSgArrayType(initName->get_type()) ) {  // optional filter (array variables only)
	        SgName varName=initName->get_name();

void runAnalyses(SgProject* root, Labeler* labeler, VariableIdMapping* variableIdMapping) {

  SPRAY::DFAnalysisBase::normalizeProgram(root);

  if(option_fi_constanalysis) {
    VarConstSetMap varConstSetMap;
    FIConstAnalysis fiConstAnalysis(variableIdMapping);
    fiConstAnalysis.runAnalysis(root);
    fiConstAnalysis.attachAstAttributes(labeler,"const-analysis-inout"); // not iolabeler
    if(csvConstResultFileName) {
      cout<<"INFO: generating const CSV file "<<option_prefix+csvConstResultFileName<<endl;
      fiConstAnalysis.writeCvsConstResult(*variableIdMapping, option_prefix+csvConstResultFileName);
    }
    cout << "INFO: annotating analysis results as comments."<<endl;
    AstAnnotator ara(labeler);
    ara.annotateAstAttributesAsCommentsBeforeStatements(root, "const-analysis-inout");
    ara.annotateAstAttributesAsCommentsAfterStatements(root, "const-analysis-inout");
  }

  if(option_at_analysis) {
    cout<<"STATUS: running address taken analysis."<<endl;
    cout << "STATUS: computing variable and function mappings."<<endl;
    // compute variableId mappings
    VariableIdMapping variableIdMapping;
    variableIdMapping.computeVariableSymbolMapping(root);
    // Compute function id mappings:
    FunctionIdMapping functionIdMapping;
    functionIdMapping.computeFunctionSymbolMapping(root);

    if(option_trace) {
      std::cout << std::endl << "TRACE: Variable Id Mapping:" << std::endl;
      variableIdMapping.toStream(std::cout);
      std::cout << std::endl << "TRACE: Function Id Mapping:" << std::endl;
      functionIdMapping.toStream(std::cout);
    }

    cout << "STATUS: computing address taken sets."<<endl;
    SPRAY::FIPointerAnalysis fipa(&variableIdMapping, &functionIdMapping, root);
    fipa.initialize();
    fipa.run();

    //cout << "STATUS: computed address taken sets:"<<endl;
    //fipa.getFIPointerInfo()->printInfoSets();

    bool createCsv = false;
    ofstream addressTakenCsvFile;
    if(csvAddressTakenResultFileName) {
      std::string addressTakenCsvFileName = option_prefix;
      addressTakenCsvFileName += csvAddressTakenResultFileName;
      addressTakenCsvFile.open(addressTakenCsvFileName.c_str());
      createCsv = true;
    }

    cout << "INFO: annotating declarations of address taken variables and functions."<<endl;

    // Annotate declarations/definitions of variables from which the address was taken:
    VariableIdSet addressTakenVariableIds = fipa.getAddressTakenVariables();
    for(VariableIdSet::const_iterator idIter = addressTakenVariableIds.begin(); idIter != addressTakenVariableIds.end(); ++idIter) {
      // Determine the variable declaration/definition:
      SgLocatedNode* decl = variableIdMapping.getVariableDeclaration(*idIter);
      if(!decl) {
        // The current variable is presumably a function parameter: Try to get the initialized name:
        SgVariableSymbol* varSymbol = isSgVariableSymbol(variableIdMapping.getSymbol(*idIter));
        ROSE_ASSERT(varSymbol);
        SgInitializedName* paramDecl = isSgInitializedName(varSymbol->get_declaration());
        // We should not have a real variable declaration for the parameter:
        ROSE_ASSERT(isSgFunctionParameterList(paramDecl->get_declaration()));

        // Use the InitializedName:
        decl = paramDecl;
      }

      if(decl) {
        // Create the comment:
        ostringstream commentStream;
        commentStream << "/* Address of \"" << variableIdMapping.variableName(*idIter) << "\" is "
                      << "presumably taken.*/";

        // Annotate first declaration:
        insertComment(commentStream.str(), PreprocessingInfo::before, decl);
        // TODO: Annotate other declarations too!

        // Annotate definition if available (e.g. not available in case of parameter):
        if(SgDeclarationStatement* variableDeclaration = isSgDeclarationStatement(decl)) {
          if(SgDeclarationStatement* definingDeclaration = variableDeclaration->get_definingDeclaration()) {
            insertComment(commentStream.str(), PreprocessingInfo::before, definingDeclaration);
          }
        }

        if(createCsv) {
          // Write variable info to csv:
          addressTakenCsvFile << VariableId::idKindIndicator << ","
                              // The id of the variable (id codes are influenced by the used system headers
                              //  and are therefore not stable/portable):
                              << (option_csv_stable ? string("<unstable>") : int_to_string((*idIter).getIdCode())) << ","
                              // Name of the variable:
                              << variableIdMapping.variableName(*idIter) << ","

                              // TODO: Mangled scope and type are currently not stable/portable
                              //  (see comments in getScopeAsMangledStableString(...))
//.........这里部分代码省略.........