1 //===- IntervalPartition.cpp - CFG Partitioning into Intervals --*- C++ -*-===// 2 // 3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. 4 // See https://llvm.org/LICENSE.txt for license information. 5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception 6 // 7 //===----------------------------------------------------------------------===// 8 // 9 // This file defines functionality for partitioning a CFG into intervals. 10 // 11 //===----------------------------------------------------------------------===// 12 13 #include "clang/Analysis/Analyses/IntervalPartition.h" 14 #include "clang/Analysis/CFG.h" 15 #include "llvm/ADT/BitVector.h" 16 #include <queue> 17 #include <set> 18 #include <vector> 19 20 namespace clang { 21 22 static CFGInterval buildInterval(llvm::BitVector &Partitioned, 23 const CFGBlock &Header) { 24 CFGInterval Interval(&Header); 25 Partitioned.set(Header.getBlockID()); 26 27 // Elements must not be null. Duplicates are prevented using `Workset`, below. 28 std::queue<const CFGBlock *> Worklist; 29 llvm::BitVector Workset(Header.getParent()->getNumBlockIDs(), false); 30 for (const CFGBlock *S : Header.succs()) 31 if (S != nullptr) 32 if (auto SID = S->getBlockID(); !Partitioned.test(SID)) { 33 // Successors are unique, so we don't test against `Workset` before 34 // adding to `Worklist`. 35 Worklist.push(S); 36 Workset.set(SID); 37 } 38 39 // Contains successors of blocks in the interval that couldn't be added to the 40 // interval on their first encounter. This occurs when they have a predecessor 41 // that is either definitively outside the interval or hasn't been considered 42 // yet. In the latter case, we'll revisit the block through some other path 43 // from the interval. At the end of processing the worklist, we filter out any 44 // that ended up in the interval to produce the output set of interval 45 // successors. It may contain duplicates -- ultimately, all relevant elements 46 // are added to `Interval.Successors`, which is a set. 47 std::vector<const CFGBlock *> MaybeSuccessors; 48 49 while (!Worklist.empty()) { 50 const auto *B = Worklist.front(); 51 auto ID = B->getBlockID(); 52 Worklist.pop(); 53 Workset.reset(ID); 54 55 // Check whether all predecessors are in the interval, in which case `B` 56 // is included as well. 57 bool AllInInterval = true; 58 for (const CFGBlock *P : B->preds()) 59 if (Interval.Blocks.find(P) == Interval.Blocks.end()) { 60 MaybeSuccessors.push_back(B); 61 AllInInterval = false; 62 break; 63 } 64 if (AllInInterval) { 65 Interval.Blocks.insert(B); 66 Partitioned.set(ID); 67 for (const CFGBlock *S : B->succs()) 68 if (S != nullptr) 69 if (auto SID = S->getBlockID(); 70 !Partitioned.test(SID) && !Workset.test(SID)) { 71 Worklist.push(S); 72 Workset.set(SID); 73 } 74 } 75 } 76 77 // Any block successors not in the current interval are interval successors. 78 for (const CFGBlock *B : MaybeSuccessors) 79 if (Interval.Blocks.find(B) == Interval.Blocks.end()) 80 Interval.Successors.insert(B); 81 82 return Interval; 83 } 84 85 CFGInterval buildInterval(const CFG &Cfg, const CFGBlock &Header) { 86 llvm::BitVector Partitioned(Cfg.getNumBlockIDs(), false); 87 return buildInterval(Partitioned, Header); 88 } 89 90 std::vector<CFGInterval> partitionIntoIntervals(const CFG &Cfg) { 91 std::vector<CFGInterval> Intervals; 92 llvm::BitVector Partitioned(Cfg.getNumBlockIDs(), false); 93 auto &EntryBlock = Cfg.getEntry(); 94 Intervals.push_back(buildInterval(Partitioned, EntryBlock)); 95 96 std::queue<const CFGBlock *> Successors; 97 for (const auto *S : Intervals[0].Successors) 98 Successors.push(S); 99 100 while (!Successors.empty()) { 101 const auto *B = Successors.front(); 102 Successors.pop(); 103 if (Partitioned.test(B->getBlockID())) 104 continue; 105 106 // B has not been partitioned, but it has a predecessor that has. 107 CFGInterval I = buildInterval(Partitioned, *B); 108 for (const auto *S : I.Successors) 109 Successors.push(S); 110 Intervals.push_back(std::move(I)); 111 } 112 113 return Intervals; 114 } 115 116 } // namespace clang 117