//===- SVFGOPT.h -- SVFG optimizer--------------------------------------------// // // SVF: Static Value-Flow Analysis // // Copyright (C) <2013-2017> // // 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 . // //===----------------------------------------------------------------------===// /* * @file: SVFGOPT.h * @author: yesen * @date: 20/03/2014 * @version: 1.0 * * @section LICENSE * * @section DESCRIPTION * */ #ifndef SVFGOPT_H_ #define SVFGOPT_H_ #include "Graphs/SVFG.h" #include "Util/WorkList.h" namespace SVF { /** * Optimised SVFG. * 1. FormalParam/ActualRet is converted into Phi. ActualParam/FormalRet becomes the * operands of Phi nodes created at callee/caller's entry/callsite. * 2. ActualIns/ActualOuts resides at direct call sites id removed. Sources of its incoming * edges are connected with the destinations of its outgoing edges directly. * 3. FormalIns/FormalOuts reside at the entry/exit of non-address-taken functions is * removed as ActualIn/ActualOuts. * 4. MSSAPHI nodes are removed if it have no self cycle. Otherwise depends on user option. */ class SVFGOPT : public SVFG { typedef Set SVFGNodeSet; typedef Map NodeIDToNodeIDMap; typedef FIFOWorkList WorkList; public: /// Constructor SVFGOPT(std::unique_ptr mssa, VFGK kind) : SVFG(std::move(mssa), kind) { keepAllSelfCycle = keepContextSelfCycle = keepActualOutFormalIn = false; } /// Destructor ~SVFGOPT() override = default; inline void setTokeepActualOutFormalIn() { keepActualOutFormalIn = true; } inline void setTokeepAllSelfCycle() { keepAllSelfCycle = true; } inline void setTokeepContextSelfCycle() { keepContextSelfCycle = true; } /// Optimised SVFG's aren't written in their optimised form; read full SVFG and optimise it void readAndOptSVFG(const std::string &filename); /// Optimised SVFG's shouldn't be written in their optimised form; writes the full SVFG to file before optimising void buildAndWriteSVFG(const std::string &filename); protected: void buildSVFG() override; /// Separate optimisation function to avoid duplicate code void optimiseSVFG(); /// Connect SVFG nodes between caller and callee for indirect call sites //@{ inline void connectAParamAndFParam(const ValVar* cs_arg, const ValVar* fun_arg, const CallICFGNode*, CallSiteID csId, SVFGEdgeSetTy& edges) override { NodeID phiId = getDef(fun_arg); SVFGEdge* edge = addCallEdge(getDef(cs_arg), phiId, csId); if (edge != nullptr) { PHISVFGNode* phi = SVFUtil::cast(getSVFGNode(phiId)); addInterPHIOperands(phi, cs_arg); edges.insert(edge); } } /// Connect formal-ret and actual ret inline void connectFRetAndARet(const ValVar* fun_ret, const ValVar* cs_ret, CallSiteID csId, SVFGEdgeSetTy& edges) override { NodeID phiId = getDef(cs_ret); NodeID retdef = getDef(fun_ret); /// If a function does not have any return instruction. The def of a FormalRetVFGNode is itself (see VFG.h: addFormalRetVFGNode). /// Therefore, we do not connect return edge from a function without any return instruction (i.e., pag->isPhiNode(fun_ret)==false) /// because unique fun_ret SVFVar was not collected as a PhiNode in SVFIRBuilder::visitReturnInst if (pag->isPhiNode(fun_ret)==false) return; SVFGEdge* edge = addRetEdge(retdef, phiId, csId); if (edge != nullptr) { PHISVFGNode* phi = SVFUtil::cast(getSVFGNode(phiId)); addInterPHIOperands(phi, fun_ret); edges.insert(edge); } } /// Connect actual-in and formal-in inline void connectAInAndFIn(const ActualINSVFGNode* actualIn, const FormalINSVFGNode* formalIn, CallSiteID csId, SVFGEdgeSetTy& edges) override { NodeBS intersection = actualIn->getPointsTo(); intersection &= formalIn->getPointsTo(); if (intersection.empty() == false) { NodeID aiDef = getActualINDef(actualIn->getId()); SVFGEdge* edge = addCallIndirectSVFGEdge(aiDef,formalIn->getId(),csId,intersection); if (edge != nullptr) edges.insert(edge); } } /// Connect formal-out and actual-out inline void connectFOutAndAOut(const FormalOUTSVFGNode* formalOut, const ActualOUTSVFGNode* actualOut, CallSiteID csId, SVFGEdgeSetTy& edges) override { NodeBS intersection = formalOut->getPointsTo(); intersection &= actualOut->getPointsTo(); if (intersection.empty() == false) { NodeID foDef = getFormalOUTDef(formalOut->getId()); SVFGEdge* edge = addRetIndirectSVFGEdge(foDef,actualOut->getId(),csId,intersection); if (edge != nullptr) edges.insert(edge); } } //@} /// Get def-site of actual-in/formal-out. //@{ inline NodeID getActualINDef(NodeID ai) const { NodeIDToNodeIDMap::const_iterator it = actualInToDefMap.find(ai); assert(it != actualInToDefMap.end() && "can not find actual-in's def"); return it->second; } inline NodeID getFormalOUTDef(NodeID fo) const { NodeIDToNodeIDMap::const_iterator it = formalOutToDefMap.find(fo); assert(it != formalOutToDefMap.end() && "can not find formal-out's def"); return it->second; } //@} private: void parseSelfCycleHandleOption(); /// Add inter-procedural value flow edge //@{ /// Add indirect call edge from src to dst with one call site ID. SVFGEdge* addCallIndirectSVFGEdge(NodeID srcId, NodeID dstId, CallSiteID csid, const NodeBS& cpts); /// Add indirect ret edge from src to dst with one call site ID. SVFGEdge* addRetIndirectSVFGEdge(NodeID srcId, NodeID dstId, CallSiteID csid, const NodeBS& cpts); //@} /// 1. Convert FormalParmSVFGNode into PHISVFGNode and add all ActualParmSVFGNoe which may /// propagate pts to it as phi's operands. /// 2. Do the same thing for ActualRetSVFGNode and FormalRetSVFGNode. /// 3. Record def site of ActualINSVFGNode. Remove all its edges and connect its predecessors /// and successors. /// 4. Do the same thing for FormalOUTSVFGNode as 3. /// 5. Remove ActualINSVFGNode/FormalINSVFGNode/ActualOUTSVFGNode/FormalOUTSVFGNode if they /// will not be used when updating call graph. void handleInterValueFlow(); /// Replace FormalParam/ActualRet node with PHI node. //@{ void replaceFParamARetWithPHI(PHISVFGNode* phi, SVFGNode* svfgNode); //@} /// Retarget edges related to actual-in/-out and formal-in/-out. //@{ /// Record def sites of actual-in/formal-out and connect from those def-sites /// to formal-in/actual-out directly if they exist. void retargetEdgesOfAInFOut(SVFGNode* node); /// Connect actual-out/formal-in's predecessors to their successors directly. void retargetEdgesOfAOutFIn(SVFGNode* node); //@} /// Remove MSSAPHI SVFG nodes. void handleIntraValueFlow(); /// Initial work list with MSSAPHI nodes which may be removed. inline void initialWorkList() { for (SVFG::const_iterator it = begin(), eit = end(); it != eit; ++it) addIntoWorklist(it->second); } /// Only MSSAPHI node which satisfy following conditions will be removed: /// 1. it's not def-site of actual-in/formal-out; /// 2. it doesn't have incoming and outgoing call/ret at the same time. inline bool addIntoWorklist(const SVFGNode* node) { if (const MSSAPHISVFGNode* phi = SVFUtil::dyn_cast(node)) { if (isConnectingTwoCallSites(phi) == false && isDefOfAInFOut(phi) == false) return worklist.push(phi); } return false; } /// Remove MSSAPHI node if possible void bypassMSSAPHINode(const MSSAPHISVFGNode* node); /// Remove self cycle edges if needed. Return TRUE if some self cycle edges remained. bool checkSelfCycleEdges(const MSSAPHISVFGNode* node); /// Add new SVFG edge from src to dst. bool addNewSVFGEdge(NodeID srcId, NodeID dstId, const SVFGEdge* preEdge, const SVFGEdge* succEdge); /// Return TRUE if both edges are indirect call/ret edges. inline bool bothInterEdges(const SVFGEdge* edge1, const SVFGEdge* edge2) const { bool inter1 = SVFUtil::isa(edge1); bool inter2 = SVFUtil::isa(edge2); return (inter1 && inter2); } inline void addInterPHIOperands(PHISVFGNode* phi, const ValVar* operand) { phi->setOpVer(phi->getOpVerNum(), operand); } /// Add inter PHI SVFG node for formal parameter inline InterPHISVFGNode* addInterPHIForFP(const FormalParmSVFGNode* fp) { InterPHISVFGNode* sNode = new InterPHISVFGNode(totalVFGNode++,fp); addSVFGNode(sNode, pag->getICFG()->getFunEntryICFGNode(fp->getFun())); resetDef(fp->getParam(),sNode); return sNode; } /// Add inter PHI SVFG node for actual return inline InterPHISVFGNode* addInterPHIForAR(const ActualRetSVFGNode* ar) { InterPHISVFGNode* sNode = new InterPHISVFGNode(totalVFGNode++,ar); addSVFGNode(sNode, const_cast( ar->getCallSite()->getRetICFGNode())); resetDef(ar->getRev(),sNode); return sNode; } inline void resetDef(const ValVar* valVar, const SVFGNode* node) { ValVarToDefMapTy::iterator it = ValVarToDefMap.find(valVar); assert(it != ValVarToDefMap.end() && "a SVFIR node doesn't have definition before"); it->second = node->getId(); } /// Set def-site of actual-in/formal-out. ///@{ inline void setActualINDef(NodeID ai, NodeID def) { bool inserted = actualInToDefMap.emplace(ai, def).second; (void)inserted; // Suppress warning of unused variable under release build assert(inserted && "can not set actual-in's def twice"); defNodes.set(def); } inline void setFormalOUTDef(NodeID fo, NodeID def) { bool inserted = formalOutToDefMap.emplace(fo, def).second; (void) inserted; assert(inserted && "can not set formal-out's def twice"); defNodes.set(def); } ///@} inline bool isDefOfAInFOut(const SVFGNode* node) { return defNodes.test(node->getId()); } /// Check if actual-in/actual-out exist at indirect call site. //@{ inline bool actualInOfIndCS(const ActualINSVFGNode* ai) const { return (SVFIR::getPAG()->isIndirectCallSites(ai->getCallSite())); } inline bool actualOutOfIndCS(const ActualOUTSVFGNode* ao) const { return (SVFIR::getPAG()->isIndirectCallSites(ao->getCallSite())); } //@} /// Check if formal-in/formal-out reside in address-taken function. //@{ inline bool formalInOfAddressTakenFunc(const FormalINSVFGNode* fi) const { return (fi->getFun()->hasAddressTaken()); } inline bool formalOutOfAddressTakenFunc(const FormalOUTSVFGNode* fo) const { return (fo->getFun()->hasAddressTaken()); } //@} /// Return TRUE if this node has both incoming call/ret and outgoing call/ret edges. bool isConnectingTwoCallSites(const SVFGNode* node) const; /// Return TRUE if this SVFGNode can be removed. /// Nodes can be removed if it is: /// 1. ActualParam/FormalParam/ActualRet/FormalRet /// 2. ActualIN if it doesn't reside at indirect call site /// 3. FormalIN if it doesn't reside at the entry of address-taken function and it's not /// definition site of ActualIN /// 4. ActualOUT if it doesn't reside at indirect call site and it's not definition site /// of FormalOUT /// 5. FormalOUT if it doesn't reside at the exit of address-taken function bool canBeRemoved(const SVFGNode * node); /// Remove edges of a SVFG node //@{ inline void removeAllEdges(const SVFGNode* node) { removeInEdges(node); removeOutEdges(node); } inline void removeInEdges(const SVFGNode* node) { /// remove incoming edges while (node->hasIncomingEdge()) removeSVFGEdge(*(node->InEdgeBegin())); } inline void removeOutEdges(const SVFGNode* node) { while (node->hasOutgoingEdge()) removeSVFGEdge(*(node->OutEdgeBegin())); } //@} NodeIDToNodeIDMap actualInToDefMap; ///< map actual-in to its def-site node NodeIDToNodeIDMap formalOutToDefMap; ///< map formal-out to its def-site node NodeBS defNodes; ///< preserved def nodes of formal-in/actual-out WorkList worklist; ///< storing MSSAPHI nodes which may be removed. bool keepActualOutFormalIn; bool keepAllSelfCycle; bool keepContextSelfCycle; }; } // End namespace SVF #endif /* SVFGOPT_H_ */