Skip to content

Commit 2372a19

Browse files
dberlindberlin
committedApr 21, 2015
Move IDF Calculation to a separate file, expose an interface to it.
Summary: MemorySSA uses this algorithm as well, and this enables us to reuse the code in both places. There are no actual algorithm or datastructure changes in here, just code movement. Reviewers: qcolombet, chandlerc Subscribers: llvm-commits Differential Revision: http://reviews.llvm.org/D9118 llvm-svn: 235406
·
llvmorg-21-initllvmorg-3.7.0-rc1
1 parent 0d7c694 commit 2372a19

File tree

4 files changed

+224
-130
lines changed

4 files changed

+224
-130
lines changed
 

‎llvm/include/llvm/Analysis/IteratedDominanceFrontier.h

+96
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,96 @@
1+
//===- IteratedDominanceFrontier.h - Calculate IDF --------------*- C++ -*-===//
2+
//
3+
// The LLVM Compiler Infrastructure
4+
//
5+
// This file is distributed under the University of Illinois Open Source
6+
// License. See LICENSE.TXT for details.
7+
//
8+
//===----------------------------------------------------------------------===//
9+
//
10+
/// \brief Compute iterated dominance frontiers using a linear time algorithm.
11+
///
12+
/// The algorithm used here is based on:
13+
///
14+
/// Sreedhar and Gao. A linear time algorithm for placing phi-nodes.
15+
/// In Proceedings of the 22nd ACM SIGPLAN-SIGACT Symposium on Principles of
16+
/// Programming Languages
17+
/// POPL '95. ACM, New York, NY, 62-73.
18+
///
19+
/// It has been modified to not explicitly use the DJ graph data structure and
20+
/// to directly compute pruned SSA using per-variable liveness information.
21+
//
22+
//===----------------------------------------------------------------------===//
23+
24+
#ifndef LLVM_ANALYSIS_IDF_H
25+
#define LLVM_ANALYSIS_IDF_H
26+
27+
#include "llvm/ADT/ArrayRef.h"
28+
#include "llvm/ADT/DenseMap.h"
29+
#include "llvm/ADT/SmallPtrSet.h"
30+
#include "llvm/ADT/SmallVector.h"
31+
32+
namespace llvm {
33+
34+
class BasicBlock;
35+
template <class T> class DomTreeNodeBase;
36+
typedef DomTreeNodeBase<BasicBlock> DomTreeNode;
37+
class DominatorTree;
38+
39+
/// \brief Determine the iterated dominance frontier, given a set of defining
40+
/// blocks, and optionally, a set of live-in blocks.
41+
///
42+
/// In turn, the results can be used to place phi nodes.
43+
///
44+
/// This algorithm is a linear time computation of Iterated Dominance Frontiers,
45+
/// pruned using the live-in set.
46+
/// By default, liveness is not used to prune the IDF computation.
47+
class IDFCalculator {
48+
49+
public:
50+
IDFCalculator(DominatorTree &DT) : DT(DT), useLiveIn(false) {}
51+
52+
/// \brief Give the IDF calculator the set of blocks in which the value is
53+
/// defined. This is equivalent to the set of starting blocks it should be
54+
/// calculating the IDF for (though later gets pruned based on liveness).
55+
///
56+
/// Note: This set *must* live for the entire lifetime of the IDF calculator.
57+
void setDefiningBlocks(const SmallPtrSetImpl<BasicBlock *> &Blocks) {
58+
DefBlocks = &Blocks;
59+
}
60+
61+
/// \brief Give the IDF calculator the set of blocks in which the value is
62+
/// live on entry to the block. This is used to prune the IDF calculation to
63+
/// not include blocks where any phi insertion would be dead.
64+
///
65+
/// Note: This set *must* live for the entire lifetime of the IDF calculator.
66+
67+
void setLiveInBlocks(const SmallPtrSetImpl<BasicBlock *> &Blocks) {
68+
LiveInBlocks = &Blocks;
69+
useLiveIn = true;
70+
}
71+
72+
/// \brief Reset the live-in block set to be empty, and tell the IDF
73+
/// calculator to not use liveness anymore.
74+
void resetLiveInBlocks() {
75+
LiveInBlocks = nullptr;
76+
useLiveIn = false;
77+
}
78+
79+
/// \brief Calculate iterated dominance frontiers
80+
///
81+
/// This uses the linear-time phi algorithm based on DJ-graphs mentioned in
82+
/// the file-level comment. It performs DF->IDF pruning using the live-in
83+
/// set, to avoid computing the IDF for blocks where an inserted PHI node
84+
/// would be dead.
85+
void calculate(SmallVectorImpl<BasicBlock *> &IDFBlocks);
86+
87+
private:
88+
DominatorTree &DT;
89+
bool useLiveIn;
90+
DenseMap<DomTreeNode *, unsigned> DomLevels;
91+
const SmallPtrSetImpl<BasicBlock *> *LiveInBlocks;
92+
const SmallPtrSetImpl<BasicBlock *> *DefBlocks;
93+
SmallVector<BasicBlock *, 32> PHIBlocks;
94+
};
95+
}
96+
#endif

‎llvm/lib/Analysis/CMakeLists.txt

+1
Original file line numberDiff line numberDiff line change
@@ -28,6 +28,7 @@ add_llvm_library(LLVMAnalysis
2828
InstructionSimplify.cpp
2929
Interval.cpp
3030
IntervalPartition.cpp
31+
IteratedDominanceFrontier.cpp
3132
LazyCallGraph.cpp
3233
LazyValueInfo.cpp
3334
LibCallAliasAnalysis.cpp

‎llvm/lib/Analysis/IteratedDominanceFrontier.cpp

+95
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,95 @@
1+
//===- IteratedDominanceFrontier.cpp - Compute IDF ------------------------===//
2+
//
3+
// The LLVM Compiler Infrastructure
4+
//
5+
// This file is distributed under the University of Illinois Open Source
6+
// License. See LICENSE.TXT for details.
7+
//
8+
//===----------------------------------------------------------------------===//
9+
//
10+
/// \brief Compute iterated dominance frontiers using a linear time algorithm.
11+
//
12+
//===----------------------------------------------------------------------===//
13+
14+
#include "llvm/Analysis/IteratedDominanceFrontier.h"
15+
#include "llvm/IR/CFG.h"
16+
#include "llvm/IR/Dominators.h"
17+
#include <queue>
18+
19+
using namespace llvm;
20+
21+
void IDFCalculator::calculate(SmallVectorImpl<BasicBlock *> &PHIBlocks) {
22+
// If we haven't computed dominator tree levels, do so now.
23+
if (DomLevels.empty()) {
24+
for (auto DFI = df_begin(DT.getRootNode()), DFE = df_end(DT.getRootNode());
25+
DFI != DFE; ++DFI) {
26+
DomLevels[*DFI] = DFI.getPathLength() - 1;
27+
}
28+
}
29+
30+
// Use a priority queue keyed on dominator tree level so that inserted nodes
31+
// are handled from the bottom of the dominator tree upwards.
32+
typedef std::pair<DomTreeNode *, unsigned> DomTreeNodePair;
33+
typedef std::priority_queue<DomTreeNodePair, SmallVector<DomTreeNodePair, 32>,
34+
less_second> IDFPriorityQueue;
35+
IDFPriorityQueue PQ;
36+
37+
for (BasicBlock *BB : *DefBlocks) {
38+
if (DomTreeNode *Node = DT.getNode(BB))
39+
PQ.push(std::make_pair(Node, DomLevels.lookup(Node)));
40+
}
41+
42+
SmallVector<DomTreeNode *, 32> Worklist;
43+
SmallPtrSet<DomTreeNode *, 32> VisitedPQ;
44+
SmallPtrSet<DomTreeNode *, 32> VisitedWorklist;
45+
46+
while (!PQ.empty()) {
47+
DomTreeNodePair RootPair = PQ.top();
48+
PQ.pop();
49+
DomTreeNode *Root = RootPair.first;
50+
unsigned RootLevel = RootPair.second;
51+
52+
// Walk all dominator tree children of Root, inspecting their CFG edges with
53+
// targets elsewhere on the dominator tree. Only targets whose level is at
54+
// most Root's level are added to the iterated dominance frontier of the
55+
// definition set.
56+
57+
Worklist.clear();
58+
Worklist.push_back(Root);
59+
VisitedWorklist.insert(Root);
60+
61+
while (!Worklist.empty()) {
62+
DomTreeNode *Node = Worklist.pop_back_val();
63+
BasicBlock *BB = Node->getBlock();
64+
65+
for (auto Succ : successors(BB)) {
66+
DomTreeNode *SuccNode = DT.getNode(Succ);
67+
68+
// Quickly skip all CFG edges that are also dominator tree edges instead
69+
// of catching them below.
70+
if (SuccNode->getIDom() == Node)
71+
continue;
72+
73+
unsigned SuccLevel = DomLevels.lookup(SuccNode);
74+
if (SuccLevel > RootLevel)
75+
continue;
76+
77+
if (!VisitedPQ.insert(SuccNode).second)
78+
continue;
79+
80+
BasicBlock *SuccBB = SuccNode->getBlock();
81+
if (useLiveIn && !LiveInBlocks->count(SuccBB))
82+
continue;
83+
84+
PHIBlocks.emplace_back(SuccBB);
85+
if (!DefBlocks->count(SuccBB))
86+
PQ.push(std::make_pair(SuccNode, SuccLevel));
87+
}
88+
89+
for (auto DomChild : *Node) {
90+
if (VisitedWorklist.insert(DomChild).second)
91+
Worklist.push_back(DomChild);
92+
}
93+
}
94+
}
95+
}

‎llvm/lib/Transforms/Utils/PromoteMemoryToRegister.cpp

+32-130
Original file line numberDiff line numberDiff line change
@@ -13,16 +13,6 @@
1313
// traversing the function in depth-first order to rewrite loads and stores as
1414
// appropriate.
1515
//
16-
// The algorithm used here is based on:
17-
//
18-
// Sreedhar and Gao. A linear time algorithm for placing phi-nodes.
19-
// In Proceedings of the 22nd ACM SIGPLAN-SIGACT Symposium on Principles of
20-
// Programming Languages
21-
// POPL '95. ACM, New York, NY, 62-73.
22-
//
23-
// It has been modified to not explicitly use the DJ graph data structure and to
24-
// directly compute pruned SSA using per-variable liveness information.
25-
//
2616
//===----------------------------------------------------------------------===//
2717

2818
#include "llvm/Transforms/Utils/PromoteMemToReg.h"
@@ -34,6 +24,7 @@
3424
#include "llvm/ADT/Statistic.h"
3525
#include "llvm/Analysis/AliasSetTracker.h"
3626
#include "llvm/Analysis/InstructionSimplify.h"
27+
#include "llvm/Analysis/IteratedDominanceFrontier.h"
3728
#include "llvm/Analysis/ValueTracking.h"
3829
#include "llvm/IR/CFG.h"
3930
#include "llvm/IR/Constants.h"
@@ -48,7 +39,6 @@
4839
#include "llvm/IR/Module.h"
4940
#include "llvm/Transforms/Utils/Local.h"
5041
#include <algorithm>
51-
#include <queue>
5242
using namespace llvm;
5343

5444
#define DEBUG_TYPE "mem2reg"
@@ -275,9 +265,6 @@ struct PromoteMem2Reg {
275265
/// behavior.
276266
DenseMap<BasicBlock *, unsigned> BBNumbers;
277267

278-
/// Maps DomTreeNodes to their level in the dominator tree.
279-
DenseMap<DomTreeNode *, unsigned> DomLevels;
280-
281268
/// Lazily compute the number of predecessors a block has.
282269
DenseMap<const BasicBlock *, unsigned> BBNumPreds;
283270

@@ -304,8 +291,6 @@ struct PromoteMem2Reg {
304291
return NP - 1;
305292
}
306293

307-
void DetermineInsertionPoint(AllocaInst *AI, unsigned AllocaNum,
308-
AllocaInfo &Info);
309294
void ComputeLiveInBlocks(AllocaInst *AI, AllocaInfo &Info,
310295
const SmallPtrSetImpl<BasicBlock *> &DefBlocks,
311296
SmallPtrSetImpl<BasicBlock *> &LiveInBlocks);
@@ -532,6 +517,7 @@ void PromoteMem2Reg::run() {
532517

533518
AllocaInfo Info;
534519
LargeBlockInfo LBI;
520+
IDFCalculator IDF(DT);
535521

536522
for (unsigned AllocaNum = 0; AllocaNum != Allocas.size(); ++AllocaNum) {
537523
AllocaInst *AI = Allocas[AllocaNum];
@@ -579,31 +565,12 @@ void PromoteMem2Reg::run() {
579565
continue;
580566
}
581567

582-
// If we haven't computed dominator tree levels, do so now.
583-
if (DomLevels.empty()) {
584-
SmallVector<DomTreeNode *, 32> Worklist;
585-
586-
DomTreeNode *Root = DT.getRootNode();
587-
DomLevels[Root] = 0;
588-
Worklist.push_back(Root);
589-
590-
while (!Worklist.empty()) {
591-
DomTreeNode *Node = Worklist.pop_back_val();
592-
unsigned ChildLevel = DomLevels[Node] + 1;
593-
for (DomTreeNode::iterator CI = Node->begin(), CE = Node->end();
594-
CI != CE; ++CI) {
595-
DomLevels[*CI] = ChildLevel;
596-
Worklist.push_back(*CI);
597-
}
598-
}
599-
}
600-
601568
// If we haven't computed a numbering for the BB's in the function, do so
602569
// now.
603570
if (BBNumbers.empty()) {
604571
unsigned ID = 0;
605-
for (Function::iterator I = F.begin(), E = F.end(); I != E; ++I)
606-
BBNumbers[I] = ID++;
572+
for (auto &BB : F)
573+
BBNumbers[&BB] = ID++;
607574
}
608575

609576
// If we have an AST to keep updated, remember some pointer value that is
@@ -622,7 +589,34 @@ void PromoteMem2Reg::run() {
622589
// the standard SSA construction algorithm. Determine which blocks need PHI
623590
// nodes and see if we can optimize out some work by avoiding insertion of
624591
// dead phi nodes.
625-
DetermineInsertionPoint(AI, AllocaNum, Info);
592+
593+
594+
// Unique the set of defining blocks for efficient lookup.
595+
SmallPtrSet<BasicBlock *, 32> DefBlocks;
596+
DefBlocks.insert(Info.DefiningBlocks.begin(), Info.DefiningBlocks.end());
597+
598+
// Determine which blocks the value is live in. These are blocks which lead
599+
// to uses.
600+
SmallPtrSet<BasicBlock *, 32> LiveInBlocks;
601+
ComputeLiveInBlocks(AI, Info, DefBlocks, LiveInBlocks);
602+
603+
// At this point, we're committed to promoting the alloca using IDF's, and
604+
// the standard SSA construction algorithm. Determine which blocks need phi
605+
// nodes and see if we can optimize out some work by avoiding insertion of
606+
// dead phi nodes.
607+
IDF.setLiveInBlocks(LiveInBlocks);
608+
IDF.setDefiningBlocks(DefBlocks);
609+
SmallVector<BasicBlock *, 32> PHIBlocks;
610+
IDF.calculate(PHIBlocks);
611+
if (PHIBlocks.size() > 1)
612+
std::sort(PHIBlocks.begin(), PHIBlocks.end(),
613+
[this](BasicBlock *A, BasicBlock *B) {
614+
return BBNumbers.lookup(A) < BBNumbers.lookup(B);
615+
});
616+
617+
unsigned CurrentVersion = 0;
618+
for (unsigned i = 0, e = PHIBlocks.size(); i != e; ++i)
619+
QueuePhiNode(PHIBlocks[i], AllocaNum, CurrentVersion);
626620
}
627621

628622
if (Allocas.empty())
@@ -844,98 +838,6 @@ void PromoteMem2Reg::ComputeLiveInBlocks(
844838
}
845839
}
846840

847-
/// At this point, we're committed to promoting the alloca using IDF's, and the
848-
/// standard SSA construction algorithm. Determine which blocks need phi nodes
849-
/// and see if we can optimize out some work by avoiding insertion of dead phi
850-
/// nodes.
851-
void PromoteMem2Reg::DetermineInsertionPoint(AllocaInst *AI, unsigned AllocaNum,
852-
AllocaInfo &Info) {
853-
// Unique the set of defining blocks for efficient lookup.
854-
SmallPtrSet<BasicBlock *, 32> DefBlocks;
855-
DefBlocks.insert(Info.DefiningBlocks.begin(), Info.DefiningBlocks.end());
856-
857-
// Determine which blocks the value is live in. These are blocks which lead
858-
// to uses.
859-
SmallPtrSet<BasicBlock *, 32> LiveInBlocks;
860-
ComputeLiveInBlocks(AI, Info, DefBlocks, LiveInBlocks);
861-
862-
// Use a priority queue keyed on dominator tree level so that inserted nodes
863-
// are handled from the bottom of the dominator tree upwards.
864-
typedef std::pair<DomTreeNode *, unsigned> DomTreeNodePair;
865-
typedef std::priority_queue<DomTreeNodePair, SmallVector<DomTreeNodePair, 32>,
866-
less_second> IDFPriorityQueue;
867-
IDFPriorityQueue PQ;
868-
869-
for (BasicBlock *BB : DefBlocks) {
870-
if (DomTreeNode *Node = DT.getNode(BB))
871-
PQ.push(std::make_pair(Node, DomLevels[Node]));
872-
}
873-
874-
SmallVector<std::pair<unsigned, BasicBlock *>, 32> DFBlocks;
875-
SmallVector<DomTreeNode *, 32> Worklist;
876-
SmallPtrSet<DomTreeNode *, 32> VisitedPQ;
877-
SmallPtrSet<DomTreeNode *, 32> VisitedWorklist;
878-
879-
while (!PQ.empty()) {
880-
DomTreeNodePair RootPair = PQ.top();
881-
PQ.pop();
882-
DomTreeNode *Root = RootPair.first;
883-
unsigned RootLevel = RootPair.second;
884-
885-
// Walk all dominator tree children of Root, inspecting their CFG edges with
886-
// targets elsewhere on the dominator tree. Only targets whose level is at
887-
// most Root's level are added to the iterated dominance frontier of the
888-
// definition set.
889-
890-
Worklist.clear();
891-
Worklist.push_back(Root);
892-
VisitedWorklist.insert(Root);
893-
894-
while (!Worklist.empty()) {
895-
DomTreeNode *Node = Worklist.pop_back_val();
896-
BasicBlock *BB = Node->getBlock();
897-
898-
for (succ_iterator SI = succ_begin(BB), SE = succ_end(BB); SI != SE;
899-
++SI) {
900-
DomTreeNode *SuccNode = DT.getNode(*SI);
901-
902-
// Quickly skip all CFG edges that are also dominator tree edges instead
903-
// of catching them below.
904-
if (SuccNode->getIDom() == Node)
905-
continue;
906-
907-
unsigned SuccLevel = DomLevels[SuccNode];
908-
if (SuccLevel > RootLevel)
909-
continue;
910-
911-
if (!VisitedPQ.insert(SuccNode).second)
912-
continue;
913-
914-
BasicBlock *SuccBB = SuccNode->getBlock();
915-
if (!LiveInBlocks.count(SuccBB))
916-
continue;
917-
918-
DFBlocks.push_back(std::make_pair(BBNumbers[SuccBB], SuccBB));
919-
if (!DefBlocks.count(SuccBB))
920-
PQ.push(std::make_pair(SuccNode, SuccLevel));
921-
}
922-
923-
for (DomTreeNode::iterator CI = Node->begin(), CE = Node->end(); CI != CE;
924-
++CI) {
925-
if (VisitedWorklist.insert(*CI).second)
926-
Worklist.push_back(*CI);
927-
}
928-
}
929-
}
930-
931-
if (DFBlocks.size() > 1)
932-
std::sort(DFBlocks.begin(), DFBlocks.end());
933-
934-
unsigned CurrentVersion = 0;
935-
for (unsigned i = 0, e = DFBlocks.size(); i != e; ++i)
936-
QueuePhiNode(DFBlocks[i].second, AllocaNum, CurrentVersion);
937-
}
938-
939841
/// \brief Queue a phi-node to be added to a basic-block for a specific Alloca.
940842
///
941843
/// Returns true if there wasn't already a phi-node for that variable

0 commit comments

Comments
 (0)
Please sign in to comment.