1 //===-- Analysis/EHUtils.h - Exception handling related utils --*-//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 #ifndef LLVM_ANALYSIS_EHUTILS_H
9 #define LLVM_ANALYSIS_EHUTILS_H
10 
11 #include "llvm/ADT/DenseMap.h"
12 #include "llvm/ADT/DenseSet.h"
13 
14 namespace llvm {
15 
16 /// Compute a list of blocks that are only reachable via EH paths.
17 template <typename FunctionT, typename BlockT>
18 static void computeEHOnlyBlocks(FunctionT &F, DenseSet<BlockT *> &EHBlocks) {
19   // A block can be unknown if its not reachable from anywhere
20   // EH if its only reachable from start blocks via some path through EH pads
21   // NonEH if it's reachable from Non EH blocks as well.
22   enum Status { Unknown = 0, EH = 1, NonEH = 2 };
23   DenseSet<BlockT *> WorkList;
24   DenseMap<BlockT *, Status> Statuses;
25 
26   auto GetStatus = [&](BlockT *BB) {
27     if (Statuses.find(BB) != Statuses.end())
28       return Statuses[BB];
29     else
30       return Unknown;
31   };
32 
33   auto CheckPredecessors = [&](BlockT *BB, Status Stat) {
34     for (auto *PredBB : predecessors(BB)) {
35       Status PredStatus = GetStatus(PredBB);
36       // If status of predecessor block has gone above current block
37       // we update current blocks status.
38       if (PredStatus > Stat)
39         Stat = PredStatus;
40     }
41     return Stat;
42   };
43 
44   auto AddSuccesors = [&](BlockT *BB) {
45     for (auto *SuccBB : successors(BB)) {
46       if (!SuccBB->isEHPad())
47         WorkList.insert(SuccBB);
48     }
49   };
50 
51   // Insert the successors of start block and landing pads successor.
52   BlockT *StartBlock = &F.front();
53   Statuses[StartBlock] = NonEH;
54   AddSuccesors(StartBlock);
55 
56   for (auto &BB : F) {
57     if (BB.isEHPad()) {
58       AddSuccesors(&BB);
59       Statuses[&BB] = EH;
60     }
61   }
62 
63   // Worklist iterative algorithm.
64   while (!WorkList.empty()) {
65     auto *BB = *WorkList.begin();
66     WorkList.erase(BB);
67 
68     Status OldStatus = GetStatus(BB);
69 
70     // Check on predecessors and check for
71     // Status update.
72     Status NewStatus = CheckPredecessors(BB, OldStatus);
73 
74     // Did the block status change?
75     bool Changed = OldStatus != NewStatus;
76     if (Changed) {
77       AddSuccesors(BB);
78       Statuses[BB] = NewStatus;
79     }
80   }
81 
82   EHBlocks.clear();
83   for (auto Entry : Statuses) {
84     if (Entry.second == EH)
85       EHBlocks.insert(Entry.first);
86   }
87 }
88 } // namespace llvm
89 
90 #endif
91