GVN.cpp revision 13d10096e1e2c1185c89d94ca69827a737550afd
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 // Filter out useless results (non-locals, etc). Keep track of the blocks 961 // where we have a value available in repl, also keep track of whether we see 962 // dependencies that produce an unknown value for the load (such as a call 963 // that could potentially clobber the load). 964 SmallVector<std::pair<BasicBlock*, Value*>, 16> ValuesPerBlock; 965 SmallVector<BasicBlock*, 16> UnavailableBlocks; 966 967 for (unsigned i = 0, e = Deps.size(); i != e; ++i) { 968 BasicBlock *DepBB = Deps[i].first; 969 MemDepResult DepInfo = Deps[i].second; 970 971 if (DepInfo.isClobber()) { 972 UnavailableBlocks.push_back(DepBB); 973 continue; 974 } 975 976 Instruction *DepInst = DepInfo.getInst(); 977 978 // Loading the allocation -> undef. 979 if (isa<AllocationInst>(DepInst)) { 980 ValuesPerBlock.push_back(std::make_pair(DepBB, 981 UndefValue::get(LI->getType()))); 982 continue; 983 } 984 985 if (StoreInst* S = dyn_cast<StoreInst>(DepInst)) { 986 // Reject loads and stores that are to the same address but are of 987 // different types. 988 // NOTE: 403.gcc does have this case (e.g. in readonly_fields_p) because 989 // of bitfield access, it would be interesting to optimize for it at some 990 // point. 991 if (S->getOperand(0)->getType() != LI->getType()) { 992 UnavailableBlocks.push_back(DepBB); 993 continue; 994 } 995 996 ValuesPerBlock.push_back(std::make_pair(DepBB, S->getOperand(0))); 997 998 } else if (LoadInst* LD = dyn_cast<LoadInst>(DepInst)) { 999 if (LD->getType() != LI->getType()) { 1000 UnavailableBlocks.push_back(DepBB); 1001 continue; 1002 } 1003 ValuesPerBlock.push_back(std::make_pair(DepBB, LD)); 1004 } else { 1005 UnavailableBlocks.push_back(DepBB); 1006 continue; 1007 } 1008 } 1009 1010 // If we have no predecessors that produce a known value for this load, exit 1011 // early. 1012 if (ValuesPerBlock.empty()) return false; 1013 1014 // If all of the instructions we depend on produce a known value for this 1015 // load, then it is fully redundant and we can use PHI insertion to compute 1016 // its value. Insert PHIs and remove the fully redundant value now. 1017 if (UnavailableBlocks.empty()) { 1018 // Use cached PHI construction information from previous runs 1019 SmallPtrSet<Instruction*, 4> &p = phiMap[LI->getPointerOperand()]; 1020 // FIXME: What does phiMap do? Are we positive it isn't getting invalidated? 1021 for (SmallPtrSet<Instruction*, 4>::iterator I = p.begin(), E = p.end(); 1022 I != E; ++I) { 1023 if ((*I)->getParent() == LI->getParent()) { 1024 DEBUG(cerr << "GVN REMOVING NONLOCAL LOAD #1: " << *LI); 1025 LI->replaceAllUsesWith(*I); 1026 if (isa<PointerType>((*I)->getType())) 1027 MD->invalidateCachedPointerInfo(*I); 1028 toErase.push_back(LI); 1029 NumGVNLoad++; 1030 return true; 1031 } 1032 1033 ValuesPerBlock.push_back(std::make_pair((*I)->getParent(), *I)); 1034 } 1035 1036 DEBUG(cerr << "GVN REMOVING NONLOCAL LOAD: " << *LI); 1037 1038 DenseMap<BasicBlock*, Value*> BlockReplValues; 1039 BlockReplValues.insert(ValuesPerBlock.begin(), ValuesPerBlock.end()); 1040 // Perform PHI construction. 1041 Value* v = GetValueForBlock(LI->getParent(), LI, BlockReplValues, true); 1042 LI->replaceAllUsesWith(v); 1043 1044 if (!isa<GlobalValue>(v)) 1045 v->takeName(LI); 1046 if (isa<PointerType>(v->getType())) 1047 MD->invalidateCachedPointerInfo(v); 1048 toErase.push_back(LI); 1049 NumGVNLoad++; 1050 return true; 1051 } 1052 1053 if (!EnablePRE || !EnableLoadPRE) 1054 return false; 1055 1056 // Okay, we have *some* definitions of the value. This means that the value 1057 // is available in some of our (transitive) predecessors. Lets think about 1058 // doing PRE of this load. This will involve inserting a new load into the 1059 // predecessor when it's not available. We could do this in general, but 1060 // prefer to not increase code size. As such, we only do this when we know 1061 // that we only have to insert *one* load (which means we're basically moving 1062 // the load, not inserting a new one). 1063 1064 // Everything we do here is based on local predecessors of LI's block. If it 1065 // only has one predecessor, bail now. 1066 BasicBlock *LoadBB = LI->getParent(); 1067 if (LoadBB->getSinglePredecessor()) 1068 return false; 1069 1070 // If we have a repl set with LI itself in it, this means we have a loop where 1071 // at least one of the values is LI. Since this means that we won't be able 1072 // to eliminate LI even if we insert uses in the other predecessors, we will 1073 // end up increasing code size. Reject this by scanning for LI. 1074 for (unsigned i = 0, e = ValuesPerBlock.size(); i != e; ++i) 1075 if (ValuesPerBlock[i].second == LI) 1076 return false; 1077 1078 // Okay, we have some hope :). Check to see if the loaded value is fully 1079 // available in all but one predecessor. 1080 // FIXME: If we could restructure the CFG, we could make a common pred with 1081 // all the preds that don't have an available LI and insert a new load into 1082 // that one block. 1083 BasicBlock *UnavailablePred = 0; 1084 1085 DenseMap<BasicBlock*, char> FullyAvailableBlocks; 1086 for (unsigned i = 0, e = ValuesPerBlock.size(); i != e; ++i) 1087 FullyAvailableBlocks[ValuesPerBlock[i].first] = true; 1088 for (unsigned i = 0, e = UnavailableBlocks.size(); i != e; ++i) 1089 FullyAvailableBlocks[UnavailableBlocks[i]] = false; 1090 1091 for (pred_iterator PI = pred_begin(LoadBB), E = pred_end(LoadBB); 1092 PI != E; ++PI) { 1093 if (IsValueFullyAvailableInBlock(*PI, FullyAvailableBlocks)) 1094 continue; 1095 1096 // If this load is not available in multiple predecessors, reject it. 1097 if (UnavailablePred && UnavailablePred != *PI) 1098 return false; 1099 UnavailablePred = *PI; 1100 } 1101 1102 assert(UnavailablePred != 0 && 1103 "Fully available value should be eliminated above!"); 1104 1105 // If the loaded pointer is PHI node defined in this block, do PHI translation 1106 // to get its value in the predecessor. 1107 Value *LoadPtr = LI->getOperand(0)->DoPHITranslation(LoadBB, UnavailablePred); 1108 1109 // Make sure the value is live in the predecessor. If it was defined by a 1110 // non-PHI instruction in this block, we don't know how to recompute it above. 1111 if (Instruction *LPInst = dyn_cast<Instruction>(LoadPtr)) 1112 if (!DT->dominates(LPInst->getParent(), UnavailablePred)) { 1113 DEBUG(cerr << "COULDN'T PRE LOAD BECAUSE PTR IS UNAVAILABLE IN PRED: " 1114 << *LPInst << *LI << "\n"); 1115 return false; 1116 } 1117 1118 // We don't currently handle critical edges :( 1119 if (UnavailablePred->getTerminator()->getNumSuccessors() != 1) { 1120 DEBUG(cerr << "COULD NOT PRE LOAD BECAUSE OF CRITICAL EDGE '" 1121 << UnavailablePred->getName() << "': " << *LI); 1122 return false; 1123 } 1124 1125 // Okay, we can eliminate this load by inserting a reload in the predecessor 1126 // and using PHI construction to get the value in the other predecessors, do 1127 // it. 1128 DEBUG(cerr << "GVN REMOVING PRE LOAD: " << *LI); 1129 1130 Value *NewLoad = new LoadInst(LoadPtr, LI->getName()+".pre", false, 1131 LI->getAlignment(), 1132 UnavailablePred->getTerminator()); 1133 1134 DenseMap<BasicBlock*, Value*> BlockReplValues; 1135 BlockReplValues.insert(ValuesPerBlock.begin(), ValuesPerBlock.end()); 1136 BlockReplValues[UnavailablePred] = NewLoad; 1137 1138 // Perform PHI construction. 1139 Value* v = GetValueForBlock(LI->getParent(), LI, BlockReplValues, true); 1140 LI->replaceAllUsesWith(v); 1141 if (!isa<GlobalValue>(v)) 1142 v->takeName(LI); 1143 if (isa<PointerType>(v->getType())) 1144 MD->invalidateCachedPointerInfo(v); 1145 toErase.push_back(LI); 1146 NumPRELoad++; 1147 return true; 1148} 1149 1150/// processLoad - Attempt to eliminate a load, first by eliminating it 1151/// locally, and then attempting non-local elimination if that fails. 1152bool GVN::processLoad(LoadInst *L, SmallVectorImpl<Instruction*> &toErase) { 1153 if (L->isVolatile()) 1154 return false; 1155 1156 Value* pointer = L->getPointerOperand(); 1157 1158 // ... to a pointer that has been loaded from before... 1159 MemDepResult dep = MD->getDependency(L); 1160 1161 // If the value isn't available, don't do anything! 1162 if (dep.isClobber()) 1163 return false; 1164 1165 // If it is defined in another block, try harder. 1166 if (dep.isNonLocal()) 1167 return processNonLocalLoad(L, toErase); 1168 1169 Instruction *DepInst = dep.getInst(); 1170 if (StoreInst *DepSI = dyn_cast<StoreInst>(DepInst)) { 1171 // Only forward substitute stores to loads of the same type. 1172 // FIXME: Could do better! 1173 if (DepSI->getPointerOperand()->getType() != pointer->getType()) 1174 return false; 1175 1176 // Remove it! 1177 L->replaceAllUsesWith(DepSI->getOperand(0)); 1178 if (isa<PointerType>(DepSI->getOperand(0)->getType())) 1179 MD->invalidateCachedPointerInfo(DepSI->getOperand(0)); 1180 toErase.push_back(L); 1181 NumGVNLoad++; 1182 return true; 1183 } 1184 1185 if (LoadInst *DepLI = dyn_cast<LoadInst>(DepInst)) { 1186 // Only forward substitute stores to loads of the same type. 1187 // FIXME: Could do better! load i32 -> load i8 -> truncate on little endian. 1188 if (DepLI->getType() != L->getType()) 1189 return false; 1190 1191 // Remove it! 1192 L->replaceAllUsesWith(DepLI); 1193 if (isa<PointerType>(DepLI->getType())) 1194 MD->invalidateCachedPointerInfo(DepLI); 1195 toErase.push_back(L); 1196 NumGVNLoad++; 1197 return true; 1198 } 1199 1200 // If this load really doesn't depend on anything, then we must be loading an 1201 // undef value. This can happen when loading for a fresh allocation with no 1202 // intervening stores, for example. 1203 if (isa<AllocationInst>(DepInst)) { 1204 L->replaceAllUsesWith(UndefValue::get(L->getType())); 1205 toErase.push_back(L); 1206 NumGVNLoad++; 1207 return true; 1208 } 1209 1210 return false; 1211} 1212 1213Value* GVN::lookupNumber(BasicBlock* BB, uint32_t num) { 1214 DenseMap<BasicBlock*, ValueNumberScope*>::iterator I = localAvail.find(BB); 1215 if (I == localAvail.end()) 1216 return 0; 1217 1218 ValueNumberScope* locals = I->second; 1219 1220 while (locals) { 1221 DenseMap<uint32_t, Value*>::iterator I = locals->table.find(num); 1222 if (I != locals->table.end()) 1223 return I->second; 1224 else 1225 locals = locals->parent; 1226 } 1227 1228 return 0; 1229} 1230 1231/// AttemptRedundancyElimination - If the "fast path" of redundancy elimination 1232/// by inheritance from the dominator fails, see if we can perform phi 1233/// construction to eliminate the redundancy. 1234Value* GVN::AttemptRedundancyElimination(Instruction* orig, unsigned valno) { 1235 BasicBlock* BaseBlock = orig->getParent(); 1236 1237 SmallPtrSet<BasicBlock*, 4> Visited; 1238 SmallVector<BasicBlock*, 8> Stack; 1239 Stack.push_back(BaseBlock); 1240 1241 DenseMap<BasicBlock*, Value*> Results; 1242 1243 // Walk backwards through our predecessors, looking for instances of the 1244 // value number we're looking for. Instances are recorded in the Results 1245 // map, which is then used to perform phi construction. 1246 while (!Stack.empty()) { 1247 BasicBlock* Current = Stack.back(); 1248 Stack.pop_back(); 1249 1250 // If we've walked all the way to a proper dominator, then give up. Cases 1251 // where the instance is in the dominator will have been caught by the fast 1252 // path, and any cases that require phi construction further than this are 1253 // probably not worth it anyways. Note that this is a SIGNIFICANT compile 1254 // time improvement. 1255 if (DT->properlyDominates(Current, orig->getParent())) return 0; 1256 1257 DenseMap<BasicBlock*, ValueNumberScope*>::iterator LA = 1258 localAvail.find(Current); 1259 if (LA == localAvail.end()) return 0; 1260 DenseMap<unsigned, Value*>::iterator V = LA->second->table.find(valno); 1261 1262 if (V != LA->second->table.end()) { 1263 // Found an instance, record it. 1264 Results.insert(std::make_pair(Current, V->second)); 1265 continue; 1266 } 1267 1268 // If we reach the beginning of the function, then give up. 1269 if (pred_begin(Current) == pred_end(Current)) 1270 return 0; 1271 1272 for (pred_iterator PI = pred_begin(Current), PE = pred_end(Current); 1273 PI != PE; ++PI) 1274 if (Visited.insert(*PI)) 1275 Stack.push_back(*PI); 1276 } 1277 1278 // If we didn't find instances, give up. Otherwise, perform phi construction. 1279 if (Results.size() == 0) 1280 return 0; 1281 else 1282 return GetValueForBlock(BaseBlock, orig, Results, true); 1283} 1284 1285/// processInstruction - When calculating availability, handle an instruction 1286/// by inserting it into the appropriate sets 1287bool GVN::processInstruction(Instruction *I, 1288 SmallVectorImpl<Instruction*> &toErase) { 1289 if (LoadInst* L = dyn_cast<LoadInst>(I)) { 1290 bool changed = processLoad(L, toErase); 1291 1292 if (!changed) { 1293 unsigned num = VN.lookup_or_add(L); 1294 localAvail[I->getParent()]->table.insert(std::make_pair(num, L)); 1295 } 1296 1297 return changed; 1298 } 1299 1300 uint32_t nextNum = VN.getNextUnusedValueNumber(); 1301 unsigned num = VN.lookup_or_add(I); 1302 1303 // Allocations are always uniquely numbered, so we can save time and memory 1304 // by fast failing them. 1305 if (isa<AllocationInst>(I) || isa<TerminatorInst>(I)) { 1306 localAvail[I->getParent()]->table.insert(std::make_pair(num, I)); 1307 return false; 1308 } 1309 1310 // Collapse PHI nodes 1311 if (PHINode* p = dyn_cast<PHINode>(I)) { 1312 Value* constVal = CollapsePhi(p); 1313 1314 if (constVal) { 1315 for (PhiMapType::iterator PI = phiMap.begin(), PE = phiMap.end(); 1316 PI != PE; ++PI) 1317 PI->second.erase(p); 1318 1319 p->replaceAllUsesWith(constVal); 1320 if (isa<PointerType>(constVal->getType())) 1321 MD->invalidateCachedPointerInfo(constVal); 1322 toErase.push_back(p); 1323 } else { 1324 localAvail[I->getParent()]->table.insert(std::make_pair(num, I)); 1325 } 1326 1327 // If the number we were assigned was a brand new VN, then we don't 1328 // need to do a lookup to see if the number already exists 1329 // somewhere in the domtree: it can't! 1330 } else if (num == nextNum) { 1331 localAvail[I->getParent()]->table.insert(std::make_pair(num, I)); 1332 1333 // Perform fast-path value-number based elimination of values inherited from 1334 // dominators. 1335 } else if (Value* repl = lookupNumber(I->getParent(), num)) { 1336 // Remove it! 1337 VN.erase(I); 1338 I->replaceAllUsesWith(repl); 1339 if (isa<PointerType>(repl->getType())) 1340 MD->invalidateCachedPointerInfo(repl); 1341 toErase.push_back(I); 1342 return true; 1343 1344#if 0 1345 // Perform slow-pathvalue-number based elimination with phi construction. 1346 } else if (Value* repl = AttemptRedundancyElimination(I, num)) { 1347 // Remove it! 1348 VN.erase(I); 1349 I->replaceAllUsesWith(repl); 1350 if (isa<PointerType>(repl->getType())) 1351 MD->invalidateCachedPointerInfo(repl); 1352 toErase.push_back(I); 1353 return true; 1354#endif 1355 } else { 1356 localAvail[I->getParent()]->table.insert(std::make_pair(num, I)); 1357 } 1358 1359 return false; 1360} 1361 1362// GVN::runOnFunction - This is the main transformation entry point for a 1363// function. 1364// 1365bool GVN::runOnFunction(Function& F) { 1366 MD = &getAnalysis<MemoryDependenceAnalysis>(); 1367 DT = &getAnalysis<DominatorTree>(); 1368 VN.setAliasAnalysis(&getAnalysis<AliasAnalysis>()); 1369 VN.setMemDep(MD); 1370 VN.setDomTree(DT); 1371 1372 bool changed = false; 1373 bool shouldContinue = true; 1374 1375 // Merge unconditional branches, allowing PRE to catch more 1376 // optimization opportunities. 1377 for (Function::iterator FI = F.begin(), FE = F.end(); FI != FE; ) { 1378 BasicBlock* BB = FI; 1379 ++FI; 1380 bool removedBlock = MergeBlockIntoPredecessor(BB, this); 1381 if (removedBlock) NumGVNBlocks++; 1382 1383 changed |= removedBlock; 1384 } 1385 1386 unsigned Iteration = 0; 1387 1388 while (shouldContinue) { 1389 DEBUG(cerr << "GVN iteration: " << Iteration << "\n"); 1390 shouldContinue = iterateOnFunction(F); 1391 changed |= shouldContinue; 1392 ++Iteration; 1393 } 1394 1395 if (EnablePRE) { 1396 bool PREChanged = true; 1397 while (PREChanged) { 1398 PREChanged = performPRE(F); 1399 changed |= PREChanged; 1400 } 1401 } 1402 // FIXME: Should perform GVN again after PRE does something. PRE can move 1403 // computations into blocks where they become fully redundant. Note that 1404 // we can't do this until PRE's critical edge splitting updates memdep. 1405 // Actually, when this happens, we should just fully integrate PRE into GVN. 1406 1407 cleanupGlobalSets(); 1408 1409 return changed; 1410} 1411 1412 1413bool GVN::processBlock(BasicBlock* BB) { 1414 DomTreeNode* DTN = DT->getNode(BB); 1415 // FIXME: Kill off toErase by doing erasing eagerly in a helper function (and 1416 // incrementing BI before processing an instruction). 1417 SmallVector<Instruction*, 8> toErase; 1418 bool changed_function = false; 1419 1420 if (DTN->getIDom()) 1421 localAvail[BB] = 1422 new ValueNumberScope(localAvail[DTN->getIDom()->getBlock()]); 1423 else 1424 localAvail[BB] = new ValueNumberScope(0); 1425 1426 for (BasicBlock::iterator BI = BB->begin(), BE = BB->end(); 1427 BI != BE;) { 1428 changed_function |= processInstruction(BI, toErase); 1429 if (toErase.empty()) { 1430 ++BI; 1431 continue; 1432 } 1433 1434 // If we need some instructions deleted, do it now. 1435 NumGVNInstr += toErase.size(); 1436 1437 // Avoid iterator invalidation. 1438 bool AtStart = BI == BB->begin(); 1439 if (!AtStart) 1440 --BI; 1441 1442 for (SmallVector<Instruction*, 4>::iterator I = toErase.begin(), 1443 E = toErase.end(); I != E; ++I) { 1444 DEBUG(cerr << "GVN removed: " << **I); 1445 MD->removeInstruction(*I); 1446 (*I)->eraseFromParent(); 1447 } 1448 toErase.clear(); 1449 1450 if (AtStart) 1451 BI = BB->begin(); 1452 else 1453 ++BI; 1454 } 1455 1456 return changed_function; 1457} 1458 1459/// performPRE - Perform a purely local form of PRE that looks for diamond 1460/// control flow patterns and attempts to perform simple PRE at the join point. 1461bool GVN::performPRE(Function& F) { 1462 bool Changed = false; 1463 SmallVector<std::pair<TerminatorInst*, unsigned>, 4> toSplit; 1464 DenseMap<BasicBlock*, Value*> predMap; 1465 for (df_iterator<BasicBlock*> DI = df_begin(&F.getEntryBlock()), 1466 DE = df_end(&F.getEntryBlock()); DI != DE; ++DI) { 1467 BasicBlock* CurrentBlock = *DI; 1468 1469 // Nothing to PRE in the entry block. 1470 if (CurrentBlock == &F.getEntryBlock()) continue; 1471 1472 for (BasicBlock::iterator BI = CurrentBlock->begin(), 1473 BE = CurrentBlock->end(); BI != BE; ) { 1474 Instruction *CurInst = BI++; 1475 1476 if (isa<AllocationInst>(CurInst) || isa<TerminatorInst>(CurInst) || 1477 isa<PHINode>(CurInst) || CurInst->mayReadFromMemory() || 1478 CurInst->mayWriteToMemory()) 1479 continue; 1480 1481 uint32_t valno = VN.lookup(CurInst); 1482 1483 // Look for the predecessors for PRE opportunities. We're 1484 // only trying to solve the basic diamond case, where 1485 // a value is computed in the successor and one predecessor, 1486 // but not the other. We also explicitly disallow cases 1487 // where the successor is its own predecessor, because they're 1488 // more complicated to get right. 1489 unsigned numWith = 0; 1490 unsigned numWithout = 0; 1491 BasicBlock* PREPred = 0; 1492 predMap.clear(); 1493 1494 for (pred_iterator PI = pred_begin(CurrentBlock), 1495 PE = pred_end(CurrentBlock); PI != PE; ++PI) { 1496 // We're not interested in PRE where the block is its 1497 // own predecessor, on in blocks with predecessors 1498 // that are not reachable. 1499 if (*PI == CurrentBlock) { 1500 numWithout = 2; 1501 break; 1502 } else if (!localAvail.count(*PI)) { 1503 numWithout = 2; 1504 break; 1505 } 1506 1507 DenseMap<uint32_t, Value*>::iterator predV = 1508 localAvail[*PI]->table.find(valno); 1509 if (predV == localAvail[*PI]->table.end()) { 1510 PREPred = *PI; 1511 numWithout++; 1512 } else if (predV->second == CurInst) { 1513 numWithout = 2; 1514 } else { 1515 predMap[*PI] = predV->second; 1516 numWith++; 1517 } 1518 } 1519 1520 // Don't do PRE when it might increase code size, i.e. when 1521 // we would need to insert instructions in more than one pred. 1522 if (numWithout != 1 || numWith == 0) 1523 continue; 1524 1525 // We can't do PRE safely on a critical edge, so instead we schedule 1526 // the edge to be split and perform the PRE the next time we iterate 1527 // on the function. 1528 unsigned succNum = 0; 1529 for (unsigned i = 0, e = PREPred->getTerminator()->getNumSuccessors(); 1530 i != e; ++i) 1531 if (PREPred->getTerminator()->getSuccessor(i) == CurrentBlock) { 1532 succNum = i; 1533 break; 1534 } 1535 1536 if (isCriticalEdge(PREPred->getTerminator(), succNum)) { 1537 toSplit.push_back(std::make_pair(PREPred->getTerminator(), succNum)); 1538 continue; 1539 } 1540 1541 // Instantiate the expression the in predecessor that lacked it. 1542 // Because we are going top-down through the block, all value numbers 1543 // will be available in the predecessor by the time we need them. Any 1544 // that weren't original present will have been instantiated earlier 1545 // in this loop. 1546 Instruction* PREInstr = CurInst->clone(); 1547 bool success = true; 1548 for (unsigned i = 0, e = CurInst->getNumOperands(); i != e; ++i) { 1549 Value *Op = PREInstr->getOperand(i); 1550 if (isa<Argument>(Op) || isa<Constant>(Op) || isa<GlobalValue>(Op)) 1551 continue; 1552 1553 if (Value *V = lookupNumber(PREPred, VN.lookup(Op))) { 1554 PREInstr->setOperand(i, V); 1555 } else { 1556 success = false; 1557 break; 1558 } 1559 } 1560 1561 // Fail out if we encounter an operand that is not available in 1562 // the PRE predecessor. This is typically because of loads which 1563 // are not value numbered precisely. 1564 if (!success) { 1565 delete PREInstr; 1566 continue; 1567 } 1568 1569 PREInstr->insertBefore(PREPred->getTerminator()); 1570 PREInstr->setName(CurInst->getName() + ".pre"); 1571 predMap[PREPred] = PREInstr; 1572 VN.add(PREInstr, valno); 1573 NumGVNPRE++; 1574 1575 // Update the availability map to include the new instruction. 1576 localAvail[PREPred]->table.insert(std::make_pair(valno, PREInstr)); 1577 1578 // Create a PHI to make the value available in this block. 1579 PHINode* Phi = PHINode::Create(CurInst->getType(), 1580 CurInst->getName() + ".pre-phi", 1581 CurrentBlock->begin()); 1582 for (pred_iterator PI = pred_begin(CurrentBlock), 1583 PE = pred_end(CurrentBlock); PI != PE; ++PI) 1584 Phi->addIncoming(predMap[*PI], *PI); 1585 1586 VN.add(Phi, valno); 1587 localAvail[CurrentBlock]->table[valno] = Phi; 1588 1589 CurInst->replaceAllUsesWith(Phi); 1590 if (isa<PointerType>(Phi->getType())) 1591 MD->invalidateCachedPointerInfo(Phi); 1592 VN.erase(CurInst); 1593 1594 DEBUG(cerr << "GVN PRE removed: " << *CurInst); 1595 MD->removeInstruction(CurInst); 1596 CurInst->eraseFromParent(); 1597 Changed = true; 1598 } 1599 } 1600 1601 for (SmallVector<std::pair<TerminatorInst*, unsigned>, 4>::iterator 1602 I = toSplit.begin(), E = toSplit.end(); I != E; ++I) 1603 SplitCriticalEdge(I->first, I->second, this); 1604 1605 return Changed || toSplit.size(); 1606} 1607 1608// iterateOnFunction - Executes one iteration of GVN 1609bool GVN::iterateOnFunction(Function &F) { 1610 cleanupGlobalSets(); 1611 1612 // Top-down walk of the dominator tree 1613 bool changed = false; 1614#if 0 1615 // Needed for value numbering with phi construction to work. 1616 ReversePostOrderTraversal<Function*> RPOT(&F); 1617 for (ReversePostOrderTraversal<Function*>::rpo_iterator RI = RPOT.begin(), 1618 RE = RPOT.end(); RI != RE; ++RI) 1619 changed |= processBlock(*RI); 1620#else 1621 for (df_iterator<DomTreeNode*> DI = df_begin(DT->getRootNode()), 1622 DE = df_end(DT->getRootNode()); DI != DE; ++DI) 1623 changed |= processBlock(DI->getBlock()); 1624#endif 1625 1626 return changed; 1627} 1628 1629void GVN::cleanupGlobalSets() { 1630 VN.clear(); 1631 phiMap.clear(); 1632 1633 for (DenseMap<BasicBlock*, ValueNumberScope*>::iterator 1634 I = localAvail.begin(), E = localAvail.end(); I != E; ++I) 1635 delete I->second; 1636 localAvail.clear(); 1637} 1638