SVFUtil.h

Go to the documentation of this file.

//===- SVFUtil.h -- Analysis helper functions----------------------------//
//
//                     SVF: Static Value-Flow Analysis
//
// Copyright (C) <2013-2017>  <Yulei Sui>
//
 
// This program is free software: you can redistribute it and/or modify
// it under the terms of the GNU Affero General Public License as published by
// the Free Software Foundation, either version 3 of the License, or
// (at your option) any later version.
 
// This program is distributed in the hope that it will be useful,
// but WITHOUT ANY WARRANTY; without even the implied warranty of
// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
// GNU Affero General Public License for more details.
 
// You should have received a copy of the GNU Affero General Public License
// along with this program.  If not, see <http://www.gnu.org/licenses/>.
//
//===----------------------------------------------------------------------===//
 
/*
 * SVFUtil.h
 *
 *  Created on: Apr 11, 2013
 *      Author: Yulei Sui, dye
 */
 
#ifndef AnalysisUtil_H_
#define AnalysisUtil_H_
 
#include "FastCluster/fastcluster.h"
#include "SVFIR/SVFValue.h"
#include "Util/SVFLoopAndDomInfo.h"
#include "Util/ExtAPI.h"
#include "MemoryModel/PointsTo.h"
#include <time.h>
#include "Util/NodeIDAllocator.h"
#include "Util/ThreadAPI.h"
 
namespace SVF
{
 
/*
 * Util class to assist pointer analysis
 */
namespace SVFUtil
{
 
inline std::ostream &outs()
{
    return std::cout;
}
 
inline std::ostream  &errs()
{
    return std::cerr;
}
 
void dumpSet(NodeBS To, OutStream & O = SVFUtil::outs());
void dumpSet(PointsTo To, OutStream & O = SVFUtil::outs());
 
void dumpPointsToSet(unsigned node, NodeBS To) ;
void dumpSparseSet(const NodeBS& To);
 
void dumpAliasSet(unsigned node, NodeBS To) ;
 
std::string sucMsg(const std::string& msg);
 
std::string wrnMsg(const std::string& msg);
 
void writeWrnMsg(const std::string& msg);
 
 
std::string  errMsg(const std::string& msg);
std::string  bugMsg1(const std::string& msg);
std::string  bugMsg2(const std::string& msg);
std::string  bugMsg3(const std::string& msg);
 
std::string  pasMsg(const std::string& msg);
 
void reportMemoryUsageKB(const std::string& infor,
                         OutStream& O = SVFUtil::outs());
 
bool getMemoryUsageKB(u32_t* vmrss_kb, u32_t* vmsize_kb);
 
void increaseStackSize();
 
inline bool cmpPts (const PointsTo& lpts,const PointsTo& rpts)
{
    if (lpts.count() != rpts.count())
        return (lpts.count() < rpts.count());
    else
    {
        PointsTo::iterator bit = lpts.begin(), eit = lpts.end();
        PointsTo::iterator rbit = rpts.begin(), reit = rpts.end();
        for (; bit != eit && rbit != reit; bit++, rbit++)
        {
            if (*bit != *rbit)
                return (*bit < *rbit);
        }
 
        return false;
    }
}
 
inline bool cmpNodeBS(const NodeBS& lpts,const NodeBS& rpts)
{
    if (lpts.count() != rpts.count())
        return (lpts.count() < rpts.count());
    else
    {
        NodeBS::iterator bit = lpts.begin(), eit = lpts.end();
        NodeBS::iterator rbit = rpts.begin(), reit = rpts.end();
        for (; bit != eit && rbit != reit; bit++, rbit++)
        {
            if (*bit != *rbit)
                return (*bit < *rbit);
        }
 
        return false;
    }
}
 
typedef struct equalPointsTo
{
    bool operator()(const PointsTo& lhs, const PointsTo& rhs) const
    {
        return SVFUtil::cmpPts(lhs, rhs);
    }
} equalPointsTo;
 
typedef struct equalNodeBS
{
    bool operator()(const NodeBS& lhs, const NodeBS& rhs) const
    {
        return SVFUtil::cmpNodeBS(lhs, rhs);
    }
} equalNodeBS;
 
inline NodeBS ptsToNodeBS(const PointsTo &pts)
{
    NodeBS nbs;
    for (const NodeID o : pts) nbs.set(o);
    return nbs;
}
 
typedef OrderedSet<PointsTo, equalPointsTo> PointsToList;
void dumpPointsToList(const PointsToList& ptl);
 
bool isIntrinsicInst(const ICFGNode* inst);
 
 
bool isCallSite(const ICFGNode* inst);
 
bool isRetInstNode(const ICFGNode* node);
 
 
inline bool isNonInstricCallSite(const ICFGNode* inst)
{
    if(isIntrinsicInst(inst))
        return false;
    return isCallSite(inst);
}
 
bool matchArgs(const CallICFGNode* cs, const FunObjVar* callee);
 
 
inline std::vector<std::string> split(const std::string& s, char separator)
{
    std::vector<std::string> output;
    std::string::size_type prev_pos = 0, pos = 0;
    while ((pos = s.find(separator, pos)) != std::string::npos)
    {
        std::string substring(s.substr(prev_pos, pos - prev_pos));
        if (!substring.empty())
        {
            output.push_back(substring);
        }
        prev_pos = ++pos;
    }
    std::string lastSubstring(s.substr(prev_pos, pos - prev_pos));
    if (!lastSubstring.empty())
    {
        output.push_back(lastSubstring);
    }
    return output;
}
 
template <typename Data>
void mergePtsOccMaps(Map<Data, unsigned> &to, const Map<Data, unsigned> from)
{
    for (const typename Map<Data, unsigned>::value_type &ptocc : from)
    {
        to[ptocc.first] += ptocc.second;
    }
}
 
std::string hclustMethodToString(hclust_fast_methods method);
 
template <typename Key, typename KeySet>
inline void insertKey(const Key &key, KeySet &keySet)
{
    keySet.insert(key);
}
 
inline void insertKey(const NodeID &key, NodeBS &keySet)
{
    keySet.set(key);
}
 
template <typename Key, typename KeySet>
inline void removeKey(const Key &key, KeySet &keySet)
{
    keySet.erase(key);
}
 
inline void removeKey(const NodeID &key, NodeBS &keySet)
{
    keySet.reset(key);
}
 
void timeLimitReached(int signum);
 
bool startAnalysisLimitTimer(unsigned timeLimit);
 
void stopAnalysisLimitTimer(bool limitTimerSet);
 
 
 
bool isExtCall(const FunObjVar* fun);
 
 
 
 
 
inline bool isHeapAllocExtFunViaRet(const FunObjVar* fun)
{
    return fun && (ExtAPI::getExtAPI()->is_alloc(fun)
                   || ExtAPI::getExtAPI()->is_realloc(fun));
}
 
inline bool isHeapAllocExtFunViaArg(const FunObjVar* fun)
{
    return fun && ExtAPI::getExtAPI()->is_arg_alloc(fun);
}
 
 
 
inline u32_t getHeapAllocHoldingArgPosition(const FunObjVar* fun)
{
    return ExtAPI::getExtAPI()->get_alloc_arg_pos(fun);
}
 
 
 
inline bool isReallocExtFun(const FunObjVar* fun)
{
    return fun && (ExtAPI::getExtAPI()->is_realloc(fun));
}
 
 
 
 
bool isProgEntryFunction(const FunObjVar*);
 
const FunObjVar* getProgFunction(const std::string& funName);
 
const FunObjVar*getProgEntryFunction();
 
 
 
bool isProgExitFunction(const FunObjVar *fun);
 
 
 
bool isArgOfUncalledFunction(const SVFVar* svfvar);
 
const ObjVar* getObjVarOfValVar(const ValVar* valVar);
 
 
inline const ValVar* getForkedFun(const CallICFGNode *inst)
{
    return ThreadAPI::getThreadAPI()->getForkedFun(inst);
}
 
 
bool isExtCall(const CallICFGNode* cs);
 
bool isExtCall(const ICFGNode* node);
 
bool isHeapAllocExtCallViaArg(const CallICFGNode* cs);
 
 
bool isHeapAllocExtCallViaRet(const CallICFGNode* cs);
 
bool isHeapAllocExtCall(const ICFGNode* cs);
 
 
u32_t getHeapAllocHoldingArgPosition(const CallICFGNode* cs);
 
bool isReallocExtCall(const CallICFGNode* cs);
 
inline bool isThreadForkCall(const CallICFGNode *inst)
{
    return ThreadAPI::getThreadAPI()->isTDFork(inst);
}
 
inline bool isThreadJoinCall(const CallICFGNode* cs)
{
    return ThreadAPI::getThreadAPI()->isTDJoin(cs);
}
 
inline bool isThreadExitCall(const CallICFGNode* cs)
{
    return ThreadAPI::getThreadAPI()->isTDExit(cs);
}
 
inline bool isLockAquireCall(const CallICFGNode* cs)
{
    return ThreadAPI::getThreadAPI()->isTDAcquire(cs);
}
 
inline bool isLockReleaseCall(const CallICFGNode* cs)
{
    return ThreadAPI::getThreadAPI()->isTDRelease(cs);
}
 
 
inline bool isBarrierWaitCall(const CallICFGNode* cs)
{
    return ThreadAPI::getThreadAPI()->isTDBarWait(cs);
}
 
 
inline const ValVar* getActualParmAtForkSite(const CallICFGNode* cs)
{
    return ThreadAPI::getThreadAPI()->getActualParmAtForkSite(cs);
}
 
 
bool isProgExitCall(const CallICFGNode* cs);
 
 
template<typename T>
constexpr typename std::remove_reference<T>::type &&
move(T &&t) noexcept
{
    return std::move(t);
}
 
template <typename... Ts> struct make_void
{
    typedef void type;
};
template <typename... Ts> using void_t = typename make_void<Ts...>::type;
 
template <typename T, typename = void> struct is_iterable : std::false_type {};
template <typename T>
struct is_iterable<T, void_t<decltype(std::begin(std::declval<T&>()) !=
                                      std::end(std::declval<T&>()))>>
: std::true_type {};
template <typename T> constexpr bool is_iterable_v = is_iterable<T>::value;
 
template <typename T> struct is_map : std::false_type {};
template <typename... Ts> struct is_map<std::map<Ts...>> : std::true_type {};
template <typename... Ts>
struct is_map<std::unordered_map<Ts...>> : std::true_type {};
template <typename... Ts> constexpr bool is_map_v = is_map<Ts...>::value;
 
template <typename T> struct is_set : std::false_type {};
template <typename... Ts> struct is_set<std::set<Ts...>> : std::true_type {};
template <typename... Ts>
struct is_set<std::unordered_set<Ts...>> : std::true_type {};
template <typename... Ts> constexpr bool is_set_v = is_set<Ts...>::value;
 
template <typename T> struct is_sequence_container : std::false_type {};
template <typename... Ts>
struct is_sequence_container<std::vector<Ts...>> : std::true_type {};
template <typename... Ts>
struct is_sequence_container<std::deque<Ts...>> : std::true_type {};
template <typename... Ts>
struct is_sequence_container<std::list<Ts...>> : std::true_type {};
template <typename... Ts>
constexpr bool is_sequence_container_v = is_sequence_container<Ts...>::value;
 
 
} // End namespace SVFUtil
 
} // End namespace SVF
 
#endif /* AnalysisUtil_H_ */