LLVM API Documentation
00001 //===- PRE.cpp - Partial Redundancy Elimination ---------------------------===// 00002 // 00003 // The LLVM Compiler Infrastructure 00004 // 00005 // This file was developed by the LLVM research group and is distributed under 00006 // the University of Illinois Open Source License. See LICENSE.TXT for details. 00007 // 00008 //===----------------------------------------------------------------------===// 00009 // 00010 // This file implements the well-known Partial Redundancy Elimination 00011 // optimization, using an SSA formulation based on e-paths. See this paper for 00012 // more information: 00013 // 00014 // E-path_PRE: partial redundancy elimination made easy 00015 // By: Dhananjay M. Dhamdhere In: ACM SIGPLAN Notices. Vol 37, #8, 2002 00016 // http://doi.acm.org/10.1145/596992.597004 00017 // 00018 // This file actually implements a sparse version of the algorithm, using SSA 00019 // and CFG properties instead of bit-vectors. 00020 // 00021 //===----------------------------------------------------------------------===// 00022 00023 #include "llvm/Pass.h" 00024 #include "llvm/Function.h" 00025 #include "llvm/Type.h" 00026 #include "llvm/Instructions.h" 00027 #include "llvm/Support/CFG.h" 00028 #include "llvm/Analysis/Dominators.h" 00029 #include "llvm/Analysis/PostDominators.h" 00030 #include "llvm/Analysis/ValueNumbering.h" 00031 #include "llvm/Transforms/Scalar.h" 00032 #include "llvm/Support/Debug.h" 00033 #include "llvm/ADT/DepthFirstIterator.h" 00034 #include "llvm/ADT/PostOrderIterator.h" 00035 #include "llvm/ADT/Statistic.h" 00036 #include "llvm/ADT/hash_set" 00037 #include "llvm/ADT/hash_map" 00038 using namespace llvm; 00039 00040 namespace { 00041 Statistic<> NumExprsEliminated("pre", "Number of expressions constantified"); 00042 Statistic<> NumRedundant ("pre", "Number of redundant exprs eliminated"); 00043 Statistic<> NumInserted ("pre", "Number of expressions inserted"); 00044 00045 struct PRE : public FunctionPass { 00046 virtual void getAnalysisUsage(AnalysisUsage &AU) const { 00047 AU.addRequiredID(BreakCriticalEdgesID); // No critical edges for now! 00048 AU.addRequired<PostDominatorTree>(); 00049 AU.addRequired<PostDominanceFrontier>(); 00050 AU.addRequired<DominatorSet>(); 00051 AU.addRequired<DominatorTree>(); 00052 AU.addRequired<DominanceFrontier>(); 00053 AU.addRequired<ValueNumbering>(); 00054 } 00055 virtual bool runOnFunction(Function &F); 00056 00057 private: 00058 // Block information - Map basic blocks in a function back and forth to 00059 // unsigned integers. 00060 std::vector<BasicBlock*> BlockMapping; 00061 hash_map<BasicBlock*, unsigned> BlockNumbering; 00062 00063 // ProcessedExpressions - Keep track of which expressions have already been 00064 // processed. 00065 hash_set<Instruction*> ProcessedExpressions; 00066 00067 // Provide access to the various analyses used... 00068 DominatorSet *DS; 00069 DominatorTree *DT; PostDominatorTree *PDT; 00070 DominanceFrontier *DF; PostDominanceFrontier *PDF; 00071 ValueNumbering *VN; 00072 00073 // AvailableBlocks - Contain a mapping of blocks with available expression 00074 // values to the expression value itself. This can be used as an efficient 00075 // way to find out if the expression is available in the block, and if so, 00076 // which version to use. This map is only used while processing a single 00077 // expression. 00078 // 00079 typedef hash_map<BasicBlock*, Instruction*> AvailableBlocksTy; 00080 AvailableBlocksTy AvailableBlocks; 00081 00082 bool ProcessBlock(BasicBlock *BB); 00083 00084 // Anticipatibility calculation... 00085 void MarkPostDominatingBlocksAnticipatible(PostDominatorTree::Node *N, 00086 std::vector<char> &AntBlocks, 00087 Instruction *Occurrence); 00088 void CalculateAnticipatiblityForOccurrence(unsigned BlockNo, 00089 std::vector<char> &AntBlocks, 00090 Instruction *Occurrence); 00091 void CalculateAnticipatibleBlocks(const std::map<unsigned, Instruction*> &D, 00092 std::vector<char> &AnticipatibleBlocks); 00093 00094 // PRE for an expression 00095 void MarkOccurrenceAvailableInAllDominatedBlocks(Instruction *Occurrence, 00096 BasicBlock *StartBlock); 00097 void ReplaceDominatedAvailableOccurrencesWith(Instruction *NewOcc, 00098 DominatorTree::Node *N); 00099 bool ProcessExpression(Instruction *I); 00100 }; 00101 00102 RegisterOpt<PRE> Z("pre", "Partial Redundancy Elimination"); 00103 } 00104 00105 00106 bool PRE::runOnFunction(Function &F) { 00107 VN = &getAnalysis<ValueNumbering>(); 00108 DS = &getAnalysis<DominatorSet>(); 00109 DT = &getAnalysis<DominatorTree>(); 00110 DF = &getAnalysis<DominanceFrontier>(); 00111 PDT = &getAnalysis<PostDominatorTree>(); 00112 PDF = &getAnalysis<PostDominanceFrontier>(); 00113 00114 DEBUG(std::cerr << "\n*** Running PRE on func '" << F.getName() << "'...\n"); 00115 00116 // Number the basic blocks based on a reverse post-order traversal of the CFG 00117 // so that all predecessors of a block (ignoring back edges) are visited 00118 // before a block is visited. 00119 // 00120 BlockMapping.reserve(F.size()); 00121 { 00122 ReversePostOrderTraversal<Function*> RPOT(&F); 00123 DEBUG(std::cerr << "Block order: "); 00124 for (ReversePostOrderTraversal<Function*>::rpo_iterator I = RPOT.begin(), 00125 E = RPOT.end(); I != E; ++I) { 00126 // Keep track of mapping... 00127 BasicBlock *BB = *I; 00128 BlockNumbering.insert(std::make_pair(BB, BlockMapping.size())); 00129 BlockMapping.push_back(BB); 00130 DEBUG(std::cerr << BB->getName() << " "); 00131 } 00132 DEBUG(std::cerr << "\n"); 00133 } 00134 00135 // Traverse the current function depth-first in dominator-tree order. This 00136 // ensures that we see all definitions before their uses (except for PHI 00137 // nodes), allowing us to hoist dependent expressions correctly. 00138 bool Changed = false; 00139 for (unsigned i = 0, e = BlockMapping.size(); i != e; ++i) 00140 Changed |= ProcessBlock(BlockMapping[i]); 00141 00142 // Free memory 00143 BlockMapping.clear(); 00144 BlockNumbering.clear(); 00145 ProcessedExpressions.clear(); 00146 return Changed; 00147 } 00148 00149 00150 // ProcessBlock - Process any expressions first seen in this block... 00151 // 00152 bool PRE::ProcessBlock(BasicBlock *BB) { 00153 bool Changed = false; 00154 00155 // DISABLED: This pass invalidates iterators and then uses them. 00156 return false; 00157 00158 // PRE expressions first defined in this block... 00159 for (BasicBlock::iterator I = BB->begin(); I != BB->end(); ) 00160 if (ProcessExpression(I++)) 00161 Changed = true; 00162 00163 return Changed; 00164 } 00165 00166 void PRE::MarkPostDominatingBlocksAnticipatible(PostDominatorTree::Node *N, 00167 std::vector<char> &AntBlocks, 00168 Instruction *Occurrence) { 00169 unsigned BlockNo = BlockNumbering[N->getBlock()]; 00170 00171 if (AntBlocks[BlockNo]) return; // Already known to be anticipatible?? 00172 00173 // Check to see if any of the operands are defined in this block, if so, the 00174 // entry of this block does not anticipate the expression. This computes 00175 // "transparency". 00176 for (unsigned i = 0, e = Occurrence->getNumOperands(); i != e; ++i) 00177 if (Instruction *I = dyn_cast<Instruction>(Occurrence->getOperand(i))) 00178 if (I->getParent() == N->getBlock()) // Operand is defined in this block! 00179 return; 00180 00181 if (isa<LoadInst>(Occurrence)) 00182 return; // FIXME: compute transparency for load instructions using AA 00183 00184 // Insert block into AntBlocks list... 00185 AntBlocks[BlockNo] = true; 00186 00187 for (PostDominatorTree::Node::iterator I = N->begin(), E = N->end(); I != E; 00188 ++I) 00189 MarkPostDominatingBlocksAnticipatible(*I, AntBlocks, Occurrence); 00190 } 00191 00192 void PRE::CalculateAnticipatiblityForOccurrence(unsigned BlockNo, 00193 std::vector<char> &AntBlocks, 00194 Instruction *Occurrence) { 00195 if (AntBlocks[BlockNo]) return; // Block already anticipatible! 00196 00197 BasicBlock *BB = BlockMapping[BlockNo]; 00198 00199 // For each occurrence, mark all post-dominated blocks as anticipatible... 00200 MarkPostDominatingBlocksAnticipatible(PDT->getNode(BB), AntBlocks, 00201 Occurrence); 00202 00203 // Next, mark any blocks in the post-dominance frontier as anticipatible iff 00204 // all successors are anticipatible. 00205 // 00206 PostDominanceFrontier::iterator PDFI = PDF->find(BB); 00207 if (PDFI != DF->end()) 00208 for (std::set<BasicBlock*>::iterator DI = PDFI->second.begin(); 00209 DI != PDFI->second.end(); ++DI) { 00210 BasicBlock *PDFBlock = *DI; 00211 bool AllSuccessorsAnticipatible = true; 00212 for (succ_iterator SI = succ_begin(PDFBlock), SE = succ_end(PDFBlock); 00213 SI != SE; ++SI) 00214 if (!AntBlocks[BlockNumbering[*SI]]) { 00215 AllSuccessorsAnticipatible = false; 00216 break; 00217 } 00218 00219 if (AllSuccessorsAnticipatible) 00220 CalculateAnticipatiblityForOccurrence(BlockNumbering[PDFBlock], 00221 AntBlocks, Occurrence); 00222 } 00223 } 00224 00225 00226 void PRE::CalculateAnticipatibleBlocks(const std::map<unsigned, 00227 Instruction*> &Defs, 00228 std::vector<char> &AntBlocks) { 00229 // Initialize to zeros... 00230 AntBlocks.resize(BlockMapping.size()); 00231 00232 // Loop over all of the expressions... 00233 for (std::map<unsigned, Instruction*>::const_iterator I = Defs.begin(), 00234 E = Defs.end(); I != E; ++I) 00235 CalculateAnticipatiblityForOccurrence(I->first, AntBlocks, I->second); 00236 } 00237 00238 /// MarkOccurrenceAvailableInAllDominatedBlocks - Add entries to AvailableBlocks 00239 /// for all nodes dominated by the occurrence to indicate that it is now the 00240 /// available occurrence to use in any of these blocks. 00241 /// 00242 void PRE::MarkOccurrenceAvailableInAllDominatedBlocks(Instruction *Occurrence, 00243 BasicBlock *BB) { 00244 // FIXME: There are much more efficient ways to get the blocks dominated 00245 // by a block. Use them. 00246 // 00247 DominatorTree::Node *N = DT->getNode(Occurrence->getParent()); 00248 for (df_iterator<DominatorTree::Node*> DI = df_begin(N), E = df_end(N); 00249 DI != E; ++DI) 00250 AvailableBlocks[(*DI)->getBlock()] = Occurrence; 00251 } 00252 00253 /// ReplaceDominatedAvailableOccurrencesWith - This loops over the region 00254 /// dominated by N, replacing any available expressions with NewOcc. 00255 void PRE::ReplaceDominatedAvailableOccurrencesWith(Instruction *NewOcc, 00256 DominatorTree::Node *N) { 00257 BasicBlock *BB = N->getBlock(); 00258 Instruction *&ExistingAvailableVal = AvailableBlocks[BB]; 00259 00260 // If there isn't a definition already active in this node, make this the new 00261 // active definition... 00262 if (ExistingAvailableVal == 0) { 00263 ExistingAvailableVal = NewOcc; 00264 00265 for (DominatorTree::Node::iterator I = N->begin(), E = N->end(); I != E;++I) 00266 ReplaceDominatedAvailableOccurrencesWith(NewOcc, *I); 00267 } else { 00268 // If there is already an active definition in this block, replace it with 00269 // NewOcc, and force it into all dominated blocks. 00270 DEBUG(std::cerr << " Replacing dominated occ %" 00271 << ExistingAvailableVal->getName() << " with %" << NewOcc->getName() 00272 << "\n"); 00273 assert(ExistingAvailableVal != NewOcc && "NewOcc already inserted??"); 00274 ExistingAvailableVal->replaceAllUsesWith(NewOcc); 00275 ++NumRedundant; 00276 00277 assert(ExistingAvailableVal->getParent() == BB && 00278 "OldOcc not defined in current block?"); 00279 BB->getInstList().erase(ExistingAvailableVal); 00280 00281 // Mark NewOCC as the Available expression in all blocks dominated by BB 00282 for (df_iterator<DominatorTree::Node*> DI = df_begin(N), E = df_end(N); 00283 DI != E; ++DI) 00284 AvailableBlocks[(*DI)->getBlock()] = NewOcc; 00285 } 00286 } 00287 00288 00289 /// ProcessExpression - Given an expression (instruction) process the 00290 /// instruction to remove any partial redundancies induced by equivalent 00291 /// computations. Note that we only need to PRE each expression once, so we 00292 /// keep track of whether an expression has been PRE'd already, and don't PRE an 00293 /// expression again. Expressions may be seen multiple times because process 00294 /// the entire equivalence class at once, which may leave expressions later in 00295 /// the control path. 00296 /// 00297 bool PRE::ProcessExpression(Instruction *Expr) { 00298 if (Expr->mayWriteToMemory() || Expr->getType() == Type::VoidTy || 00299 isa<PHINode>(Expr)) 00300 return false; // Cannot move expression 00301 if (ProcessedExpressions.count(Expr)) return false; // Already processed. 00302 00303 // Ok, this is the first time we have seen the expression. Build a set of 00304 // equivalent expressions using SSA def/use information. We consider 00305 // expressions to be equivalent if they are the same opcode and have 00306 // equivalent operands. As a special case for SSA, values produced by PHI 00307 // nodes are considered to be equivalent to all of their operands. 00308 // 00309 std::vector<Value*> Values; 00310 VN->getEqualNumberNodes(Expr, Values); 00311 00312 #if 0 00313 // FIXME: This should handle PHI nodes correctly. To do this, we need to 00314 // consider expressions of the following form equivalent to this set of 00315 // expressions: 00316 // 00317 // If an operand is a PHI node, add any occurrences of the expression with the 00318 // PHI operand replaced with the PHI node operands. This is only valid if the 00319 // PHI operand occurrences exist in blocks post-dominated by the incoming edge 00320 // of the PHI node. 00321 #endif 00322 00323 // We have to be careful to handle expression definitions which dominated by 00324 // other expressions. These can be directly eliminated in favor of their 00325 // dominating value. Keep track of which blocks contain definitions (the key) 00326 // and if a block contains a definition, which instruction it is. 00327 // 00328 std::map<unsigned, Instruction*> Definitions; 00329 Definitions.insert(std::make_pair(BlockNumbering[Expr->getParent()], Expr)); 00330 00331 bool Changed = false; 00332 00333 // Look at all of the equal values. If any of the values is not an 00334 // instruction, replace all other expressions immediately with it (it must be 00335 // an argument or a constant or something). Otherwise, convert the list of 00336 // values into a list of expression (instruction) definitions ordering 00337 // according to their dominator tree ordering. 00338 // 00339 Value *NonInstValue = 0; 00340 for (unsigned i = 0, e = Values.size(); i != e; ++i) 00341 if (Instruction *I = dyn_cast<Instruction>(Values[i])) { 00342 Instruction *&BlockInst = Definitions[BlockNumbering[I->getParent()]]; 00343 if (BlockInst && BlockInst != I) { // Eliminate direct redundancy 00344 if (DS->dominates(I, BlockInst)) { // I dom BlockInst 00345 BlockInst->replaceAllUsesWith(I); 00346 BlockInst->getParent()->getInstList().erase(BlockInst); 00347 } else { // BlockInst dom I 00348 I->replaceAllUsesWith(BlockInst); 00349 I->getParent()->getInstList().erase(I); 00350 I = BlockInst; 00351 } 00352 ++NumRedundant; 00353 } 00354 BlockInst = I; 00355 } else { 00356 NonInstValue = Values[i]; 00357 } 00358 00359 std::vector<Value*>().swap(Values); // Done with the values list 00360 00361 if (NonInstValue) { 00362 // This is the good, though unlikely, case where we find out that this 00363 // expression is equal to a constant or argument directly. We can replace 00364 // this and all of the other equivalent instructions with the value 00365 // directly. 00366 // 00367 for (std::map<unsigned, Instruction*>::iterator I = Definitions.begin(), 00368 E = Definitions.end(); I != E; ++I) { 00369 Instruction *Inst = I->second; 00370 // Replace the value with the specified non-instruction value. 00371 Inst->replaceAllUsesWith(NonInstValue); // Fixup any uses 00372 Inst->getParent()->getInstList().erase(Inst); // Erase the instruction 00373 } 00374 NumExprsEliminated += Definitions.size(); 00375 return true; // Program modified! 00376 } 00377 00378 // There are no expressions equal to this one. Exit early. 00379 assert(!Definitions.empty() && "no equal expressions??"); 00380 #if 0 00381 if (Definitions.size() == 1) { 00382 ProcessedExpressions.insert(Definitions.begin()->second); 00383 return Changed; 00384 } 00385 #endif 00386 DEBUG(std::cerr << "\n====--- Expression: " << *Expr); 00387 const Type *ExprType = Expr->getType(); 00388 00389 // AnticipatibleBlocks - Blocks where the current expression is anticipatible. 00390 // This is logically std::vector<bool> but using 'char' for performance. 00391 std::vector<char> AnticipatibleBlocks; 00392 00393 // Calculate all of the blocks which the current expression is anticipatible. 00394 CalculateAnticipatibleBlocks(Definitions, AnticipatibleBlocks); 00395 00396 // Print out anticipatible blocks... 00397 DEBUG(std::cerr << "AntBlocks: "; 00398 for (unsigned i = 0, e = AnticipatibleBlocks.size(); i != e; ++i) 00399 if (AnticipatibleBlocks[i]) 00400 std::cerr << BlockMapping[i]->getName() <<" "; 00401 std::cerr << "\n";); 00402 00403 00404 00405 // AvailabilityFrontier - Calculates the availability frontier for the current 00406 // expression. The availability frontier contains the blocks on the dominance 00407 // frontier of the current available expressions, iff they anticipate a 00408 // definition of the expression. 00409 hash_set<unsigned> AvailabilityFrontier; 00410 00411 Instruction *NonPHIOccurrence = 0; 00412 00413 while (!Definitions.empty() || !AvailabilityFrontier.empty()) { 00414 if (!Definitions.empty() && 00415 (AvailabilityFrontier.empty() || 00416 Definitions.begin()->first < *AvailabilityFrontier.begin())) { 00417 Instruction *Occurrence = Definitions.begin()->second; 00418 BasicBlock *BB = Occurrence->getParent(); 00419 Definitions.erase(Definitions.begin()); 00420 00421 DEBUG(std::cerr << "PROCESSING Occurrence: " << *Occurrence); 00422 00423 // Check to see if there is already an incoming value for this block... 00424 AvailableBlocksTy::iterator LBI = AvailableBlocks.find(BB); 00425 if (LBI != AvailableBlocks.end()) { 00426 // Yes, there is a dominating definition for this block. Replace this 00427 // occurrence with the incoming value. 00428 if (LBI->second != Occurrence) { 00429 DEBUG(std::cerr << " replacing with: " << *LBI->second); 00430 Occurrence->replaceAllUsesWith(LBI->second); 00431 BB->getInstList().erase(Occurrence); // Delete instruction 00432 ++NumRedundant; 00433 } 00434 } else { 00435 ProcessedExpressions.insert(Occurrence); 00436 if (!isa<PHINode>(Occurrence)) 00437 NonPHIOccurrence = Occurrence; // Keep an occurrence of this expr 00438 00439 // Okay, there is no incoming value for this block, so this expression 00440 // is a new definition that is good for this block and all blocks 00441 // dominated by it. Add this information to the AvailableBlocks map. 00442 // 00443 MarkOccurrenceAvailableInAllDominatedBlocks(Occurrence, BB); 00444 00445 // Update the dominance frontier for the definitions so far... if a node 00446 // in the dominator frontier now has all of its predecessors available, 00447 // and the block is in an anticipatible region, we can insert a PHI node 00448 // in that block. 00449 DominanceFrontier::iterator DFI = DF->find(BB); 00450 if (DFI != DF->end()) { 00451 for (std::set<BasicBlock*>::iterator DI = DFI->second.begin(); 00452 DI != DFI->second.end(); ++DI) { 00453 BasicBlock *DFBlock = *DI; 00454 unsigned DFBlockID = BlockNumbering[DFBlock]; 00455 if (AnticipatibleBlocks[DFBlockID]) { 00456 // Check to see if any of the predecessors of this block on the 00457 // frontier are not available... 00458 bool AnyNotAvailable = false; 00459 for (pred_iterator PI = pred_begin(DFBlock), 00460 PE = pred_end(DFBlock); PI != PE; ++PI) 00461 if (!AvailableBlocks.count(*PI)) { 00462 AnyNotAvailable = true; 00463 break; 00464 } 00465 00466 // If any predecessor blocks are not available, add the node to 00467 // the current expression dominance frontier. 00468 if (AnyNotAvailable) { 00469 AvailabilityFrontier.insert(DFBlockID); 00470 } else { 00471 // This block is no longer in the availability frontier, it IS 00472 // available. 00473 AvailabilityFrontier.erase(DFBlockID); 00474 00475 // If all of the predecessor blocks are available (and the block 00476 // anticipates a definition along the path to the exit), we need 00477 // to insert a new PHI node in this block. This block serves as 00478 // a new definition for the expression, extending the available 00479 // region. 00480 // 00481 PHINode *PN = new PHINode(ExprType, Expr->getName()+".pre", 00482 DFBlock->begin()); 00483 ProcessedExpressions.insert(PN); 00484 00485 DEBUG(std::cerr << " INSERTING PHI on frontier: " << *PN); 00486 00487 // Add the incoming blocks for the PHI node 00488 for (pred_iterator PI = pred_begin(DFBlock), 00489 PE = pred_end(DFBlock); PI != PE; ++PI) 00490 if (*PI != DFBlock) 00491 PN->addIncoming(AvailableBlocks[*PI], *PI); 00492 else // edge from the current block 00493 PN->addIncoming(PN, DFBlock); 00494 00495 Instruction *&BlockOcc = Definitions[DFBlockID]; 00496 if (BlockOcc) { 00497 DEBUG(std::cerr <<" PHI superceeds occurrence: "<< 00498 *BlockOcc); 00499 BlockOcc->replaceAllUsesWith(PN); 00500 BlockOcc->getParent()->getInstList().erase(BlockOcc); 00501 ++NumRedundant; 00502 } 00503 BlockOcc = PN; 00504 } 00505 } 00506 } 00507 } 00508 } 00509 00510 } else { 00511 // Otherwise we must be looking at a node in the availability frontier! 00512 unsigned AFBlockID = *AvailabilityFrontier.begin(); 00513 AvailabilityFrontier.erase(AvailabilityFrontier.begin()); 00514 BasicBlock *AFBlock = BlockMapping[AFBlockID]; 00515 00516 // We eliminate the partial redundancy on this frontier by inserting a PHI 00517 // node into this block, merging any incoming available versions into the 00518 // PHI and inserting a new computation into predecessors without an 00519 // incoming value. Note that we would have to insert the expression on 00520 // the edge if the predecessor didn't anticipate the expression and we 00521 // didn't break critical edges. 00522 // 00523 PHINode *PN = new PHINode(ExprType, Expr->getName()+".PRE", 00524 AFBlock->begin()); 00525 DEBUG(std::cerr << "INSERTING PHI for PR: " << *PN); 00526 00527 // If there is a pending occurrence in this block, make sure to replace it 00528 // with the PHI node... 00529 std::map<unsigned, Instruction*>::iterator EDFI = 00530 Definitions.find(AFBlockID); 00531 if (EDFI != Definitions.end()) { 00532 // There is already an occurrence in this block. Replace it with PN and 00533 // remove it. 00534 Instruction *OldOcc = EDFI->second; 00535 DEBUG(std::cerr << " Replaces occurrence: " << *OldOcc); 00536 OldOcc->replaceAllUsesWith(PN); 00537 AFBlock->getInstList().erase(OldOcc); 00538 Definitions.erase(EDFI); 00539 ++NumRedundant; 00540 } 00541 00542 for (pred_iterator PI = pred_begin(AFBlock), PE = pred_end(AFBlock); 00543 PI != PE; ++PI) { 00544 BasicBlock *Pred = *PI; 00545 AvailableBlocksTy::iterator LBI = AvailableBlocks.find(Pred); 00546 if (LBI != AvailableBlocks.end()) { // If there is a available value 00547 PN->addIncoming(LBI->second, Pred); // for this pred, use it. 00548 } else { // No available value yet... 00549 unsigned PredID = BlockNumbering[Pred]; 00550 00551 // Is the predecessor the same block that we inserted the PHI into? 00552 // (self loop) 00553 if (Pred == AFBlock) { 00554 // Yes, reuse the incoming value here... 00555 PN->addIncoming(PN, Pred); 00556 } else { 00557 // No, we must insert a new computation into this block and add it 00558 // to the definitions list... 00559 assert(NonPHIOccurrence && "No non-phi occurrences seen so far???"); 00560 Instruction *New = NonPHIOccurrence->clone(); 00561 New->setName(NonPHIOccurrence->getName() + ".PRE-inserted"); 00562 ProcessedExpressions.insert(New); 00563 00564 DEBUG(std::cerr << " INSERTING OCCURRRENCE: " << *New); 00565 00566 // Insert it into the bottom of the predecessor, right before the 00567 // terminator instruction... 00568 Pred->getInstList().insert(Pred->getTerminator(), New); 00569 00570 // Make this block be the available definition for any blocks it 00571 // dominates. The ONLY case that this can affect more than just the 00572 // block itself is when we are moving a computation to a loop 00573 // header. In all other cases, because we don't have critical 00574 // edges, the node is guaranteed to only dominate itself. 00575 // 00576 ReplaceDominatedAvailableOccurrencesWith(New, DT->getNode(Pred)); 00577 00578 // Add it as an incoming value on this edge to the PHI node 00579 PN->addIncoming(New, Pred); 00580 NonPHIOccurrence = New; 00581 NumInserted++; 00582 } 00583 } 00584 } 00585 00586 // Find out if there is already an available value in this block. If so, 00587 // we need to replace the available value with the PHI node. This can 00588 // only happen when we just inserted a PHI node on a backedge. 00589 // 00590 AvailableBlocksTy::iterator LBBlockAvailableValIt = 00591 AvailableBlocks.find(AFBlock); 00592 if (LBBlockAvailableValIt != AvailableBlocks.end()) { 00593 if (LBBlockAvailableValIt->second->getParent() == AFBlock) { 00594 Instruction *OldVal = LBBlockAvailableValIt->second; 00595 OldVal->replaceAllUsesWith(PN); // Use the new PHI node now 00596 ++NumRedundant; 00597 DEBUG(std::cerr << " PHI replaces available value: %" 00598 << OldVal->getName() << "\n"); 00599 00600 // Loop over all of the blocks dominated by this PHI node, and change 00601 // the AvailableBlocks entries to be the PHI node instead of the old 00602 // instruction. 00603 MarkOccurrenceAvailableInAllDominatedBlocks(PN, AFBlock); 00604 00605 AFBlock->getInstList().erase(OldVal); // Delete old instruction! 00606 00607 // The resultant PHI node is a new definition of the value! 00608 Definitions.insert(std::make_pair(AFBlockID, PN)); 00609 } else { 00610 // If the value is not defined in this block, that means that an 00611 // inserted occurrence in a predecessor is now the live value for the 00612 // region (occurs when hoisting loop invariants, f.e.). In this case, 00613 // the PHI node should actually just be removed. 00614 assert(PN->use_empty() && "No uses should exist for dead PHI node!"); 00615 PN->getParent()->getInstList().erase(PN); 00616 } 00617 } else { 00618 // The resultant PHI node is a new definition of the value! 00619 Definitions.insert(std::make_pair(AFBlockID, PN)); 00620 } 00621 } 00622 } 00623 00624 AvailableBlocks.clear(); 00625 00626 return Changed; 00627 } 00628