[Mesa-dev] [PATCH 01/12] R600/structurizer: add class to find the Nearest Common Dominator

Tom Stellard tom at stellard.net
Thu Feb 14 10:50:55 PST 2013


On Thu, Feb 14, 2013 at 06:34:14PM +0100, Christian König wrote:
> From: Christian König <christian.koenig at amd.com>
> 
> Signed-off-by: Christian König <christian.koenig at amd.com>

For the series:

Reviewed-by: Tom Stellard <thomas.stellard at amd.com>

Don't forget to mark these as candidates for the stable branch.


> ---
>  lib/Target/R600/AMDGPUStructurizeCFG.cpp |   66 ++++++++++++++++++++++++++++++
>  1 file changed, 66 insertions(+)
> 
> diff --git a/lib/Target/R600/AMDGPUStructurizeCFG.cpp b/lib/Target/R600/AMDGPUStructurizeCFG.cpp
> index c4c9762..86cb04a 100644
> --- a/lib/Target/R600/AMDGPUStructurizeCFG.cpp
> +++ b/lib/Target/R600/AMDGPUStructurizeCFG.cpp
> @@ -39,6 +39,7 @@ typedef SmallVector<BBValuePair, 2> BBValueVector;
>  typedef SmallPtrSet<BasicBlock *, 8> BBSet;
>  
>  typedef DenseMap<PHINode *, BBValueVector> PhiMap;
> +typedef DenseMap<DomTreeNode *, unsigned> DTN2UnsignedMap;
>  typedef DenseMap<BasicBlock *, PhiMap> BBPhiMap;
>  typedef DenseMap<BasicBlock *, Value *> BBPredicates;
>  typedef DenseMap<BasicBlock *, BBPredicates> PredMap;
> @@ -48,6 +49,71 @@ typedef DenseMap<BasicBlock *, BBVector> BB2BBVecMap;
>  
>  static const char *FlowBlockName = "Flow";
>  
> +/// @brief Find the nearest common dominator for multiple BasicBlocks
> +///
> +/// Helper class for AMDGPUStructurizeCFG
> +/// TODO: Maybe move into common code
> +class NearestCommonDominator {
> +
> +  DominatorTree *DT;
> +
> +  DTN2UnsignedMap IndexMap;
> +
> +  BasicBlock *Result;
> +  unsigned ResultIndex;
> +  bool ExplicitMentioned;
> +
> +public:
> +  /// \brief Start a new query
> +  NearestCommonDominator(DominatorTree *DomTree) {
> +    DT = DomTree;
> +    Result = 0;
> +  }
> +
> +  /// \brief Add BB to the resulting dominator
> +  void addBlock(BasicBlock *BB, bool Remember = true) {
> +
> +    DomTreeNode *Node = DT->getNode(BB);
> +
> +    if (Result == 0) {
> +      unsigned Numbering = 0;
> +      for (;Node;Node = Node->getIDom())
> +        IndexMap[Node] = ++Numbering;
> +      Result = BB;
> +      ResultIndex = 1;
> +      ExplicitMentioned = Remember;
> +      return;
> +    }
> +
> +    for (;Node;Node = Node->getIDom())
> +      if (IndexMap.count(Node))
> +        break;
> +      else
> +        IndexMap[Node] = 0;
> +
> +    assert(Node && "Dominator tree invalid!");
> +
> +    unsigned Numbering = IndexMap[Node];
> +    if (Numbering > ResultIndex) {
> +      Result = Node->getBlock();
> +      ResultIndex = Numbering;
> +      ExplicitMentioned = Remember && (Result == BB);
> +    } else if (Numbering == ResultIndex) {
> +      ExplicitMentioned |= Remember;
> +    }
> +  }
> +
> +  /// \brief Is "Result" one of the BBs added with "Remember" = True?
> +  bool wasResultExplicitMentioned() {
> +    return ExplicitMentioned;
> +  }
> +
> +  /// \brief Get the query result
> +  BasicBlock *getResult() {
> +    return Result;
> +  }
> +};
> +
>  /// @brief Transforms the control flow graph on one single entry/exit region
>  /// at a time.
>  ///
> -- 
> 1.7.10.4
> 
> _______________________________________________
> mesa-dev mailing list
> mesa-dev at lists.freedesktop.org
> http://lists.freedesktop.org/mailman/listinfo/mesa-dev


More information about the mesa-dev mailing list