Static Value-Flow Analysis
Loading...
Searching...
No Matches
Static Public Member Functions | Private Types | Static Private Member Functions | List of all members
SVF::NodeIDAllocator::Clusterer Class Reference

#include <NodeIDAllocator.h>

Static Public Member Functions

static std::vector< NodeIDcluster (BVDataPTAImpl *pta, const std::vector< std::pair< NodeID, unsigned > > keys, std::vector< std::pair< hclust_fast_methods, std::vector< NodeID > > > &candidates, std::string evalSubtitle="")
 
static std::vector< NodeIDgetReverseNodeMapping (const std::vector< NodeID > &nodeMapping)
 
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 void printStats (std::string title, Map< std::string, std::string > &stats)
 

Private Types

typedef Map< NodePair, std::pair< unsigned, unsigned > > DistOccMap
 

Static Private Member Functions

static size_t condensedIndex (size_t n, size_t i, size_t j)
 
static unsigned requiredBits (const PointsTo &pts)
 Returns the minimum number of bits required to represent pts in a perfect world.
 
static unsigned requiredBits (const size_t n)
 Returns the minimum number of bits required to represent n items in a perfect world.
 
static doublegetDistanceMatrix (const std::vector< std::pair< const PointsTo *, unsigned > > pointsToSets, const size_t numObjects, const Map< NodeID, unsigned > &nodeMap, double &distanceMatrixTime)
 
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 > &regionNodeMap)
 
static std::vector< unsignedregionObjects (const Map< NodeID, Set< NodeID > > &graph, size_t numObjects, size_t &numLabels)
 
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)
 

Static Private Attributes

static const std::string NumObjects = "NumObjects"
 
static const std::string RegioningTime = "RegioningTime"
 
static const std::string DistanceMatrixTime = "DistanceMatrixTime"
 
static const std::string FastClusterTime = "FastClusterTime"
 
static const std::string DendrogramTraversalTime = "DendrogramTravTime"
 
static const std::string EvalTime = "EvalTime"
 
static const std::string TotalTime = "TotalTime"
 
static const std::string TheoreticalNumWords = "TheoreticalWords"
 
static const std::string OriginalBvNumWords = "OriginalBvWords"
 
static const std::string OriginalSbvNumWords = "OriginalSbvWords"
 
static const std::string NewBvNumWords = "NewBvWords"
 
static const std::string NewSbvNumWords = "NewSbvWords"
 
static const std::string NumRegions = "NumRegions"
 
static const std::string NumGtIntRegions = "NumGtIntRegions"
 
static const std::string LargestRegion = "LargestRegion"
 
static const std::string BestCandidate = "BestCandidate"
 
static const std::string NumNonTrivialRegionObjects = "NumNonTrivObj"
 

Detailed Description

Perform clustering given points-to sets with nodes allocated according to the DENSE strategy.

Definition at line 122 of file NodeIDAllocator.h.

Member Typedef Documentation

◆ DistOccMap

Maps a pair of nodes to their (minimum) distance and the number of times that distance occurs in a set of unique points-to sets.

Definition at line 127 of file NodeIDAllocator.h.

Member Function Documentation

◆ cluster()

std::vector< NodeID > SVF::NodeIDAllocator::Clusterer::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 = "" 
)
static

Returns vector mapping previously allocated node IDs to a smarter allocation based on the points-to sets in pta accessed through keys. The second part of the keys pairs are the number of (potential) occurrences of that points-to set or a subset, depending on the client's wish. TODO: interfaces are getting unwieldy, an initialised object may be better. TODO: kind of sucks pta can't be const here because getPts isn't.

Definition at line 193 of file NodeIDAllocator.cpp.

194{
195 assert(pta != nullptr && "Clusterer::cluster: given null BVDataPTAImpl");
196 assert(Options::NodeAllocStrat() == Strategy::DENSE && "Clusterer::cluster: only dense allocation clustering currently supported");
197
199 double fastClusterTime = 0.0;
200 double distanceMatrixTime = 0.0;
201 double dendrogramTraversalTime = 0.0;
202 double regioningTime = 0.0;
203 double evalTime = 0.0;
204
205 // Pair of nodes to their (minimum) distance and the number of occurrences of that distance.
206 Map<std::pair<NodeID, NodeID>, std::pair<unsigned, unsigned>> distances;
207
208 double clkStart = PTAStat::getClk(true);
209
210 // Map points-to sets to occurrences.
212
213 // Objects each object shares at least a points-to set with.
215 for (const std::pair<NodeID, unsigned> &keyOcc : keys)
216 {
217 const PointsTo &pts = pta->getPts(keyOcc.first);
218 const size_t oldSize = pointsToSets.size();
219 pointsToSets[pts] += keyOcc.second;;
220
221 // Edges in this graph have no weight or uniqueness, so we only need to
222 // do this for each points-to set once.
223 if (oldSize != pointsToSets.size())
224 {
225 NodeID firstO = !pts.empty() ? *(pts.begin()) : 0;
227 for (const NodeID o : pts)
228 {
229 if (o != firstO)
230 {
231 firstOsNeighbours.insert(o);
232 coPointeeGraph[o].insert(firstO);
233 }
234 }
235 }
236 }
237
239 overallStats[NumObjects] = std::to_string(numObjects);
240
241 size_t numRegions = 0;
242 std::vector<unsigned> objectsRegion;
244 {
246 }
247 else
248 {
249 // Just a single big region (0).
250 objectsRegion.insert(objectsRegion.end(), numObjects, 0);
251 numRegions = 1;
252 }
253
254 // Set needs to be ordered because getDistanceMatrix, in its n^2 iteration, expects
255 // sets to be ordered (we are building a condensed matrix, not a full matrix, so it
256 // matters). In getDistanceMatrix, doing regionReverseMapping for oi and oj, where
257 // oi < oj, and getting a result moi > moj gives incorrect results.
258 // In the condensed matrix, [b][a] where b >= a, is incorrect.
259 std::vector<OrderedSet<NodeID>> regionsObjects(numRegions);
260 for (NodeID o = 0; o < numObjects; ++o) regionsObjects[objectsRegion[o]].insert(o);
261
262 // Size of the return node mapping. It is potentially larger than the number of
263 // objects because we align each region to NATIVE_INT_SIZE.
264 // size_t numMappings = 0;
265
266 // Maps a region to a mapping which maps 0 to n to all objects
267 // in that region.
268 std::vector<std::vector<NodeID>> regionMappings(numRegions);
269 // The reverse: region to mapping of objects to a 0 to n from above.
270 std::vector<Map<NodeID, unsigned>> regionReverseMappings(numRegions);
271 // We can thus use 0 to n for each region to create smaller distance matrices.
272 for (unsigned region = 0; region < numRegions; ++region)
273 {
274 size_t curr = 0;
275 // With the OrderedSet above, o1 < o2 => map[o1] < map[o2].
277 {
278 // push_back here is just like p...[region][curr] = o.
279 regionMappings[region].push_back(o);
281 }
282
283 // curr is the number of objects. A region with no objects makes no sense.
284 assert(curr != 0);
285
286 // Number of bits needed for this region if we were
287 // to start assigning from 0 rounded up to the fewest needed
288 // native ints. This is added to the number of mappings since
289 // we align each region to a native int.
290 // numMappings += requiredBits(regionsObjects[region].size());
291 }
292
293 // Points-to sets which are relevant to a region, i.e., those whose elements
294 // belong to that region. Pair is for occurrences.
295 std::vector<std::vector<std::pair<const PointsTo *, unsigned>>> regionsPointsTos(numRegions);
296 for (const Map<PointsTo, unsigned>::value_type &ptocc : pointsToSets)
297 {
298 const PointsTo &pt = ptocc.first;
299 const unsigned occ = ptocc.second;
300 if (pt.empty()) continue;
301 // Guaranteed that begin() != end() because of the continue above. All objects in pt
302 // will be relevant to the same region.
303 unsigned region = objectsRegion[*(pt.begin())];
304 // In our "graph", objects in the same points-to set have an edge between them,
305 // so they are all in the same connected component/region.
306 regionsPointsTos[region].push_back(std::make_pair(&pt, occ));
307 }
308
309 double clkEnd = PTAStat::getClk(true);
311 overallStats[RegioningTime] = std::to_string(regioningTime);
312 overallStats[NumRegions] = std::to_string(numRegions);
313
314 std::vector<hclust_fast_methods> methods;
316 {
317 methods.push_back(HCLUST_METHOD_SINGLE);
320 }
321 else
322 {
324 }
325
327 {
328 std::vector<NodeID> nodeMap(numObjects, UINT_MAX);
329
330 unsigned numGtIntRegions = 0;
331 unsigned largestRegion = 0;
332 unsigned nonTrivialRegionObjects = 0;
333 unsigned allocCounter = 0;
334 for (unsigned region = 0; region < numRegions; ++region)
335 {
336 const size_t regionNumObjects = regionsObjects[region].size();
337 // Round up to next Word: ceiling of current allocation to get how
338 // many words and multiply to get the number of bits; if we're aligning.
340 {
343 }
344
346
347 // For regions with fewer than 64 objects, we can just allocate them
348 // however as they will be in the one int regardless..
350 {
352 continue;
353 }
354
357
360
362 int *dendrogram = new int[2 * (regionNumObjects - 1)];
363 double *height = new double[regionNumObjects - 1];
365 delete[] distMatrix;
366 delete[] height;
367 clkEnd = PTAStat::getClk(true);
369
371 Set<int> visited;
373 visited, regionNumObjects - 1, regionMappings[region]);
374 delete[] dendrogram;
375 clkEnd = PTAStat::getClk(true);
377 }
378
379 candidates.push_back(std::make_pair(method, nodeMap));
380
381 // Though we "update" these in the loop, they will be the same every iteration.
383 overallStats[LargestRegion] = std::to_string(largestRegion);
385 }
386
387 // Work out which of the mappings we generated looks best.
388 std::pair<hclust_fast_methods, std::vector<NodeID>> bestMapping = determineBestMapping(candidates, pointsToSets,
390
394 overallStats[EvalTime] = std::to_string(evalTime);
396
398 printStats(evalSubtitle + ": overall", overallStats);
399
400 return bestMapping.second;
401}
#define TIMEINTERVAL
Definition SVFType.h:540
#define NATIVE_INT_SIZE
Size of native integer that we'll use for bit vectors, in bits.
Definition SVFType.h:544
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 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)
static const std::string BestCandidate
static const std::string DendrogramTraversalTime
static double * getDistanceMatrix(const std::vector< std::pair< const PointsTo *, unsigned > > pointsToSets, const size_t numObjects, const Map< NodeID, unsigned > &nodeMap, double &distanceMatrixTime)
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 > &regionNodeMap)
static void printStats(std::string title, Map< std::string, std::string > &stats)
static const std::string NumRegions
static const std::string RegioningTime
static const std::string NumGtIntRegions
static const std::string FastClusterTime
static const std::string NumObjects
static const std::string TotalTime
static NodeIDAllocator * get(void)
Return (singleton) allocator.
static const OptionMap< SVF::NodeIDAllocator::Strategy > NodeAllocStrat
Definition Options.h:32
static const Option< bool > RegionAlign
Align identifiers in each region to a word.
Definition Options.h:59
static const Option< bool > RegionedClustering
Cluster partitions separately.
Definition Options.h:56
static const OptionMap< u32_t > ClusterMethod
Definition Options.h:53
static double getClk(bool mark=false)
Definition SVFStat.cpp:48
hclust_fast_methods
Definition fastcluster.h:66
@ HCLUST_METHOD_AVERAGE
Definition fastcluster.h:72
@ HCLUST_METHOD_COMPLETE
Definition fastcluster.h:70
@ HCLUST_METHOD_SVF_BEST
Definition fastcluster.h:76
@ HCLUST_METHOD_SINGLE
Definition fastcluster.h:68
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.
Definition SVFUtil.cpp:248
u32_t NodeID
Definition GeneralType.h:56
llvm::IRBuilder IRBuilder
Definition BasicTypes.h:74

◆ condensedIndex()

size_t SVF::NodeIDAllocator::Clusterer::condensedIndex ( size_t  n,
size_t  i,
size_t  j 
)
inlinestaticprivate

Returns an index into a condensed matrix (upper triangle, excluding diagonals) corresponding to an nxn matrix.

Definition at line 417 of file NodeIDAllocator.cpp.

418{
419 // From https://stackoverflow.com/a/14839010
420 return n*(n-1)/2 - (n-i)*(n-i-1)/2 + j - i - 1;
421}
cJSON * n
Definition cJSON.cpp:2558

◆ determineBestMapping()

std::pair< hclust_fast_methods, std::vector< NodeID > > SVF::NodeIDAllocator::Clusterer::determineBestMapping ( const std::vector< std::pair< hclust_fast_methods, std::vector< NodeID > > > &  candidates,
Map< PointsTo, unsigned pointsToSets,
const std::string &  evalSubtitle,
double evalTime 
)
inlinestaticprivate

Definition at line 656 of file NodeIDAllocator.cpp.

659{
660 // In case we're not comparing anything, set to first "candidate".
661 std::pair<hclust_fast_methods, std::vector<NodeID>> bestMapping = candidates[0];
662 // Number of bits required for the best candidate.
663 size_t bestWords = std::numeric_limits<size_t>::max();
665 {
666 for (const std::pair<hclust_fast_methods, std::vector<NodeID>> &candidate : candidates)
667 {
671 std::vector<NodeID> candidateMapping = candidate.second;
672
673 // TODO: parameterise final arg.
674 const double clkStart = PTAStat::getClk(true);
676 const double clkEnd = PTAStat::getClk(true);
679
680 size_t candidateWords = 0;
683 else assert(false && "Clusterer::cluster: unsupported BV type for clustering.");
684
686 {
689 }
690 }
691 }
692
693 return bestMapping;
694}
static const std::string NewSbvNumWords
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 NewBvNumWords
static const OptionMap< PointsTo::Type > PtType
Type of points-to set to use for all analyses.
Definition Options.h:47

◆ evaluate()

void SVF::NodeIDAllocator::Clusterer::evaluate ( const std::vector< NodeID > &  nodeMap,
const Map< PointsTo, unsigned pointsToSets,
Map< std::string, std::string > &  stats,
bool  accountForOcc 
)
static

Fills in *NumWords statistics in stats..

Definition at line 578 of file NodeIDAllocator.cpp.

579{
583 u64_t totalNewSbv = 0;
584 u64_t totalNewBv = 0;
585
586 for (const Map<PointsTo, unsigned>::value_type &ptsOcc : pointsToSets)
587 {
588 const PointsTo &pts = ptsOcc.first;
589 const unsigned occ = ptsOcc.second;
590 if (pts.count() == 0) continue;
591
594
595 // Check number of words for original SBV.
596 Set<unsigned> words;
597 // TODO: nasty hardcoding.
598 for (const NodeID o : pts) words.insert(o / 128);
599 u64_t originalSbv = words.size() * 2;
601
602 // Check number of words for original BV.
603 NodeID min = UINT_MAX;
604 NodeID max = 0;
605 for (NodeID o : pts)
606 {
607 if (o < min) min = o;
608 if (o > max) max = o;
609 }
610 words.clear();
611 for (NodeID b = min; b <= max; ++b)
612 {
613 words.insert(b / NATIVE_INT_SIZE);
614 }
615 u64_t originalBv = words.size();
617
618 // Check number of words for new SBV.
619 words.clear();
620 // TODO: nasty hardcoding.
621 for (const NodeID o : pts) words.insert(nodeMap[o] / 128);
622 u64_t newSbv = words.size() * 2;
623 if (accountForOcc) newSbv *= occ;
624
625 // Check number of words for new BV.
626 min = UINT_MAX;
627 max = 0;
628 for (const NodeID o : pts)
629 {
630 const NodeID mappedO = nodeMap[o];
631 if (mappedO < min) min = mappedO;
632 if (mappedO > max) max = mappedO;
633 }
634
635 words.clear();
636 // No nodeMap[b] because min and max and from nodeMap.
637 for (NodeID b = min; b <= max; ++b) words.insert(b / NATIVE_INT_SIZE);
638 u64_t newBv = words.size();
639 if (accountForOcc) newBv *= occ;
640
645 totalNewBv += newBv;
646 }
647
648 stats[TheoreticalNumWords] = std::to_string(totalTheoretical);
649 stats[OriginalSbvNumWords] = std::to_string(totalOriginalSbv);
650 stats[OriginalBvNumWords] = std::to_string(totalOriginalBv);
651 stats[NewSbvNumWords] = std::to_string(totalNewSbv);
652 stats[NewBvNumWords] = std::to_string(totalNewBv);
653}
const cJSON *const b
Definition cJSON.h:255
static const std::string TheoreticalNumWords
static const std::string OriginalSbvNumWords
static unsigned requiredBits(const PointsTo &pts)
Returns the minimum number of bits required to represent pts in a perfect world.
static const std::string OriginalBvNumWords
unsigned long long u64_t
Definition GeneralType.h:49

◆ getDistanceMatrix()

double * SVF::NodeIDAllocator::Clusterer::getDistanceMatrix ( const std::vector< std::pair< const PointsTo *, unsigned > >  pointsToSets,
const size_t  numObjects,
const Map< NodeID, unsigned > &  nodeMap,
double distanceMatrixTime 
)
inlinestaticprivate

Builds the upper triangle of the distance matrix, as an array of length (numObjects * (numObjects - 1)) / 2, as required by fastcluster. Responsibility of caller to delete.

Definition at line 436 of file NodeIDAllocator.cpp.

439{
440 const double clkStart = PTAStat::getClk(true);
441 size_t condensedSize = (numObjects * (numObjects - 1)) / 2;
442 double *distMatrix = new double[condensedSize];
443 for (size_t i = 0; i < condensedSize; ++i) distMatrix[i] = numObjects * numObjects;
444
445 // TODO: maybe use machine epsilon?
446 // For reducing distance due to extra occurrences.
447 // Can differentiate ~9999 occurrences.
448 double occurrenceEpsilon = 0.0001;
449
450 for (const std::pair<const PointsTo *, unsigned> &ptsOcc : pointsToSets)
451 {
452 const PointsTo *pts = ptsOcc.first;
453 assert(pts != nullptr);
454 const unsigned occ = ptsOcc.second;
455
456 // Distance between each element of pts.
458
459 // Use a vector so we can index into pts.
460 std::vector<NodeID> ptsVec;
461 for (const NodeID o : *pts) ptsVec.push_back(o);
462 for (size_t i = 0; i < ptsVec.size(); ++i)
463 {
464 const NodeID oi = ptsVec[i];
465 const Map<NodeID, unsigned>::const_iterator moi = nodeMap.find(oi);
466 assert(moi != nodeMap.end());
467 for (size_t j = i + 1; j < ptsVec.size(); ++j)
468 {
469 const NodeID oj = ptsVec[j];
470 const Map<NodeID, unsigned>::const_iterator moj = nodeMap.find(oj);
471 assert(moj != nodeMap.end());
472 double &existingDistance = distMatrix[condensedIndex(numObjects, moi->second, moj->second)];
473
474 // Subtract extra occurrenceEpsilon to make upcoming logic simpler.
475 // When existingDistance is never whole, it is always between two distances.
477
478 if (distance == std::ceil(existingDistance))
479 {
480 // We have something like distance == x, existingDistance == x - e, for some e < 1
481 // (potentially even set during this iteration).
482 // So, the new distance is an occurrence the existingDistance being tracked, it just
483 // had some reductions because of multiple occurrences.
484 // If there is not room within this distance to reduce more (increase priority),
485 // just ignore it. TODO: maybe warn?
487 {
489 }
490 else
491 {
492 // Reached minimum.
494 }
495 }
496 }
497 }
498
499 }
500
501 const double clkEnd = PTAStat::getClk(true);
503
504 return distMatrix;
505}
static size_t condensedIndex(size_t n, size_t i, size_t j)

◆ getReverseNodeMapping()

std::vector< NodeID > SVF::NodeIDAllocator::Clusterer::getReverseNodeMapping ( const std::vector< NodeID > &  nodeMapping)
static

Definition at line 403 of file NodeIDAllocator.cpp.

404{
405 // nodeMapping.size() may not be big enough because we leave some gaps, but it's a start.
406 std::vector<NodeID> reverseNodeMapping(nodeMapping.size(), UINT_MAX);
407 for (size_t i = 0; i < nodeMapping.size(); ++i)
408 {
409 const NodeID mapsTo = nodeMapping.at(i);
410 if (mapsTo >= reverseNodeMapping.size()) reverseNodeMapping.resize(mapsTo + 1, UINT_MAX);
411 reverseNodeMapping.at(mapsTo) = i;
412 }
413
414 return reverseNodeMapping;
415}

◆ printStats()

void SVF::NodeIDAllocator::Clusterer::printStats ( std::string  title,
Map< std::string, std::string > &  stats 
)
static

Prints statistics to SVFUtil::outs(). TODO: make stats const.

Definition at line 696 of file NodeIDAllocator.cpp.

697{
698 // When not in order, it is too hard to compare original/new SBV/BV words, so this array forces an order.
699 static const std::string statKeys[] =
700 {
706 };
707
708 const unsigned fieldWidth = 20;
709 SVFUtil::outs().flags(std::ios::left);
710 SVFUtil::outs() << "****Clusterer Statistics: " << subtitle << "****\n";
711 for (const std::string& statKey : statKeys)
712 {
713 Map<std::string, std::string>::const_iterator stat = stats.find(statKey);
714 if (stat != stats.end())
715 {
716 SVFUtil::outs() << std::setw(fieldWidth) << statKey << " " << stat->second << "\n";
717 }
718 }
719
720 SVFUtil::outs().flush();
721}
std::ostream & outs()
Overwrite llvm::outs()
Definition SVFUtil.h:52

◆ regionObjects()

std::vector< NodeID > SVF::NodeIDAllocator::Clusterer::regionObjects ( const Map< NodeID, Set< NodeID > > &  graph,
size_t  numObjects,
size_t numLabels 
)
inlinestaticprivate

Returns a vector mapping object IDs to a label such that if two objects appear in the same points-to set, they have the same label. The "appear in the same points-to set" is encoded by graph which is an adjacency list ensuring that x in pt(p) and y in pt(p) -> x is reachable from y.

Definition at line 538 of file NodeIDAllocator.cpp.

539{
540 unsigned label = UINT_MAX;
541 std::vector<NodeID> labels(numObjects, UINT_MAX);
543 for (const Map<NodeID, Set<NodeID>>::value_type &oos : graph)
544 {
545 const NodeID o = oos.first;
546 if (labels[o] != UINT_MAX) continue;
547 std::queue<NodeID> bfsQueue;
548 bfsQueue.push(o);
549 ++label;
550 while (!bfsQueue.empty())
551 {
552 const NodeID o = bfsQueue.front();
553 bfsQueue.pop();
554 if (labels[o] != UINT_MAX)
555 {
556 assert(labels[o] == label);
557 continue;
558 }
559
560 labels[o] = label;
561 Map<NodeID, Set<NodeID>>::const_iterator neighboursIt = graph.find(o);
562 assert(neighboursIt != graph.end());
564 }
565 }
566
567 // The remaining objects have no relation with others: they get their own label.
568 for (size_t o = 0; o < numObjects; ++o)
569 {
570 if (labels[o] == UINT_MAX) labels[o] = ++label;
571 }
572
573 numLabels = label + 1;
574
575 return labels;
576}
std::unordered_map< Key, Value, Hash, KeyEqual, Allocator > Map

◆ requiredBits() [1/2]

unsigned SVF::NodeIDAllocator::Clusterer::requiredBits ( const PointsTo pts)
inlinestaticprivate

Returns the minimum number of bits required to represent pts in a perfect world.

Definition at line 423 of file NodeIDAllocator.cpp.

424{
425 return requiredBits(pts.count());
426}

◆ requiredBits() [2/2]

unsigned SVF::NodeIDAllocator::Clusterer::requiredBits ( const size_t  n)
inlinestaticprivate

Returns the minimum number of bits required to represent n items in a perfect world.

Definition at line 428 of file NodeIDAllocator.cpp.

429{
430 if (n == 0) return 0;
431 // Ceiling of number of bits amongst each native integer gives needed native ints,
432 // so we then multiply again by the number of bits in each native int.
433 return ((n - 1) / NATIVE_INT_SIZE + 1) * NATIVE_INT_SIZE;
434}

◆ traverseDendrogram()

void SVF::NodeIDAllocator::Clusterer::traverseDendrogram ( std::vector< NodeID > &  nodeMap,
const int dendrogram,
const size_t  numObjects,
unsigned allocCounter,
Set< int > &  visited,
const int  index,
const std::vector< NodeID > &  regionNodeMap 
)
inlinestaticprivate

Traverses the dendrogram produced by fastcluster, making node o, where o is the nth leaf (per recursive DFS) map to n. index is the dendrogram node to work off. The traversal should start at the top, which is the "last" (consider that it is 2D) element of the dendrogram, numObjects - 1.

Definition at line 507 of file NodeIDAllocator.cpp.

508{
509 if (visited.find(index) != visited.end()) return;
510 visited.insert(index);
511
512 int left = dendrogram[index - 1];
513 if (left < 0)
514 {
515 // Reached a leaf.
516 // -1 because the items start from 1 per fastcluster (TODO).
517 nodeMap[regionNodeMap[std::abs(left) - 1]] = allocCounter;
518 ++allocCounter;
519 }
520 else
521 {
523 }
524
525 // Repeat for the right child.
526 int right = dendrogram[(numObjects - 1) + index - 1];
527 if (right < 0)
528 {
529 nodeMap[regionNodeMap[std::abs(right) - 1]] = allocCounter;
530 ++allocCounter;
531 }
532 else
533 {
535 }
536}
int index
Definition cJSON.h:170

Member Data Documentation

◆ BestCandidate

const std::string SVF::NodeIDAllocator::Clusterer::BestCandidate = "BestCandidate"
staticprivate

Definition at line 146 of file NodeIDAllocator.h.

◆ DendrogramTraversalTime

const std::string SVF::NodeIDAllocator::Clusterer::DendrogramTraversalTime = "DendrogramTravTime"
staticprivate

Definition at line 135 of file NodeIDAllocator.h.

◆ DistanceMatrixTime

const std::string SVF::NodeIDAllocator::Clusterer::DistanceMatrixTime = "DistanceMatrixTime"
staticprivate

Definition at line 133 of file NodeIDAllocator.h.

◆ EvalTime

const std::string SVF::NodeIDAllocator::Clusterer::EvalTime = "EvalTime"
staticprivate

Definition at line 136 of file NodeIDAllocator.h.

◆ FastClusterTime

const std::string SVF::NodeIDAllocator::Clusterer::FastClusterTime = "FastClusterTime"
staticprivate

Definition at line 134 of file NodeIDAllocator.h.

◆ LargestRegion

const std::string SVF::NodeIDAllocator::Clusterer::LargestRegion = "LargestRegion"
staticprivate

Definition at line 145 of file NodeIDAllocator.h.

◆ NewBvNumWords

const std::string SVF::NodeIDAllocator::Clusterer::NewBvNumWords = "NewBvWords"
staticprivate

Definition at line 141 of file NodeIDAllocator.h.

◆ NewSbvNumWords

const std::string SVF::NodeIDAllocator::Clusterer::NewSbvNumWords = "NewSbvWords"
staticprivate

Definition at line 142 of file NodeIDAllocator.h.

◆ NumGtIntRegions

const std::string SVF::NodeIDAllocator::Clusterer::NumGtIntRegions = "NumGtIntRegions"
staticprivate

Definition at line 144 of file NodeIDAllocator.h.

◆ NumNonTrivialRegionObjects

const std::string SVF::NodeIDAllocator::Clusterer::NumNonTrivialRegionObjects = "NumNonTrivObj"
staticprivate

Definition at line 147 of file NodeIDAllocator.h.

◆ NumObjects

const std::string SVF::NodeIDAllocator::Clusterer::NumObjects = "NumObjects"
staticprivate

Statistics strings.

Definition at line 131 of file NodeIDAllocator.h.

◆ NumRegions

const std::string SVF::NodeIDAllocator::Clusterer::NumRegions = "NumRegions"
staticprivate

Definition at line 143 of file NodeIDAllocator.h.

◆ OriginalBvNumWords

const std::string SVF::NodeIDAllocator::Clusterer::OriginalBvNumWords = "OriginalBvWords"
staticprivate

Definition at line 139 of file NodeIDAllocator.h.

◆ OriginalSbvNumWords

const std::string SVF::NodeIDAllocator::Clusterer::OriginalSbvNumWords = "OriginalSbvWords"
staticprivate

Definition at line 140 of file NodeIDAllocator.h.

◆ RegioningTime

const std::string SVF::NodeIDAllocator::Clusterer::RegioningTime = "RegioningTime"
staticprivate

Definition at line 132 of file NodeIDAllocator.h.

◆ TheoreticalNumWords

const std::string SVF::NodeIDAllocator::Clusterer::TheoreticalNumWords = "TheoreticalWords"
staticprivate

Definition at line 138 of file NodeIDAllocator.h.

◆ TotalTime

const std::string SVF::NodeIDAllocator::Clusterer::TotalTime = "TotalTime"
staticprivate

Definition at line 137 of file NodeIDAllocator.h.


The documentation for this class was generated from the following files: