diff options
author | Juergen Ributzka <juergen@apple.com> | 2014-03-21 06:04:39 +0000 |
---|---|---|
committer | Juergen Ributzka <juergen@apple.com> | 2014-03-21 06:04:39 +0000 |
commit | 337eb3adbed6d1ba790555bd3a0dc2d02d2345bc (patch) | |
tree | 7ce48ee90c407b6ffa3b49f3b5aec92443d38b59 /lib | |
parent | 8ebaf637500a6bac4bf734b1c7e8600ac9add6f7 (diff) | |
download | llvm-337eb3adbed6d1ba790555bd3a0dc2d02d2345bc.tar.gz llvm-337eb3adbed6d1ba790555bd3a0dc2d02d2345bc.tar.bz2 llvm-337eb3adbed6d1ba790555bd3a0dc2d02d2345bc.tar.xz |
[Constant Hoisting] Lazily compute the idom and cache the result.
Related to <rdar://problem/16381500>
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@204434 91177308-0d34-0410-b5e6-96231b3b80d8
Diffstat (limited to 'lib')
-rw-r--r-- | lib/Transforms/Scalar/ConstantHoisting.cpp | 47 |
1 files changed, 43 insertions, 4 deletions
diff --git a/lib/Transforms/Scalar/ConstantHoisting.cpp b/lib/Transforms/Scalar/ConstantHoisting.cpp index 25fef5f500..89df2b496f 100644 --- a/lib/Transforms/Scalar/ConstantHoisting.cpp +++ b/lib/Transforms/Scalar/ConstantHoisting.cpp @@ -87,9 +87,10 @@ struct ConstantCandidate { struct RebasedConstantInfo { ConstantUseListType Uses; Constant *Offset; + mutable BasicBlock *IDom; RebasedConstantInfo(ConstantUseListType &&Uses, Constant *Offset) - : Uses(Uses), Offset(Offset) { } + : Uses(Uses), Offset(Offset), IDom(nullptr) { } }; /// \brief A base constant and all its rebased constants. @@ -152,6 +153,17 @@ private: Entry = nullptr; } + /// \brief Find the common dominator of all uses and cache the result for + /// future lookup. + BasicBlock *getIDom(const RebasedConstantInfo &RCI) const { + if (RCI.IDom) + return RCI.IDom; + RCI.IDom = findIDomOfAllUses(RCI.Uses); + assert(RCI.IDom && "Invalid IDom."); + return RCI.IDom; + } + + BasicBlock *findIDomOfAllUses(const ConstantUseListType &Uses) const; Instruction *findMatInsertPt(Instruction *Inst, unsigned Idx = ~0U) const; Instruction *findConstantInsertionPoint(const ConstantInfo &ConstInfo) const; void collectConstantCandidates(Instruction *Inst, unsigned Idx, @@ -202,6 +214,32 @@ bool ConstantHoisting::runOnFunction(Function &Fn) { return MadeChange; } +/// \brief Find nearest common dominator of all uses. +/// FIXME: Replace this with NearestCommonDominator once it is in common code. +BasicBlock * +ConstantHoisting::findIDomOfAllUses(const ConstantUseListType &Uses) const { + // Collect all basic blocks. + SmallPtrSet<BasicBlock *, 8> BBs; + for (auto const &U : Uses) + BBs.insert(findMatInsertPt(U.Inst, U.OpndIdx)->getParent()); + + if (BBs.count(Entry)) + return Entry; + + while (BBs.size() >= 2) { + BasicBlock *BB, *BB1, *BB2; + BB1 = *BBs.begin(); + BB2 = *std::next(BBs.begin()); + BB = DT->findNearestCommonDominator(BB1, BB2); + if (BB == Entry) + return Entry; + BBs.erase(BB1); + BBs.erase(BB2); + BBs.insert(BB); + } + assert((BBs.size() == 1) && "Expected only one element."); + return *BBs.begin(); +} /// \brief Find the constant materialization insertion point. Instruction *ConstantHoisting::findMatInsertPt(Instruction *Inst, @@ -224,11 +262,12 @@ Instruction *ConstantHoisting::findMatInsertPt(Instruction *Inst, Instruction *ConstantHoisting:: findConstantInsertionPoint(const ConstantInfo &ConstInfo) const { assert(!ConstInfo.RebasedConstants.empty() && "Invalid constant info entry."); - // Collect all basic blocks. + // Collect all IDoms. SmallPtrSet<BasicBlock *, 8> BBs; for (auto const &RCI : ConstInfo.RebasedConstants) - for (auto const &U : RCI.Uses) - BBs.insert(U.Inst->getParent()); + BBs.insert(getIDom(RCI)); + + assert(!BBs.empty() && "No dominators!?"); if (BBs.count(Entry)) return &Entry->front(); |