2021SC@SDUSC

前文的分析过程之中涉及到了dominance phase，主要是用于构建支配树和支配边界，为ssa分析做准备工作。本文将对dominance phase进行简要分析。

dominance phase的实现类是MeDoDominance，MeDoDominance继承于MeFuncPhase。MeDoDominance的定义和实现在文件src/maple_me/include/me_dominance.h和src/maple_me/src/me_dominance.cpp之中。

MeDoDominance的定义很简单：

class MeDoDominance : public MeFuncPhase {
 public:
  explicit MeDoDominance(MePhaseID id) : MeFuncPhase(id) {}

  virtual ~MeDoDominance() = default;
  AnalysisResult *Run(MeFunction *func, MeFuncResultMgr *funcResMgr, ModuleResultMgr *moduleResMgr) override;

  std::string PhaseName() const override {
    return "dominance";
  }
};

 具体实现上只有一个Run函数：

AnalysisResult *MeDoDominance::Run(MeFunction *func, MeFuncResultMgr *funcResMgr, ModuleResultMgr *moduleResMgr) {
  MemPool *memPool = NewMemPool();
  Dominance *dom = memPool->New<Dominance>(*memPool, *NewMemPool(), func->GetAllBBs(),
                                           *func->GetCommonEntryBB(), *func->GetCommonExitBB());
  dom->GenPostOrderID();
  dom->ComputeDominance();
  dom->ComputeDomFrontiers();
  dom->ComputeDomChildren();
  size_t num = 0;
  dom->ComputeDtPreorder(*func->GetCommonEntryBB(), num);
  dom->GetDtPreOrder().resize(num);
  dom->ComputeDtDfn();
  dom->PdomGenPostOrderID();
  dom->ComputePostDominance();
  dom->ComputePdomFrontiers();
  dom->ComputePdomChildren();
  num = 0;
  dom->ComputePdtPreorder(*func->GetCommonExitBB(), num);
  dom->ResizePdtPreOrder(num);
  dom->ComputePdtDfn();
  if (DEBUGFUNC(func)) {
    LogInfo::MapleLogger() << "-----------------Dump dominance info and postdominance info---------\n";
    dom->DumpDoms();
    dom->DumpPdoms();
  }
  return dom;
}

 

Run函数里涉及到了Dominance *类型的dom变量，主要的操作都是通过dom来进行的，同时dom变量也是Run函数的返回值。

Dominance继承于AnalysisResult，用于表达分析结果。Dominance的定义和实现在文件src/maple_me/include/dominance.h和src/maple_me/src/dominance.cpp之中。

关于支配树以及支配边界的计算和生成，其实都是在Dominance的成员函数之中实现的，只不过在MeDoDominance的Run函数之中被调用了。也就是说，MeDoDominance的Run函数之中生成了一个Dominance，然后调用Dominance的成员变量去做支配树和支配边界的计算和生成，然后将结果存储在Dominance之中进行返回。

MeDoDominance的Run函数实际上计算了两次支配树和支配边界。只不过其依赖的遍历顺序不同罢了，第一次是使用的逆后序（Reverse PostOrder，RPO），而第二次使用的是反向逆后序。

MeDoDominance中构建支配树和支配边界的算法，可以参考Keih Cooper的论文《A Simple, Fast Dominance Algorithm》，具体实现都是直接参考论文中的算法。论文具体地址：https://www.cs.rice.edu/~keith/EMBED/dom.pdf。

关于支配树和支配边界的计算，也可以阅读《Engineering a Compiler》 Second Edition中的9.2和9.3两节。