1 //===- SCCVN.cpp - Eliminate redundant values -----------------------------===//
3 // The LLVM Compiler Infrastructure
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
8 //===----------------------------------------------------------------------===//
10 // This pass performs global value numbering to eliminate fully redundant
11 // instructions. This is based on the paper "SCC-based Value Numbering"
14 //===----------------------------------------------------------------------===//
16 #define DEBUG_TYPE "sccvn"
17 #include "llvm/Transforms/Scalar.h"
18 #include "llvm/BasicBlock.h"
19 #include "llvm/Constants.h"
20 #include "llvm/DerivedTypes.h"
21 #include "llvm/Function.h"
22 #include "llvm/Operator.h"
23 #include "llvm/Value.h"
24 #include "llvm/ADT/DenseMap.h"
25 #include "llvm/ADT/DepthFirstIterator.h"
26 #include "llvm/ADT/PostOrderIterator.h"
27 #include "llvm/ADT/SmallPtrSet.h"
28 #include "llvm/ADT/SmallVector.h"
29 #include "llvm/ADT/SparseBitVector.h"
30 #include "llvm/ADT/Statistic.h"
31 #include "llvm/Analysis/Dominators.h"
32 #include "llvm/Support/CFG.h"
33 #include "llvm/Support/CommandLine.h"
34 #include "llvm/Support/Debug.h"
35 #include "llvm/Support/ErrorHandling.h"
36 #include "llvm/Transforms/Utils/SSAUpdater.h"
39 STATISTIC(NumSCCVNInstr, "Number of instructions deleted by SCCVN");
40 STATISTIC(NumSCCVNPhi, "Number of phis deleted by SCCVN");
42 //===----------------------------------------------------------------------===//
44 //===----------------------------------------------------------------------===//
46 /// This class holds the mapping between values and value numbers. It is used
47 /// as an efficient mechanism to determine the expression-wise equivalence of
51 enum ExpressionOpcode { ADD, FADD, SUB, FSUB, MUL, FMUL,
52 UDIV, SDIV, FDIV, UREM, SREM,
53 FREM, SHL, LSHR, ASHR, AND, OR, XOR, ICMPEQ,
54 ICMPNE, ICMPUGT, ICMPUGE, ICMPULT, ICMPULE,
55 ICMPSGT, ICMPSGE, ICMPSLT, ICMPSLE, FCMPOEQ,
56 FCMPOGT, FCMPOGE, FCMPOLT, FCMPOLE, FCMPONE,
57 FCMPORD, FCMPUNO, FCMPUEQ, FCMPUGT, FCMPUGE,
58 FCMPULT, FCMPULE, FCMPUNE, EXTRACT, INSERT,
59 SHUFFLE, SELECT, TRUNC, ZEXT, SEXT, FPTOUI,
60 FPTOSI, UITOFP, SITOFP, FPTRUNC, FPEXT,
61 PTRTOINT, INTTOPTR, BITCAST, GEP, CALL, CONSTANT,
62 INSERTVALUE, EXTRACTVALUE, EMPTY, TOMBSTONE };
64 ExpressionOpcode opcode;
66 SmallVector<uint32_t, 4> varargs;
69 Expression(ExpressionOpcode o) : opcode(o) { }
71 bool operator==(const Expression &other) const {
72 if (opcode != other.opcode)
74 else if (opcode == EMPTY || opcode == TOMBSTONE)
76 else if (type != other.type)
79 if (varargs.size() != other.varargs.size())
82 for (size_t i = 0; i < varargs.size(); ++i)
83 if (varargs[i] != other.varargs[i])
90 bool operator!=(const Expression &other) const {
91 return !(*this == other);
97 DenseMap<Value*, uint32_t> valueNumbering;
98 DenseMap<Expression, uint32_t> expressionNumbering;
99 DenseMap<Value*, uint32_t> constantsNumbering;
101 uint32_t nextValueNumber;
103 Expression::ExpressionOpcode getOpcode(BinaryOperator* BO);
104 Expression::ExpressionOpcode getOpcode(CmpInst* C);
105 Expression::ExpressionOpcode getOpcode(CastInst* C);
106 Expression create_expression(BinaryOperator* BO);
107 Expression create_expression(CmpInst* C);
108 Expression create_expression(ShuffleVectorInst* V);
109 Expression create_expression(ExtractElementInst* C);
110 Expression create_expression(InsertElementInst* V);
111 Expression create_expression(SelectInst* V);
112 Expression create_expression(CastInst* C);
113 Expression create_expression(GetElementPtrInst* G);
114 Expression create_expression(CallInst* C);
115 Expression create_expression(Constant* C);
116 Expression create_expression(ExtractValueInst* C);
117 Expression create_expression(InsertValueInst* C);
119 ValueTable() : nextValueNumber(1) { }
120 uint32_t computeNumber(Value *V);
121 uint32_t lookup(Value *V);
122 void add(Value *V, uint32_t num);
124 void clearExpressions();
125 void erase(Value *v);
127 void verifyRemoved(const Value *) const;
132 template <> struct DenseMapInfo<Expression> {
133 static inline Expression getEmptyKey() {
134 return Expression(Expression::EMPTY);
137 static inline Expression getTombstoneKey() {
138 return Expression(Expression::TOMBSTONE);
141 static unsigned getHashValue(const Expression e) {
142 unsigned hash = e.opcode;
144 hash = ((unsigned)((uintptr_t)e.type >> 4) ^
145 (unsigned)((uintptr_t)e.type >> 9));
147 for (SmallVector<uint32_t, 4>::const_iterator I = e.varargs.begin(),
148 E = e.varargs.end(); I != E; ++I)
149 hash = *I + hash * 37;
153 static bool isEqual(const Expression &LHS, const Expression &RHS) {
158 struct isPodLike<Expression> { static const bool value = true; };
162 //===----------------------------------------------------------------------===//
163 // ValueTable Internal Functions
164 //===----------------------------------------------------------------------===//
165 Expression::ExpressionOpcode ValueTable::getOpcode(BinaryOperator* BO) {
166 switch(BO->getOpcode()) {
167 default: // THIS SHOULD NEVER HAPPEN
168 llvm_unreachable("Binary operator with unknown opcode?");
169 case Instruction::Add: return Expression::ADD;
170 case Instruction::FAdd: return Expression::FADD;
171 case Instruction::Sub: return Expression::SUB;
172 case Instruction::FSub: return Expression::FSUB;
173 case Instruction::Mul: return Expression::MUL;
174 case Instruction::FMul: return Expression::FMUL;
175 case Instruction::UDiv: return Expression::UDIV;
176 case Instruction::SDiv: return Expression::SDIV;
177 case Instruction::FDiv: return Expression::FDIV;
178 case Instruction::URem: return Expression::UREM;
179 case Instruction::SRem: return Expression::SREM;
180 case Instruction::FRem: return Expression::FREM;
181 case Instruction::Shl: return Expression::SHL;
182 case Instruction::LShr: return Expression::LSHR;
183 case Instruction::AShr: return Expression::ASHR;
184 case Instruction::And: return Expression::AND;
185 case Instruction::Or: return Expression::OR;
186 case Instruction::Xor: return Expression::XOR;
190 Expression::ExpressionOpcode ValueTable::getOpcode(CmpInst* C) {
191 if (isa<ICmpInst>(C)) {
192 switch (C->getPredicate()) {
193 default: // THIS SHOULD NEVER HAPPEN
194 llvm_unreachable("Comparison with unknown predicate?");
195 case ICmpInst::ICMP_EQ: return Expression::ICMPEQ;
196 case ICmpInst::ICMP_NE: return Expression::ICMPNE;
197 case ICmpInst::ICMP_UGT: return Expression::ICMPUGT;
198 case ICmpInst::ICMP_UGE: return Expression::ICMPUGE;
199 case ICmpInst::ICMP_ULT: return Expression::ICMPULT;
200 case ICmpInst::ICMP_ULE: return Expression::ICMPULE;
201 case ICmpInst::ICMP_SGT: return Expression::ICMPSGT;
202 case ICmpInst::ICMP_SGE: return Expression::ICMPSGE;
203 case ICmpInst::ICMP_SLT: return Expression::ICMPSLT;
204 case ICmpInst::ICMP_SLE: return Expression::ICMPSLE;
207 switch (C->getPredicate()) {
208 default: // THIS SHOULD NEVER HAPPEN
209 llvm_unreachable("Comparison with unknown predicate?");
210 case FCmpInst::FCMP_OEQ: return Expression::FCMPOEQ;
211 case FCmpInst::FCMP_OGT: return Expression::FCMPOGT;
212 case FCmpInst::FCMP_OGE: return Expression::FCMPOGE;
213 case FCmpInst::FCMP_OLT: return Expression::FCMPOLT;
214 case FCmpInst::FCMP_OLE: return Expression::FCMPOLE;
215 case FCmpInst::FCMP_ONE: return Expression::FCMPONE;
216 case FCmpInst::FCMP_ORD: return Expression::FCMPORD;
217 case FCmpInst::FCMP_UNO: return Expression::FCMPUNO;
218 case FCmpInst::FCMP_UEQ: return Expression::FCMPUEQ;
219 case FCmpInst::FCMP_UGT: return Expression::FCMPUGT;
220 case FCmpInst::FCMP_UGE: return Expression::FCMPUGE;
221 case FCmpInst::FCMP_ULT: return Expression::FCMPULT;
222 case FCmpInst::FCMP_ULE: return Expression::FCMPULE;
223 case FCmpInst::FCMP_UNE: return Expression::FCMPUNE;
228 Expression::ExpressionOpcode ValueTable::getOpcode(CastInst* C) {
229 switch(C->getOpcode()) {
230 default: // THIS SHOULD NEVER HAPPEN
231 llvm_unreachable("Cast operator with unknown opcode?");
232 case Instruction::Trunc: return Expression::TRUNC;
233 case Instruction::ZExt: return Expression::ZEXT;
234 case Instruction::SExt: return Expression::SEXT;
235 case Instruction::FPToUI: return Expression::FPTOUI;
236 case Instruction::FPToSI: return Expression::FPTOSI;
237 case Instruction::UIToFP: return Expression::UITOFP;
238 case Instruction::SIToFP: return Expression::SITOFP;
239 case Instruction::FPTrunc: return Expression::FPTRUNC;
240 case Instruction::FPExt: return Expression::FPEXT;
241 case Instruction::PtrToInt: return Expression::PTRTOINT;
242 case Instruction::IntToPtr: return Expression::INTTOPTR;
243 case Instruction::BitCast: return Expression::BITCAST;
247 Expression ValueTable::create_expression(CallInst* C) {
250 e.type = C->getType();
251 e.opcode = Expression::CALL;
253 e.varargs.push_back(lookup(C->getCalledFunction()));
254 for (CallInst::op_iterator I = C->op_begin()+1, E = C->op_end();
256 e.varargs.push_back(lookup(*I));
261 Expression ValueTable::create_expression(BinaryOperator* BO) {
263 e.varargs.push_back(lookup(BO->getOperand(0)));
264 e.varargs.push_back(lookup(BO->getOperand(1)));
265 e.type = BO->getType();
266 e.opcode = getOpcode(BO);
271 Expression ValueTable::create_expression(CmpInst* C) {
274 e.varargs.push_back(lookup(C->getOperand(0)));
275 e.varargs.push_back(lookup(C->getOperand(1)));
276 e.type = C->getType();
277 e.opcode = getOpcode(C);
282 Expression ValueTable::create_expression(CastInst* C) {
285 e.varargs.push_back(lookup(C->getOperand(0)));
286 e.type = C->getType();
287 e.opcode = getOpcode(C);
292 Expression ValueTable::create_expression(ShuffleVectorInst* S) {
295 e.varargs.push_back(lookup(S->getOperand(0)));
296 e.varargs.push_back(lookup(S->getOperand(1)));
297 e.varargs.push_back(lookup(S->getOperand(2)));
298 e.type = S->getType();
299 e.opcode = Expression::SHUFFLE;
304 Expression ValueTable::create_expression(ExtractElementInst* E) {
307 e.varargs.push_back(lookup(E->getOperand(0)));
308 e.varargs.push_back(lookup(E->getOperand(1)));
309 e.type = E->getType();
310 e.opcode = Expression::EXTRACT;
315 Expression ValueTable::create_expression(InsertElementInst* I) {
318 e.varargs.push_back(lookup(I->getOperand(0)));
319 e.varargs.push_back(lookup(I->getOperand(1)));
320 e.varargs.push_back(lookup(I->getOperand(2)));
321 e.type = I->getType();
322 e.opcode = Expression::INSERT;
327 Expression ValueTable::create_expression(SelectInst* I) {
330 e.varargs.push_back(lookup(I->getCondition()));
331 e.varargs.push_back(lookup(I->getTrueValue()));
332 e.varargs.push_back(lookup(I->getFalseValue()));
333 e.type = I->getType();
334 e.opcode = Expression::SELECT;
339 Expression ValueTable::create_expression(GetElementPtrInst* G) {
342 e.varargs.push_back(lookup(G->getPointerOperand()));
343 e.type = G->getType();
344 e.opcode = Expression::GEP;
346 for (GetElementPtrInst::op_iterator I = G->idx_begin(), E = G->idx_end();
348 e.varargs.push_back(lookup(*I));
353 Expression ValueTable::create_expression(ExtractValueInst* E) {
356 e.varargs.push_back(lookup(E->getAggregateOperand()));
357 for (ExtractValueInst::idx_iterator II = E->idx_begin(), IE = E->idx_end();
359 e.varargs.push_back(*II);
360 e.type = E->getType();
361 e.opcode = Expression::EXTRACTVALUE;
366 Expression ValueTable::create_expression(InsertValueInst* E) {
369 e.varargs.push_back(lookup(E->getAggregateOperand()));
370 e.varargs.push_back(lookup(E->getInsertedValueOperand()));
371 for (InsertValueInst::idx_iterator II = E->idx_begin(), IE = E->idx_end();
373 e.varargs.push_back(*II);
374 e.type = E->getType();
375 e.opcode = Expression::INSERTVALUE;
380 //===----------------------------------------------------------------------===//
381 // ValueTable External Functions
382 //===----------------------------------------------------------------------===//
384 /// add - Insert a value into the table with a specified value number.
385 void ValueTable::add(Value *V, uint32_t num) {
386 valueNumbering[V] = num;
389 /// computeNumber - Returns the value number for the specified value, assigning
390 /// it a new number if it did not have one before.
391 uint32_t ValueTable::computeNumber(Value *V) {
392 if (uint32_t v = valueNumbering[V])
394 else if (uint32_t v= constantsNumbering[V])
397 if (!isa<Instruction>(V)) {
398 constantsNumbering[V] = nextValueNumber;
399 return nextValueNumber++;
402 Instruction* I = cast<Instruction>(V);
404 switch (I->getOpcode()) {
405 case Instruction::Add:
406 case Instruction::FAdd:
407 case Instruction::Sub:
408 case Instruction::FSub:
409 case Instruction::Mul:
410 case Instruction::FMul:
411 case Instruction::UDiv:
412 case Instruction::SDiv:
413 case Instruction::FDiv:
414 case Instruction::URem:
415 case Instruction::SRem:
416 case Instruction::FRem:
417 case Instruction::Shl:
418 case Instruction::LShr:
419 case Instruction::AShr:
420 case Instruction::And:
421 case Instruction::Or :
422 case Instruction::Xor:
423 exp = create_expression(cast<BinaryOperator>(I));
425 case Instruction::ICmp:
426 case Instruction::FCmp:
427 exp = create_expression(cast<CmpInst>(I));
429 case Instruction::Trunc:
430 case Instruction::ZExt:
431 case Instruction::SExt:
432 case Instruction::FPToUI:
433 case Instruction::FPToSI:
434 case Instruction::UIToFP:
435 case Instruction::SIToFP:
436 case Instruction::FPTrunc:
437 case Instruction::FPExt:
438 case Instruction::PtrToInt:
439 case Instruction::IntToPtr:
440 case Instruction::BitCast:
441 exp = create_expression(cast<CastInst>(I));
443 case Instruction::Select:
444 exp = create_expression(cast<SelectInst>(I));
446 case Instruction::ExtractElement:
447 exp = create_expression(cast<ExtractElementInst>(I));
449 case Instruction::InsertElement:
450 exp = create_expression(cast<InsertElementInst>(I));
452 case Instruction::ShuffleVector:
453 exp = create_expression(cast<ShuffleVectorInst>(I));
455 case Instruction::ExtractValue:
456 exp = create_expression(cast<ExtractValueInst>(I));
458 case Instruction::InsertValue:
459 exp = create_expression(cast<InsertValueInst>(I));
461 case Instruction::GetElementPtr:
462 exp = create_expression(cast<GetElementPtrInst>(I));
465 valueNumbering[V] = nextValueNumber;
466 return nextValueNumber++;
469 uint32_t& e = expressionNumbering[exp];
470 if (!e) e = nextValueNumber++;
471 valueNumbering[V] = e;
476 /// lookup - Returns the value number of the specified value. Returns 0 if
477 /// the value has not yet been numbered.
478 uint32_t ValueTable::lookup(Value *V) {
479 if (!isa<Instruction>(V)) {
480 if (!constantsNumbering.count(V))
481 constantsNumbering[V] = nextValueNumber++;
482 return constantsNumbering[V];
485 return valueNumbering[V];
488 /// clear - Remove all entries from the ValueTable
489 void ValueTable::clear() {
490 valueNumbering.clear();
491 expressionNumbering.clear();
492 constantsNumbering.clear();
496 void ValueTable::clearExpressions() {
497 expressionNumbering.clear();
498 constantsNumbering.clear();
502 /// erase - Remove a value from the value numbering
503 void ValueTable::erase(Value *V) {
504 valueNumbering.erase(V);
507 /// verifyRemoved - Verify that the value is removed from all internal data
509 void ValueTable::verifyRemoved(const Value *V) const {
510 for (DenseMap<Value*, uint32_t>::const_iterator
511 I = valueNumbering.begin(), E = valueNumbering.end(); I != E; ++I) {
512 assert(I->first != V && "Inst still occurs in value numbering map!");
516 //===----------------------------------------------------------------------===//
518 //===----------------------------------------------------------------------===//
522 struct ValueNumberScope {
523 ValueNumberScope* parent;
524 DenseMap<uint32_t, Value*> table;
525 SparseBitVector<128> availIn;
526 SparseBitVector<128> availOut;
528 ValueNumberScope(ValueNumberScope* p) : parent(p) { }
531 class SCCVN : public FunctionPass {
532 bool runOnFunction(Function &F);
534 static char ID; // Pass identification, replacement for typeid
535 SCCVN() : FunctionPass(&ID) { }
539 DenseMap<BasicBlock*, ValueNumberScope*> BBMap;
541 // This transformation requires dominator postdominator info
542 virtual void getAnalysisUsage(AnalysisUsage &AU) const {
543 AU.addRequired<DominatorTree>();
545 AU.addPreserved<DominatorTree>();
546 AU.setPreservesCFG();
553 // createSCCVNPass - The public interface to this file...
554 FunctionPass *llvm::createSCCVNPass() { return new SCCVN(); }
556 static RegisterPass<SCCVN> X("sccvn",
557 "SCC Value Numbering");
559 static Value *lookupNumber(ValueNumberScope *Locals, uint32_t num) {
561 DenseMap<uint32_t, Value*>::iterator I = Locals->table.find(num);
562 if (I != Locals->table.end())
564 Locals = Locals->parent;
570 bool SCCVN::runOnFunction(Function& F) {
571 // Implement the RPO version of the SCCVN algorithm. Conceptually,
572 // we optimisitically assume that all instructions with the same opcode have
573 // the same VN. Then we deepen our comparison by one level, to all
574 // instructions whose operands have the same opcodes get the same VN. We
575 // iterate this process until the partitioning stops changing, at which
576 // point we have computed a full numbering.
577 ReversePostOrderTraversal<Function*> RPOT(&F);
581 VT.clearExpressions();
582 for (ReversePostOrderTraversal<Function*>::rpo_iterator I = RPOT.begin(),
583 E = RPOT.end(); I != E; ++I) {
585 for (BasicBlock::iterator BI = BB->begin(), BE = BB->end();
587 uint32_t origVN = VT.lookup(BI);
588 uint32_t newVN = VT.computeNumber(BI);
595 // Now, do a dominator walk, eliminating simple, dominated redundancies as we
596 // go. Also, build the ValueNumberScope structure that will be used for
597 // computing full availability.
598 DominatorTree& DT = getAnalysis<DominatorTree>();
599 bool changed = false;
600 for (df_iterator<DomTreeNode*> DI = df_begin(DT.getRootNode()),
601 DE = df_end(DT.getRootNode()); DI != DE; ++DI) {
602 BasicBlock* BB = DI->getBlock();
604 BBMap[BB] = new ValueNumberScope(BBMap[DI->getIDom()->getBlock()]);
606 BBMap[BB] = new ValueNumberScope(0);
608 for (BasicBlock::iterator I = BB->begin(), E = BB->end(); I != E; ) {
609 uint32_t num = VT.lookup(I);
610 Value* repl = lookupNumber(BBMap[BB], num);
617 I->replaceAllUsesWith(repl);
618 Instruction* OldInst = I;
620 BBMap[BB]->table[num] = repl;
621 OldInst->eraseFromParent();
624 BBMap[BB]->table[num] = I;
625 BBMap[BB]->availOut.set(num);
632 // Perform a forward data-flow to compute availability at all points on
636 for (ReversePostOrderTraversal<Function*>::rpo_iterator I = RPOT.begin(),
637 E = RPOT.end(); I != E; ++I) {
639 ValueNumberScope *VNS = BBMap[BB];
641 SparseBitVector<128> preds;
643 for (pred_iterator PI = pred_begin(BB), PE = pred_end(BB);
646 preds = BBMap[*PI]->availOut;
649 preds &= BBMap[*PI]->availOut;
653 changed |= (VNS->availIn |= preds);
654 changed |= (VNS->availOut |= preds);
658 // Use full availability information to perform non-dominated replacements.
660 for (Function::iterator FI = F.begin(), FE = F.end(); FI != FE; ++FI) {
661 if (!BBMap.count(FI)) continue;
662 for (BasicBlock::iterator BI = FI->begin(), BE = FI->end();
664 uint32_t num = VT.lookup(BI);
665 if (!BBMap[FI]->availIn.test(num)) {
672 SmallPtrSet<BasicBlock*, 8> visited;
673 SmallVector<BasicBlock*, 8> stack;
675 for (pred_iterator PI = pred_begin(FI), PE = pred_end(FI);
677 if (!visited.count(*PI))
678 stack.push_back(*PI);
680 while (!stack.empty()) {
681 BasicBlock* CurrBB = stack.pop_back_val();
682 visited.insert(CurrBB);
684 ValueNumberScope* S = BBMap[CurrBB];
685 if (S->table.count(num)) {
686 SSU.AddAvailableValue(CurrBB, S->table[num]);
688 for (pred_iterator PI = pred_begin(CurrBB), PE = pred_end(CurrBB);
690 if (!visited.count(*PI))
691 stack.push_back(*PI);
695 Value* repl = SSU.GetValueInMiddleOfBlock(FI);
696 BI->replaceAllUsesWith(repl);
697 Instruction* CurInst = BI;
699 BBMap[FI]->table[num] = repl;
700 if (isa<PHINode>(CurInst))
705 CurInst->eraseFromParent();
710 for (DenseMap<BasicBlock*, ValueNumberScope*>::iterator
711 I = BBMap.begin(), E = BBMap.end(); I != E; ++I)