Home | History | Annotate | Line # | Download | only in Analysis 
      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"
     20 #include "llvm/ADT/PostOrderIterator.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 
     33 using ConstBlockSet = SmallPtrSet<const BasicBlock *, 4>;
     34 struct ControlDivergenceDesc {
     35   // Join points of divergent disjoint paths.
     36   ConstBlockSet JoinDivBlocks;
     37   // Divergent loop exits
     38   ConstBlockSet LoopDivBlocks;
     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.
     60 class SyncDependenceAnalysis {
     61 public:
     62   ~SyncDependenceAnalysis();
     63   SyncDependenceAnalysis(const DominatorTree &DT, const PostDominatorTree &PDT,
     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.
     75   const ControlDivergenceDesc &getJoinBlocks(const Instruction &Term);
     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
     93