CIRCT 20.0.0git
Loading...
Searching...
No Matches
TemporalRegions.cpp
Go to the documentation of this file.
1//===- TemporalRegions.cpp - LLHD temporal regions analysis ---------------===//
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 implements an Analysis for Behavioral LLHD to find the temporal
10// regions of an LLHD process.
11//
12//===----------------------------------------------------------------------===//
13
14#include "TemporalRegions.h"
16#include "llvm/ADT/SmallPtrSet.h"
17
18using namespace circt;
19
20static void addBlockToTR(Block *block, int tr, DenseMap<Block *, int> &blockMap,
21 DenseMap<int, SmallVector<Block *, 8>> &trMap) {
22 blockMap.insert(std::make_pair(block, tr));
23 SmallVector<Block *, 8> b;
24 b.push_back(block);
25 trMap.insert(std::make_pair(tr, b));
26}
27
28static bool anyPredecessorHasWait(Block *block) {
29 return std::any_of(block->pred_begin(), block->pred_end(), [](Block *pred) {
30 return isa<llhd::WaitOp>(pred->getTerminator());
31 });
32}
33
34static bool allPredecessorTRsKnown(Block *block,
35 SmallPtrSetImpl<Block *> &known) {
36 return std::all_of(block->pred_begin(), block->pred_end(), [&](Block *pred) {
37 return std::find(known.begin(), known.end(), pred) != known.end();
38 });
39}
40
42 assert(isa<ProcessOp>(operation) &&
43 "TemporalRegionAnalysis: operation needs to be llhd::ProcessOp");
44 auto proc = cast<ProcessOp>(operation);
45 int nextTRnum = -1;
46 blockMap.clear();
47 trMap.clear();
48
49 SmallPtrSet<Block *, 32> workQueue;
50 SmallPtrSet<Block *, 32> workDone;
51
52 // Add the entry block and all blocks targeted by a wait terminator to the
53 // initial work queue because they are always the entry block of a new TR
54 workQueue.insert(&proc.getBody().front());
55 proc.walk([&](WaitOp wait) { workQueue.insert(wait.getDest()); });
56
57 while (!workQueue.empty()) {
58 // Find basic block in the work queue which has all predecessors already
59 // processed or at least one predecessor has a wait terminator
60 auto iter =
61 std::find_if(workQueue.begin(), workQueue.end(), [&](Block *block) {
62 return allPredecessorTRsKnown(block, workDone) ||
63 anyPredecessorHasWait(block);
64 });
65
66 // If no element in the work queue has all predecessors finished or is
67 // targeted by a wait, there is probably a loop within a TR, in this case we
68 // are conservatively assign a new temporal region
69 if (iter == workQueue.end())
70 iter = workQueue.begin();
71
72 // This is the current block to be processed
73 Block *block = *iter;
74
75 // Delete this block from the work queue and add it to the list of alredy
76 // processed blocks
77 workQueue.erase(block);
78 workDone.insert(block);
79
80 // Add all successors of this block which were not already processed to the
81 // work queue
82 for (Block *succ : block->getSuccessors()) {
83 if (!workDone.count(succ))
84 workQueue.insert(succ);
85 }
86
87 // The entry block is always assigned -1 as a placeholder as this block must
88 // not contain any temporal operations
89 if (block->isEntryBlock()) {
90 addBlockToTR(block, -1, blockMap, trMap);
91 // If at least one predecessor has a wait terminator or at least one
92 // predecessor has an unknown temporal region or not all predecessors have
93 // the same TR, create a new TR
94 // FIXME: `!allPredecessorTRsKnown` is a problem when there are CFG loops
95 // in the process. If there is no wait op along any of the CFG edges of
96 // such a loop we don't want to assign a new temporal region. However, we
97 // also cannot just assume here that we can just assign the same TR, so
98 // this might require a bigger change to the algorithm.
99 } else if (!allPredecessorTRsKnown(block, workDone) ||
100 anyPredecessorHasWait(block) ||
101 !(std::adjacent_find(block->pred_begin(), block->pred_end(),
102 [&](Block *pred1, Block *pred2) {
103 return blockMap[pred1] != blockMap[pred2];
104 }) == block->pred_end())) {
105 addBlockToTR(block, ++nextTRnum, blockMap, trMap);
106 // If all predecessors have the same TR and none has a wait terminator,
107 // inherit the TR
108 } else {
109 int tr = blockMap[*block->pred_begin()];
110 blockMap.insert(std::make_pair(block, tr));
111 trMap[tr].push_back(block);
112 trMap[tr].erase(std::unique(trMap[tr].begin(), trMap[tr].end()),
113 trMap[tr].end());
114 }
115 }
116
117 numTRs = nextTRnum + 1;
118}
119
121 assert(blockMap.count(block) &&
122 "This block is not present in the temporal regions map.");
123 return blockMap.at(block);
124}
125
126SmallVector<Block *, 8>
128 if (!trMap.count(tr))
129 return SmallVector<Block *, 8>();
130 return trMap.at(tr);
131}
132
133SmallVector<Block *, 8>
135 SmallVector<Block *, 8> blocks = getBlocksInTR(tr);
136 SmallVector<Block *, 8> exitingBlocks;
137 for (Block *block : blocks) {
138 for (auto *succ : block->getSuccessors()) {
139 if (blockMap.at(succ) != blockMap.at(block) ||
140 isa<WaitOp>(block->getTerminator())) {
141 exitingBlocks.push_back(block);
142 break;
143 }
144 }
145 }
146 return exitingBlocks;
147}
148
150 SmallVector<int, 8> res;
151 for (Block *block : getExitingBlocksInTR(tr)) {
152 for (Block *succ : block->getSuccessors()) {
153 if (getBlockTR(succ) != tr || isa<llhd::WaitOp>(block->getTerminator()))
154 res.push_back(getBlockTR(succ));
155 }
156 }
157 res.erase(std::unique(res.begin(), res.end()), res.end());
158 return res;
159}
160
162 for (Block *block : getBlocksInTR(tr)) {
163 if (block->hasNoPredecessors() || anyPredecessorHasWait(block))
164 return block;
165
166 for (Block *pred : block->getPredecessors()) {
167 if (getBlockTR(pred) != tr)
168 return block;
169 }
170 }
171 return nullptr;
172}
assert(baseType &&"element must be base type")
static void addBlockToTR(Block *block, int tr, DenseMap< Block *, int > &blockMap, DenseMap< int, SmallVector< Block *, 8 > > &trMap)
static bool allPredecessorTRsKnown(Block *block, SmallPtrSetImpl< Block * > &known)
static bool anyPredecessorHasWait(Block *block)
The InstanceGraph op interface, see InstanceGraphInterface.td for more details.
SmallVector< Block *, 8 > getExitingBlocksInTR(int) const
SmallVector< Block *, 8 > getBlocksInTR(int) const
SmallVector< int, 8 > getTRSuccessors(int)