Loading [MathJax]/extensions/tex2jax.js
CIRCT  20.0.0git
All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Pages
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 
18 using namespace circt;
19 
20 static 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 
28 static 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 
34 static 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 
41 void llhd::TemporalRegionAnalysis::recalculate(Operation *operation) {
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  } else if (!allPredecessorTRsKnown(block, workDone) ||
95  anyPredecessorHasWait(block) ||
96  !(std::adjacent_find(block->pred_begin(), block->pred_end(),
97  [&](Block *pred1, Block *pred2) {
98  return blockMap[pred1] != blockMap[pred2];
99  }) == block->pred_end())) {
100  addBlockToTR(block, ++nextTRnum, blockMap, trMap);
101  // If all predecessors have the same TR and none has a wait terminator,
102  // inherit the TR
103  } else {
104  int tr = blockMap[*block->pred_begin()];
105  blockMap.insert(std::make_pair(block, tr));
106  trMap[tr].push_back(block);
107  trMap[tr].erase(std::unique(trMap[tr].begin(), trMap[tr].end()),
108  trMap[tr].end());
109  }
110  }
111 
112  numTRs = nextTRnum + 1;
113 }
114 
116  assert(blockMap.count(block) &&
117  "This block is not present in the temporal regions map.");
118  return blockMap.at(block);
119 }
120 
121 SmallVector<Block *, 8>
123  if (!trMap.count(tr))
124  return SmallVector<Block *, 8>();
125  return trMap.at(tr);
126 }
127 
128 SmallVector<Block *, 8>
130  SmallVector<Block *, 8> blocks = getBlocksInTR(tr);
131  SmallVector<Block *, 8> exitingBlocks;
132  for (Block *block : blocks) {
133  for (auto *succ : block->getSuccessors()) {
134  if (blockMap.at(succ) != blockMap.at(block) ||
135  isa<WaitOp>(block->getTerminator())) {
136  exitingBlocks.push_back(block);
137  break;
138  }
139  }
140  }
141  return exitingBlocks;
142 }
143 
145  SmallVector<int, 8> res;
146  for (Block *block : getExitingBlocksInTR(tr)) {
147  for (Block *succ : block->getSuccessors()) {
148  if (getBlockTR(succ) != tr || isa<llhd::WaitOp>(block->getTerminator()))
149  res.push_back(getBlockTR(succ));
150  }
151  }
152  res.erase(std::unique(res.begin(), res.end()), res.end());
153  return res;
154 }
155 
157  for (Block *block : getBlocksInTR(tr)) {
158  if (block->hasNoPredecessors() || anyPredecessorHasWait(block))
159  return block;
160 
161  for (Block *pred : block->getPredecessors()) {
162  if (getBlockTR(pred) != tr)
163  return block;
164  }
165  }
166  return nullptr;
167 }
assert(baseType &&"element must be base type")
static bool allPredecessorTRsKnown(Block *block, SmallPtrSetImpl< Block * > &known)
static bool anyPredecessorHasWait(Block *block)
static void addBlockToTR(Block *block, int tr, DenseMap< Block *, int > &blockMap, DenseMap< int, SmallVector< Block *, 8 >> &trMap)
The InstanceGraph op interface, see InstanceGraphInterface.td for more details.
Definition: DebugAnalysis.h:21
SmallVector< Block *, 8 > getExitingBlocksInTR(int) const
SmallVector< Block *, 8 > getBlocksInTR(int) const
SmallVector< int, 8 > getTRSuccessors(int)