GVN.cpp revision d34ac6e7820c8c0ad7f5d5681bc1ecf8b52a2391
1//===- GVN.cpp - Eliminate redundant values and loads ------------===// 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// This pass performs global value numbering to eliminate fully redundant 11// instructions. It also performs simple dead load elimination. 12// 13// Note that this pass does the value numbering itself, it does not use the 14// ValueNumbering analysis passes. 15// 16//===----------------------------------------------------------------------===// 17 18#define DEBUG_TYPE "gvn" 19#include "llvm/Transforms/Scalar.h" 20#include "llvm/BasicBlock.h" 21#include "llvm/Constants.h" 22#include "llvm/DerivedTypes.h" 23#include "llvm/Function.h" 24#include "llvm/Instructions.h" 25#include "llvm/Value.h" 26#include "llvm/ADT/DenseMap.h" 27#include "llvm/ADT/DepthFirstIterator.h" 28#include "llvm/ADT/SmallPtrSet.h" 29#include "llvm/ADT/SmallVector.h" 30#include "llvm/ADT/Statistic.h" 31#include "llvm/Analysis/Dominators.h" 32#include "llvm/Analysis/AliasAnalysis.h" 33#include "llvm/Analysis/MemoryDependenceAnalysis.h" 34#include "llvm/Support/CFG.h" 35#include "llvm/Support/Compiler.h" 36#include "llvm/Support/Debug.h" 37using namespace llvm; 38 39STATISTIC(NumGVNInstr, "Number of instructions deleted"); 40STATISTIC(NumGVNLoad, "Number of loads deleted"); 41STATISTIC(NumGVNPRE, "Number of instructions PRE'd"); 42 43//===----------------------------------------------------------------------===// 44// ValueTable Class 45//===----------------------------------------------------------------------===// 46 47/// This class holds the mapping between values and value numbers. It is used 48/// as an efficient mechanism to determine the expression-wise equivalence of 49/// two values. 50namespace { 51 struct VISIBILITY_HIDDEN Expression { 52 enum ExpressionOpcode { ADD, SUB, MUL, 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 EXTRACTVALUE, INSERTVALUE, EMPTY, TOMBSTONE }; 63 64 ExpressionOpcode opcode; 65 const Type* type; 66 uint32_t firstVN; 67 uint32_t secondVN; 68 uint32_t thirdVN; 69 SmallVector<uint32_t, 4> varargs; 70 Value* function; 71 72 Expression() { } 73 Expression(ExpressionOpcode o) : opcode(o) { } 74 75 bool operator==(const Expression &other) const { 76 if (opcode != other.opcode) 77 return false; 78 else if (opcode == EMPTY || opcode == TOMBSTONE) 79 return true; 80 else if (type != other.type) 81 return false; 82 else if (function != other.function) 83 return false; 84 else if (firstVN != other.firstVN) 85 return false; 86 else if (secondVN != other.secondVN) 87 return false; 88 else if (thirdVN != other.thirdVN) 89 return false; 90 else { 91 if (varargs.size() != other.varargs.size()) 92 return false; 93 94 for (size_t i = 0; i < varargs.size(); ++i) 95 if (varargs[i] != other.varargs[i]) 96 return false; 97 98 return true; 99 } 100 } 101 102 bool operator!=(const Expression &other) const { 103 if (opcode != other.opcode) 104 return true; 105 else if (opcode == EMPTY || opcode == TOMBSTONE) 106 return false; 107 else if (type != other.type) 108 return true; 109 else if (function != other.function) 110 return true; 111 else if (firstVN != other.firstVN) 112 return true; 113 else if (secondVN != other.secondVN) 114 return true; 115 else if (thirdVN != other.thirdVN) 116 return true; 117 else { 118 if (varargs.size() != other.varargs.size()) 119 return true; 120 121 for (size_t i = 0; i < varargs.size(); ++i) 122 if (varargs[i] != other.varargs[i]) 123 return true; 124 125 return false; 126 } 127 } 128 }; 129 130 class VISIBILITY_HIDDEN ValueTable { 131 private: 132 DenseMap<Value*, uint32_t> valueNumbering; 133 DenseMap<Expression, uint32_t> expressionNumbering; 134 AliasAnalysis* AA; 135 MemoryDependenceAnalysis* MD; 136 DominatorTree* DT; 137 138 uint32_t nextValueNumber; 139 140 Expression::ExpressionOpcode getOpcode(BinaryOperator* BO); 141 Expression::ExpressionOpcode getOpcode(CmpInst* C); 142 Expression::ExpressionOpcode getOpcode(CastInst* C); 143 Expression create_expression(BinaryOperator* BO); 144 Expression create_expression(CmpInst* C); 145 Expression create_expression(ShuffleVectorInst* V); 146 Expression create_expression(ExtractElementInst* C); 147 Expression create_expression(InsertElementInst* V); 148 Expression create_expression(SelectInst* V); 149 Expression create_expression(CastInst* C); 150 Expression create_expression(GetElementPtrInst* G); 151 Expression create_expression(CallInst* C); 152 Expression create_expression(Constant* C); 153 Expression create_expression(InsertValueInst* I); 154 Expression create_expression(ExtractValueInst* I); 155 public: 156 ValueTable() : nextValueNumber(1) { } 157 uint32_t lookup_or_add(Value* V); 158 uint32_t lookup(Value* V) const; 159 void add(Value* V, uint32_t num); 160 void clear(); 161 void erase(Value* v); 162 unsigned size(); 163 void setAliasAnalysis(AliasAnalysis* A) { AA = A; } 164 void setMemDep(MemoryDependenceAnalysis* M) { MD = M; } 165 void setDomTree(DominatorTree* D) { DT = D; } 166 }; 167} 168 169namespace llvm { 170template <> struct DenseMapInfo<Expression> { 171 static inline Expression getEmptyKey() { 172 return Expression(Expression::EMPTY); 173 } 174 175 static inline Expression getTombstoneKey() { 176 return Expression(Expression::TOMBSTONE); 177 } 178 179 static unsigned getHashValue(const Expression e) { 180 unsigned hash = e.opcode; 181 182 hash = e.firstVN + hash * 37; 183 hash = e.secondVN + hash * 37; 184 hash = e.thirdVN + hash * 37; 185 186 hash = ((unsigned)((uintptr_t)e.type >> 4) ^ 187 (unsigned)((uintptr_t)e.type >> 9)) + 188 hash * 37; 189 190 for (SmallVector<uint32_t, 4>::const_iterator I = e.varargs.begin(), 191 E = e.varargs.end(); I != E; ++I) 192 hash = *I + hash * 37; 193 194 hash = ((unsigned)((uintptr_t)e.function >> 4) ^ 195 (unsigned)((uintptr_t)e.function >> 9)) + 196 hash * 37; 197 198 return hash; 199 } 200 static bool isEqual(const Expression &LHS, const Expression &RHS) { 201 return LHS == RHS; 202 } 203 static bool isPod() { return true; } 204}; 205} 206 207//===----------------------------------------------------------------------===// 208// ValueTable Internal Functions 209//===----------------------------------------------------------------------===// 210Expression::ExpressionOpcode ValueTable::getOpcode(BinaryOperator* BO) { 211 switch(BO->getOpcode()) { 212 default: // THIS SHOULD NEVER HAPPEN 213 assert(0 && "Binary operator with unknown opcode?"); 214 case Instruction::Add: return Expression::ADD; 215 case Instruction::Sub: return Expression::SUB; 216 case Instruction::Mul: return Expression::MUL; 217 case Instruction::UDiv: return Expression::UDIV; 218 case Instruction::SDiv: return Expression::SDIV; 219 case Instruction::FDiv: return Expression::FDIV; 220 case Instruction::URem: return Expression::UREM; 221 case Instruction::SRem: return Expression::SREM; 222 case Instruction::FRem: return Expression::FREM; 223 case Instruction::Shl: return Expression::SHL; 224 case Instruction::LShr: return Expression::LSHR; 225 case Instruction::AShr: return Expression::ASHR; 226 case Instruction::And: return Expression::AND; 227 case Instruction::Or: return Expression::OR; 228 case Instruction::Xor: return Expression::XOR; 229 } 230} 231 232Expression::ExpressionOpcode ValueTable::getOpcode(CmpInst* C) { 233 if (isa<ICmpInst>(C) || isa<VICmpInst>(C)) { 234 switch (C->getPredicate()) { 235 default: // THIS SHOULD NEVER HAPPEN 236 assert(0 && "Comparison with unknown predicate?"); 237 case ICmpInst::ICMP_EQ: return Expression::ICMPEQ; 238 case ICmpInst::ICMP_NE: return Expression::ICMPNE; 239 case ICmpInst::ICMP_UGT: return Expression::ICMPUGT; 240 case ICmpInst::ICMP_UGE: return Expression::ICMPUGE; 241 case ICmpInst::ICMP_ULT: return Expression::ICMPULT; 242 case ICmpInst::ICMP_ULE: return Expression::ICMPULE; 243 case ICmpInst::ICMP_SGT: return Expression::ICMPSGT; 244 case ICmpInst::ICMP_SGE: return Expression::ICMPSGE; 245 case ICmpInst::ICMP_SLT: return Expression::ICMPSLT; 246 case ICmpInst::ICMP_SLE: return Expression::ICMPSLE; 247 } 248 } 249 assert((isa<FCmpInst>(C) || isa<VFCmpInst>(C)) && "Unknown compare"); 250 switch (C->getPredicate()) { 251 default: // THIS SHOULD NEVER HAPPEN 252 assert(0 && "Comparison with unknown predicate?"); 253 case FCmpInst::FCMP_OEQ: return Expression::FCMPOEQ; 254 case FCmpInst::FCMP_OGT: return Expression::FCMPOGT; 255 case FCmpInst::FCMP_OGE: return Expression::FCMPOGE; 256 case FCmpInst::FCMP_OLT: return Expression::FCMPOLT; 257 case FCmpInst::FCMP_OLE: return Expression::FCMPOLE; 258 case FCmpInst::FCMP_ONE: return Expression::FCMPONE; 259 case FCmpInst::FCMP_ORD: return Expression::FCMPORD; 260 case FCmpInst::FCMP_UNO: return Expression::FCMPUNO; 261 case FCmpInst::FCMP_UEQ: return Expression::FCMPUEQ; 262 case FCmpInst::FCMP_UGT: return Expression::FCMPUGT; 263 case FCmpInst::FCMP_UGE: return Expression::FCMPUGE; 264 case FCmpInst::FCMP_ULT: return Expression::FCMPULT; 265 case FCmpInst::FCMP_ULE: return Expression::FCMPULE; 266 case FCmpInst::FCMP_UNE: return Expression::FCMPUNE; 267 } 268} 269 270Expression::ExpressionOpcode ValueTable::getOpcode(CastInst* C) { 271 switch(C->getOpcode()) { 272 default: // THIS SHOULD NEVER HAPPEN 273 assert(0 && "Cast operator with unknown opcode?"); 274 case Instruction::Trunc: return Expression::TRUNC; 275 case Instruction::ZExt: return Expression::ZEXT; 276 case Instruction::SExt: return Expression::SEXT; 277 case Instruction::FPToUI: return Expression::FPTOUI; 278 case Instruction::FPToSI: return Expression::FPTOSI; 279 case Instruction::UIToFP: return Expression::UITOFP; 280 case Instruction::SIToFP: return Expression::SITOFP; 281 case Instruction::FPTrunc: return Expression::FPTRUNC; 282 case Instruction::FPExt: return Expression::FPEXT; 283 case Instruction::PtrToInt: return Expression::PTRTOINT; 284 case Instruction::IntToPtr: return Expression::INTTOPTR; 285 case Instruction::BitCast: return Expression::BITCAST; 286 } 287} 288 289Expression ValueTable::create_expression(InsertValueInst* I) { 290 Expression e; 291 292 e.type = I->getType(); 293 e.firstVN = lookup_or_add(I->getOperand(0)); 294 e.secondVN = lookup_or_add(I->getOperand(1)); 295 e.thirdVN = 0; 296 e.function = 0; 297 e.opcode = Expression::INSERTVALUE; 298 299 for (InsertValueInst::op_iterator OI = I->op_begin()+2, 300 OE = I->op_end(); OI != OE; ++OI) 301 e.varargs.push_back(lookup_or_add(I)); 302 303 return e; 304} 305 306Expression ValueTable::create_expression(ExtractValueInst* I) { 307 Expression e; 308 309 e.type = I->getType(); 310 e.firstVN = lookup_or_add(I->getOperand(0)); 311 e.secondVN = lookup_or_add(I->getOperand(1)); 312 e.thirdVN = 0; 313 e.function = 0; 314 e.opcode = Expression::EXTRACTVALUE; 315 316 for (InsertValueInst::op_iterator OI = I->op_begin()+2, 317 OE = I->op_end(); OI != OE; ++OI) 318 e.varargs.push_back(lookup_or_add(I)); 319 320 return e; 321} 322 323Expression ValueTable::create_expression(CallInst* C) { 324 Expression e; 325 326 e.type = C->getType(); 327 e.firstVN = 0; 328 e.secondVN = 0; 329 e.thirdVN = 0; 330 e.function = C->getCalledFunction(); 331 e.opcode = Expression::CALL; 332 333 for (CallInst::op_iterator I = C->op_begin()+1, E = C->op_end(); 334 I != E; ++I) 335 e.varargs.push_back(lookup_or_add(*I)); 336 337 return e; 338} 339 340Expression ValueTable::create_expression(BinaryOperator* BO) { 341 Expression e; 342 343 e.firstVN = lookup_or_add(BO->getOperand(0)); 344 e.secondVN = lookup_or_add(BO->getOperand(1)); 345 e.thirdVN = 0; 346 e.function = 0; 347 e.type = BO->getType(); 348 e.opcode = getOpcode(BO); 349 350 return e; 351} 352 353Expression ValueTable::create_expression(CmpInst* C) { 354 Expression e; 355 356 e.firstVN = lookup_or_add(C->getOperand(0)); 357 e.secondVN = lookup_or_add(C->getOperand(1)); 358 e.thirdVN = 0; 359 e.function = 0; 360 e.type = C->getType(); 361 e.opcode = getOpcode(C); 362 363 return e; 364} 365 366Expression ValueTable::create_expression(CastInst* C) { 367 Expression e; 368 369 e.firstVN = lookup_or_add(C->getOperand(0)); 370 e.secondVN = 0; 371 e.thirdVN = 0; 372 e.function = 0; 373 e.type = C->getType(); 374 e.opcode = getOpcode(C); 375 376 return e; 377} 378 379Expression ValueTable::create_expression(ShuffleVectorInst* S) { 380 Expression e; 381 382 e.firstVN = lookup_or_add(S->getOperand(0)); 383 e.secondVN = lookup_or_add(S->getOperand(1)); 384 e.thirdVN = lookup_or_add(S->getOperand(2)); 385 e.function = 0; 386 e.type = S->getType(); 387 e.opcode = Expression::SHUFFLE; 388 389 return e; 390} 391 392Expression ValueTable::create_expression(ExtractElementInst* E) { 393 Expression e; 394 395 e.firstVN = lookup_or_add(E->getOperand(0)); 396 e.secondVN = lookup_or_add(E->getOperand(1)); 397 e.thirdVN = 0; 398 e.function = 0; 399 e.type = E->getType(); 400 e.opcode = Expression::EXTRACT; 401 402 return e; 403} 404 405Expression ValueTable::create_expression(InsertElementInst* I) { 406 Expression e; 407 408 e.firstVN = lookup_or_add(I->getOperand(0)); 409 e.secondVN = lookup_or_add(I->getOperand(1)); 410 e.thirdVN = lookup_or_add(I->getOperand(2)); 411 e.function = 0; 412 e.type = I->getType(); 413 e.opcode = Expression::INSERT; 414 415 return e; 416} 417 418Expression ValueTable::create_expression(SelectInst* I) { 419 Expression e; 420 421 e.firstVN = lookup_or_add(I->getCondition()); 422 e.secondVN = lookup_or_add(I->getTrueValue()); 423 e.thirdVN = lookup_or_add(I->getFalseValue()); 424 e.function = 0; 425 e.type = I->getType(); 426 e.opcode = Expression::SELECT; 427 428 return e; 429} 430 431Expression ValueTable::create_expression(GetElementPtrInst* G) { 432 Expression e; 433 434 e.firstVN = lookup_or_add(G->getPointerOperand()); 435 e.secondVN = 0; 436 e.thirdVN = 0; 437 e.function = 0; 438 e.type = G->getType(); 439 e.opcode = Expression::GEP; 440 441 for (GetElementPtrInst::op_iterator I = G->idx_begin(), E = G->idx_end(); 442 I != E; ++I) 443 e.varargs.push_back(lookup_or_add(*I)); 444 445 return e; 446} 447 448//===----------------------------------------------------------------------===// 449// ValueTable External Functions 450//===----------------------------------------------------------------------===// 451 452/// add - Insert a value into the table with a specified value number. 453void ValueTable::add(Value* V, uint32_t num) { 454 valueNumbering.insert(std::make_pair(V, num)); 455} 456 457/// lookup_or_add - Returns the value number for the specified value, assigning 458/// it a new number if it did not have one before. 459uint32_t ValueTable::lookup_or_add(Value* V) { 460 DenseMap<Value*, uint32_t>::iterator VI = valueNumbering.find(V); 461 if (VI != valueNumbering.end()) 462 return VI->second; 463 464 if (CallInst* C = dyn_cast<CallInst>(V)) { 465 if (AA->doesNotAccessMemory(C)) { 466 Expression e = create_expression(C); 467 468 DenseMap<Expression, uint32_t>::iterator EI = expressionNumbering.find(e); 469 if (EI != expressionNumbering.end()) { 470 valueNumbering.insert(std::make_pair(V, EI->second)); 471 return EI->second; 472 } else { 473 expressionNumbering.insert(std::make_pair(e, nextValueNumber)); 474 valueNumbering.insert(std::make_pair(V, nextValueNumber)); 475 476 return nextValueNumber++; 477 } 478 } else if (AA->onlyReadsMemory(C)) { 479 Expression e = create_expression(C); 480 481 if (expressionNumbering.find(e) == expressionNumbering.end()) { 482 expressionNumbering.insert(std::make_pair(e, nextValueNumber)); 483 valueNumbering.insert(std::make_pair(V, nextValueNumber)); 484 return nextValueNumber++; 485 } 486 487 Instruction* local_dep = MD->getDependency(C); 488 489 if (local_dep == MemoryDependenceAnalysis::None) { 490 valueNumbering.insert(std::make_pair(V, nextValueNumber)); 491 return nextValueNumber++; 492 } else if (local_dep != MemoryDependenceAnalysis::NonLocal) { 493 if (!isa<CallInst>(local_dep)) { 494 valueNumbering.insert(std::make_pair(V, nextValueNumber)); 495 return nextValueNumber++; 496 } 497 498 CallInst* local_cdep = cast<CallInst>(local_dep); 499 500 if (local_cdep->getCalledFunction() != C->getCalledFunction() || 501 local_cdep->getNumOperands() != C->getNumOperands()) { 502 valueNumbering.insert(std::make_pair(V, nextValueNumber)); 503 return nextValueNumber++; 504 } else if (!C->getCalledFunction()) { 505 valueNumbering.insert(std::make_pair(V, nextValueNumber)); 506 return nextValueNumber++; 507 } else { 508 for (unsigned i = 1; i < C->getNumOperands(); ++i) { 509 uint32_t c_vn = lookup_or_add(C->getOperand(i)); 510 uint32_t cd_vn = lookup_or_add(local_cdep->getOperand(i)); 511 if (c_vn != cd_vn) { 512 valueNumbering.insert(std::make_pair(V, nextValueNumber)); 513 return nextValueNumber++; 514 } 515 } 516 517 uint32_t v = lookup_or_add(local_cdep); 518 valueNumbering.insert(std::make_pair(V, v)); 519 return v; 520 } 521 } 522 523 524 DenseMap<BasicBlock*, Value*> deps; 525 MD->getNonLocalDependency(C, deps); 526 CallInst* cdep = 0; 527 528 for (DenseMap<BasicBlock*, Value*>::iterator I = deps.begin(), 529 E = deps.end(); I != E; ++I) { 530 if (I->second == MemoryDependenceAnalysis::None) { 531 valueNumbering.insert(std::make_pair(V, nextValueNumber)); 532 533 return nextValueNumber++; 534 } else if (I->second != MemoryDependenceAnalysis::NonLocal) { 535 if (DT->properlyDominates(I->first, C->getParent())) { 536 if (CallInst* CD = dyn_cast<CallInst>(I->second)) 537 cdep = CD; 538 else { 539 valueNumbering.insert(std::make_pair(V, nextValueNumber)); 540 return nextValueNumber++; 541 } 542 } else { 543 valueNumbering.insert(std::make_pair(V, nextValueNumber)); 544 return nextValueNumber++; 545 } 546 } 547 } 548 549 if (!cdep) { 550 valueNumbering.insert(std::make_pair(V, nextValueNumber)); 551 return nextValueNumber++; 552 } 553 554 if (cdep->getCalledFunction() != C->getCalledFunction() || 555 cdep->getNumOperands() != C->getNumOperands()) { 556 valueNumbering.insert(std::make_pair(V, nextValueNumber)); 557 return nextValueNumber++; 558 } else if (!C->getCalledFunction()) { 559 valueNumbering.insert(std::make_pair(V, nextValueNumber)); 560 return nextValueNumber++; 561 } else { 562 for (unsigned i = 1; i < C->getNumOperands(); ++i) { 563 uint32_t c_vn = lookup_or_add(C->getOperand(i)); 564 uint32_t cd_vn = lookup_or_add(cdep->getOperand(i)); 565 if (c_vn != cd_vn) { 566 valueNumbering.insert(std::make_pair(V, nextValueNumber)); 567 return nextValueNumber++; 568 } 569 } 570 571 uint32_t v = lookup_or_add(cdep); 572 valueNumbering.insert(std::make_pair(V, v)); 573 return v; 574 } 575 576 } else { 577 valueNumbering.insert(std::make_pair(V, nextValueNumber)); 578 return nextValueNumber++; 579 } 580 } else if (InsertValueInst* II = dyn_cast<InsertValueInst>(V)) { 581 Expression e = create_expression(II); 582 583 DenseMap<Expression, uint32_t>::iterator EI = expressionNumbering.find(e); 584 if (EI != expressionNumbering.end()) { 585 valueNumbering.insert(std::make_pair(V, EI->second)); 586 return EI->second; 587 } else { 588 expressionNumbering.insert(std::make_pair(e, nextValueNumber)); 589 valueNumbering.insert(std::make_pair(V, nextValueNumber)); 590 591 return nextValueNumber++; 592 } 593 } else if (ExtractValueInst* E = dyn_cast<ExtractValueInst>(V)) { 594 Expression e = create_expression(E); 595 596 DenseMap<Expression, uint32_t>::iterator EI = expressionNumbering.find(e); 597 if (EI != expressionNumbering.end()) { 598 valueNumbering.insert(std::make_pair(V, EI->second)); 599 return EI->second; 600 } else { 601 expressionNumbering.insert(std::make_pair(e, nextValueNumber)); 602 valueNumbering.insert(std::make_pair(V, nextValueNumber)); 603 604 return nextValueNumber++; 605 } 606 } else if (BinaryOperator* BO = dyn_cast<BinaryOperator>(V)) { 607 Expression e = create_expression(BO); 608 609 DenseMap<Expression, uint32_t>::iterator EI = expressionNumbering.find(e); 610 if (EI != expressionNumbering.end()) { 611 valueNumbering.insert(std::make_pair(V, EI->second)); 612 return EI->second; 613 } else { 614 expressionNumbering.insert(std::make_pair(e, nextValueNumber)); 615 valueNumbering.insert(std::make_pair(V, nextValueNumber)); 616 617 return nextValueNumber++; 618 } 619 } else if (CmpInst* C = dyn_cast<CmpInst>(V)) { 620 Expression e = create_expression(C); 621 622 DenseMap<Expression, uint32_t>::iterator EI = expressionNumbering.find(e); 623 if (EI != expressionNumbering.end()) { 624 valueNumbering.insert(std::make_pair(V, EI->second)); 625 return EI->second; 626 } else { 627 expressionNumbering.insert(std::make_pair(e, nextValueNumber)); 628 valueNumbering.insert(std::make_pair(V, nextValueNumber)); 629 630 return nextValueNumber++; 631 } 632 } else if (ShuffleVectorInst* U = dyn_cast<ShuffleVectorInst>(V)) { 633 Expression e = create_expression(U); 634 635 DenseMap<Expression, uint32_t>::iterator EI = expressionNumbering.find(e); 636 if (EI != expressionNumbering.end()) { 637 valueNumbering.insert(std::make_pair(V, EI->second)); 638 return EI->second; 639 } else { 640 expressionNumbering.insert(std::make_pair(e, nextValueNumber)); 641 valueNumbering.insert(std::make_pair(V, nextValueNumber)); 642 643 return nextValueNumber++; 644 } 645 } else if (ExtractElementInst* U = dyn_cast<ExtractElementInst>(V)) { 646 Expression e = create_expression(U); 647 648 DenseMap<Expression, uint32_t>::iterator EI = expressionNumbering.find(e); 649 if (EI != expressionNumbering.end()) { 650 valueNumbering.insert(std::make_pair(V, EI->second)); 651 return EI->second; 652 } else { 653 expressionNumbering.insert(std::make_pair(e, nextValueNumber)); 654 valueNumbering.insert(std::make_pair(V, nextValueNumber)); 655 656 return nextValueNumber++; 657 } 658 } else if (InsertElementInst* U = dyn_cast<InsertElementInst>(V)) { 659 Expression e = create_expression(U); 660 661 DenseMap<Expression, uint32_t>::iterator EI = expressionNumbering.find(e); 662 if (EI != expressionNumbering.end()) { 663 valueNumbering.insert(std::make_pair(V, EI->second)); 664 return EI->second; 665 } else { 666 expressionNumbering.insert(std::make_pair(e, nextValueNumber)); 667 valueNumbering.insert(std::make_pair(V, nextValueNumber)); 668 669 return nextValueNumber++; 670 } 671 } else if (SelectInst* U = dyn_cast<SelectInst>(V)) { 672 Expression e = create_expression(U); 673 674 DenseMap<Expression, uint32_t>::iterator EI = expressionNumbering.find(e); 675 if (EI != expressionNumbering.end()) { 676 valueNumbering.insert(std::make_pair(V, EI->second)); 677 return EI->second; 678 } else { 679 expressionNumbering.insert(std::make_pair(e, nextValueNumber)); 680 valueNumbering.insert(std::make_pair(V, nextValueNumber)); 681 682 return nextValueNumber++; 683 } 684 } else if (CastInst* U = dyn_cast<CastInst>(V)) { 685 Expression e = create_expression(U); 686 687 DenseMap<Expression, uint32_t>::iterator EI = expressionNumbering.find(e); 688 if (EI != expressionNumbering.end()) { 689 valueNumbering.insert(std::make_pair(V, EI->second)); 690 return EI->second; 691 } else { 692 expressionNumbering.insert(std::make_pair(e, nextValueNumber)); 693 valueNumbering.insert(std::make_pair(V, nextValueNumber)); 694 695 return nextValueNumber++; 696 } 697 } else if (GetElementPtrInst* U = dyn_cast<GetElementPtrInst>(V)) { 698 Expression e = create_expression(U); 699 700 DenseMap<Expression, uint32_t>::iterator EI = expressionNumbering.find(e); 701 if (EI != expressionNumbering.end()) { 702 valueNumbering.insert(std::make_pair(V, EI->second)); 703 return EI->second; 704 } else { 705 expressionNumbering.insert(std::make_pair(e, nextValueNumber)); 706 valueNumbering.insert(std::make_pair(V, nextValueNumber)); 707 708 return nextValueNumber++; 709 } 710 } else { 711 valueNumbering.insert(std::make_pair(V, nextValueNumber)); 712 return nextValueNumber++; 713 } 714} 715 716/// lookup - Returns the value number of the specified value. Fails if 717/// the value has not yet been numbered. 718uint32_t ValueTable::lookup(Value* V) const { 719 DenseMap<Value*, uint32_t>::iterator VI = valueNumbering.find(V); 720 assert(VI != valueNumbering.end() && "Value not numbered?"); 721 return VI->second; 722} 723 724/// clear - Remove all entries from the ValueTable 725void ValueTable::clear() { 726 valueNumbering.clear(); 727 expressionNumbering.clear(); 728 nextValueNumber = 1; 729} 730 731/// erase - Remove a value from the value numbering 732void ValueTable::erase(Value* V) { 733 valueNumbering.erase(V); 734} 735 736//===----------------------------------------------------------------------===// 737// GVN Pass 738//===----------------------------------------------------------------------===// 739 740namespace llvm { 741 template<> struct DenseMapInfo<uint32_t> { 742 static inline uint32_t getEmptyKey() { return ~0; } 743 static inline uint32_t getTombstoneKey() { return ~0 - 1; } 744 static unsigned getHashValue(const uint32_t& Val) { return Val * 37; } 745 static bool isPod() { return true; } 746 static bool isEqual(const uint32_t& LHS, const uint32_t& RHS) { 747 return LHS == RHS; 748 } 749 }; 750} 751 752namespace { 753 754 class VISIBILITY_HIDDEN GVN : public FunctionPass { 755 bool runOnFunction(Function &F); 756 public: 757 static char ID; // Pass identification, replacement for typeid 758 GVN() : FunctionPass((intptr_t)&ID) { } 759 760 private: 761 ValueTable VN; 762 DenseMap<BasicBlock*, DenseMap<uint32_t, Value*> > localAvail; 763 764 typedef DenseMap<Value*, SmallPtrSet<Instruction*, 4> > PhiMapType; 765 PhiMapType phiMap; 766 767 768 // This transformation requires dominator postdominator info 769 virtual void getAnalysisUsage(AnalysisUsage &AU) const { 770 AU.setPreservesCFG(); 771 AU.addRequired<DominatorTree>(); 772 AU.addRequired<MemoryDependenceAnalysis>(); 773 AU.addRequired<AliasAnalysis>(); 774 AU.addPreserved<AliasAnalysis>(); 775 AU.addPreserved<MemoryDependenceAnalysis>(); 776 } 777 778 // Helper fuctions 779 // FIXME: eliminate or document these better 780 bool processLoad(LoadInst* L, 781 DenseMap<Value*, LoadInst*> &lastLoad, 782 SmallVectorImpl<Instruction*> &toErase); 783 bool processInstruction(Instruction* I, 784 DenseMap<Value*, LoadInst*>& lastSeenLoad, 785 SmallVectorImpl<Instruction*> &toErase); 786 bool processNonLocalLoad(LoadInst* L, 787 SmallVectorImpl<Instruction*> &toErase); 788 bool processBlock(DomTreeNode* DTN); 789 Value *GetValueForBlock(BasicBlock *BB, LoadInst* orig, 790 DenseMap<BasicBlock*, Value*> &Phis, 791 bool top_level = false); 792 void dump(DenseMap<uint32_t, Value*>& d); 793 bool iterateOnFunction(Function &F); 794 Value* CollapsePhi(PHINode* p); 795 bool isSafeReplacement(PHINode* p, Instruction* inst); 796 bool performPRE(Function& F); 797 }; 798 799 char GVN::ID = 0; 800} 801 802// createGVNPass - The public interface to this file... 803FunctionPass *llvm::createGVNPass() { return new GVN(); } 804 805static RegisterPass<GVN> X("gvn", 806 "Global Value Numbering"); 807 808void GVN::dump(DenseMap<uint32_t, Value*>& d) { 809 printf("{\n"); 810 for (DenseMap<uint32_t, Value*>::iterator I = d.begin(), 811 E = d.end(); I != E; ++I) { 812 printf("%d\n", I->first); 813 I->second->dump(); 814 } 815 printf("}\n"); 816} 817 818Value* GVN::CollapsePhi(PHINode* p) { 819 DominatorTree &DT = getAnalysis<DominatorTree>(); 820 Value* constVal = p->hasConstantValue(); 821 822 if (!constVal) return 0; 823 824 Instruction* inst = dyn_cast<Instruction>(constVal); 825 if (!inst) 826 return constVal; 827 828 if (DT.dominates(inst, p)) 829 if (isSafeReplacement(p, inst)) 830 return inst; 831 return 0; 832} 833 834bool GVN::isSafeReplacement(PHINode* p, Instruction* inst) { 835 if (!isa<PHINode>(inst)) 836 return true; 837 838 for (Instruction::use_iterator UI = p->use_begin(), E = p->use_end(); 839 UI != E; ++UI) 840 if (PHINode* use_phi = dyn_cast<PHINode>(UI)) 841 if (use_phi->getParent() == inst->getParent()) 842 return false; 843 844 return true; 845} 846 847/// GetValueForBlock - Get the value to use within the specified basic block. 848/// available values are in Phis. 849Value *GVN::GetValueForBlock(BasicBlock *BB, LoadInst* orig, 850 DenseMap<BasicBlock*, Value*> &Phis, 851 bool top_level) { 852 853 // If we have already computed this value, return the previously computed val. 854 DenseMap<BasicBlock*, Value*>::iterator V = Phis.find(BB); 855 if (V != Phis.end() && !top_level) return V->second; 856 857 BasicBlock* singlePred = BB->getSinglePredecessor(); 858 if (singlePred) { 859 Value *ret = GetValueForBlock(singlePred, orig, Phis); 860 Phis[BB] = ret; 861 return ret; 862 } 863 864 // Otherwise, the idom is the loop, so we need to insert a PHI node. Do so 865 // now, then get values to fill in the incoming values for the PHI. 866 PHINode *PN = PHINode::Create(orig->getType(), orig->getName()+".rle", 867 BB->begin()); 868 PN->reserveOperandSpace(std::distance(pred_begin(BB), pred_end(BB))); 869 870 if (Phis.count(BB) == 0) 871 Phis.insert(std::make_pair(BB, PN)); 872 873 // Fill in the incoming values for the block. 874 for (pred_iterator PI = pred_begin(BB), E = pred_end(BB); PI != E; ++PI) { 875 Value* val = GetValueForBlock(*PI, orig, Phis); 876 PN->addIncoming(val, *PI); 877 } 878 879 AliasAnalysis& AA = getAnalysis<AliasAnalysis>(); 880 AA.copyValue(orig, PN); 881 882 // Attempt to collapse PHI nodes that are trivially redundant 883 Value* v = CollapsePhi(PN); 884 if (!v) { 885 // Cache our phi construction results 886 phiMap[orig->getPointerOperand()].insert(PN); 887 return PN; 888 } 889 890 MemoryDependenceAnalysis& MD = getAnalysis<MemoryDependenceAnalysis>(); 891 892 MD.removeInstruction(PN); 893 PN->replaceAllUsesWith(v); 894 895 for (DenseMap<BasicBlock*, Value*>::iterator I = Phis.begin(), 896 E = Phis.end(); I != E; ++I) 897 if (I->second == PN) 898 I->second = v; 899 900 PN->eraseFromParent(); 901 902 Phis[BB] = v; 903 return v; 904} 905 906/// processNonLocalLoad - Attempt to eliminate a load whose dependencies are 907/// non-local by performing PHI construction. 908bool GVN::processNonLocalLoad(LoadInst* L, 909 SmallVectorImpl<Instruction*> &toErase) { 910 MemoryDependenceAnalysis& MD = getAnalysis<MemoryDependenceAnalysis>(); 911 912 // Find the non-local dependencies of the load 913 DenseMap<BasicBlock*, Value*> deps; 914 MD.getNonLocalDependency(L, deps); 915 916 DenseMap<BasicBlock*, Value*> repl; 917 918 // Filter out useless results (non-locals, etc) 919 for (DenseMap<BasicBlock*, Value*>::iterator I = deps.begin(), E = deps.end(); 920 I != E; ++I) { 921 if (I->second == MemoryDependenceAnalysis::None) 922 return false; 923 924 if (I->second == MemoryDependenceAnalysis::NonLocal) 925 continue; 926 927 if (StoreInst* S = dyn_cast<StoreInst>(I->second)) { 928 if (S->getPointerOperand() != L->getPointerOperand()) 929 return false; 930 repl[I->first] = S->getOperand(0); 931 } else if (LoadInst* LD = dyn_cast<LoadInst>(I->second)) { 932 if (LD->getPointerOperand() != L->getPointerOperand()) 933 return false; 934 repl[I->first] = LD; 935 } else { 936 return false; 937 } 938 } 939 940 // Use cached PHI construction information from previous runs 941 SmallPtrSet<Instruction*, 4>& p = phiMap[L->getPointerOperand()]; 942 for (SmallPtrSet<Instruction*, 4>::iterator I = p.begin(), E = p.end(); 943 I != E; ++I) { 944 if ((*I)->getParent() == L->getParent()) { 945 MD.removeInstruction(L); 946 L->replaceAllUsesWith(*I); 947 toErase.push_back(L); 948 NumGVNLoad++; 949 return true; 950 } 951 952 repl.insert(std::make_pair((*I)->getParent(), *I)); 953 } 954 955 // Perform PHI construction 956 SmallPtrSet<BasicBlock*, 4> visited; 957 Value* v = GetValueForBlock(L->getParent(), L, repl, true); 958 959 MD.removeInstruction(L); 960 L->replaceAllUsesWith(v); 961 toErase.push_back(L); 962 NumGVNLoad++; 963 964 return true; 965} 966 967/// processLoad - Attempt to eliminate a load, first by eliminating it 968/// locally, and then attempting non-local elimination if that fails. 969bool GVN::processLoad(LoadInst *L, DenseMap<Value*, LoadInst*> &lastLoad, 970 SmallVectorImpl<Instruction*> &toErase) { 971 if (L->isVolatile()) { 972 lastLoad[L->getPointerOperand()] = L; 973 return false; 974 } 975 976 Value* pointer = L->getPointerOperand(); 977 LoadInst*& last = lastLoad[pointer]; 978 979 // ... to a pointer that has been loaded from before... 980 MemoryDependenceAnalysis& MD = getAnalysis<MemoryDependenceAnalysis>(); 981 bool removedNonLocal = false; 982 Instruction* dep = MD.getDependency(L); 983 if (dep == MemoryDependenceAnalysis::NonLocal && 984 L->getParent() != &L->getParent()->getParent()->getEntryBlock()) { 985 removedNonLocal = processNonLocalLoad(L, toErase); 986 987 if (!removedNonLocal) 988 last = L; 989 990 return removedNonLocal; 991 } 992 993 994 bool deletedLoad = false; 995 996 // Walk up the dependency chain until we either find 997 // a dependency we can use, or we can't walk any further 998 while (dep != MemoryDependenceAnalysis::None && 999 dep != MemoryDependenceAnalysis::NonLocal && 1000 (isa<LoadInst>(dep) || isa<StoreInst>(dep))) { 1001 // ... that depends on a store ... 1002 if (StoreInst* S = dyn_cast<StoreInst>(dep)) { 1003 if (S->getPointerOperand() == pointer) { 1004 // Remove it! 1005 MD.removeInstruction(L); 1006 1007 L->replaceAllUsesWith(S->getOperand(0)); 1008 toErase.push_back(L); 1009 deletedLoad = true; 1010 NumGVNLoad++; 1011 } 1012 1013 // Whether we removed it or not, we can't 1014 // go any further 1015 break; 1016 } else if (!last) { 1017 // If we don't depend on a store, and we haven't 1018 // been loaded before, bail. 1019 break; 1020 } else if (dep == last) { 1021 // Remove it! 1022 MD.removeInstruction(L); 1023 1024 L->replaceAllUsesWith(last); 1025 toErase.push_back(L); 1026 deletedLoad = true; 1027 NumGVNLoad++; 1028 1029 break; 1030 } else { 1031 dep = MD.getDependency(L, dep); 1032 } 1033 } 1034 1035 if (dep != MemoryDependenceAnalysis::None && 1036 dep != MemoryDependenceAnalysis::NonLocal && 1037 isa<AllocationInst>(dep)) { 1038 // Check that this load is actually from the 1039 // allocation we found 1040 Value* v = L->getOperand(0); 1041 while (true) { 1042 if (BitCastInst *BC = dyn_cast<BitCastInst>(v)) 1043 v = BC->getOperand(0); 1044 else if (GetElementPtrInst *GEP = dyn_cast<GetElementPtrInst>(v)) 1045 v = GEP->getOperand(0); 1046 else 1047 break; 1048 } 1049 if (v == dep) { 1050 // If this load depends directly on an allocation, there isn't 1051 // anything stored there; therefore, we can optimize this load 1052 // to undef. 1053 MD.removeInstruction(L); 1054 1055 L->replaceAllUsesWith(UndefValue::get(L->getType())); 1056 toErase.push_back(L); 1057 deletedLoad = true; 1058 NumGVNLoad++; 1059 } 1060 } 1061 1062 if (!deletedLoad) 1063 last = L; 1064 1065 return deletedLoad; 1066} 1067 1068/// processInstruction - When calculating availability, handle an instruction 1069/// by inserting it into the appropriate sets 1070bool GVN::processInstruction(Instruction *I, 1071 DenseMap<Value*, LoadInst*> &lastSeenLoad, 1072 SmallVectorImpl<Instruction*> &toErase) { 1073 if (LoadInst* L = dyn_cast<LoadInst>(I)) { 1074 bool changed = processLoad(L, lastSeenLoad, toErase); 1075 1076 if (!changed) { 1077 unsigned num = VN.lookup_or_add(L); 1078 localAvail[I->getParent()].insert(std::make_pair(num, L)); 1079 } 1080 1081 return changed; 1082 } 1083 1084 unsigned num = VN.lookup_or_add(I); 1085 1086 // Allocations are always uniquely numbered, so we can save time and memory 1087 // by fast failing them. 1088 if (isa<AllocationInst>(I)) { 1089 localAvail[I->getParent()].insert(std::make_pair(num, I)); 1090 return false; 1091 } 1092 1093 // Collapse PHI nodes 1094 if (PHINode* p = dyn_cast<PHINode>(I)) { 1095 Value* constVal = CollapsePhi(p); 1096 1097 if (constVal) { 1098 for (PhiMapType::iterator PI = phiMap.begin(), PE = phiMap.end(); 1099 PI != PE; ++PI) 1100 if (PI->second.count(p)) 1101 PI->second.erase(p); 1102 1103 p->replaceAllUsesWith(constVal); 1104 toErase.push_back(p); 1105 } else { 1106 localAvail[I->getParent()].insert(std::make_pair(num, I)); 1107 } 1108 // Perform value-number based elimination 1109 } else if (localAvail[I->getParent()].count(num)) { 1110 Value* repl = localAvail[I->getParent()][num]; 1111 1112 // Remove it! 1113 MemoryDependenceAnalysis& MD = getAnalysis<MemoryDependenceAnalysis>(); 1114 MD.removeInstruction(I); 1115 1116 VN.erase(I); 1117 I->replaceAllUsesWith(repl); 1118 toErase.push_back(I); 1119 return true; 1120 } else if (!I->isTerminator()) { 1121 localAvail[I->getParent()].insert(std::make_pair(num, I)); 1122 } 1123 1124 return false; 1125} 1126 1127// GVN::runOnFunction - This is the main transformation entry point for a 1128// function. 1129// 1130bool GVN::runOnFunction(Function& F) { 1131 VN.setAliasAnalysis(&getAnalysis<AliasAnalysis>()); 1132 VN.setMemDep(&getAnalysis<MemoryDependenceAnalysis>()); 1133 VN.setDomTree(&getAnalysis<DominatorTree>()); 1134 1135 bool changed = false; 1136 bool shouldContinue = true; 1137 1138 while (shouldContinue) { 1139 shouldContinue = iterateOnFunction(F); 1140 changed |= shouldContinue; 1141 } 1142 1143 return changed; 1144} 1145 1146 1147bool GVN::processBlock(DomTreeNode* DTN) { 1148 BasicBlock* BB = DTN->getBlock(); 1149 1150 SmallVector<Instruction*, 8> toErase; 1151 DenseMap<Value*, LoadInst*> lastSeenLoad; 1152 bool changed_function = false; 1153 1154 if (DTN->getIDom()) 1155 localAvail.insert(std::make_pair(BB, 1156 localAvail[DTN->getIDom()->getBlock()])); 1157 1158 for (BasicBlock::iterator BI = BB->begin(), BE = BB->end(); 1159 BI != BE;) { 1160 changed_function |= processInstruction(BI, lastSeenLoad, toErase); 1161 if (toErase.empty()) { 1162 ++BI; 1163 continue; 1164 } 1165 1166 // If we need some instructions deleted, do it now. 1167 NumGVNInstr += toErase.size(); 1168 1169 // Avoid iterator invalidation. 1170 bool AtStart = BI == BB->begin(); 1171 if (!AtStart) 1172 --BI; 1173 1174 for (SmallVector<Instruction*, 4>::iterator I = toErase.begin(), 1175 E = toErase.end(); I != E; ++I) 1176 (*I)->eraseFromParent(); 1177 1178 if (AtStart) 1179 BI = BB->begin(); 1180 else 1181 ++BI; 1182 1183 toErase.clear(); 1184 } 1185 1186 return changed_function; 1187} 1188 1189/// performPRE - Perform a purely local form of PRE that looks for diamond 1190/// control flow patterns and attempts to perform simple PRE at the join point. 1191bool GVN::performPRE(Function& F) { 1192 bool changed = false; 1193 for (df_iterator<BasicBlock*> DI = df_begin(&F.getEntryBlock()), 1194 DE = df_end(&F.getEntryBlock()); DI != DE; ++DI) { 1195 BasicBlock* CurrentBlock = *DI; 1196 1197 // Nothing to PRE in the entry block. 1198 if (CurrentBlock == &F.getEntryBlock()) continue; 1199 1200 for (BasicBlock::iterator BI = CurrentBlock->begin(), 1201 BE = CurrentBlock->end(); BI != BE; ) { 1202 if (isa<AllocaInst>(BI) || isa<TerminatorInst>(BI) || 1203 isa<LoadInst>(BI) || isa<StoreInst>(BI) || 1204 isa<CallInst>(BI) || isa<PHINode>(BI)) { 1205 BI++; 1206 continue; 1207 } 1208 1209 uint32_t valno = VN.lookup(BI); 1210 1211 // Look for the predecessors for PRE opportunities. We're 1212 // only trying to solve the basic diamond case, where 1213 // a value is computed in the successor and one predecessor, 1214 // but not the other. We also explicitly disallow cases 1215 // where the successor is its own predecessor, because they're 1216 // more complicated to get right. 1217 unsigned numWith = 0; 1218 unsigned numWithout = 0; 1219 BasicBlock* PREPred = 0; 1220 for (pred_iterator PI = pred_begin(CurrentBlock), 1221 PE = pred_end(CurrentBlock); PI != PE; ++PI) { 1222 // We're not interested in PRE where the block is its 1223 // own predecessor. 1224 if (*PI == CurrentBlock) 1225 numWithout = 2; 1226 1227 if (!localAvail[*PI].count(valno)) { 1228 PREPred = *PI; 1229 numWithout++; 1230 } else if (localAvail[*PI][valno] == BI) { 1231 numWithout = 2; 1232 } else { 1233 numWith++; 1234 } 1235 } 1236 1237 // Don't do PRE when it might increase code size, i.e. when 1238 // we would need to insert instructions in more than one pred. 1239 if (numWithout != 1 || numWith == 0) { 1240 BI++; 1241 continue; 1242 } 1243 1244 // Instantiate the expression the in predecessor that lacked it. 1245 // Because we are going top-down through the block, all value numbers 1246 // will be available in the predecessor by the time we need them. Any 1247 // that weren't original present will have been instantiated earlier 1248 // in this loop. 1249 Instruction* PREInstr = BI->clone(); 1250 bool success = true; 1251 for (unsigned i = 0; i < BI->getNumOperands(); ++i) { 1252 Value* op = BI->getOperand(i); 1253 if (isa<Argument>(op) || isa<Constant>(op) || isa<GlobalValue>(op)) 1254 PREInstr->setOperand(i, op); 1255 else if (!localAvail[PREPred].count(VN.lookup(op))) { 1256 success = false; 1257 break; 1258 } else 1259 PREInstr->setOperand(i, localAvail[PREPred][VN.lookup(op)]); 1260 } 1261 1262 // Fail out if we encounter an operand that is not available in 1263 // the PRE predecessor. This is typically because of loads which 1264 // are not value numbered precisely. 1265 if (!success) { 1266 delete PREInstr; 1267 BI++; 1268 continue; 1269 } 1270 1271 PREInstr->insertBefore(PREPred->getTerminator()); 1272 PREInstr->setName(BI->getName() + ".pre"); 1273 VN.add(PREInstr, valno); 1274 NumGVNPRE++; 1275 1276 // Update the availability map to include the new instruction. 1277 localAvail[PREPred].insert(std::make_pair(valno, PREInstr)); 1278 1279 // Create a PHI to make the value available in this block. 1280 PHINode* Phi = PHINode::Create(BI->getType(), 1281 BI->getName() + ".pre-phi", 1282 CurrentBlock->begin()); 1283 for (pred_iterator PI = pred_begin(CurrentBlock), 1284 PE = pred_end(CurrentBlock); PI != PE; ++PI) 1285 Phi->addIncoming(localAvail[*PI][valno], *PI); 1286 1287 VN.add(Phi, valno); 1288 1289 // The newly created PHI completely replaces the old instruction, 1290 // so we need to update the maps to reflect this. 1291 for (DenseMap<BasicBlock*, DenseMap<uint32_t, Value*> >::iterator 1292 UI = localAvail.begin(), UE = localAvail.end(); UI != UE; ++UI) 1293 for (DenseMap<uint32_t, Value*>::iterator UUI = UI->second.begin(), 1294 UUE = UI->second.end(); UUI != UUE; ++UUI) 1295 if (UUI->second == BI) 1296 UUI->second = Phi; 1297 1298 BI->replaceAllUsesWith(Phi); 1299 1300 Instruction* erase = BI; 1301 BI++; 1302 erase->eraseFromParent(); 1303 1304 changed = true; 1305 } 1306 } 1307 1308 return changed; 1309} 1310 1311// GVN::iterateOnFunction - Executes one iteration of GVN 1312bool GVN::iterateOnFunction(Function &F) { 1313 // Clean out global sets from any previous functions 1314 VN.clear(); 1315 localAvail.clear(); 1316 phiMap.clear(); 1317 1318 DominatorTree &DT = getAnalysis<DominatorTree>(); 1319 1320 // Top-down walk of the dominator tree 1321 bool changed = false; 1322 for (df_iterator<DomTreeNode*> DI = df_begin(DT.getRootNode()), 1323 DE = df_end(DT.getRootNode()); DI != DE; ++DI) 1324 changed |= processBlock(*DI); 1325 1326 changed |= performPRE(F); 1327 return changed; 1328} 1329