FSMPTA.h

Go to the documentation of this file.

//===- FSMPTA.h -- Flow-sensitive multithreaded pointer analysis (FSAM) -===//
//
//                     SVF: Static Value-Flow Analysis
//
// Copyright (C) <2013->  <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/>.
//
//===----------------------------------------------------------------------===//
 
/*
 * FSMPTA.h
 *
 *      Author: Jiawei Yang
 *
 * Sparse flow-sensitive pointer analysis for multithreaded programs (FSAM,
 * Sui/Di/Xue CGO'16). It runs the sparse flow-sensitive solver
 * (`FlowSensitive`) over a *thread-aware* SVFG built by `MTASVFGBuilder`,
 * i.e. the stock thread-oblivious value flow augmented with inter-thread
 * (interference) edges derived from the MHP and lock analyses.
 */
 
#ifndef INCLUDE_MTA_FSMPTA_H_
#define INCLUDE_MTA_FSMPTA_H_
 
#include "WPA/FlowSensitive.h"
#include "Graphs/SlicedGraphs.h"
 
#include <deque>
 
namespace SVF
{
 
class AndersenBase;
class AndersenWaveDiff;
 
template<class SVFGGraph>
class FSMPTA final : public FlowSensitive
{
public:
    FSMPTA(AndersenWaveDiff& preAnalysis, SVFG& backingGraph,
           SVFGGraph solveGraph);
    ~FSMPTA() override = default;
 
    void initialize() override;
    void finalize() override;
 
    static bool supportsCurrentConfiguration();
 
    static NodeBS buildExecutionDependencyClosure(
        SVFG* graph, AndersenBase* preAnalysis, NodeBS dependencyNodes);
 
protected:
    NodeStack& SCCDetect() override;
    void processNode(NodeID nodeId) override;
    void updateConnectedNodes(const SVFGEdgeSetTy& edges) override;
 
private:
    using SolveGraphTraits = GenericGraphTraits<SVFGGraph>;
 
    static void enqueueSVFGNode(const SVFGNode* node, NodeBS& retained,
                                std::deque<NodeID>& worklist);
    static void demandTopLevelPointer(const SVFVar* var, SVFG* graph,
                                      NodeBS& demandedVars, NodeBS& retained,
                                      std::deque<NodeID>& worklist);
    static void collectNodeInputDependencies(
        const SVFGNode* node, SVFG* graph, NodeBS& demandedVars,
        NodeBS& retained, std::deque<NodeID>& worklist);
    void buildRetainedAdjacency();
    void cacheRetainedEdge(SVFGEdge* edge);
 
    AndersenWaveDiff* preAnalysis;
    SVFG* backingGraph;
    SVFGGraph solveGraph;
    std::unique_ptr<SCCDetection<SVFGGraph>> solveSCC;
    NodeStack solveNodeStack;
    Map<NodeID, std::vector<SVFGEdge*>> retainedOutEdges;
    Set<const SVFGEdge*> retainedEdgeSet;
};
 
extern template class FSMPTA<SVFG*>;
extern template class FSMPTA<const SlicedSVFGView*>;
 
} // End namespace SVF
 
#endif /* INCLUDE_MTA_FSMPTA_H_ */