LLVM API Documentation
00001 //===- CodeGenPrepare.cpp - Prepare a function for code generation --------===// 00002 // 00003 // The LLVM Compiler Infrastructure 00004 // 00005 // This file is distributed under the University of Illinois Open Source 00006 // License. See LICENSE.TXT for details. 00007 // 00008 //===----------------------------------------------------------------------===// 00009 // 00010 // This pass munges the code in the input function to better prepare it for 00011 // SelectionDAG-based code generation. This works around limitations in it's 00012 // basic-block-at-a-time approach. It should eventually be removed. 00013 // 00014 //===----------------------------------------------------------------------===// 00015 00016 #define DEBUG_TYPE "codegenprepare" 00017 #include "llvm/Transforms/Scalar.h" 00018 #include "llvm/Constants.h" 00019 #include "llvm/DerivedTypes.h" 00020 #include "llvm/Function.h" 00021 #include "llvm/InlineAsm.h" 00022 #include "llvm/Instructions.h" 00023 #include "llvm/IntrinsicInst.h" 00024 #include "llvm/LLVMContext.h" 00025 #include "llvm/Pass.h" 00026 #include "llvm/Target/TargetData.h" 00027 #include "llvm/Target/TargetLowering.h" 00028 #include "llvm/Transforms/Utils/AddrModeMatcher.h" 00029 #include "llvm/Transforms/Utils/BasicBlockUtils.h" 00030 #include "llvm/Transforms/Utils/Local.h" 00031 #include "llvm/ADT/DenseMap.h" 00032 #include "llvm/ADT/SmallSet.h" 00033 #include "llvm/Assembly/Writer.h" 00034 #include "llvm/Support/CallSite.h" 00035 #include "llvm/Support/CommandLine.h" 00036 #include "llvm/Support/Compiler.h" 00037 #include "llvm/Support/Debug.h" 00038 #include "llvm/Support/GetElementPtrTypeIterator.h" 00039 #include "llvm/Support/PatternMatch.h" 00040 #include "llvm/Support/raw_ostream.h" 00041 using namespace llvm; 00042 using namespace llvm::PatternMatch; 00043 00044 static cl::opt<bool> FactorCommonPreds("split-critical-paths-tweak", 00045 cl::init(false), cl::Hidden); 00046 00047 namespace { 00048 class VISIBILITY_HIDDEN CodeGenPrepare : public FunctionPass { 00049 /// TLI - Keep a pointer of a TargetLowering to consult for determining 00050 /// transformation profitability. 00051 const TargetLowering *TLI; 00052 00053 /// BackEdges - Keep a set of all the loop back edges. 00054 /// 00055 SmallSet<std::pair<const BasicBlock*, const BasicBlock*>, 8> BackEdges; 00056 public: 00057 static char ID; // Pass identification, replacement for typeid 00058 explicit CodeGenPrepare(const TargetLowering *tli = 0) 00059 : FunctionPass(&ID), TLI(tli) {} 00060 bool runOnFunction(Function &F); 00061 00062 private: 00063 bool EliminateMostlyEmptyBlocks(Function &F); 00064 bool CanMergeBlocks(const BasicBlock *BB, const BasicBlock *DestBB) const; 00065 void EliminateMostlyEmptyBlock(BasicBlock *BB); 00066 bool OptimizeBlock(BasicBlock &BB); 00067 bool OptimizeMemoryInst(Instruction *I, Value *Addr, const Type *AccessTy, 00068 DenseMap<Value*,Value*> &SunkAddrs); 00069 bool OptimizeInlineAsmInst(Instruction *I, CallSite CS, 00070 DenseMap<Value*,Value*> &SunkAddrs); 00071 bool OptimizeExtUses(Instruction *I); 00072 void findLoopBackEdges(const Function &F); 00073 }; 00074 } 00075 00076 char CodeGenPrepare::ID = 0; 00077 static RegisterPass<CodeGenPrepare> X("codegenprepare", 00078 "Optimize for code generation"); 00079 00080 FunctionPass *llvm::createCodeGenPreparePass(const TargetLowering *TLI) { 00081 return new CodeGenPrepare(TLI); 00082 } 00083 00084 /// findLoopBackEdges - Do a DFS walk to find loop back edges. 00085 /// 00086 void CodeGenPrepare::findLoopBackEdges(const Function &F) { 00087 SmallVector<std::pair<const BasicBlock*,const BasicBlock*>, 32> Edges; 00088 FindFunctionBackedges(F, Edges); 00089 00090 BackEdges.insert(Edges.begin(), Edges.end()); 00091 } 00092 00093 00094 bool CodeGenPrepare::runOnFunction(Function &F) { 00095 bool EverMadeChange = false; 00096 00097 // First pass, eliminate blocks that contain only PHI nodes and an 00098 // unconditional branch. 00099 EverMadeChange |= EliminateMostlyEmptyBlocks(F); 00100 00101 // Now find loop back edges. 00102 findLoopBackEdges(F); 00103 00104 bool MadeChange = true; 00105 while (MadeChange) { 00106 MadeChange = false; 00107 for (Function::iterator BB = F.begin(), E = F.end(); BB != E; ++BB) 00108 MadeChange |= OptimizeBlock(*BB); 00109 EverMadeChange |= MadeChange; 00110 } 00111 return EverMadeChange; 00112 } 00113 00114 /// EliminateMostlyEmptyBlocks - eliminate blocks that contain only PHI nodes, 00115 /// debug info directives, and an unconditional branch. Passes before isel 00116 /// (e.g. LSR/loopsimplify) often split edges in ways that are non-optimal for 00117 /// isel. Start by eliminating these blocks so we can split them the way we 00118 /// want them. 00119 bool CodeGenPrepare::EliminateMostlyEmptyBlocks(Function &F) { 00120 bool MadeChange = false; 00121 // Note that this intentionally skips the entry block. 00122 for (Function::iterator I = ++F.begin(), E = F.end(); I != E; ) { 00123 BasicBlock *BB = I++; 00124 00125 // If this block doesn't end with an uncond branch, ignore it. 00126 BranchInst *BI = dyn_cast<BranchInst>(BB->getTerminator()); 00127 if (!BI || !BI->isUnconditional()) 00128 continue; 00129 00130 // If the instruction before the branch (skipping debug info) isn't a phi 00131 // node, then other stuff is happening here. 00132 BasicBlock::iterator BBI = BI; 00133 if (BBI != BB->begin()) { 00134 --BBI; 00135 while (isa<DbgInfoIntrinsic>(BBI)) { 00136 if (BBI == BB->begin()) 00137 break; 00138 --BBI; 00139 } 00140 if (!isa<DbgInfoIntrinsic>(BBI) && !isa<PHINode>(BBI)) 00141 continue; 00142 } 00143 00144 // Do not break infinite loops. 00145 BasicBlock *DestBB = BI->getSuccessor(0); 00146 if (DestBB == BB) 00147 continue; 00148 00149 if (!CanMergeBlocks(BB, DestBB)) 00150 continue; 00151 00152 EliminateMostlyEmptyBlock(BB); 00153 MadeChange = true; 00154 } 00155 return MadeChange; 00156 } 00157 00158 /// CanMergeBlocks - Return true if we can merge BB into DestBB if there is a 00159 /// single uncond branch between them, and BB contains no other non-phi 00160 /// instructions. 00161 bool CodeGenPrepare::CanMergeBlocks(const BasicBlock *BB, 00162 const BasicBlock *DestBB) const { 00163 // We only want to eliminate blocks whose phi nodes are used by phi nodes in 00164 // the successor. If there are more complex condition (e.g. preheaders), 00165 // don't mess around with them. 00166 BasicBlock::const_iterator BBI = BB->begin(); 00167 while (const PHINode *PN = dyn_cast<PHINode>(BBI++)) { 00168 for (Value::use_const_iterator UI = PN->use_begin(), E = PN->use_end(); 00169 UI != E; ++UI) { 00170 const Instruction *User = cast<Instruction>(*UI); 00171 if (User->getParent() != DestBB || !isa<PHINode>(User)) 00172 return false; 00173 // If User is inside DestBB block and it is a PHINode then check 00174 // incoming value. If incoming value is not from BB then this is 00175 // a complex condition (e.g. preheaders) we want to avoid here. 00176 if (User->getParent() == DestBB) { 00177 if (const PHINode *UPN = dyn_cast<PHINode>(User)) 00178 for (unsigned I = 0, E = UPN->getNumIncomingValues(); I != E; ++I) { 00179 Instruction *Insn = dyn_cast<Instruction>(UPN->getIncomingValue(I)); 00180 if (Insn && Insn->getParent() == BB && 00181 Insn->getParent() != UPN->getIncomingBlock(I)) 00182 return false; 00183 } 00184 } 00185 } 00186 } 00187 00188 // If BB and DestBB contain any common predecessors, then the phi nodes in BB 00189 // and DestBB may have conflicting incoming values for the block. If so, we 00190 // can't merge the block. 00191 const PHINode *DestBBPN = dyn_cast<PHINode>(DestBB->begin()); 00192 if (!DestBBPN) return true; // no conflict. 00193 00194 // Collect the preds of BB. 00195 SmallPtrSet<const BasicBlock*, 16> BBPreds; 00196 if (const PHINode *BBPN = dyn_cast<PHINode>(BB->begin())) { 00197 // It is faster to get preds from a PHI than with pred_iterator. 00198 for (unsigned i = 0, e = BBPN->getNumIncomingValues(); i != e; ++i) 00199 BBPreds.insert(BBPN->getIncomingBlock(i)); 00200 } else { 00201 BBPreds.insert(pred_begin(BB), pred_end(BB)); 00202 } 00203 00204 // Walk the preds of DestBB. 00205 for (unsigned i = 0, e = DestBBPN->getNumIncomingValues(); i != e; ++i) { 00206 BasicBlock *Pred = DestBBPN->getIncomingBlock(i); 00207 if (BBPreds.count(Pred)) { // Common predecessor? 00208 BBI = DestBB->begin(); 00209 while (const PHINode *PN = dyn_cast<PHINode>(BBI++)) { 00210 const Value *V1 = PN->getIncomingValueForBlock(Pred); 00211 const Value *V2 = PN->getIncomingValueForBlock(BB); 00212 00213 // If V2 is a phi node in BB, look up what the mapped value will be. 00214 if (const PHINode *V2PN = dyn_cast<PHINode>(V2)) 00215 if (V2PN->getParent() == BB) 00216 V2 = V2PN->getIncomingValueForBlock(Pred); 00217 00218 // If there is a conflict, bail out. 00219 if (V1 != V2) return false; 00220 } 00221 } 00222 } 00223 00224 return true; 00225 } 00226 00227 00228 /// EliminateMostlyEmptyBlock - Eliminate a basic block that have only phi's and 00229 /// an unconditional branch in it. 00230 void CodeGenPrepare::EliminateMostlyEmptyBlock(BasicBlock *BB) { 00231 BranchInst *BI = cast<BranchInst>(BB->getTerminator()); 00232 BasicBlock *DestBB = BI->getSuccessor(0); 00233 00234 DOUT << "MERGING MOSTLY EMPTY BLOCKS - BEFORE:\n" << *BB << *DestBB; 00235 00236 // If the destination block has a single pred, then this is a trivial edge, 00237 // just collapse it. 00238 if (BasicBlock *SinglePred = DestBB->getSinglePredecessor()) { 00239 if (SinglePred != DestBB) { 00240 // Remember if SinglePred was the entry block of the function. If so, we 00241 // will need to move BB back to the entry position. 00242 bool isEntry = SinglePred == &SinglePred->getParent()->getEntryBlock(); 00243 MergeBasicBlockIntoOnlyPred(DestBB); 00244 00245 if (isEntry && BB != &BB->getParent()->getEntryBlock()) 00246 BB->moveBefore(&BB->getParent()->getEntryBlock()); 00247 00248 DOUT << "AFTER:\n" << *DestBB << "\n\n\n"; 00249 return; 00250 } 00251 } 00252 00253 // Otherwise, we have multiple predecessors of BB. Update the PHIs in DestBB 00254 // to handle the new incoming edges it is about to have. 00255 PHINode *PN; 00256 for (BasicBlock::iterator BBI = DestBB->begin(); 00257 (PN = dyn_cast<PHINode>(BBI)); ++BBI) { 00258 // Remove the incoming value for BB, and remember it. 00259 Value *InVal = PN->removeIncomingValue(BB, false); 00260 00261 // Two options: either the InVal is a phi node defined in BB or it is some 00262 // value that dominates BB. 00263 PHINode *InValPhi = dyn_cast<PHINode>(InVal); 00264 if (InValPhi && InValPhi->getParent() == BB) { 00265 // Add all of the input values of the input PHI as inputs of this phi. 00266 for (unsigned i = 0, e = InValPhi->getNumIncomingValues(); i != e; ++i) 00267 PN->addIncoming(InValPhi->getIncomingValue(i), 00268 InValPhi->getIncomingBlock(i)); 00269 } else { 00270 // Otherwise, add one instance of the dominating value for each edge that 00271 // we will be adding. 00272 if (PHINode *BBPN = dyn_cast<PHINode>(BB->begin())) { 00273 for (unsigned i = 0, e = BBPN->getNumIncomingValues(); i != e; ++i) 00274 PN->addIncoming(InVal, BBPN->getIncomingBlock(i)); 00275 } else { 00276 for (pred_iterator PI = pred_begin(BB), E = pred_end(BB); PI != E; ++PI) 00277 PN->addIncoming(InVal, *PI); 00278 } 00279 } 00280 } 00281 00282 // The PHIs are now updated, change everything that refers to BB to use 00283 // DestBB and remove BB. 00284 BB->replaceAllUsesWith(DestBB); 00285 BB->eraseFromParent(); 00286 00287 DOUT << "AFTER:\n" << *DestBB << "\n\n\n"; 00288 } 00289 00290 00291 /// SplitEdgeNicely - Split the critical edge from TI to its specified 00292 /// successor if it will improve codegen. We only do this if the successor has 00293 /// phi nodes (otherwise critical edges are ok). If there is already another 00294 /// predecessor of the succ that is empty (and thus has no phi nodes), use it 00295 /// instead of introducing a new block. 00296 static void SplitEdgeNicely(TerminatorInst *TI, unsigned SuccNum, 00297 SmallSet<std::pair<const BasicBlock*, 00298 const BasicBlock*>, 8> &BackEdges, 00299 Pass *P) { 00300 BasicBlock *TIBB = TI->getParent(); 00301 BasicBlock *Dest = TI->getSuccessor(SuccNum); 00302 assert(isa<PHINode>(Dest->begin()) && 00303 "This should only be called if Dest has a PHI!"); 00304 00305 // Do not split edges to EH landing pads. 00306 if (InvokeInst *Invoke = dyn_cast<InvokeInst>(TI)) { 00307 if (Invoke->getSuccessor(1) == Dest) 00308 return; 00309 } 00310 00311 // As a hack, never split backedges of loops. Even though the copy for any 00312 // PHIs inserted on the backedge would be dead for exits from the loop, we 00313 // assume that the cost of *splitting* the backedge would be too high. 00314 if (BackEdges.count(std::make_pair(TIBB, Dest))) 00315 return; 00316 00317 if (!FactorCommonPreds) { 00318 /// TIPHIValues - This array is lazily computed to determine the values of 00319 /// PHIs in Dest that TI would provide. 00320 SmallVector<Value*, 32> TIPHIValues; 00321 00322 // Check to see if Dest has any blocks that can be used as a split edge for 00323 // this terminator. 00324 for (pred_iterator PI = pred_begin(Dest), E = pred_end(Dest); PI != E; ++PI) { 00325 BasicBlock *Pred = *PI; 00326 // To be usable, the pred has to end with an uncond branch to the dest. 00327 BranchInst *PredBr = dyn_cast<BranchInst>(Pred->getTerminator()); 00328 if (!PredBr || !PredBr->isUnconditional()) 00329 continue; 00330 // Must be empty other than the branch and debug info. 00331 BasicBlock::iterator I = Pred->begin(); 00332 while (isa<DbgInfoIntrinsic>(I)) 00333 I++; 00334 if (dyn_cast<Instruction>(I) != PredBr) 00335 continue; 00336 // Cannot be the entry block; its label does not get emitted. 00337 if (Pred == &(Dest->getParent()->getEntryBlock())) 00338 continue; 00339 00340 // Finally, since we know that Dest has phi nodes in it, we have to make 00341 // sure that jumping to Pred will have the same effect as going to Dest in 00342 // terms of PHI values. 00343 PHINode *PN; 00344 unsigned PHINo = 0; 00345 bool FoundMatch = true; 00346 for (BasicBlock::iterator I = Dest->begin(); 00347 (PN = dyn_cast<PHINode>(I)); ++I, ++PHINo) { 00348 if (PHINo == TIPHIValues.size()) 00349 TIPHIValues.push_back(PN->getIncomingValueForBlock(TIBB)); 00350 00351 // If the PHI entry doesn't work, we can't use this pred. 00352 if (TIPHIValues[PHINo] != PN->getIncomingValueForBlock(Pred)) { 00353 FoundMatch = false; 00354 break; 00355 } 00356 } 00357 00358 // If we found a workable predecessor, change TI to branch to Succ. 00359 if (FoundMatch) { 00360 Dest->removePredecessor(TIBB); 00361 TI->setSuccessor(SuccNum, Pred); 00362 return; 00363 } 00364 } 00365 00366 SplitCriticalEdge(TI, SuccNum, P, true); 00367 return; 00368 } 00369 00370 PHINode *PN; 00371 SmallVector<Value*, 8> TIPHIValues; 00372 for (BasicBlock::iterator I = Dest->begin(); 00373 (PN = dyn_cast<PHINode>(I)); ++I) 00374 TIPHIValues.push_back(PN->getIncomingValueForBlock(TIBB)); 00375 00376 SmallVector<BasicBlock*, 8> IdenticalPreds; 00377 for (pred_iterator PI = pred_begin(Dest), E = pred_end(Dest); PI != E; ++PI) { 00378 BasicBlock *Pred = *PI; 00379 if (BackEdges.count(std::make_pair(Pred, Dest))) 00380 continue; 00381 if (PI == TIBB) 00382 IdenticalPreds.push_back(Pred); 00383 else { 00384 bool Identical = true; 00385 unsigned PHINo = 0; 00386 for (BasicBlock::iterator I = Dest->begin(); 00387 (PN = dyn_cast<PHINode>(I)); ++I, ++PHINo) 00388 if (TIPHIValues[PHINo] != PN->getIncomingValueForBlock(Pred)) { 00389 Identical = false; 00390 break; 00391 } 00392 if (Identical) 00393 IdenticalPreds.push_back(Pred); 00394 } 00395 } 00396 00397 assert(!IdenticalPreds.empty()); 00398 SplitBlockPredecessors(Dest, &IdenticalPreds[0], IdenticalPreds.size(), 00399 ".critedge", P); 00400 } 00401 00402 00403 /// OptimizeNoopCopyExpression - If the specified cast instruction is a noop 00404 /// copy (e.g. it's casting from one pointer type to another, i32->i8 on PPC), 00405 /// sink it into user blocks to reduce the number of virtual 00406 /// registers that must be created and coalesced. 00407 /// 00408 /// Return true if any changes are made. 00409 /// 00410 static bool OptimizeNoopCopyExpression(CastInst *CI, const TargetLowering &TLI){ 00411 // If this is a noop copy, 00412 EVT SrcVT = TLI.getValueType(CI->getOperand(0)->getType()); 00413 EVT DstVT = TLI.getValueType(CI->getType()); 00414 00415 // This is an fp<->int conversion? 00416 if (SrcVT.isInteger() != DstVT.isInteger()) 00417 return false; 00418 00419 // If this is an extension, it will be a zero or sign extension, which 00420 // isn't a noop. 00421 if (SrcVT.bitsLT(DstVT)) return false; 00422 00423 // If these values will be promoted, find out what they will be promoted 00424 // to. This helps us consider truncates on PPC as noop copies when they 00425 // are. 00426 if (TLI.getTypeAction(CI->getContext(), SrcVT) == TargetLowering::Promote) 00427 SrcVT = TLI.getTypeToTransformTo(CI->getContext(), SrcVT); 00428 if (TLI.getTypeAction(CI->getContext(), DstVT) == TargetLowering::Promote) 00429 DstVT = TLI.getTypeToTransformTo(CI->getContext(), DstVT); 00430 00431 // If, after promotion, these are the same types, this is a noop copy. 00432 if (SrcVT != DstVT) 00433 return false; 00434 00435 BasicBlock *DefBB = CI->getParent(); 00436 00437 /// InsertedCasts - Only insert a cast in each block once. 00438 DenseMap<BasicBlock*, CastInst*> InsertedCasts; 00439 00440 bool MadeChange = false; 00441 for (Value::use_iterator UI = CI->use_begin(), E = CI->use_end(); 00442 UI != E; ) { 00443 Use &TheUse = UI.getUse(); 00444 Instruction *User = cast<Instruction>(*UI); 00445 00446 // Figure out which BB this cast is used in. For PHI's this is the 00447 // appropriate predecessor block. 00448 BasicBlock *UserBB = User->getParent(); 00449 if (PHINode *PN = dyn_cast<PHINode>(User)) { 00450 UserBB = PN->getIncomingBlock(UI); 00451 } 00452 00453 // Preincrement use iterator so we don't invalidate it. 00454 ++UI; 00455 00456 // If this user is in the same block as the cast, don't change the cast. 00457 if (UserBB == DefBB) continue; 00458 00459 // If we have already inserted a cast into this block, use it. 00460 CastInst *&InsertedCast = InsertedCasts[UserBB]; 00461 00462 if (!InsertedCast) { 00463 BasicBlock::iterator InsertPt = UserBB->getFirstNonPHI(); 00464 00465 InsertedCast = 00466 CastInst::Create(CI->getOpcode(), CI->getOperand(0), CI->getType(), "", 00467 InsertPt); 00468 MadeChange = true; 00469 } 00470 00471 // Replace a use of the cast with a use of the new cast. 00472 TheUse = InsertedCast; 00473 } 00474 00475 // If we removed all uses, nuke the cast. 00476 if (CI->use_empty()) { 00477 CI->eraseFromParent(); 00478 MadeChange = true; 00479 } 00480 00481 return MadeChange; 00482 } 00483 00484 /// OptimizeCmpExpression - sink the given CmpInst into user blocks to reduce 00485 /// the number of virtual registers that must be created and coalesced. This is 00486 /// a clear win except on targets with multiple condition code registers 00487 /// (PowerPC), where it might lose; some adjustment may be wanted there. 00488 /// 00489 /// Return true if any changes are made. 00490 static bool OptimizeCmpExpression(CmpInst *CI) { 00491 BasicBlock *DefBB = CI->getParent(); 00492 00493 /// InsertedCmp - Only insert a cmp in each block once. 00494 DenseMap<BasicBlock*, CmpInst*> InsertedCmps; 00495 00496 bool MadeChange = false; 00497 for (Value::use_iterator UI = CI->use_begin(), E = CI->use_end(); 00498 UI != E; ) { 00499 Use &TheUse = UI.getUse(); 00500 Instruction *User = cast<Instruction>(*UI); 00501 00502 // Preincrement use iterator so we don't invalidate it. 00503 ++UI; 00504 00505 // Don't bother for PHI nodes. 00506 if (isa<PHINode>(User)) 00507 continue; 00508 00509 // Figure out which BB this cmp is used in. 00510 BasicBlock *UserBB = User->getParent(); 00511 00512 // If this user is in the same block as the cmp, don't change the cmp. 00513 if (UserBB == DefBB) continue; 00514 00515 // If we have already inserted a cmp into this block, use it. 00516 CmpInst *&InsertedCmp = InsertedCmps[UserBB]; 00517 00518 if (!InsertedCmp) { 00519 BasicBlock::iterator InsertPt = UserBB->getFirstNonPHI(); 00520 00521 InsertedCmp = 00522 CmpInst::Create(DefBB->getContext(), CI->getOpcode(), 00523 CI->getPredicate(), CI->getOperand(0), 00524 CI->getOperand(1), "", InsertPt); 00525 MadeChange = true; 00526 } 00527 00528 // Replace a use of the cmp with a use of the new cmp. 00529 TheUse = InsertedCmp; 00530 } 00531 00532 // If we removed all uses, nuke the cmp. 00533 if (CI->use_empty()) 00534 CI->eraseFromParent(); 00535 00536 return MadeChange; 00537 } 00538 00539 //===----------------------------------------------------------------------===// 00540 // Memory Optimization 00541 //===----------------------------------------------------------------------===// 00542 00543 /// IsNonLocalValue - Return true if the specified values are defined in a 00544 /// different basic block than BB. 00545 static bool IsNonLocalValue(Value *V, BasicBlock *BB) { 00546 if (Instruction *I = dyn_cast<Instruction>(V)) 00547 return I->getParent() != BB; 00548 return false; 00549 } 00550 00551 /// OptimizeMemoryInst - Load and Store Instructions have often have 00552 /// addressing modes that can do significant amounts of computation. As such, 00553 /// instruction selection will try to get the load or store to do as much 00554 /// computation as possible for the program. The problem is that isel can only 00555 /// see within a single block. As such, we sink as much legal addressing mode 00556 /// stuff into the block as possible. 00557 /// 00558 /// This method is used to optimize both load/store and inline asms with memory 00559 /// operands. 00560 bool CodeGenPrepare::OptimizeMemoryInst(Instruction *MemoryInst, Value *Addr, 00561 const Type *AccessTy, 00562 DenseMap<Value*,Value*> &SunkAddrs) { 00563 // Figure out what addressing mode will be built up for this operation. 00564 SmallVector<Instruction*, 16> AddrModeInsts; 00565 ExtAddrMode AddrMode = AddressingModeMatcher::Match(Addr, AccessTy,MemoryInst, 00566 AddrModeInsts, *TLI); 00567 00568 // Check to see if any of the instructions supersumed by this addr mode are 00569 // non-local to I's BB. 00570 bool AnyNonLocal = false; 00571 for (unsigned i = 0, e = AddrModeInsts.size(); i != e; ++i) { 00572 if (IsNonLocalValue(AddrModeInsts[i], MemoryInst->getParent())) { 00573 AnyNonLocal = true; 00574 break; 00575 } 00576 } 00577 00578 // If all the instructions matched are already in this BB, don't do anything. 00579 if (!AnyNonLocal) { 00580 DEBUG(errs() << "CGP: Found local addrmode: " << AddrMode << "\n"); 00581 return false; 00582 } 00583 00584 // Insert this computation right after this user. Since our caller is 00585 // scanning from the top of the BB to the bottom, reuse of the expr are 00586 // guaranteed to happen later. 00587 BasicBlock::iterator InsertPt = MemoryInst; 00588 00589 // Now that we determined the addressing expression we want to use and know 00590 // that we have to sink it into this block. Check to see if we have already 00591 // done this for some other load/store instr in this block. If so, reuse the 00592 // computation. 00593 Value *&SunkAddr = SunkAddrs[Addr]; 00594 if (SunkAddr) { 00595 DEBUG(errs() << "CGP: Reusing nonlocal addrmode: " << AddrMode << " for " 00596 << *MemoryInst); 00597 if (SunkAddr->getType() != Addr->getType()) 00598 SunkAddr = new BitCastInst(SunkAddr, Addr->getType(), "tmp", InsertPt); 00599 } else { 00600 DEBUG(errs() << "CGP: SINKING nonlocal addrmode: " << AddrMode << " for " 00601 << *MemoryInst); 00602 const Type *IntPtrTy = 00603 TLI->getTargetData()->getIntPtrType(AccessTy->getContext()); 00604 00605 Value *Result = 0; 00606 // Start with the scale value. 00607 if (AddrMode.Scale) { 00608 Value *V = AddrMode.ScaledReg; 00609 if (V->getType() == IntPtrTy) { 00610 // done. 00611 } else if (isa<PointerType>(V->getType())) { 00612 V = new PtrToIntInst(V, IntPtrTy, "sunkaddr", InsertPt); 00613 } else if (cast<IntegerType>(IntPtrTy)->getBitWidth() < 00614 cast<IntegerType>(V->getType())->getBitWidth()) { 00615 V = new TruncInst(V, IntPtrTy, "sunkaddr", InsertPt); 00616 } else { 00617 V = new SExtInst(V, IntPtrTy, "sunkaddr", InsertPt); 00618 } 00619 if (AddrMode.Scale != 1) 00620 V = BinaryOperator::CreateMul(V, ConstantInt::get(IntPtrTy, 00621 AddrMode.Scale), 00622 "sunkaddr", InsertPt); 00623 Result = V; 00624 } 00625 00626 // Add in the base register. 00627 if (AddrMode.BaseReg) { 00628 Value *V = AddrMode.BaseReg; 00629 if (isa<PointerType>(V->getType())) 00630 V = new PtrToIntInst(V, IntPtrTy, "sunkaddr", InsertPt); 00631 if (V->getType() != IntPtrTy) 00632 V = CastInst::CreateIntegerCast(V, IntPtrTy, /*isSigned=*/true, 00633 "sunkaddr", InsertPt); 00634 if (Result) 00635 Result = BinaryOperator::CreateAdd(Result, V, "sunkaddr", InsertPt); 00636 else 00637 Result = V; 00638 } 00639 00640 // Add in the BaseGV if present. 00641 if (AddrMode.BaseGV) { 00642 Value *V = new PtrToIntInst(AddrMode.BaseGV, IntPtrTy, "sunkaddr", 00643 InsertPt); 00644 if (Result) 00645 Result = BinaryOperator::CreateAdd(Result, V, "sunkaddr", InsertPt); 00646 else 00647 Result = V; 00648 } 00649 00650 // Add in the Base Offset if present. 00651 if (AddrMode.BaseOffs) { 00652 Value *V = ConstantInt::get(IntPtrTy, AddrMode.BaseOffs); 00653 if (Result) 00654 Result = BinaryOperator::CreateAdd(Result, V, "sunkaddr", InsertPt); 00655 else 00656 Result = V; 00657 } 00658 00659 if (Result == 0) 00660 SunkAddr = Constant::getNullValue(Addr->getType()); 00661 else 00662 SunkAddr = new IntToPtrInst(Result, Addr->getType(), "sunkaddr",InsertPt); 00663 } 00664 00665 MemoryInst->replaceUsesOfWith(Addr, SunkAddr); 00666 00667 if (Addr->use_empty()) 00668 RecursivelyDeleteTriviallyDeadInstructions(Addr); 00669 return true; 00670 } 00671 00672 /// OptimizeInlineAsmInst - If there are any memory operands, use 00673 /// OptimizeMemoryInst to sink their address computing into the block when 00674 /// possible / profitable. 00675 bool CodeGenPrepare::OptimizeInlineAsmInst(Instruction *I, CallSite CS, 00676 DenseMap<Value*,Value*> &SunkAddrs) { 00677 bool MadeChange = false; 00678 InlineAsm *IA = cast<InlineAsm>(CS.getCalledValue()); 00679 00680 // Do a prepass over the constraints, canonicalizing them, and building up the 00681 // ConstraintOperands list. 00682 std::vector<InlineAsm::ConstraintInfo> 00683 ConstraintInfos = IA->ParseConstraints(); 00684 00685 /// ConstraintOperands - Information about all of the constraints. 00686 std::vector<TargetLowering::AsmOperandInfo> ConstraintOperands; 00687 unsigned ArgNo = 0; // ArgNo - The argument of the CallInst. 00688 for (unsigned i = 0, e = ConstraintInfos.size(); i != e; ++i) { 00689 ConstraintOperands. 00690 push_back(TargetLowering::AsmOperandInfo(ConstraintInfos[i])); 00691 TargetLowering::AsmOperandInfo &OpInfo = ConstraintOperands.back(); 00692 00693 // Compute the value type for each operand. 00694 switch (OpInfo.Type) { 00695 case InlineAsm::isOutput: 00696 if (OpInfo.isIndirect) 00697 OpInfo.CallOperandVal = CS.getArgument(ArgNo++); 00698 break; 00699 case InlineAsm::isInput: 00700 OpInfo.CallOperandVal = CS.getArgument(ArgNo++); 00701 break; 00702 case InlineAsm::isClobber: 00703 // Nothing to do. 00704 break; 00705 } 00706 00707 // Compute the constraint code and ConstraintType to use. 00708 TLI->ComputeConstraintToUse(OpInfo, SDValue(), 00709 OpInfo.ConstraintType == TargetLowering::C_Memory); 00710 00711 if (OpInfo.ConstraintType == TargetLowering::C_Memory && 00712 OpInfo.isIndirect) { 00713 Value *OpVal = OpInfo.CallOperandVal; 00714 MadeChange |= OptimizeMemoryInst(I, OpVal, OpVal->getType(), SunkAddrs); 00715 } 00716 } 00717 00718 return MadeChange; 00719 } 00720 00721 bool CodeGenPrepare::OptimizeExtUses(Instruction *I) { 00722 BasicBlock *DefBB = I->getParent(); 00723 00724 // If both result of the {s|z}xt and its source are live out, rewrite all 00725 // other uses of the source with result of extension. 00726 Value *Src = I->getOperand(0); 00727 if (Src->hasOneUse()) 00728 return false; 00729 00730 // Only do this xform if truncating is free. 00731 if (TLI && !TLI->isTruncateFree(I->getType(), Src->getType())) 00732 return false; 00733 00734 // Only safe to perform the optimization if the source is also defined in 00735 // this block. 00736 if (!isa<Instruction>(Src) || DefBB != cast<Instruction>(Src)->getParent()) 00737 return false; 00738 00739 bool DefIsLiveOut = false; 00740 for (Value::use_iterator UI = I->use_begin(), E = I->use_end(); 00741 UI != E; ++UI) { 00742 Instruction *User = cast<Instruction>(*UI); 00743 00744 // Figure out which BB this ext is used in. 00745 BasicBlock *UserBB = User->getParent(); 00746 if (UserBB == DefBB) continue; 00747 DefIsLiveOut = true; 00748 break; 00749 } 00750 if (!DefIsLiveOut) 00751 return false; 00752 00753 // Make sure non of the uses are PHI nodes. 00754 for (Value::use_iterator UI = Src->use_begin(), E = Src->use_end(); 00755 UI != E; ++UI) { 00756 Instruction *User = cast<Instruction>(*UI); 00757 BasicBlock *UserBB = User->getParent(); 00758 if (UserBB == DefBB) continue; 00759 // Be conservative. We don't want this xform to end up introducing 00760 // reloads just before load / store instructions. 00761 if (isa<PHINode>(User) || isa<LoadInst>(User) || isa<StoreInst>(User)) 00762 return false; 00763 } 00764 00765 // InsertedTruncs - Only insert one trunc in each block once. 00766 DenseMap<BasicBlock*, Instruction*> InsertedTruncs; 00767 00768 bool MadeChange = false; 00769 for (Value::use_iterator UI = Src->use_begin(), E = Src->use_end(); 00770 UI != E; ++UI) { 00771 Use &TheUse = UI.getUse(); 00772 Instruction *User = cast<Instruction>(*UI); 00773 00774 // Figure out which BB this ext is used in. 00775 BasicBlock *UserBB = User->getParent(); 00776 if (UserBB == DefBB) continue; 00777 00778 // Both src and def are live in this block. Rewrite the use. 00779 Instruction *&InsertedTrunc = InsertedTruncs[UserBB]; 00780 00781 if (!InsertedTrunc) { 00782 BasicBlock::iterator InsertPt = UserBB->getFirstNonPHI(); 00783 00784 InsertedTrunc = new TruncInst(I, Src->getType(), "", InsertPt); 00785 } 00786 00787 // Replace a use of the {s|z}ext source with a use of the result. 00788 TheUse = InsertedTrunc; 00789 00790 MadeChange = true; 00791 } 00792 00793 return MadeChange; 00794 } 00795 00796 // In this pass we look for GEP and cast instructions that are used 00797 // across basic blocks and rewrite them to improve basic-block-at-a-time 00798 // selection. 00799 bool CodeGenPrepare::OptimizeBlock(BasicBlock &BB) { 00800 bool MadeChange = false; 00801 00802 // Split all critical edges where the dest block has a PHI. 00803 TerminatorInst *BBTI = BB.getTerminator(); 00804 if (BBTI->getNumSuccessors() > 1) { 00805 for (unsigned i = 0, e = BBTI->getNumSuccessors(); i != e; ++i) { 00806 BasicBlock *SuccBB = BBTI->getSuccessor(i); 00807 if (isa<PHINode>(SuccBB->begin()) && isCriticalEdge(BBTI, i, true)) 00808 SplitEdgeNicely(BBTI, i, BackEdges, this); 00809 } 00810 } 00811 00812 // Keep track of non-local addresses that have been sunk into this block. 00813 // This allows us to avoid inserting duplicate code for blocks with multiple 00814 // load/stores of the same address. 00815 DenseMap<Value*, Value*> SunkAddrs; 00816 00817 for (BasicBlock::iterator BBI = BB.begin(), E = BB.end(); BBI != E; ) { 00818 Instruction *I = BBI++; 00819 00820 if (CastInst *CI = dyn_cast<CastInst>(I)) { 00821 // If the source of the cast is a constant, then this should have 00822 // already been constant folded. The only reason NOT to constant fold 00823 // it is if something (e.g. LSR) was careful to place the constant 00824 // evaluation in a block other than then one that uses it (e.g. to hoist 00825 // the address of globals out of a loop). If this is the case, we don't 00826 // want to forward-subst the cast. 00827 if (isa<Constant>(CI->getOperand(0))) 00828 continue; 00829 00830 bool Change = false; 00831 if (TLI) { 00832 Change = OptimizeNoopCopyExpression(CI, *TLI); 00833 MadeChange |= Change; 00834 } 00835 00836 if (!Change && (isa<ZExtInst>(I) || isa<SExtInst>(I))) 00837 MadeChange |= OptimizeExtUses(I); 00838 } else if (CmpInst *CI = dyn_cast<CmpInst>(I)) { 00839 MadeChange |= OptimizeCmpExpression(CI); 00840 } else if (LoadInst *LI = dyn_cast<LoadInst>(I)) { 00841 if (TLI) 00842 MadeChange |= OptimizeMemoryInst(I, I->getOperand(0), LI->getType(), 00843 SunkAddrs); 00844 } else if (StoreInst *SI = dyn_cast<StoreInst>(I)) { 00845 if (TLI) 00846 MadeChange |= OptimizeMemoryInst(I, SI->getOperand(1), 00847 SI->getOperand(0)->getType(), 00848 SunkAddrs); 00849 } else if (GetElementPtrInst *GEPI = dyn_cast<GetElementPtrInst>(I)) { 00850 if (GEPI->hasAllZeroIndices()) { 00851 /// The GEP operand must be a pointer, so must its result -> BitCast 00852 Instruction *NC = new BitCastInst(GEPI->getOperand(0), GEPI->getType(), 00853 GEPI->getName(), GEPI); 00854 GEPI->replaceAllUsesWith(NC); 00855 GEPI->eraseFromParent(); 00856 MadeChange = true; 00857 BBI = NC; 00858 } 00859 } else if (CallInst *CI = dyn_cast<CallInst>(I)) { 00860 // If we found an inline asm expession, and if the target knows how to 00861 // lower it to normal LLVM code, do so now. 00862 if (TLI && isa<InlineAsm>(CI->getCalledValue())) { 00863 if (TLI->ExpandInlineAsm(CI)) { 00864 BBI = BB.begin(); 00865 // Avoid processing instructions out of order, which could cause 00866 // reuse before a value is defined. 00867 SunkAddrs.clear(); 00868 } else 00869 // Sink address computing for memory operands into the block. 00870 MadeChange |= OptimizeInlineAsmInst(I, &(*CI), SunkAddrs); 00871 } 00872 } 00873 } 00874 00875 return MadeChange; 00876 }