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