GVN.cpp revision 5f4f84ba3ec3cd5c9d6fb8acd770042a5cfdf8aa
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/PostOrderIterator.h" 29#include "llvm/ADT/SmallPtrSet.h" 30#include "llvm/ADT/SmallVector.h" 31#include "llvm/ADT/Statistic.h" 32#include "llvm/Analysis/Dominators.h" 33#include "llvm/Analysis/AliasAnalysis.h" 34#include "llvm/Analysis/MemoryDependenceAnalysis.h" 35#include "llvm/Support/CFG.h" 36#include "llvm/Support/CommandLine.h" 37#include "llvm/Support/Compiler.h" 38#include "llvm/Support/Debug.h" 39#include "llvm/Transforms/Utils/BasicBlockUtils.h" 40#include <cstdio> 41using namespace llvm; 42 43STATISTIC(NumGVNInstr, "Number of instructions deleted"); 44STATISTIC(NumGVNLoad, "Number of loads deleted"); 45STATISTIC(NumGVNPRE, "Number of instructions PRE'd"); 46STATISTIC(NumGVNBlocks, "Number of blocks merged"); 47STATISTIC(NumPRELoad, "Number of loads PRE'd"); 48 49static cl::opt<bool> EnablePRE("enable-pre", 50 cl::init(true), cl::Hidden); 51cl::opt<bool> EnableLoadPRE("enable-load-pre"/*, cl::init(true)*/); 52 53//===----------------------------------------------------------------------===// 54// ValueTable Class 55//===----------------------------------------------------------------------===// 56 57/// This class holds the mapping between values and value numbers. It is used 58/// as an efficient mechanism to determine the expression-wise equivalence of 59/// two values. 60namespace { 61 struct VISIBILITY_HIDDEN Expression { 62 enum ExpressionOpcode { ADD, SUB, MUL, UDIV, SDIV, FDIV, UREM, SREM, 63 FREM, SHL, LSHR, ASHR, AND, OR, XOR, ICMPEQ, 64 ICMPNE, ICMPUGT, ICMPUGE, ICMPULT, ICMPULE, 65 ICMPSGT, ICMPSGE, ICMPSLT, ICMPSLE, FCMPOEQ, 66 FCMPOGT, FCMPOGE, FCMPOLT, FCMPOLE, FCMPONE, 67 FCMPORD, FCMPUNO, FCMPUEQ, FCMPUGT, FCMPUGE, 68 FCMPULT, FCMPULE, FCMPUNE, EXTRACT, INSERT, 69 SHUFFLE, SELECT, TRUNC, ZEXT, SEXT, FPTOUI, 70 FPTOSI, UITOFP, SITOFP, FPTRUNC, FPEXT, 71 PTRTOINT, INTTOPTR, BITCAST, GEP, CALL, CONSTANT, 72 EMPTY, TOMBSTONE }; 73 74 ExpressionOpcode opcode; 75 const Type* type; 76 uint32_t firstVN; 77 uint32_t secondVN; 78 uint32_t thirdVN; 79 SmallVector<uint32_t, 4> varargs; 80 Value* function; 81 82 Expression() { } 83 Expression(ExpressionOpcode o) : opcode(o) { } 84 85 bool operator==(const Expression &other) const { 86 if (opcode != other.opcode) 87 return false; 88 else if (opcode == EMPTY || opcode == TOMBSTONE) 89 return true; 90 else if (type != other.type) 91 return false; 92 else if (function != other.function) 93 return false; 94 else if (firstVN != other.firstVN) 95 return false; 96 else if (secondVN != other.secondVN) 97 return false; 98 else if (thirdVN != other.thirdVN) 99 return false; 100 else { 101 if (varargs.size() != other.varargs.size()) 102 return false; 103 104 for (size_t i = 0; i < varargs.size(); ++i) 105 if (varargs[i] != other.varargs[i]) 106 return false; 107 108 return true; 109 } 110 } 111 112 bool operator!=(const Expression &other) const { 113 if (opcode != other.opcode) 114 return true; 115 else if (opcode == EMPTY || opcode == TOMBSTONE) 116 return false; 117 else if (type != other.type) 118 return true; 119 else if (function != other.function) 120 return true; 121 else if (firstVN != other.firstVN) 122 return true; 123 else if (secondVN != other.secondVN) 124 return true; 125 else if (thirdVN != other.thirdVN) 126 return true; 127 else { 128 if (varargs.size() != other.varargs.size()) 129 return true; 130 131 for (size_t i = 0; i < varargs.size(); ++i) 132 if (varargs[i] != other.varargs[i]) 133 return true; 134 135 return false; 136 } 137 } 138 }; 139 140 class VISIBILITY_HIDDEN ValueTable { 141 private: 142 DenseMap<Value*, uint32_t> valueNumbering; 143 DenseMap<Expression, uint32_t> expressionNumbering; 144 AliasAnalysis* AA; 145 MemoryDependenceAnalysis* MD; 146 DominatorTree* DT; 147 148 uint32_t nextValueNumber; 149 150 Expression::ExpressionOpcode getOpcode(BinaryOperator* BO); 151 Expression::ExpressionOpcode getOpcode(CmpInst* C); 152 Expression::ExpressionOpcode getOpcode(CastInst* C); 153 Expression create_expression(BinaryOperator* BO); 154 Expression create_expression(CmpInst* C); 155 Expression create_expression(ShuffleVectorInst* V); 156 Expression create_expression(ExtractElementInst* C); 157 Expression create_expression(InsertElementInst* V); 158 Expression create_expression(SelectInst* V); 159 Expression create_expression(CastInst* C); 160 Expression create_expression(GetElementPtrInst* G); 161 Expression create_expression(CallInst* C); 162 Expression create_expression(Constant* C); 163 public: 164 ValueTable() : nextValueNumber(1) { } 165 uint32_t lookup_or_add(Value* V); 166 uint32_t lookup(Value* V) const; 167 void add(Value* V, uint32_t num); 168 void clear(); 169 void erase(Value* v); 170 unsigned size(); 171 void setAliasAnalysis(AliasAnalysis* A) { AA = A; } 172 AliasAnalysis *getAliasAnalysis() const { return AA; } 173 void setMemDep(MemoryDependenceAnalysis* M) { MD = M; } 174 void setDomTree(DominatorTree* D) { DT = D; } 175 uint32_t getNextUnusedValueNumber() { return nextValueNumber; } 176 }; 177} 178 179namespace llvm { 180template <> struct DenseMapInfo<Expression> { 181 static inline Expression getEmptyKey() { 182 return Expression(Expression::EMPTY); 183 } 184 185 static inline Expression getTombstoneKey() { 186 return Expression(Expression::TOMBSTONE); 187 } 188 189 static unsigned getHashValue(const Expression e) { 190 unsigned hash = e.opcode; 191 192 hash = e.firstVN + hash * 37; 193 hash = e.secondVN + hash * 37; 194 hash = e.thirdVN + hash * 37; 195 196 hash = ((unsigned)((uintptr_t)e.type >> 4) ^ 197 (unsigned)((uintptr_t)e.type >> 9)) + 198 hash * 37; 199 200 for (SmallVector<uint32_t, 4>::const_iterator I = e.varargs.begin(), 201 E = e.varargs.end(); I != E; ++I) 202 hash = *I + hash * 37; 203 204 hash = ((unsigned)((uintptr_t)e.function >> 4) ^ 205 (unsigned)((uintptr_t)e.function >> 9)) + 206 hash * 37; 207 208 return hash; 209 } 210 static bool isEqual(const Expression &LHS, const Expression &RHS) { 211 return LHS == RHS; 212 } 213 static bool isPod() { return true; } 214}; 215} 216 217//===----------------------------------------------------------------------===// 218// ValueTable Internal Functions 219//===----------------------------------------------------------------------===// 220Expression::ExpressionOpcode ValueTable::getOpcode(BinaryOperator* BO) { 221 switch(BO->getOpcode()) { 222 default: // THIS SHOULD NEVER HAPPEN 223 assert(0 && "Binary operator with unknown opcode?"); 224 case Instruction::Add: return Expression::ADD; 225 case Instruction::Sub: return Expression::SUB; 226 case Instruction::Mul: return Expression::MUL; 227 case Instruction::UDiv: return Expression::UDIV; 228 case Instruction::SDiv: return Expression::SDIV; 229 case Instruction::FDiv: return Expression::FDIV; 230 case Instruction::URem: return Expression::UREM; 231 case Instruction::SRem: return Expression::SREM; 232 case Instruction::FRem: return Expression::FREM; 233 case Instruction::Shl: return Expression::SHL; 234 case Instruction::LShr: return Expression::LSHR; 235 case Instruction::AShr: return Expression::ASHR; 236 case Instruction::And: return Expression::AND; 237 case Instruction::Or: return Expression::OR; 238 case Instruction::Xor: return Expression::XOR; 239 } 240} 241 242Expression::ExpressionOpcode ValueTable::getOpcode(CmpInst* C) { 243 if (isa<ICmpInst>(C) || isa<VICmpInst>(C)) { 244 switch (C->getPredicate()) { 245 default: // THIS SHOULD NEVER HAPPEN 246 assert(0 && "Comparison with unknown predicate?"); 247 case ICmpInst::ICMP_EQ: return Expression::ICMPEQ; 248 case ICmpInst::ICMP_NE: return Expression::ICMPNE; 249 case ICmpInst::ICMP_UGT: return Expression::ICMPUGT; 250 case ICmpInst::ICMP_UGE: return Expression::ICMPUGE; 251 case ICmpInst::ICMP_ULT: return Expression::ICMPULT; 252 case ICmpInst::ICMP_ULE: return Expression::ICMPULE; 253 case ICmpInst::ICMP_SGT: return Expression::ICMPSGT; 254 case ICmpInst::ICMP_SGE: return Expression::ICMPSGE; 255 case ICmpInst::ICMP_SLT: return Expression::ICMPSLT; 256 case ICmpInst::ICMP_SLE: return Expression::ICMPSLE; 257 } 258 } 259 assert((isa<FCmpInst>(C) || isa<VFCmpInst>(C)) && "Unknown compare"); 260 switch (C->getPredicate()) { 261 default: // THIS SHOULD NEVER HAPPEN 262 assert(0 && "Comparison with unknown predicate?"); 263 case FCmpInst::FCMP_OEQ: return Expression::FCMPOEQ; 264 case FCmpInst::FCMP_OGT: return Expression::FCMPOGT; 265 case FCmpInst::FCMP_OGE: return Expression::FCMPOGE; 266 case FCmpInst::FCMP_OLT: return Expression::FCMPOLT; 267 case FCmpInst::FCMP_OLE: return Expression::FCMPOLE; 268 case FCmpInst::FCMP_ONE: return Expression::FCMPONE; 269 case FCmpInst::FCMP_ORD: return Expression::FCMPORD; 270 case FCmpInst::FCMP_UNO: return Expression::FCMPUNO; 271 case FCmpInst::FCMP_UEQ: return Expression::FCMPUEQ; 272 case FCmpInst::FCMP_UGT: return Expression::FCMPUGT; 273 case FCmpInst::FCMP_UGE: return Expression::FCMPUGE; 274 case FCmpInst::FCMP_ULT: return Expression::FCMPULT; 275 case FCmpInst::FCMP_ULE: return Expression::FCMPULE; 276 case FCmpInst::FCMP_UNE: return Expression::FCMPUNE; 277 } 278} 279 280Expression::ExpressionOpcode ValueTable::getOpcode(CastInst* C) { 281 switch(C->getOpcode()) { 282 default: // THIS SHOULD NEVER HAPPEN 283 assert(0 && "Cast operator with unknown opcode?"); 284 case Instruction::Trunc: return Expression::TRUNC; 285 case Instruction::ZExt: return Expression::ZEXT; 286 case Instruction::SExt: return Expression::SEXT; 287 case Instruction::FPToUI: return Expression::FPTOUI; 288 case Instruction::FPToSI: return Expression::FPTOSI; 289 case Instruction::UIToFP: return Expression::UITOFP; 290 case Instruction::SIToFP: return Expression::SITOFP; 291 case Instruction::FPTrunc: return Expression::FPTRUNC; 292 case Instruction::FPExt: return Expression::FPEXT; 293 case Instruction::PtrToInt: return Expression::PTRTOINT; 294 case Instruction::IntToPtr: return Expression::INTTOPTR; 295 case Instruction::BitCast: return Expression::BITCAST; 296 } 297} 298 299Expression ValueTable::create_expression(CallInst* C) { 300 Expression e; 301 302 e.type = C->getType(); 303 e.firstVN = 0; 304 e.secondVN = 0; 305 e.thirdVN = 0; 306 e.function = C->getCalledFunction(); 307 e.opcode = Expression::CALL; 308 309 for (CallInst::op_iterator I = C->op_begin()+1, E = C->op_end(); 310 I != E; ++I) 311 e.varargs.push_back(lookup_or_add(*I)); 312 313 return e; 314} 315 316Expression ValueTable::create_expression(BinaryOperator* BO) { 317 Expression e; 318 319 e.firstVN = lookup_or_add(BO->getOperand(0)); 320 e.secondVN = lookup_or_add(BO->getOperand(1)); 321 e.thirdVN = 0; 322 e.function = 0; 323 e.type = BO->getType(); 324 e.opcode = getOpcode(BO); 325 326 return e; 327} 328 329Expression ValueTable::create_expression(CmpInst* C) { 330 Expression e; 331 332 e.firstVN = lookup_or_add(C->getOperand(0)); 333 e.secondVN = lookup_or_add(C->getOperand(1)); 334 e.thirdVN = 0; 335 e.function = 0; 336 e.type = C->getType(); 337 e.opcode = getOpcode(C); 338 339 return e; 340} 341 342Expression ValueTable::create_expression(CastInst* C) { 343 Expression e; 344 345 e.firstVN = lookup_or_add(C->getOperand(0)); 346 e.secondVN = 0; 347 e.thirdVN = 0; 348 e.function = 0; 349 e.type = C->getType(); 350 e.opcode = getOpcode(C); 351 352 return e; 353} 354 355Expression ValueTable::create_expression(ShuffleVectorInst* S) { 356 Expression e; 357 358 e.firstVN = lookup_or_add(S->getOperand(0)); 359 e.secondVN = lookup_or_add(S->getOperand(1)); 360 e.thirdVN = lookup_or_add(S->getOperand(2)); 361 e.function = 0; 362 e.type = S->getType(); 363 e.opcode = Expression::SHUFFLE; 364 365 return e; 366} 367 368Expression ValueTable::create_expression(ExtractElementInst* E) { 369 Expression e; 370 371 e.firstVN = lookup_or_add(E->getOperand(0)); 372 e.secondVN = lookup_or_add(E->getOperand(1)); 373 e.thirdVN = 0; 374 e.function = 0; 375 e.type = E->getType(); 376 e.opcode = Expression::EXTRACT; 377 378 return e; 379} 380 381Expression ValueTable::create_expression(InsertElementInst* I) { 382 Expression e; 383 384 e.firstVN = lookup_or_add(I->getOperand(0)); 385 e.secondVN = lookup_or_add(I->getOperand(1)); 386 e.thirdVN = lookup_or_add(I->getOperand(2)); 387 e.function = 0; 388 e.type = I->getType(); 389 e.opcode = Expression::INSERT; 390 391 return e; 392} 393 394Expression ValueTable::create_expression(SelectInst* I) { 395 Expression e; 396 397 e.firstVN = lookup_or_add(I->getCondition()); 398 e.secondVN = lookup_or_add(I->getTrueValue()); 399 e.thirdVN = lookup_or_add(I->getFalseValue()); 400 e.function = 0; 401 e.type = I->getType(); 402 e.opcode = Expression::SELECT; 403 404 return e; 405} 406 407Expression ValueTable::create_expression(GetElementPtrInst* G) { 408 Expression e; 409 410 e.firstVN = lookup_or_add(G->getPointerOperand()); 411 e.secondVN = 0; 412 e.thirdVN = 0; 413 e.function = 0; 414 e.type = G->getType(); 415 e.opcode = Expression::GEP; 416 417 for (GetElementPtrInst::op_iterator I = G->idx_begin(), E = G->idx_end(); 418 I != E; ++I) 419 e.varargs.push_back(lookup_or_add(*I)); 420 421 return e; 422} 423 424//===----------------------------------------------------------------------===// 425// ValueTable External Functions 426//===----------------------------------------------------------------------===// 427 428/// add - Insert a value into the table with a specified value number. 429void ValueTable::add(Value* V, uint32_t num) { 430 valueNumbering.insert(std::make_pair(V, num)); 431} 432 433/// lookup_or_add - Returns the value number for the specified value, assigning 434/// it a new number if it did not have one before. 435uint32_t ValueTable::lookup_or_add(Value* V) { 436 DenseMap<Value*, uint32_t>::iterator VI = valueNumbering.find(V); 437 if (VI != valueNumbering.end()) 438 return VI->second; 439 440 if (CallInst* C = dyn_cast<CallInst>(V)) { 441 if (AA->doesNotAccessMemory(C)) { 442 Expression e = create_expression(C); 443 444 DenseMap<Expression, uint32_t>::iterator EI = expressionNumbering.find(e); 445 if (EI != expressionNumbering.end()) { 446 valueNumbering.insert(std::make_pair(V, EI->second)); 447 return EI->second; 448 } else { 449 expressionNumbering.insert(std::make_pair(e, nextValueNumber)); 450 valueNumbering.insert(std::make_pair(V, nextValueNumber)); 451 452 return nextValueNumber++; 453 } 454 } else if (AA->onlyReadsMemory(C)) { 455 Expression e = create_expression(C); 456 457 if (expressionNumbering.find(e) == expressionNumbering.end()) { 458 expressionNumbering.insert(std::make_pair(e, nextValueNumber)); 459 valueNumbering.insert(std::make_pair(V, nextValueNumber)); 460 return nextValueNumber++; 461 } 462 463 MemDepResult local_dep = MD->getDependency(C); 464 465 if (!local_dep.isDef() && !local_dep.isNonLocal()) { 466 valueNumbering.insert(std::make_pair(V, nextValueNumber)); 467 return nextValueNumber++; 468 } 469 470 if (local_dep.isDef()) { 471 CallInst* local_cdep = cast<CallInst>(local_dep.getInst()); 472 473 if (local_cdep->getNumOperands() != C->getNumOperands()) { 474 valueNumbering.insert(std::make_pair(V, nextValueNumber)); 475 return nextValueNumber++; 476 } 477 478 for (unsigned i = 1; i < C->getNumOperands(); ++i) { 479 uint32_t c_vn = lookup_or_add(C->getOperand(i)); 480 uint32_t cd_vn = lookup_or_add(local_cdep->getOperand(i)); 481 if (c_vn != cd_vn) { 482 valueNumbering.insert(std::make_pair(V, nextValueNumber)); 483 return nextValueNumber++; 484 } 485 } 486 487 uint32_t v = lookup_or_add(local_cdep); 488 valueNumbering.insert(std::make_pair(V, v)); 489 return v; 490 } 491 492 // Non-local case. 493 const MemoryDependenceAnalysis::NonLocalDepInfo &deps = 494 MD->getNonLocalCallDependency(CallSite(C)); 495 // FIXME: call/call dependencies for readonly calls should return def, not 496 // clobber! Move the checking logic to MemDep! 497 CallInst* cdep = 0; 498 499 // Check to see if we have a single dominating call instruction that is 500 // identical to C. 501 for (unsigned i = 0, e = deps.size(); i != e; ++i) { 502 const MemoryDependenceAnalysis::NonLocalDepEntry *I = &deps[i]; 503 // Ignore non-local dependencies. 504 if (I->second.isNonLocal()) 505 continue; 506 507 // We don't handle non-depedencies. If we already have a call, reject 508 // instruction dependencies. 509 if (I->second.isClobber() || cdep != 0) { 510 cdep = 0; 511 break; 512 } 513 514 CallInst *NonLocalDepCall = dyn_cast<CallInst>(I->second.getInst()); 515 // FIXME: All duplicated with non-local case. 516 if (NonLocalDepCall && DT->properlyDominates(I->first, C->getParent())){ 517 cdep = NonLocalDepCall; 518 continue; 519 } 520 521 cdep = 0; 522 break; 523 } 524 525 if (!cdep) { 526 valueNumbering.insert(std::make_pair(V, nextValueNumber)); 527 return nextValueNumber++; 528 } 529 530 if (cdep->getNumOperands() != C->getNumOperands()) { 531 valueNumbering.insert(std::make_pair(V, nextValueNumber)); 532 return nextValueNumber++; 533 } 534 for (unsigned i = 1; i < C->getNumOperands(); ++i) { 535 uint32_t c_vn = lookup_or_add(C->getOperand(i)); 536 uint32_t cd_vn = lookup_or_add(cdep->getOperand(i)); 537 if (c_vn != cd_vn) { 538 valueNumbering.insert(std::make_pair(V, nextValueNumber)); 539 return nextValueNumber++; 540 } 541 } 542 543 uint32_t v = lookup_or_add(cdep); 544 valueNumbering.insert(std::make_pair(V, v)); 545 return v; 546 547 } else { 548 valueNumbering.insert(std::make_pair(V, nextValueNumber)); 549 return nextValueNumber++; 550 } 551 } else if (BinaryOperator* BO = dyn_cast<BinaryOperator>(V)) { 552 Expression e = create_expression(BO); 553 554 DenseMap<Expression, uint32_t>::iterator EI = expressionNumbering.find(e); 555 if (EI != expressionNumbering.end()) { 556 valueNumbering.insert(std::make_pair(V, EI->second)); 557 return EI->second; 558 } else { 559 expressionNumbering.insert(std::make_pair(e, nextValueNumber)); 560 valueNumbering.insert(std::make_pair(V, nextValueNumber)); 561 562 return nextValueNumber++; 563 } 564 } else if (CmpInst* C = dyn_cast<CmpInst>(V)) { 565 Expression e = create_expression(C); 566 567 DenseMap<Expression, uint32_t>::iterator EI = expressionNumbering.find(e); 568 if (EI != expressionNumbering.end()) { 569 valueNumbering.insert(std::make_pair(V, EI->second)); 570 return EI->second; 571 } else { 572 expressionNumbering.insert(std::make_pair(e, nextValueNumber)); 573 valueNumbering.insert(std::make_pair(V, nextValueNumber)); 574 575 return nextValueNumber++; 576 } 577 } else if (ShuffleVectorInst* U = dyn_cast<ShuffleVectorInst>(V)) { 578 Expression e = create_expression(U); 579 580 DenseMap<Expression, uint32_t>::iterator EI = expressionNumbering.find(e); 581 if (EI != expressionNumbering.end()) { 582 valueNumbering.insert(std::make_pair(V, EI->second)); 583 return EI->second; 584 } else { 585 expressionNumbering.insert(std::make_pair(e, nextValueNumber)); 586 valueNumbering.insert(std::make_pair(V, nextValueNumber)); 587 588 return nextValueNumber++; 589 } 590 } else if (ExtractElementInst* U = dyn_cast<ExtractElementInst>(V)) { 591 Expression e = create_expression(U); 592 593 DenseMap<Expression, uint32_t>::iterator EI = expressionNumbering.find(e); 594 if (EI != expressionNumbering.end()) { 595 valueNumbering.insert(std::make_pair(V, EI->second)); 596 return EI->second; 597 } else { 598 expressionNumbering.insert(std::make_pair(e, nextValueNumber)); 599 valueNumbering.insert(std::make_pair(V, nextValueNumber)); 600 601 return nextValueNumber++; 602 } 603 } else if (InsertElementInst* U = dyn_cast<InsertElementInst>(V)) { 604 Expression e = create_expression(U); 605 606 DenseMap<Expression, uint32_t>::iterator EI = expressionNumbering.find(e); 607 if (EI != expressionNumbering.end()) { 608 valueNumbering.insert(std::make_pair(V, EI->second)); 609 return EI->second; 610 } else { 611 expressionNumbering.insert(std::make_pair(e, nextValueNumber)); 612 valueNumbering.insert(std::make_pair(V, nextValueNumber)); 613 614 return nextValueNumber++; 615 } 616 } else if (SelectInst* U = dyn_cast<SelectInst>(V)) { 617 Expression e = create_expression(U); 618 619 DenseMap<Expression, uint32_t>::iterator EI = expressionNumbering.find(e); 620 if (EI != expressionNumbering.end()) { 621 valueNumbering.insert(std::make_pair(V, EI->second)); 622 return EI->second; 623 } else { 624 expressionNumbering.insert(std::make_pair(e, nextValueNumber)); 625 valueNumbering.insert(std::make_pair(V, nextValueNumber)); 626 627 return nextValueNumber++; 628 } 629 } else if (CastInst* U = dyn_cast<CastInst>(V)) { 630 Expression e = create_expression(U); 631 632 DenseMap<Expression, uint32_t>::iterator EI = expressionNumbering.find(e); 633 if (EI != expressionNumbering.end()) { 634 valueNumbering.insert(std::make_pair(V, EI->second)); 635 return EI->second; 636 } else { 637 expressionNumbering.insert(std::make_pair(e, nextValueNumber)); 638 valueNumbering.insert(std::make_pair(V, nextValueNumber)); 639 640 return nextValueNumber++; 641 } 642 } else if (GetElementPtrInst* U = dyn_cast<GetElementPtrInst>(V)) { 643 Expression e = create_expression(U); 644 645 DenseMap<Expression, uint32_t>::iterator EI = expressionNumbering.find(e); 646 if (EI != expressionNumbering.end()) { 647 valueNumbering.insert(std::make_pair(V, EI->second)); 648 return EI->second; 649 } else { 650 expressionNumbering.insert(std::make_pair(e, nextValueNumber)); 651 valueNumbering.insert(std::make_pair(V, nextValueNumber)); 652 653 return nextValueNumber++; 654 } 655 } else { 656 valueNumbering.insert(std::make_pair(V, nextValueNumber)); 657 return nextValueNumber++; 658 } 659} 660 661/// lookup - Returns the value number of the specified value. Fails if 662/// the value has not yet been numbered. 663uint32_t ValueTable::lookup(Value* V) const { 664 DenseMap<Value*, uint32_t>::iterator VI = valueNumbering.find(V); 665 assert(VI != valueNumbering.end() && "Value not numbered?"); 666 return VI->second; 667} 668 669/// clear - Remove all entries from the ValueTable 670void ValueTable::clear() { 671 valueNumbering.clear(); 672 expressionNumbering.clear(); 673 nextValueNumber = 1; 674} 675 676/// erase - Remove a value from the value numbering 677void ValueTable::erase(Value* V) { 678 valueNumbering.erase(V); 679} 680 681//===----------------------------------------------------------------------===// 682// GVN Pass 683//===----------------------------------------------------------------------===// 684 685namespace { 686 struct VISIBILITY_HIDDEN ValueNumberScope { 687 ValueNumberScope* parent; 688 DenseMap<uint32_t, Value*> table; 689 690 ValueNumberScope(ValueNumberScope* p) : parent(p) { } 691 }; 692} 693 694namespace { 695 696 class VISIBILITY_HIDDEN GVN : public FunctionPass { 697 bool runOnFunction(Function &F); 698 public: 699 static char ID; // Pass identification, replacement for typeid 700 GVN() : FunctionPass(&ID) { } 701 702 private: 703 MemoryDependenceAnalysis *MD; 704 DominatorTree *DT; 705 706 ValueTable VN; 707 DenseMap<BasicBlock*, ValueNumberScope*> localAvail; 708 709 typedef DenseMap<Value*, SmallPtrSet<Instruction*, 4> > PhiMapType; 710 PhiMapType phiMap; 711 712 713 // This transformation requires dominator postdominator info 714 virtual void getAnalysisUsage(AnalysisUsage &AU) const { 715 AU.addRequired<DominatorTree>(); 716 AU.addRequired<MemoryDependenceAnalysis>(); 717 AU.addRequired<AliasAnalysis>(); 718 719 AU.addPreserved<DominatorTree>(); 720 AU.addPreserved<AliasAnalysis>(); 721 } 722 723 // Helper fuctions 724 // FIXME: eliminate or document these better 725 bool processLoad(LoadInst* L, 726 SmallVectorImpl<Instruction*> &toErase); 727 bool processInstruction(Instruction* I, 728 SmallVectorImpl<Instruction*> &toErase); 729 bool processNonLocalLoad(LoadInst* L, 730 SmallVectorImpl<Instruction*> &toErase); 731 bool processBlock(BasicBlock* BB); 732 Value *GetValueForBlock(BasicBlock *BB, Instruction* orig, 733 DenseMap<BasicBlock*, Value*> &Phis, 734 bool top_level = false); 735 void dump(DenseMap<uint32_t, Value*>& d); 736 bool iterateOnFunction(Function &F); 737 Value* CollapsePhi(PHINode* p); 738 bool isSafeReplacement(PHINode* p, Instruction* inst); 739 bool performPRE(Function& F); 740 Value* lookupNumber(BasicBlock* BB, uint32_t num); 741 bool mergeBlockIntoPredecessor(BasicBlock* BB); 742 Value* AttemptRedundancyElimination(Instruction* orig, unsigned valno); 743 void cleanupGlobalSets(); 744 }; 745 746 char GVN::ID = 0; 747} 748 749// createGVNPass - The public interface to this file... 750FunctionPass *llvm::createGVNPass() { return new GVN(); } 751 752static RegisterPass<GVN> X("gvn", 753 "Global Value Numbering"); 754 755void GVN::dump(DenseMap<uint32_t, Value*>& d) { 756 printf("{\n"); 757 for (DenseMap<uint32_t, Value*>::iterator I = d.begin(), 758 E = d.end(); I != E; ++I) { 759 printf("%d\n", I->first); 760 I->second->dump(); 761 } 762 printf("}\n"); 763} 764 765Value* GVN::CollapsePhi(PHINode* p) { 766 Value* constVal = p->hasConstantValue(); 767 if (!constVal) return 0; 768 769 Instruction* inst = dyn_cast<Instruction>(constVal); 770 if (!inst) 771 return constVal; 772 773 if (DT->dominates(inst, p)) 774 if (isSafeReplacement(p, inst)) 775 return inst; 776 return 0; 777} 778 779bool GVN::isSafeReplacement(PHINode* p, Instruction* inst) { 780 if (!isa<PHINode>(inst)) 781 return true; 782 783 for (Instruction::use_iterator UI = p->use_begin(), E = p->use_end(); 784 UI != E; ++UI) 785 if (PHINode* use_phi = dyn_cast<PHINode>(UI)) 786 if (use_phi->getParent() == inst->getParent()) 787 return false; 788 789 return true; 790} 791 792/// GetValueForBlock - Get the value to use within the specified basic block. 793/// available values are in Phis. 794Value *GVN::GetValueForBlock(BasicBlock *BB, Instruction* orig, 795 DenseMap<BasicBlock*, Value*> &Phis, 796 bool top_level) { 797 798 // If we have already computed this value, return the previously computed val. 799 DenseMap<BasicBlock*, Value*>::iterator V = Phis.find(BB); 800 if (V != Phis.end() && !top_level) return V->second; 801 802 // If the block is unreachable, just return undef, since this path 803 // can't actually occur at runtime. 804 if (!DT->isReachableFromEntry(BB)) 805 return Phis[BB] = UndefValue::get(orig->getType()); 806 807 if (BasicBlock *Pred = BB->getSinglePredecessor()) { 808 Value *ret = GetValueForBlock(Pred, orig, Phis); 809 Phis[BB] = ret; 810 return ret; 811 } 812 813 // Get the number of predecessors of this block so we can reserve space later. 814 // If there is already a PHI in it, use the #preds from it, otherwise count. 815 // Getting it from the PHI is constant time. 816 unsigned NumPreds; 817 if (PHINode *ExistingPN = dyn_cast<PHINode>(BB->begin())) 818 NumPreds = ExistingPN->getNumIncomingValues(); 819 else 820 NumPreds = std::distance(pred_begin(BB), pred_end(BB)); 821 822 // Otherwise, the idom is the loop, so we need to insert a PHI node. Do so 823 // now, then get values to fill in the incoming values for the PHI. 824 PHINode *PN = PHINode::Create(orig->getType(), orig->getName()+".rle", 825 BB->begin()); 826 PN->reserveOperandSpace(NumPreds); 827 828 Phis.insert(std::make_pair(BB, PN)); 829 830 // Fill in the incoming values for the block. 831 for (pred_iterator PI = pred_begin(BB), E = pred_end(BB); PI != E; ++PI) { 832 Value* val = GetValueForBlock(*PI, orig, Phis); 833 PN->addIncoming(val, *PI); 834 } 835 836 VN.getAliasAnalysis()->copyValue(orig, PN); 837 838 // Attempt to collapse PHI nodes that are trivially redundant 839 Value* v = CollapsePhi(PN); 840 if (!v) { 841 // Cache our phi construction results 842 if (LoadInst* L = dyn_cast<LoadInst>(orig)) 843 phiMap[L->getPointerOperand()].insert(PN); 844 else 845 phiMap[orig].insert(PN); 846 847 return PN; 848 } 849 850 PN->replaceAllUsesWith(v); 851 if (isa<PointerType>(v->getType())) 852 MD->invalidateCachedPointerInfo(v); 853 854 for (DenseMap<BasicBlock*, Value*>::iterator I = Phis.begin(), 855 E = Phis.end(); I != E; ++I) 856 if (I->second == PN) 857 I->second = v; 858 859 DEBUG(cerr << "GVN removed: " << *PN); 860 MD->removeInstruction(PN); 861 PN->eraseFromParent(); 862 863 Phis[BB] = v; 864 return v; 865} 866 867/// IsValueFullyAvailableInBlock - Return true if we can prove that the value 868/// we're analyzing is fully available in the specified block. As we go, keep 869/// track of which blocks we know are fully alive in FullyAvailableBlocks. This 870/// map is actually a tri-state map with the following values: 871/// 0) we know the block *is not* fully available. 872/// 1) we know the block *is* fully available. 873/// 2) we do not know whether the block is fully available or not, but we are 874/// currently speculating that it will be. 875/// 3) we are speculating for this block and have used that to speculate for 876/// other blocks. 877static bool IsValueFullyAvailableInBlock(BasicBlock *BB, 878 DenseMap<BasicBlock*, char> &FullyAvailableBlocks) { 879 // Optimistically assume that the block is fully available and check to see 880 // if we already know about this block in one lookup. 881 std::pair<DenseMap<BasicBlock*, char>::iterator, char> IV = 882 FullyAvailableBlocks.insert(std::make_pair(BB, 2)); 883 884 // If the entry already existed for this block, return the precomputed value. 885 if (!IV.second) { 886 // If this is a speculative "available" value, mark it as being used for 887 // speculation of other blocks. 888 if (IV.first->second == 2) 889 IV.first->second = 3; 890 return IV.first->second != 0; 891 } 892 893 // Otherwise, see if it is fully available in all predecessors. 894 pred_iterator PI = pred_begin(BB), PE = pred_end(BB); 895 896 // If this block has no predecessors, it isn't live-in here. 897 if (PI == PE) 898 goto SpeculationFailure; 899 900 for (; PI != PE; ++PI) 901 // If the value isn't fully available in one of our predecessors, then it 902 // isn't fully available in this block either. Undo our previous 903 // optimistic assumption and bail out. 904 if (!IsValueFullyAvailableInBlock(*PI, FullyAvailableBlocks)) 905 goto SpeculationFailure; 906 907 return true; 908 909// SpeculationFailure - If we get here, we found out that this is not, after 910// all, a fully-available block. We have a problem if we speculated on this and 911// used the speculation to mark other blocks as available. 912SpeculationFailure: 913 char &BBVal = FullyAvailableBlocks[BB]; 914 915 // If we didn't speculate on this, just return with it set to false. 916 if (BBVal == 2) { 917 BBVal = 0; 918 return false; 919 } 920 921 // If we did speculate on this value, we could have blocks set to 1 that are 922 // incorrect. Walk the (transitive) successors of this block and mark them as 923 // 0 if set to one. 924 SmallVector<BasicBlock*, 32> BBWorklist; 925 BBWorklist.push_back(BB); 926 927 while (!BBWorklist.empty()) { 928 BasicBlock *Entry = BBWorklist.pop_back_val(); 929 // Note that this sets blocks to 0 (unavailable) if they happen to not 930 // already be in FullyAvailableBlocks. This is safe. 931 char &EntryVal = FullyAvailableBlocks[Entry]; 932 if (EntryVal == 0) continue; // Already unavailable. 933 934 // Mark as unavailable. 935 EntryVal = 0; 936 937 for (succ_iterator I = succ_begin(Entry), E = succ_end(Entry); I != E; ++I) 938 BBWorklist.push_back(*I); 939 } 940 941 return false; 942} 943 944/// processNonLocalLoad - Attempt to eliminate a load whose dependencies are 945/// non-local by performing PHI construction. 946bool GVN::processNonLocalLoad(LoadInst *LI, 947 SmallVectorImpl<Instruction*> &toErase) { 948 // Find the non-local dependencies of the load. 949 SmallVector<MemoryDependenceAnalysis::NonLocalDepEntry, 64> Deps; 950 MD->getNonLocalPointerDependency(LI->getOperand(0), true, LI->getParent(), 951 Deps); 952 //DEBUG(cerr << "INVESTIGATING NONLOCAL LOAD: " << Deps.size() << *LI); 953 954 // If we had to process more than one hundred blocks to find the 955 // dependencies, this load isn't worth worrying about. Optimizing 956 // it will be too expensive. 957 if (Deps.size() > 100) 958 return false; 959 960 // If we had a phi translation failure, we'll have a single entry which is a 961 // clobber in the current block. Reject this early. 962 if (Deps.size() == 1 && Deps[0].second.isClobber()) 963 return false; 964 965 // Filter out useless results (non-locals, etc). Keep track of the blocks 966 // where we have a value available in repl, also keep track of whether we see 967 // dependencies that produce an unknown value for the load (such as a call 968 // that could potentially clobber the load). 969 SmallVector<std::pair<BasicBlock*, Value*>, 16> ValuesPerBlock; 970 SmallVector<BasicBlock*, 16> UnavailableBlocks; 971 972 for (unsigned i = 0, e = Deps.size(); i != e; ++i) { 973 BasicBlock *DepBB = Deps[i].first; 974 MemDepResult DepInfo = Deps[i].second; 975 976 if (DepInfo.isClobber()) { 977 UnavailableBlocks.push_back(DepBB); 978 continue; 979 } 980 981 Instruction *DepInst = DepInfo.getInst(); 982 983 // Loading the allocation -> undef. 984 if (isa<AllocationInst>(DepInst)) { 985 ValuesPerBlock.push_back(std::make_pair(DepBB, 986 UndefValue::get(LI->getType()))); 987 continue; 988 } 989 990 if (StoreInst* S = dyn_cast<StoreInst>(DepInst)) { 991 // Reject loads and stores that are to the same address but are of 992 // different types. 993 // NOTE: 403.gcc does have this case (e.g. in readonly_fields_p) because 994 // of bitfield access, it would be interesting to optimize for it at some 995 // point. 996 if (S->getOperand(0)->getType() != LI->getType()) { 997 UnavailableBlocks.push_back(DepBB); 998 continue; 999 } 1000 1001 ValuesPerBlock.push_back(std::make_pair(DepBB, S->getOperand(0))); 1002 1003 } else if (LoadInst* LD = dyn_cast<LoadInst>(DepInst)) { 1004 if (LD->getType() != LI->getType()) { 1005 UnavailableBlocks.push_back(DepBB); 1006 continue; 1007 } 1008 ValuesPerBlock.push_back(std::make_pair(DepBB, LD)); 1009 } else { 1010 UnavailableBlocks.push_back(DepBB); 1011 continue; 1012 } 1013 } 1014 1015 // If we have no predecessors that produce a known value for this load, exit 1016 // early. 1017 if (ValuesPerBlock.empty()) return false; 1018 1019 // If all of the instructions we depend on produce a known value for this 1020 // load, then it is fully redundant and we can use PHI insertion to compute 1021 // its value. Insert PHIs and remove the fully redundant value now. 1022 if (UnavailableBlocks.empty()) { 1023 // Use cached PHI construction information from previous runs 1024 SmallPtrSet<Instruction*, 4> &p = phiMap[LI->getPointerOperand()]; 1025 // FIXME: What does phiMap do? Are we positive it isn't getting invalidated? 1026 for (SmallPtrSet<Instruction*, 4>::iterator I = p.begin(), E = p.end(); 1027 I != E; ++I) { 1028 if ((*I)->getParent() == LI->getParent()) { 1029 DEBUG(cerr << "GVN REMOVING NONLOCAL LOAD #1: " << *LI); 1030 LI->replaceAllUsesWith(*I); 1031 if (isa<PointerType>((*I)->getType())) 1032 MD->invalidateCachedPointerInfo(*I); 1033 toErase.push_back(LI); 1034 NumGVNLoad++; 1035 return true; 1036 } 1037 1038 ValuesPerBlock.push_back(std::make_pair((*I)->getParent(), *I)); 1039 } 1040 1041 DEBUG(cerr << "GVN REMOVING NONLOCAL LOAD: " << *LI); 1042 1043 DenseMap<BasicBlock*, Value*> BlockReplValues; 1044 BlockReplValues.insert(ValuesPerBlock.begin(), ValuesPerBlock.end()); 1045 // Perform PHI construction. 1046 Value* v = GetValueForBlock(LI->getParent(), LI, BlockReplValues, true); 1047 LI->replaceAllUsesWith(v); 1048 1049 if (!isa<GlobalValue>(v)) 1050 v->takeName(LI); 1051 if (isa<PointerType>(v->getType())) 1052 MD->invalidateCachedPointerInfo(v); 1053 toErase.push_back(LI); 1054 NumGVNLoad++; 1055 return true; 1056 } 1057 1058 if (!EnablePRE || !EnableLoadPRE) 1059 return false; 1060 1061 // Okay, we have *some* definitions of the value. This means that the value 1062 // is available in some of our (transitive) predecessors. Lets think about 1063 // doing PRE of this load. This will involve inserting a new load into the 1064 // predecessor when it's not available. We could do this in general, but 1065 // prefer to not increase code size. As such, we only do this when we know 1066 // that we only have to insert *one* load (which means we're basically moving 1067 // the load, not inserting a new one). 1068 1069 // Everything we do here is based on local predecessors of LI's block. If it 1070 // only has one predecessor, bail now. 1071 BasicBlock *LoadBB = LI->getParent(); 1072 if (LoadBB->getSinglePredecessor()) 1073 return false; 1074 1075 // If we have a repl set with LI itself in it, this means we have a loop where 1076 // at least one of the values is LI. Since this means that we won't be able 1077 // to eliminate LI even if we insert uses in the other predecessors, we will 1078 // end up increasing code size. Reject this by scanning for LI. 1079 for (unsigned i = 0, e = ValuesPerBlock.size(); i != e; ++i) 1080 if (ValuesPerBlock[i].second == LI) 1081 return false; 1082 1083 // Okay, we have some hope :). Check to see if the loaded value is fully 1084 // available in all but one predecessor. 1085 // FIXME: If we could restructure the CFG, we could make a common pred with 1086 // all the preds that don't have an available LI and insert a new load into 1087 // that one block. 1088 BasicBlock *UnavailablePred = 0; 1089 1090 DenseMap<BasicBlock*, char> FullyAvailableBlocks; 1091 for (unsigned i = 0, e = ValuesPerBlock.size(); i != e; ++i) 1092 FullyAvailableBlocks[ValuesPerBlock[i].first] = true; 1093 for (unsigned i = 0, e = UnavailableBlocks.size(); i != e; ++i) 1094 FullyAvailableBlocks[UnavailableBlocks[i]] = false; 1095 1096 for (pred_iterator PI = pred_begin(LoadBB), E = pred_end(LoadBB); 1097 PI != E; ++PI) { 1098 if (IsValueFullyAvailableInBlock(*PI, FullyAvailableBlocks)) 1099 continue; 1100 1101 // If this load is not available in multiple predecessors, reject it. 1102 if (UnavailablePred && UnavailablePred != *PI) 1103 return false; 1104 UnavailablePred = *PI; 1105 } 1106 1107 assert(UnavailablePred != 0 && 1108 "Fully available value should be eliminated above!"); 1109 1110 // If the loaded pointer is PHI node defined in this block, do PHI translation 1111 // to get its value in the predecessor. 1112 Value *LoadPtr = LI->getOperand(0)->DoPHITranslation(LoadBB, UnavailablePred); 1113 1114 // Make sure the value is live in the predecessor. If it was defined by a 1115 // non-PHI instruction in this block, we don't know how to recompute it above. 1116 if (Instruction *LPInst = dyn_cast<Instruction>(LoadPtr)) 1117 if (!DT->dominates(LPInst->getParent(), UnavailablePred)) { 1118 DEBUG(cerr << "COULDN'T PRE LOAD BECAUSE PTR IS UNAVAILABLE IN PRED: " 1119 << *LPInst << *LI << "\n"); 1120 return false; 1121 } 1122 1123 // We don't currently handle critical edges :( 1124 if (UnavailablePred->getTerminator()->getNumSuccessors() != 1) { 1125 DEBUG(cerr << "COULD NOT PRE LOAD BECAUSE OF CRITICAL EDGE '" 1126 << UnavailablePred->getName() << "': " << *LI); 1127 return false; 1128 } 1129 1130 // Okay, we can eliminate this load by inserting a reload in the predecessor 1131 // and using PHI construction to get the value in the other predecessors, do 1132 // it. 1133 DEBUG(cerr << "GVN REMOVING PRE LOAD: " << *LI); 1134 1135 Value *NewLoad = new LoadInst(LoadPtr, LI->getName()+".pre", false, 1136 LI->getAlignment(), 1137 UnavailablePred->getTerminator()); 1138 1139 DenseMap<BasicBlock*, Value*> BlockReplValues; 1140 BlockReplValues.insert(ValuesPerBlock.begin(), ValuesPerBlock.end()); 1141 BlockReplValues[UnavailablePred] = NewLoad; 1142 1143 // Perform PHI construction. 1144 Value* v = GetValueForBlock(LI->getParent(), LI, BlockReplValues, true); 1145 LI->replaceAllUsesWith(v); 1146 if (!isa<GlobalValue>(v)) 1147 v->takeName(LI); 1148 if (isa<PointerType>(v->getType())) 1149 MD->invalidateCachedPointerInfo(v); 1150 toErase.push_back(LI); 1151 NumPRELoad++; 1152 return true; 1153} 1154 1155/// processLoad - Attempt to eliminate a load, first by eliminating it 1156/// locally, and then attempting non-local elimination if that fails. 1157bool GVN::processLoad(LoadInst *L, SmallVectorImpl<Instruction*> &toErase) { 1158 if (L->isVolatile()) 1159 return false; 1160 1161 Value* pointer = L->getPointerOperand(); 1162 1163 // ... to a pointer that has been loaded from before... 1164 MemDepResult dep = MD->getDependency(L); 1165 1166 // If the value isn't available, don't do anything! 1167 if (dep.isClobber()) 1168 return false; 1169 1170 // If it is defined in another block, try harder. 1171 if (dep.isNonLocal()) 1172 return processNonLocalLoad(L, toErase); 1173 1174 Instruction *DepInst = dep.getInst(); 1175 if (StoreInst *DepSI = dyn_cast<StoreInst>(DepInst)) { 1176 // Only forward substitute stores to loads of the same type. 1177 // FIXME: Could do better! 1178 if (DepSI->getPointerOperand()->getType() != pointer->getType()) 1179 return false; 1180 1181 // Remove it! 1182 L->replaceAllUsesWith(DepSI->getOperand(0)); 1183 if (isa<PointerType>(DepSI->getOperand(0)->getType())) 1184 MD->invalidateCachedPointerInfo(DepSI->getOperand(0)); 1185 toErase.push_back(L); 1186 NumGVNLoad++; 1187 return true; 1188 } 1189 1190 if (LoadInst *DepLI = dyn_cast<LoadInst>(DepInst)) { 1191 // Only forward substitute stores to loads of the same type. 1192 // FIXME: Could do better! load i32 -> load i8 -> truncate on little endian. 1193 if (DepLI->getType() != L->getType()) 1194 return false; 1195 1196 // Remove it! 1197 L->replaceAllUsesWith(DepLI); 1198 if (isa<PointerType>(DepLI->getType())) 1199 MD->invalidateCachedPointerInfo(DepLI); 1200 toErase.push_back(L); 1201 NumGVNLoad++; 1202 return true; 1203 } 1204 1205 // If this load really doesn't depend on anything, then we must be loading an 1206 // undef value. This can happen when loading for a fresh allocation with no 1207 // intervening stores, for example. 1208 if (isa<AllocationInst>(DepInst)) { 1209 L->replaceAllUsesWith(UndefValue::get(L->getType())); 1210 toErase.push_back(L); 1211 NumGVNLoad++; 1212 return true; 1213 } 1214 1215 return false; 1216} 1217 1218Value* GVN::lookupNumber(BasicBlock* BB, uint32_t num) { 1219 DenseMap<BasicBlock*, ValueNumberScope*>::iterator I = localAvail.find(BB); 1220 if (I == localAvail.end()) 1221 return 0; 1222 1223 ValueNumberScope* locals = I->second; 1224 1225 while (locals) { 1226 DenseMap<uint32_t, Value*>::iterator I = locals->table.find(num); 1227 if (I != locals->table.end()) 1228 return I->second; 1229 else 1230 locals = locals->parent; 1231 } 1232 1233 return 0; 1234} 1235 1236/// AttemptRedundancyElimination - If the "fast path" of redundancy elimination 1237/// by inheritance from the dominator fails, see if we can perform phi 1238/// construction to eliminate the redundancy. 1239Value* GVN::AttemptRedundancyElimination(Instruction* orig, unsigned valno) { 1240 BasicBlock* BaseBlock = orig->getParent(); 1241 1242 SmallPtrSet<BasicBlock*, 4> Visited; 1243 SmallVector<BasicBlock*, 8> Stack; 1244 Stack.push_back(BaseBlock); 1245 1246 DenseMap<BasicBlock*, Value*> Results; 1247 1248 // Walk backwards through our predecessors, looking for instances of the 1249 // value number we're looking for. Instances are recorded in the Results 1250 // map, which is then used to perform phi construction. 1251 while (!Stack.empty()) { 1252 BasicBlock* Current = Stack.back(); 1253 Stack.pop_back(); 1254 1255 // If we've walked all the way to a proper dominator, then give up. Cases 1256 // where the instance is in the dominator will have been caught by the fast 1257 // path, and any cases that require phi construction further than this are 1258 // probably not worth it anyways. Note that this is a SIGNIFICANT compile 1259 // time improvement. 1260 if (DT->properlyDominates(Current, orig->getParent())) return 0; 1261 1262 DenseMap<BasicBlock*, ValueNumberScope*>::iterator LA = 1263 localAvail.find(Current); 1264 if (LA == localAvail.end()) return 0; 1265 DenseMap<unsigned, Value*>::iterator V = LA->second->table.find(valno); 1266 1267 if (V != LA->second->table.end()) { 1268 // Found an instance, record it. 1269 Results.insert(std::make_pair(Current, V->second)); 1270 continue; 1271 } 1272 1273 // If we reach the beginning of the function, then give up. 1274 if (pred_begin(Current) == pred_end(Current)) 1275 return 0; 1276 1277 for (pred_iterator PI = pred_begin(Current), PE = pred_end(Current); 1278 PI != PE; ++PI) 1279 if (Visited.insert(*PI)) 1280 Stack.push_back(*PI); 1281 } 1282 1283 // If we didn't find instances, give up. Otherwise, perform phi construction. 1284 if (Results.size() == 0) 1285 return 0; 1286 else 1287 return GetValueForBlock(BaseBlock, orig, Results, true); 1288} 1289 1290/// processInstruction - When calculating availability, handle an instruction 1291/// by inserting it into the appropriate sets 1292bool GVN::processInstruction(Instruction *I, 1293 SmallVectorImpl<Instruction*> &toErase) { 1294 if (LoadInst* L = dyn_cast<LoadInst>(I)) { 1295 bool changed = processLoad(L, toErase); 1296 1297 if (!changed) { 1298 unsigned num = VN.lookup_or_add(L); 1299 localAvail[I->getParent()]->table.insert(std::make_pair(num, L)); 1300 } 1301 1302 return changed; 1303 } 1304 1305 uint32_t nextNum = VN.getNextUnusedValueNumber(); 1306 unsigned num = VN.lookup_or_add(I); 1307 1308 // Allocations are always uniquely numbered, so we can save time and memory 1309 // by fast failing them. 1310 if (isa<AllocationInst>(I) || isa<TerminatorInst>(I)) { 1311 localAvail[I->getParent()]->table.insert(std::make_pair(num, I)); 1312 return false; 1313 } 1314 1315 // Collapse PHI nodes 1316 if (PHINode* p = dyn_cast<PHINode>(I)) { 1317 Value* constVal = CollapsePhi(p); 1318 1319 if (constVal) { 1320 for (PhiMapType::iterator PI = phiMap.begin(), PE = phiMap.end(); 1321 PI != PE; ++PI) 1322 PI->second.erase(p); 1323 1324 p->replaceAllUsesWith(constVal); 1325 if (isa<PointerType>(constVal->getType())) 1326 MD->invalidateCachedPointerInfo(constVal); 1327 toErase.push_back(p); 1328 } else { 1329 localAvail[I->getParent()]->table.insert(std::make_pair(num, I)); 1330 } 1331 1332 // If the number we were assigned was a brand new VN, then we don't 1333 // need to do a lookup to see if the number already exists 1334 // somewhere in the domtree: it can't! 1335 } else if (num == nextNum) { 1336 localAvail[I->getParent()]->table.insert(std::make_pair(num, I)); 1337 1338 // Perform fast-path value-number based elimination of values inherited from 1339 // dominators. 1340 } else if (Value* repl = lookupNumber(I->getParent(), num)) { 1341 // Remove it! 1342 VN.erase(I); 1343 I->replaceAllUsesWith(repl); 1344 if (isa<PointerType>(repl->getType())) 1345 MD->invalidateCachedPointerInfo(repl); 1346 toErase.push_back(I); 1347 return true; 1348 1349#if 0 1350 // Perform slow-pathvalue-number based elimination with phi construction. 1351 } else if (Value* repl = AttemptRedundancyElimination(I, num)) { 1352 // Remove it! 1353 VN.erase(I); 1354 I->replaceAllUsesWith(repl); 1355 if (isa<PointerType>(repl->getType())) 1356 MD->invalidateCachedPointerInfo(repl); 1357 toErase.push_back(I); 1358 return true; 1359#endif 1360 } else { 1361 localAvail[I->getParent()]->table.insert(std::make_pair(num, I)); 1362 } 1363 1364 return false; 1365} 1366 1367// GVN::runOnFunction - This is the main transformation entry point for a 1368// function. 1369// 1370bool GVN::runOnFunction(Function& F) { 1371 MD = &getAnalysis<MemoryDependenceAnalysis>(); 1372 DT = &getAnalysis<DominatorTree>(); 1373 VN.setAliasAnalysis(&getAnalysis<AliasAnalysis>()); 1374 VN.setMemDep(MD); 1375 VN.setDomTree(DT); 1376 1377 bool changed = false; 1378 bool shouldContinue = true; 1379 1380 // Merge unconditional branches, allowing PRE to catch more 1381 // optimization opportunities. 1382 for (Function::iterator FI = F.begin(), FE = F.end(); FI != FE; ) { 1383 BasicBlock* BB = FI; 1384 ++FI; 1385 bool removedBlock = MergeBlockIntoPredecessor(BB, this); 1386 if (removedBlock) NumGVNBlocks++; 1387 1388 changed |= removedBlock; 1389 } 1390 1391 unsigned Iteration = 0; 1392 1393 while (shouldContinue) { 1394 DEBUG(cerr << "GVN iteration: " << Iteration << "\n"); 1395 shouldContinue = iterateOnFunction(F); 1396 changed |= shouldContinue; 1397 ++Iteration; 1398 } 1399 1400 if (EnablePRE) { 1401 bool PREChanged = true; 1402 while (PREChanged) { 1403 PREChanged = performPRE(F); 1404 changed |= PREChanged; 1405 } 1406 } 1407 // FIXME: Should perform GVN again after PRE does something. PRE can move 1408 // computations into blocks where they become fully redundant. Note that 1409 // we can't do this until PRE's critical edge splitting updates memdep. 1410 // Actually, when this happens, we should just fully integrate PRE into GVN. 1411 1412 cleanupGlobalSets(); 1413 1414 return changed; 1415} 1416 1417 1418bool GVN::processBlock(BasicBlock* BB) { 1419 DomTreeNode* DTN = DT->getNode(BB); 1420 // FIXME: Kill off toErase by doing erasing eagerly in a helper function (and 1421 // incrementing BI before processing an instruction). 1422 SmallVector<Instruction*, 8> toErase; 1423 bool changed_function = false; 1424 1425 if (DTN->getIDom()) 1426 localAvail[BB] = 1427 new ValueNumberScope(localAvail[DTN->getIDom()->getBlock()]); 1428 else 1429 localAvail[BB] = new ValueNumberScope(0); 1430 1431 for (BasicBlock::iterator BI = BB->begin(), BE = BB->end(); 1432 BI != BE;) { 1433 changed_function |= processInstruction(BI, toErase); 1434 if (toErase.empty()) { 1435 ++BI; 1436 continue; 1437 } 1438 1439 // If we need some instructions deleted, do it now. 1440 NumGVNInstr += toErase.size(); 1441 1442 // Avoid iterator invalidation. 1443 bool AtStart = BI == BB->begin(); 1444 if (!AtStart) 1445 --BI; 1446 1447 for (SmallVector<Instruction*, 4>::iterator I = toErase.begin(), 1448 E = toErase.end(); I != E; ++I) { 1449 DEBUG(cerr << "GVN removed: " << **I); 1450 MD->removeInstruction(*I); 1451 (*I)->eraseFromParent(); 1452 } 1453 toErase.clear(); 1454 1455 if (AtStart) 1456 BI = BB->begin(); 1457 else 1458 ++BI; 1459 } 1460 1461 return changed_function; 1462} 1463 1464/// performPRE - Perform a purely local form of PRE that looks for diamond 1465/// control flow patterns and attempts to perform simple PRE at the join point. 1466bool GVN::performPRE(Function& F) { 1467 bool Changed = false; 1468 SmallVector<std::pair<TerminatorInst*, unsigned>, 4> toSplit; 1469 DenseMap<BasicBlock*, Value*> predMap; 1470 for (df_iterator<BasicBlock*> DI = df_begin(&F.getEntryBlock()), 1471 DE = df_end(&F.getEntryBlock()); DI != DE; ++DI) { 1472 BasicBlock* CurrentBlock = *DI; 1473 1474 // Nothing to PRE in the entry block. 1475 if (CurrentBlock == &F.getEntryBlock()) continue; 1476 1477 for (BasicBlock::iterator BI = CurrentBlock->begin(), 1478 BE = CurrentBlock->end(); BI != BE; ) { 1479 Instruction *CurInst = BI++; 1480 1481 if (isa<AllocationInst>(CurInst) || isa<TerminatorInst>(CurInst) || 1482 isa<PHINode>(CurInst) || CurInst->mayReadFromMemory() || 1483 CurInst->mayWriteToMemory()) 1484 continue; 1485 1486 uint32_t valno = VN.lookup(CurInst); 1487 1488 // Look for the predecessors for PRE opportunities. We're 1489 // only trying to solve the basic diamond case, where 1490 // a value is computed in the successor and one predecessor, 1491 // but not the other. We also explicitly disallow cases 1492 // where the successor is its own predecessor, because they're 1493 // more complicated to get right. 1494 unsigned numWith = 0; 1495 unsigned numWithout = 0; 1496 BasicBlock* PREPred = 0; 1497 predMap.clear(); 1498 1499 for (pred_iterator PI = pred_begin(CurrentBlock), 1500 PE = pred_end(CurrentBlock); PI != PE; ++PI) { 1501 // We're not interested in PRE where the block is its 1502 // own predecessor, on in blocks with predecessors 1503 // that are not reachable. 1504 if (*PI == CurrentBlock) { 1505 numWithout = 2; 1506 break; 1507 } else if (!localAvail.count(*PI)) { 1508 numWithout = 2; 1509 break; 1510 } 1511 1512 DenseMap<uint32_t, Value*>::iterator predV = 1513 localAvail[*PI]->table.find(valno); 1514 if (predV == localAvail[*PI]->table.end()) { 1515 PREPred = *PI; 1516 numWithout++; 1517 } else if (predV->second == CurInst) { 1518 numWithout = 2; 1519 } else { 1520 predMap[*PI] = predV->second; 1521 numWith++; 1522 } 1523 } 1524 1525 // Don't do PRE when it might increase code size, i.e. when 1526 // we would need to insert instructions in more than one pred. 1527 if (numWithout != 1 || numWith == 0) 1528 continue; 1529 1530 // We can't do PRE safely on a critical edge, so instead we schedule 1531 // the edge to be split and perform the PRE the next time we iterate 1532 // on the function. 1533 unsigned succNum = 0; 1534 for (unsigned i = 0, e = PREPred->getTerminator()->getNumSuccessors(); 1535 i != e; ++i) 1536 if (PREPred->getTerminator()->getSuccessor(i) == CurrentBlock) { 1537 succNum = i; 1538 break; 1539 } 1540 1541 if (isCriticalEdge(PREPred->getTerminator(), succNum)) { 1542 toSplit.push_back(std::make_pair(PREPred->getTerminator(), succNum)); 1543 continue; 1544 } 1545 1546 // Instantiate the expression the in predecessor that lacked it. 1547 // Because we are going top-down through the block, all value numbers 1548 // will be available in the predecessor by the time we need them. Any 1549 // that weren't original present will have been instantiated earlier 1550 // in this loop. 1551 Instruction* PREInstr = CurInst->clone(); 1552 bool success = true; 1553 for (unsigned i = 0, e = CurInst->getNumOperands(); i != e; ++i) { 1554 Value *Op = PREInstr->getOperand(i); 1555 if (isa<Argument>(Op) || isa<Constant>(Op) || isa<GlobalValue>(Op)) 1556 continue; 1557 1558 if (Value *V = lookupNumber(PREPred, VN.lookup(Op))) { 1559 PREInstr->setOperand(i, V); 1560 } else { 1561 success = false; 1562 break; 1563 } 1564 } 1565 1566 // Fail out if we encounter an operand that is not available in 1567 // the PRE predecessor. This is typically because of loads which 1568 // are not value numbered precisely. 1569 if (!success) { 1570 delete PREInstr; 1571 continue; 1572 } 1573 1574 PREInstr->insertBefore(PREPred->getTerminator()); 1575 PREInstr->setName(CurInst->getName() + ".pre"); 1576 predMap[PREPred] = PREInstr; 1577 VN.add(PREInstr, valno); 1578 NumGVNPRE++; 1579 1580 // Update the availability map to include the new instruction. 1581 localAvail[PREPred]->table.insert(std::make_pair(valno, PREInstr)); 1582 1583 // Create a PHI to make the value available in this block. 1584 PHINode* Phi = PHINode::Create(CurInst->getType(), 1585 CurInst->getName() + ".pre-phi", 1586 CurrentBlock->begin()); 1587 for (pred_iterator PI = pred_begin(CurrentBlock), 1588 PE = pred_end(CurrentBlock); PI != PE; ++PI) 1589 Phi->addIncoming(predMap[*PI], *PI); 1590 1591 VN.add(Phi, valno); 1592 localAvail[CurrentBlock]->table[valno] = Phi; 1593 1594 CurInst->replaceAllUsesWith(Phi); 1595 if (isa<PointerType>(Phi->getType())) 1596 MD->invalidateCachedPointerInfo(Phi); 1597 VN.erase(CurInst); 1598 1599 DEBUG(cerr << "GVN PRE removed: " << *CurInst); 1600 MD->removeInstruction(CurInst); 1601 CurInst->eraseFromParent(); 1602 Changed = true; 1603 } 1604 } 1605 1606 for (SmallVector<std::pair<TerminatorInst*, unsigned>, 4>::iterator 1607 I = toSplit.begin(), E = toSplit.end(); I != E; ++I) 1608 SplitCriticalEdge(I->first, I->second, this); 1609 1610 return Changed || toSplit.size(); 1611} 1612 1613// iterateOnFunction - Executes one iteration of GVN 1614bool GVN::iterateOnFunction(Function &F) { 1615 cleanupGlobalSets(); 1616 1617 // Top-down walk of the dominator tree 1618 bool changed = false; 1619#if 0 1620 // Needed for value numbering with phi construction to work. 1621 ReversePostOrderTraversal<Function*> RPOT(&F); 1622 for (ReversePostOrderTraversal<Function*>::rpo_iterator RI = RPOT.begin(), 1623 RE = RPOT.end(); RI != RE; ++RI) 1624 changed |= processBlock(*RI); 1625#else 1626 for (df_iterator<DomTreeNode*> DI = df_begin(DT->getRootNode()), 1627 DE = df_end(DT->getRootNode()); DI != DE; ++DI) 1628 changed |= processBlock(DI->getBlock()); 1629#endif 1630 1631 return changed; 1632} 1633 1634void GVN::cleanupGlobalSets() { 1635 VN.clear(); 1636 phiMap.clear(); 1637 1638 for (DenseMap<BasicBlock*, ValueNumberScope*>::iterator 1639 I = localAvail.begin(), E = localAvail.end(); I != E; ++I) 1640 delete I->second; 1641 localAvail.clear(); 1642} 1643