1 //===- GVNPRE.cpp - Eliminate redundant values and expressions ------------===//
3 // The LLVM Compiler Infrastructure
5 // This file was developed by the Owen Anderson and is distributed under
6 // the University of Illinois Open Source License. See LICENSE.TXT for details.
8 //===----------------------------------------------------------------------===//
10 // This pass performs a hybrid of global value numbering and partial redundancy
11 // elimination, known as GVN-PRE. It performs partial redundancy elimination on
12 // values, rather than lexical expressions, allowing a more comprehensive view
13 // the optimization. It replaces redundant values with uses of earlier
14 // occurences of the same value. While this is beneficial in that it eliminates
15 // unneeded computation, it also increases register pressure by creating large
16 // live ranges, and should be used with caution on platforms that a very
17 // sensitive to register pressure.
19 //===----------------------------------------------------------------------===//
21 #define DEBUG_TYPE "gvnpre"
22 #include "llvm/Value.h"
23 #include "llvm/Transforms/Scalar.h"
24 #include "llvm/Instructions.h"
25 #include "llvm/Function.h"
26 #include "llvm/Analysis/Dominators.h"
27 #include "llvm/Analysis/PostDominators.h"
28 #include "llvm/ADT/DepthFirstIterator.h"
29 #include "llvm/ADT/Statistic.h"
30 #include "llvm/Support/Compiler.h"
39 class VISIBILITY_HIDDEN GVNPRE : public FunctionPass {
40 bool runOnFunction(Function &F);
42 static char ID; // Pass identification, replacement for typeid
43 GVNPRE() : FunctionPass((intptr_t)&ID) { nextValueNumber = 0; }
46 uint32_t nextValueNumber;
54 bool operator<(const Expression& other) const {
55 if (opcode < other.opcode)
57 else if (other.opcode < opcode)
61 if (value < other.value)
68 else if (other.lhs < lhs)
70 else if (rhs < other.rhs)
77 bool operator==(const Expression& other) const {
78 if (opcode != other.opcode)
81 if (value != other.value)
94 typedef std::map<Expression, uint32_t> ValueTable;
96 virtual void getAnalysisUsage(AnalysisUsage &AU) const {
98 AU.addRequired<DominatorTree>();
99 AU.addRequired<PostDominatorTree>();
103 // FIXME: eliminate or document these better
104 void dump(ValueTable& VN, std::set<Expression>& s);
105 void clean(ValueTable VN, std::set<Expression>& set);
106 Expression add(ValueTable& VN, std::set<Expression>& MS, Instruction* V);
107 ValueTable::iterator lookup(ValueTable& VN, Value* V);
108 Expression buildExpression(ValueTable& VN, Value* V);
109 std::set<Expression>::iterator find_leader(ValueTable VN,
110 std::set<Expression>& vals,
112 void phi_translate(ValueTable& VN,
113 std::set<Expression>& anticIn, BasicBlock* B,
114 std::set<Expression>& out);
116 // For a given block, calculate the generated expressions, temporaries,
117 // and the AVAIL_OUT set
118 void CalculateAvailOut(ValueTable& VN, std::set<Expression>& MS,
119 DominatorTree::Node* DI,
120 std::set<Expression>& currExps,
121 std::set<PHINode*>& currPhis,
122 std::set<Expression>& currTemps,
123 std::set<Expression>& currAvail,
124 std::map<BasicBlock*, std::set<Expression> > availOut);
132 FunctionPass *llvm::createGVNPREPass() { return new GVNPRE(); }
134 RegisterPass<GVNPRE> X("gvnpre",
135 "Global Value Numbering/Partial Redundancy Elimination");
137 // Given a Value, build an Expression to represent it
138 GVNPRE::Expression GVNPRE::buildExpression(ValueTable& VN, Value* V) {
139 if (Instruction* I = dyn_cast<Instruction>(V)) {
142 switch (I->getOpcode()) {
153 e.opcode = 4; // UDIV
156 e.opcode = 5; // SDIV
159 e.opcode = 6; // FDIV
162 e.opcode = 7; // UREM
165 e.opcode = 8; // SREM
168 e.opcode = 9; // FREM
171 e.opcode = 0; // OPAQUE
180 ValueTable::iterator lhs = lookup(VN, I->getOperand(0));
181 if (lhs == VN.end()) {
182 Expression lhsExp = buildExpression(VN, I->getOperand(0));
183 VN.insert(std::make_pair(lhsExp, nextValueNumber));
184 e.lhs = nextValueNumber;
188 ValueTable::iterator rhs = lookup(VN, I->getOperand(1));
189 if (rhs == VN.end()) {
190 Expression rhsExp = buildExpression(VN, I->getOperand(1));
191 VN.insert(std::make_pair(rhsExp, nextValueNumber));
192 e.rhs = nextValueNumber;
209 GVNPRE::Expression GVNPRE::add(ValueTable& VN, std::set<Expression>& MS,
211 Expression e = buildExpression(VN, V);
212 if (VN.insert(std::make_pair(e, nextValueNumber)).second)
214 if (e.opcode != 0 || (e.opcode == 0 && isa<PHINode>(e.value)))
219 GVNPRE::ValueTable::iterator GVNPRE::lookup(ValueTable& VN, Value* V) {
220 Expression e = buildExpression(VN, V);
224 std::set<GVNPRE::Expression>::iterator GVNPRE::find_leader(GVNPRE::ValueTable VN,
225 std::set<GVNPRE::Expression>& vals,
227 for (std::set<Expression>::iterator I = vals.begin(), E = vals.end();
235 void GVNPRE::phi_translate(GVNPRE::ValueTable& VN,
236 std::set<GVNPRE::Expression>& anticIn, BasicBlock* B,
237 std::set<GVNPRE::Expression>& out) {
238 BasicBlock* succ = B->getTerminator()->getSuccessor(0);
240 for (std::set<Expression>::iterator I = anticIn.begin(), E = anticIn.end();
242 if (I->opcode == 0) {
244 if (PHINode* p = dyn_cast<PHINode>(v))
245 if (p->getParent() == succ) {
246 out.insert(buildExpression(VN, p->getIncomingValueForBlock(B)));
254 // Remove all expressions whose operands are not themselves in the set
255 void GVNPRE::clean(GVNPRE::ValueTable VN, std::set<GVNPRE::Expression>& set) {
256 unsigned size = set.size();
259 while (size != old) {
262 std::vector<Expression> worklist(set.begin(), set.end());
263 while (!worklist.empty()) {
264 Expression e = worklist.back();
267 if (e.opcode == 0) // OPAQUE
270 bool lhsValid = false;
271 for (std::set<Expression>::iterator I = set.begin(), E = set.end();
273 if (VN[*I] == e.lhs);
276 bool rhsValid = false;
277 for (std::set<Expression>::iterator I = set.begin(), E = set.end();
279 if (VN[*I] == e.rhs);
282 if (!lhsValid || !rhsValid)
290 void GVNPRE::dump(GVNPRE::ValueTable& VN, std::set<GVNPRE::Expression>& s) {
292 for (std::set<Expression>::iterator I = s.begin(), E = s.end(); I != E; ++I) {
293 printf("(%d, %s, value.%d, value.%d) ", I->opcode, I->value == 0 ? "0" : I->value->getName().c_str(), I->lhs, I->rhs);
298 void GVNPRE::CalculateAvailOut(GVNPRE::ValueTable& VN, std::set<Expression>& MS,
299 DominatorTree::Node* DI,
300 std::set<Expression>& currExps,
301 std::set<PHINode*>& currPhis,
302 std::set<Expression>& currTemps,
303 std::set<Expression>& currAvail,
304 std::map<BasicBlock*, std::set<Expression> > availOut) {
306 BasicBlock* BB = DI->getBlock();
308 // A block inherits AVAIL_OUT from its dominator
309 if (DI->getIDom() != 0)
310 currAvail.insert(availOut[DI->getIDom()->getBlock()].begin(),
311 availOut[DI->getIDom()->getBlock()].end());
314 for (BasicBlock::iterator BI = BB->begin(), BE = BB->end();
317 // Handle PHI nodes...
318 if (PHINode* p = dyn_cast<PHINode>(BI)) {
322 // Handle binary ops...
323 } else if (BinaryOperator* BO = dyn_cast<BinaryOperator>(BI)) {
324 Expression leftValue = buildExpression(VN, BO->getOperand(0));
325 Expression rightValue = buildExpression(VN, BO->getOperand(1));
327 Expression e = add(VN, MS, BO);
329 currExps.insert(leftValue);
330 currExps.insert(rightValue);
335 // Handle unsupported ops
337 Expression e = add(VN, MS, BI);
341 currAvail.insert(buildExpression(VN, BI));
345 bool GVNPRE::runOnFunction(Function &F) {
347 std::set<Expression> maximalSet;
349 std::map<BasicBlock*, std::set<Expression> > generatedExpressions;
350 std::map<BasicBlock*, std::set<PHINode*> > generatedPhis;
351 std::map<BasicBlock*, std::set<Expression> > generatedTemporaries;
352 std::map<BasicBlock*, std::set<Expression> > availableOut;
353 std::map<BasicBlock*, std::set<Expression> > anticipatedIn;
355 DominatorTree &DT = getAnalysis<DominatorTree>();
357 // First Phase of BuildSets - calculate AVAIL_OUT
359 // Top-down walk of the dominator tree
360 for (df_iterator<DominatorTree::Node*> DI = df_begin(DT.getRootNode()),
361 E = df_end(DT.getRootNode()); DI != E; ++DI) {
363 // Get the sets to update for this block
364 std::set<Expression>& currExps = generatedExpressions[DI->getBlock()];
365 std::set<PHINode*>& currPhis = generatedPhis[DI->getBlock()];
366 std::set<Expression>& currTemps = generatedTemporaries[DI->getBlock()];
367 std::set<Expression>& currAvail = availableOut[DI->getBlock()];
369 CalculateAvailOut(VN, maximalSet, *DI, currExps, currPhis,
370 currTemps, currAvail, availableOut);
373 PostDominatorTree &PDT = getAnalysis<PostDominatorTree>();
375 // Second Phase of BuildSets - calculate ANTIC_IN
378 unsigned iterations = 0;
381 std::set<Expression> anticOut;
383 // Top-down walk of the postdominator tree
384 for (df_iterator<PostDominatorTree::Node*> PDI =
385 df_begin(PDT.getRootNode()), E = df_end(DT.getRootNode());
387 BasicBlock* BB = PDI->getBlock();
389 std::set<Expression>& anticIn = anticipatedIn[BB];
390 std::set<Expression> old (anticIn.begin(), anticIn.end());
392 if (BB->getTerminator()->getNumSuccessors() == 1) {
393 phi_translate(VN, anticIn, BB, anticOut);
394 } else if (BB->getTerminator()->getNumSuccessors() > 1) {
395 for (unsigned i = 0; i < BB->getTerminator()->getNumSuccessors(); ++i) {
396 BasicBlock* currSucc = BB->getTerminator()->getSuccessor(i);
397 std::set<Expression> temp;
399 temp.insert(maximalSet.begin(), maximalSet.end());
401 temp.insert(anticIn.begin(), anticIn.end());
404 std::insert_iterator<std::set<Expression> > ai_ins(anticIn,
407 std::set_difference(anticipatedIn[currSucc].begin(),
408 anticipatedIn[currSucc].end(),
415 std::set<Expression> S;
416 std::insert_iterator<std::set<Expression> > s_ins(S, S.begin());
417 std::set_union(anticOut.begin(), anticOut.end(),
418 generatedExpressions[BB].begin(),
419 generatedExpressions[BB].end(),
423 std::insert_iterator<std::set<Expression> > antic_ins(anticIn,
425 std::set_difference(S.begin(), S.end(),
426 generatedTemporaries[BB].begin(),
427 generatedTemporaries[BB].end(),
442 /* printf("Iterations: %d\n", iterations);
444 for (Function::iterator I = F.begin(), E = F.end(); I != E; ++I) {
446 printf(I->getName().c_str());
447 printf("\nTMP_GEN: ");
448 dump(VN, generatedTemporaries[I]);
449 printf("\nEXP_GEN: ");
450 dump(VN, generatedExpressions[I]);
451 //printf("\nANTIC_OUT: ");
452 //dump(VN, anticipatedOut[I]);
453 printf("\nANTIC_IN: \n");
454 dump(VN, anticipatedIn[I]);