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