75 assert(
false &&
"NodeIDAllocator::allocateObjectId: unimplemented node allocation strategy.");
80 assert(
id != 0 &&
"NodeIDAllocator::allocateObjectId: ID not allocated");
114 NodeID gepMultiplier = pow(10, ceil(log10(
118 id = (
offset + 1) * gepMultiplier + base;
119 assert(
id >
numSymbols &&
"NodeIDAllocator::allocateGepObjectId: GEP allocation clashing with other nodes");
123 assert(
false &&
"NodeIDAllocator::allocateGepObjectId: unimplemented node allocation strategy");
128 assert(
id != 0 &&
"NodeIDAllocator::allocateGepObjectId: ID not allocated");
157 assert(
false &&
"NodeIDAllocator::allocateValueId: unimplemented node allocation strategy");
163 assert(
id != 0 &&
"NodeIDAllocator::allocateValueId: ID not allocated");
193 const std::vector<std::pair<NodeID, unsigned>> keys,
195 std::string evalSubtitle,
199 assert(pta !=
nullptr &&
"Clusterer::cluster: given null BVDataPTAImpl");
203 double fastClusterTime = 0.0;
204 double distanceMatrixTime = 0.0;
205 double dendrogramTraversalTime = 0.0;
206 double regioningTime = 0.0;
207 double evalTime = 0.0;
219 for (
const std::pair<NodeID, unsigned> &keyOcc : keys)
222 const size_t oldSize = pointsToSets.size();
223 pointsToSets[pts] += keyOcc.second;;
227 if (oldSize != pointsToSets.size())
230 Set<NodeID> &firstOsNeighbours = coPointeeGraph[firstO];
231 for (
const NodeID o : pts)
235 firstOsNeighbours.insert(o);
236 coPointeeGraph[o].insert(firstO);
245 size_t numRegions = 0;
246 std::vector<unsigned> objectsRegion;
254 objectsRegion.insert(objectsRegion.end(),
numObjects, 0);
263 std::vector<OrderedSet<NodeID>> regionsObjects(numRegions);
264 for (
NodeID o = 0; o <
numObjects; ++o) regionsObjects[objectsRegion[o]].insert(o);
272 std::vector<std::vector<NodeID>> regionMappings(numRegions);
274 std::vector<Map<NodeID, unsigned>> regionReverseMappings(numRegions);
276 for (
unsigned region = 0; region < numRegions; ++region)
280 for (
NodeID o : regionsObjects[region])
283 regionMappings[region].push_back(o);
284 regionReverseMappings[region][o] = curr++;
299 std::vector<std::vector<std::pair<const PointsTo *, unsigned>>> regionsPointsTos(numRegions);
303 const unsigned occ = ptocc.second;
304 if (pt.
empty())
continue;
307 unsigned region = objectsRegion[*(pt.
begin())];
310 regionsPointsTos[region].push_back(std::make_pair(&pt, occ));
316 overallStats[
NumRegions] = std::to_string(numRegions);
318 std::vector<hclust_fast_methods> methods;
332 std::vector<NodeID> nodeMap(
numObjects, UINT_MAX);
334 unsigned numGtIntRegions = 0;
335 unsigned largestRegion = 0;
336 unsigned nonTrivialRegionObjects = 0;
337 unsigned allocCounter = 0;
338 for (
unsigned region = 0; region < numRegions; ++region)
340 const size_t regionNumObjects = regionsObjects[region].size();
349 if (regionNumObjects > largestRegion) largestRegion = regionNumObjects;
355 for (
NodeID o : regionsObjects[region]) nodeMap[o] = allocCounter++;
360 nonTrivialRegionObjects += regionNumObjects;
362 double *distMatrix =
getDistanceMatrix(regionsPointsTos[region], regionNumObjects,
363 regionReverseMappings[region], distanceMatrixTime);
366 int *dendrogram =
new int[2 * (regionNumObjects - 1)];
367 double *height =
new double[regionNumObjects - 1];
368 hclust_fast(regionNumObjects, distMatrix, method, dendrogram, height);
377 visited, regionNumObjects - 1, regionMappings[region]);
380 dendrogramTraversalTime += (clkEnd - clkStart) /
TIMEINTERVAL;
383 candidates.push_back(std::make_pair(method, nodeMap));
392 std::pair<hclust_fast_methods, std::vector<NodeID>> bestMapping =
398 overallStats[
EvalTime] = std::to_string(evalTime);
399 overallStats[
TotalTime] = std::to_string(distanceMatrixTime + dendrogramTraversalTime + fastClusterTime + regioningTime + evalTime);
404 printStats(evalSubtitle +
": overall", overallStats);
407 return bestMapping.second;
413 std::vector<NodeID> reverseNodeMapping(nodeMapping.size(), UINT_MAX);
414 for (
size_t i = 0; i < nodeMapping.size(); ++i)
416 const NodeID mapsTo = nodeMapping.at(i);
417 if (mapsTo >= reverseNodeMapping.size()) reverseNodeMapping.resize(mapsTo + 1, UINT_MAX);
418 reverseNodeMapping.at(mapsTo) = i;
421 return reverseNodeMapping;
427 return n*(
n-1)/2 - (
n-i)*(
n-i-1)/2 + j - i - 1;
437 if (
n == 0)
return 0;
445 double &distanceMatrixTime)
449 double *distMatrix =
new double[condensedSize];
455 double occurrenceEpsilon = 0.0001;
457 for (
const std::pair<const PointsTo *, unsigned> &ptsOcc : pointsToSets)
460 assert(pts !=
nullptr);
461 const unsigned occ = ptsOcc.second;
467 std::vector<NodeID> ptsVec;
468 for (
const NodeID o : *pts) ptsVec.push_back(o);
469 for (
size_t i = 0; i < ptsVec.size(); ++i)
471 const NodeID oi = ptsVec[i];
473 assert(moi != nodeMap.end());
474 for (
size_t j = i + 1; j < ptsVec.size(); ++j)
476 const NodeID oj = ptsVec[j];
478 assert(moj != nodeMap.end());
483 if (distance < existingDistance) existingDistance = distance - occurrenceEpsilon;
485 if (distance == std::ceil(existingDistance))
493 if (existingDistance - occ * occurrenceEpsilon > std::floor(existingDistance))
495 existingDistance -= occ * occurrenceEpsilon;
500 existingDistance = std::floor(existingDistance) + occurrenceEpsilon;
509 distanceMatrixTime += (clkEnd - clkStart) /
TIMEINTERVAL;
516 if (visited.find(
index) != visited.end())
return;
517 visited.insert(
index);
519 int left = dendrogram[
index - 1];
524 nodeMap[regionNodeMap[std::abs(left) - 1]] = allocCounter;
536 nodeMap[regionNodeMap[std::abs(right) - 1]] = allocCounter;
547 unsigned label = UINT_MAX;
548 std::vector<NodeID> labels(
numObjects, UINT_MAX);
552 const NodeID o = oos.first;
553 if (labels[o] != UINT_MAX)
continue;
554 std::queue<NodeID> bfsQueue;
557 while (!bfsQueue.empty())
559 const NodeID o = bfsQueue.front();
561 if (labels[o] != UINT_MAX)
563 assert(labels[o] == label);
569 assert(neighboursIt != graph.end());
570 for (
const NodeID neighbour : neighboursIt->second) bfsQueue.push(neighbour);
577 if (labels[o] == UINT_MAX) labels[o] = ++label;
580 numLabels = label + 1;
587 u64_t totalTheoretical = 0;
588 u64_t totalOriginalSbv = 0;
589 u64_t totalOriginalBv = 0;
590 u64_t totalNewSbv = 0;
591 u64_t totalNewBv = 0;
596 const unsigned occ = ptsOcc.second;
597 if (pts.
count() == 0)
continue;
600 if (accountForOcc) theoretical *= occ;
605 for (
const NodeID o : pts) words.insert(o / 128);
606 u64_t originalSbv = words.size() * 2;
607 if (accountForOcc) originalSbv *= occ;
614 if (o < min) min = o;
615 if (o > max) max = o;
622 u64_t originalBv = words.size();
623 if (accountForOcc) originalBv *= occ;
628 for (
const NodeID o : pts) words.insert(nodeMap[o] / 128);
629 u64_t newSbv = words.size() * 2;
630 if (accountForOcc) newSbv *= occ;
635 for (
const NodeID o : pts)
637 const NodeID mappedO = nodeMap[o];
638 if (mappedO < min) min = mappedO;
639 if (mappedO > max) max = mappedO;
645 u64_t newBv = words.size();
646 if (accountForOcc) newBv *= occ;
648 totalTheoretical += theoretical;
649 totalOriginalSbv += originalSbv;
650 totalOriginalBv += originalBv;
651 totalNewSbv += newSbv;
666 const std::string &evalSubtitle,
672 std::pair<hclust_fast_methods, std::vector<NodeID>> bestMapping = candidates[0];
674 size_t bestWords = std::numeric_limits<size_t>::max();
682 std::vector<NodeID> candidateMapping = candidate.second;
686 evaluate(candidateMapping, pointsToSets, candidateStats,
true);
691 printStats(evalSubtitle +
": candidate " + candidateMethodName, candidateStats);
694 size_t candidateWords = 0;
697 else assert(
false &&
"Clusterer::cluster: unsupported BV type for clustering.");
699 if (candidateWords < bestWords)
701 bestWords = candidateWords;
702 bestMapping = candidate;
713 static const std::string statKeys[] =
722 const unsigned fieldWidth = 20;
724 SVFUtil::outs() <<
"****Clusterer Statistics: " << subtitle <<
"****\n";
725 for (
const std::string& statKey : statKeys)
728 if (stat != stats.end())
730 SVFUtil::outs() << std::setw(fieldWidth) << statKey <<
" " << stat->second <<
"\n";
#define NATIVE_INT_SIZE
Size of native integer that we'll use for bit vectors, in bits.
const PointsTo & getPts(NodeID id) override
static const std::string DistanceMatrixTime
static const std::string LargestRegion
static const std::string NumNonTrivialRegionObjects
static const std::string EvalTime
static std::vector< unsigned > regionObjects(const Map< NodeID, Set< NodeID > > &graph, size_t numObjects, size_t &numLabels)
static const std::string TheoreticalNumWords
static const std::string BestCandidate
static std::vector< NodeID > getReverseNodeMapping(const std::vector< NodeID > &nodeMapping)
static std::pair< hclust_fast_methods, std::vector< NodeID > > determineBestMapping(const std::vector< std::pair< hclust_fast_methods, std::vector< NodeID > > > &candidates, Map< PointsTo, unsigned > pointsToSets, const std::string &evalSubtitle, double &evalTime, bool printStat)
static const std::string OriginalSbvNumWords
static const std::string DendrogramTraversalTime
static const std::string NewSbvNumWords
static double * getDistanceMatrix(const std::vector< std::pair< const PointsTo *, unsigned > > pointsToSets, const size_t numObjects, const Map< NodeID, unsigned > &nodeMap, double &distanceMatrixTime)
static unsigned requiredBits(const PointsTo &pts)
Returns the minimum number of bits required to represent pts in a perfect world.
static std::vector< NodeID > cluster(BVDataPTAImpl *pta, const std::vector< std::pair< NodeID, unsigned > > keys, std::vector< std::pair< hclust_fast_methods, std::vector< NodeID > > > &candidates, std::string evalSubtitle="", bool printStat=true)
static void traverseDendrogram(std::vector< NodeID > &nodeMap, const int *dendrogram, const size_t numObjects, unsigned &allocCounter, Set< int > &visited, const int index, const std::vector< NodeID > ®ionNodeMap)
static void printStats(std::string title, Map< std::string, std::string > &stats)
static const std::string NumRegions
static size_t condensedIndex(size_t n, size_t i, size_t j)
static void evaluate(const std::vector< NodeID > &nodeMap, const Map< PointsTo, unsigned > pointsToSets, Map< std::string, std::string > &stats, bool accountForOcc)
Fills in *NumWords statistics in stats..
static const std::string RegioningTime
static const std::string NumGtIntRegions
static const std::string FastClusterTime
static const std::string OriginalBvNumWords
static const std::string NewBvNumWords
static const std::string NumObjects
static const std::string TotalTime
NodeID numValues
Number of values allocated, including specials.
static const NodeID nullPointerId
NodeID allocateValueId(void)
Allocate a value ID as determined by the strategy.
static NodeIDAllocator * get(void)
Return (singleton) allocator.
NodeID numSymbols
Number of explicit symbols allocated (e.g., llvm::Values), including specials.
enum Strategy strategy
Strategy to allocate with.
static const NodeID blackHolePointerId
NodeID numType
Total number of svftypes.
static NodeIDAllocator * allocator
Single allocator.
static const NodeID constantObjectId
NodeID allocateTypeId(void)
Allocate an type ID as determined by the strategy.
NodeID allocateObjectId(void)
Allocate an object ID as determined by the strategy.
static const NodeID blackHoleObjectId
@ SEQ
Allocate objects objects and values sequentially, intermixed.
NodeID numNodes
Total number of objects and values allocated.
NodeID endSymbolAllocation(void)
Notify the allocator that all symbols have had IDs allocated.
void increaseNumOfObjAndNodes()
NodeID allocateGepObjectId(NodeID base, u32_t offset, u32_t maxFieldLimit)
NodeIDAllocator(void)
Builds a node ID allocator with the strategy specified on the command line.
static void unset(void)
Deletes the (singleton) allocator.
Carries around command line options.
static const OptionMap< SVF::NodeIDAllocator::Strategy > NodeAllocStrat
static const OptionMap< PointsTo::Type > PtType
Type of points-to set to use for all analyses.
static const Option< bool > RegionAlign
Align identifiers in each region to a word.
static const Option< bool > RegionedClustering
Cluster partitions separately.
static const OptionMap< u32_t > ClusterMethod
bool empty() const
Returns true if set is empty.
u32_t count() const
Returns number of elements.
const_iterator begin() const
static double getClk(bool mark=false)
int hclust_fast(int n, double *distmat, int method, int *merge, double *height)
std::string hclustMethodToString(hclust_fast_methods method)
Returns a string representation of a hclust method.
std::ostream & outs()
Overwrite llvm::outs().
std::unordered_set< Key, Hash, KeyEqual, Allocator > Set
std::unordered_map< Key, Value, Hash, KeyEqual, Allocator > Map