LLVM  14.0.0git
SyncDependenceAnalysis.h
Go to the documentation of this file.
1 //===- SyncDependenceAnalysis.h - Divergent Branch Dependence -*- 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 // \file
10 // This file defines the SyncDependenceAnalysis class, which computes for
11 // every divergent branch the set of phi nodes that the branch will make
12 // divergent.
13 //
14 //===----------------------------------------------------------------------===//
15 
16 #ifndef LLVM_ANALYSIS_SYNCDEPENDENCEANALYSIS_H
17 #define LLVM_ANALYSIS_SYNCDEPENDENCEANALYSIS_H
18 
19 #include "llvm/ADT/DenseMap.h"
21 #include "llvm/ADT/SmallPtrSet.h"
22 #include "llvm/Analysis/LoopInfo.h"
23 #include <memory>
24 #include <unordered_map>
25 
26 namespace llvm {
27 
28 class BasicBlock;
29 class DominatorTree;
30 class Loop;
31 class PostDominatorTree;
32 
35  // Join points of divergent disjoint paths.
37  // Divergent loop exits
39 };
40 
41 struct ModifiedPO {
42  std::vector<const BasicBlock *> LoopPO;
43  std::unordered_map<const BasicBlock *, unsigned> POIndex;
44  void appendBlock(const BasicBlock &BB) {
45  POIndex[&BB] = LoopPO.size();
46  LoopPO.push_back(&BB);
47  }
48  unsigned getIndexOf(const BasicBlock &BB) const {
49  return POIndex.find(&BB)->second;
50  }
51  unsigned size() const { return LoopPO.size(); }
52  const BasicBlock *getBlockAt(unsigned Idx) const { return LoopPO[Idx]; }
53 };
54 
55 /// \brief Relates points of divergent control to join points in
56 /// reducible CFGs.
57 ///
58 /// This analysis relates points of divergent control to points of converging
59 /// divergent control. The analysis requires all loops to be reducible.
61 public:
64  const LoopInfo &LI);
65 
66  /// \brief Computes divergent join points and loop exits caused by branch
67  /// divergence in \p Term.
68  ///
69  /// The set of blocks which are reachable by disjoint paths from \p Term.
70  /// The set also contains loop exits if there two disjoint paths:
71  /// one from \p Term to the loop exit and another from \p Term to the loop
72  /// header. Those exit blocks are added to the returned set.
73  /// If L is the parent loop of \p Term and an exit of L is in the returned
74  /// set then L is a divergent loop.
76 
77 private:
78  static ControlDivergenceDesc EmptyDivergenceDesc;
79 
80  ModifiedPO LoopPO;
81 
82  const DominatorTree &DT;
83  const PostDominatorTree &PDT;
84  const LoopInfo &LI;
85 
86  std::map<const Instruction *, std::unique_ptr<ControlDivergenceDesc>>
87  CachedControlDivDescs;
88 };
89 
90 } // namespace llvm
91 
92 #endif // LLVM_ANALYSIS_SYNCDEPENDENCEANALYSIS_H
llvm
This is an optimization pass for GlobalISel generic memory operations.
Definition: AllocatorList.h:23
llvm::ControlDivergenceDesc::LoopDivBlocks
ConstBlockSet LoopDivBlocks
Definition: SyncDependenceAnalysis.h:38
llvm::DominatorTree
Concrete subclass of DominatorTreeBase that is used to compute a normal dominator tree.
Definition: Dominators.h:151
DenseMap.h
llvm::SmallPtrSet< const BasicBlock *, 4 >
llvm::BasicBlock
LLVM Basic Block Representation.
Definition: BasicBlock.h:58
llvm::ModifiedPO::size
unsigned size() const
Definition: SyncDependenceAnalysis.h:51
llvm::ModifiedPO::LoopPO
std::vector< const BasicBlock * > LoopPO
Definition: SyncDependenceAnalysis.h:42
llvm::ControlDivergenceDesc::JoinDivBlocks
ConstBlockSet JoinDivBlocks
Definition: SyncDependenceAnalysis.h:36
llvm::ModifiedPO::getIndexOf
unsigned getIndexOf(const BasicBlock &BB) const
Definition: SyncDependenceAnalysis.h:48
llvm::Instruction
Definition: Instruction.h:45
llvm::SyncDependenceAnalysis::~SyncDependenceAnalysis
~SyncDependenceAnalysis()
Definition: SyncDependenceAnalysis.cpp:260
llvm::M68kBeads::Term
@ Term
Definition: M68kBaseInfo.h:71
SmallPtrSet.h
LoopInfo.h
llvm::SyncDependenceAnalysis::SyncDependenceAnalysis
SyncDependenceAnalysis(const DominatorTree &DT, const PostDominatorTree &PDT, const LoopInfo &LI)
Definition: SyncDependenceAnalysis.cpp:252
llvm::ModifiedPO::POIndex
std::unordered_map< const BasicBlock *, unsigned > POIndex
Definition: SyncDependenceAnalysis.h:43
llvm::ModifiedPO::appendBlock
void appendBlock(const BasicBlock &BB)
Definition: SyncDependenceAnalysis.h:44
llvm::ModifiedPO
Definition: SyncDependenceAnalysis.h:41
llvm::ISD::BasicBlock
@ BasicBlock
Various leaf nodes.
Definition: ISDOpcodes.h:71
llvm::LoopInfo
Definition: LoopInfo.h:1083
llvm::ControlDivergenceDesc
Definition: SyncDependenceAnalysis.h:34
llvm::PostDominatorTree
PostDominatorTree Class - Concrete subclass of DominatorTree that is used to compute the post-dominat...
Definition: PostDominators.h:28
llvm::SyncDependenceAnalysis
Relates points of divergent control to join points in reducible CFGs.
Definition: SyncDependenceAnalysis.h:60
llvm::SyncDependenceAnalysis::getJoinBlocks
const ControlDivergenceDesc & getJoinBlocks(const Instruction &Term)
Computes divergent join points and loop exits caused by branch divergence in Term.
Definition: SyncDependenceAnalysis.cpp:450
PostOrderIterator.h
llvm::ModifiedPO::getBlockAt
const BasicBlock * getBlockAt(unsigned Idx) const
Definition: SyncDependenceAnalysis.h:52
BB
Common register allocation spilling lr str ldr sxth r3 ldr mla r4 can lr mov lr str ldr sxth r3 mla r4 and then merge mul and lr str ldr sxth r3 mla r4 It also increase the likelihood the store may become dead bb27 Successors according to LLVM BB
Definition: README.txt:39