CodeGenPrepare.cpp revision dbe0deca339585dfbaed5951ef0ca2c6a0df173c
1//===- CodeGenPrepare.cpp - Prepare a function for code generation --------===// 2// 3// The LLVM Compiler Infrastructure 4// 5// This file was developed by Chris Lattner and is distributed under 6// the University of Illinois Open Source License. See LICENSE.TXT for details. 7// 8//===----------------------------------------------------------------------===// 9// 10// This pass munges the code in the input function to better prepare it for 11// SelectionDAG-based code generation. This works around limitations in it's 12// basic-block-at-a-time approach. It should eventually be removed. 13// 14//===----------------------------------------------------------------------===// 15 16#define DEBUG_TYPE "codegenprepare" 17#include "llvm/Transforms/Scalar.h" 18#include "llvm/Constants.h" 19#include "llvm/DerivedTypes.h" 20#include "llvm/Function.h" 21#include "llvm/Instructions.h" 22#include "llvm/Pass.h" 23#include "llvm/Support/Compiler.h" 24#include "llvm/Target/TargetAsmInfo.h" 25#include "llvm/Target/TargetData.h" 26#include "llvm/Target/TargetLowering.h" 27#include "llvm/Target/TargetMachine.h" 28#include "llvm/Transforms/Utils/BasicBlockUtils.h" 29#include "llvm/ADT/SmallSet.h" 30using namespace llvm; 31 32namespace { 33 class VISIBILITY_HIDDEN CodeGenPrepare : public FunctionPass { 34 /// TLI - Keep a pointer of a TargetLowering to consult for determining 35 /// transformation profitability. 36 const TargetLowering *TLI; 37 public: 38 CodeGenPrepare(const TargetLowering *tli = 0) : TLI(tli) {} 39 bool runOnFunction(Function &F); 40 41 private: 42 bool OptimizeBlock(BasicBlock &BB); 43 bool OptimizeGEPExpression(GetElementPtrInst *GEPI); 44 }; 45} 46static RegisterPass<CodeGenPrepare> X("codegenprepare", 47 "Optimize for code generation"); 48 49FunctionPass *llvm::createCodeGenPreparePass(const TargetLowering *TLI) { 50 return new CodeGenPrepare(TLI); 51} 52 53 54bool CodeGenPrepare::runOnFunction(Function &F) { 55 bool MadeChange = true; 56 bool EverMadeChange = false; 57 while (MadeChange) { 58 MadeChange = false; 59 for (Function::iterator BB = F.begin(), E = F.end(); BB != E; ++BB) 60 MadeChange |= OptimizeBlock(*BB); 61 EverMadeChange |= MadeChange; 62 } 63 return EverMadeChange; 64} 65 66/// SplitEdgeNicely - Split the critical edge from TI to it's specified 67/// successor if it will improve codegen. We only do this if the successor has 68/// phi nodes (otherwise critical edges are ok). If there is already another 69/// predecessor of the succ that is empty (and thus has no phi nodes), use it 70/// instead of introducing a new block. 71static void SplitEdgeNicely(TerminatorInst *TI, unsigned SuccNum, Pass *P) { 72 BasicBlock *TIBB = TI->getParent(); 73 BasicBlock *Dest = TI->getSuccessor(SuccNum); 74 assert(isa<PHINode>(Dest->begin()) && 75 "This should only be called if Dest has a PHI!"); 76 77 /// TIPHIValues - This array is lazily computed to determine the values of 78 /// PHIs in Dest that TI would provide. 79 std::vector<Value*> TIPHIValues; 80 81 // Check to see if Dest has any blocks that can be used as a split edge for 82 // this terminator. 83 for (pred_iterator PI = pred_begin(Dest), E = pred_end(Dest); PI != E; ++PI) { 84 BasicBlock *Pred = *PI; 85 // To be usable, the pred has to end with an uncond branch to the dest. 86 BranchInst *PredBr = dyn_cast<BranchInst>(Pred->getTerminator()); 87 if (!PredBr || !PredBr->isUnconditional() || 88 // Must be empty other than the branch. 89 &Pred->front() != PredBr) 90 continue; 91 92 // Finally, since we know that Dest has phi nodes in it, we have to make 93 // sure that jumping to Pred will have the same affect as going to Dest in 94 // terms of PHI values. 95 PHINode *PN; 96 unsigned PHINo = 0; 97 bool FoundMatch = true; 98 for (BasicBlock::iterator I = Dest->begin(); 99 (PN = dyn_cast<PHINode>(I)); ++I, ++PHINo) { 100 if (PHINo == TIPHIValues.size()) 101 TIPHIValues.push_back(PN->getIncomingValueForBlock(TIBB)); 102 103 // If the PHI entry doesn't work, we can't use this pred. 104 if (TIPHIValues[PHINo] != PN->getIncomingValueForBlock(Pred)) { 105 FoundMatch = false; 106 break; 107 } 108 } 109 110 // If we found a workable predecessor, change TI to branch to Succ. 111 if (FoundMatch) { 112 Dest->removePredecessor(TIBB); 113 TI->setSuccessor(SuccNum, Pred); 114 return; 115 } 116 } 117 118 SplitCriticalEdge(TI, SuccNum, P, true); 119} 120 121 122/// InsertGEPComputeCode - Insert code into BB to compute Ptr+PtrOffset, 123/// casting to the type of GEPI. 124static Instruction *InsertGEPComputeCode(Instruction *&V, BasicBlock *BB, 125 Instruction *GEPI, Value *Ptr, 126 Value *PtrOffset) { 127 if (V) return V; // Already computed. 128 129 // Figure out the insertion point 130 BasicBlock::iterator InsertPt; 131 if (BB == GEPI->getParent()) { 132 // If GEP is already inserted into BB, insert right after the GEP. 133 InsertPt = GEPI; 134 ++InsertPt; 135 } else { 136 // Otherwise, insert at the top of BB, after any PHI nodes 137 InsertPt = BB->begin(); 138 while (isa<PHINode>(InsertPt)) ++InsertPt; 139 } 140 141 // If Ptr is itself a cast, but in some other BB, emit a copy of the cast into 142 // BB so that there is only one value live across basic blocks (the cast 143 // operand). 144 if (CastInst *CI = dyn_cast<CastInst>(Ptr)) 145 if (CI->getParent() != BB && isa<PointerType>(CI->getOperand(0)->getType())) 146 Ptr = CastInst::create(CI->getOpcode(), CI->getOperand(0), CI->getType(), 147 "", InsertPt); 148 149 // Add the offset, cast it to the right type. 150 Ptr = BinaryOperator::createAdd(Ptr, PtrOffset, "", InsertPt); 151 // Ptr is an integer type, GEPI is pointer type ==> IntToPtr 152 return V = CastInst::create(Instruction::IntToPtr, Ptr, GEPI->getType(), 153 "", InsertPt); 154} 155 156/// ReplaceUsesOfGEPInst - Replace all uses of RepPtr with inserted code to 157/// compute its value. The RepPtr value can be computed with Ptr+PtrOffset. One 158/// trivial way of doing this would be to evaluate Ptr+PtrOffset in RepPtr's 159/// block, then ReplaceAllUsesWith'ing everything. However, we would prefer to 160/// sink PtrOffset into user blocks where doing so will likely allow us to fold 161/// the constant add into a load or store instruction. Additionally, if a user 162/// is a pointer-pointer cast, we look through it to find its users. 163static void ReplaceUsesOfGEPInst(Instruction *RepPtr, Value *Ptr, 164 Constant *PtrOffset, BasicBlock *DefBB, 165 GetElementPtrInst *GEPI, 166 std::map<BasicBlock*,Instruction*> &InsertedExprs) { 167 while (!RepPtr->use_empty()) { 168 Instruction *User = cast<Instruction>(RepPtr->use_back()); 169 170 // If the user is a Pointer-Pointer cast, recurse. Only BitCast can be 171 // used for a Pointer-Pointer cast. 172 if (isa<BitCastInst>(User)) { 173 ReplaceUsesOfGEPInst(User, Ptr, PtrOffset, DefBB, GEPI, InsertedExprs); 174 175 // Drop the use of RepPtr. The cast is dead. Don't delete it now, else we 176 // could invalidate an iterator. 177 User->setOperand(0, UndefValue::get(RepPtr->getType())); 178 continue; 179 } 180 181 // If this is a load of the pointer, or a store through the pointer, emit 182 // the increment into the load/store block. 183 Instruction *NewVal; 184 if (isa<LoadInst>(User) || 185 (isa<StoreInst>(User) && User->getOperand(0) != RepPtr)) { 186 NewVal = InsertGEPComputeCode(InsertedExprs[User->getParent()], 187 User->getParent(), GEPI, 188 Ptr, PtrOffset); 189 } else { 190 // If this use is not foldable into the addressing mode, use a version 191 // emitted in the GEP block. 192 NewVal = InsertGEPComputeCode(InsertedExprs[DefBB], DefBB, GEPI, 193 Ptr, PtrOffset); 194 } 195 196 if (GEPI->getType() != RepPtr->getType()) { 197 BasicBlock::iterator IP = NewVal; 198 ++IP; 199 // NewVal must be a GEP which must be pointer type, so BitCast 200 NewVal = new BitCastInst(NewVal, RepPtr->getType(), "", IP); 201 } 202 User->replaceUsesOfWith(RepPtr, NewVal); 203 } 204} 205 206/// OptimizeGEPExpression - Since we are doing basic-block-at-a-time instruction 207/// selection, we want to be a bit careful about some things. In particular, if 208/// we have a GEP instruction that is used in a different block than it is 209/// defined, the addressing expression of the GEP cannot be folded into loads or 210/// stores that use it. In this case, decompose the GEP and move constant 211/// indices into blocks that use it. 212bool CodeGenPrepare::OptimizeGEPExpression(GetElementPtrInst *GEPI) { 213 // If this GEP is only used inside the block it is defined in, there is no 214 // need to rewrite it. 215 bool isUsedOutsideDefBB = false; 216 BasicBlock *DefBB = GEPI->getParent(); 217 for (Value::use_iterator UI = GEPI->use_begin(), E = GEPI->use_end(); 218 UI != E; ++UI) { 219 if (cast<Instruction>(*UI)->getParent() != DefBB) { 220 isUsedOutsideDefBB = true; 221 break; 222 } 223 } 224 if (!isUsedOutsideDefBB) return false; 225 226 // If this GEP has no non-zero constant indices, there is nothing we can do, 227 // ignore it. 228 bool hasConstantIndex = false; 229 bool hasVariableIndex = false; 230 for (GetElementPtrInst::op_iterator OI = GEPI->op_begin()+1, 231 E = GEPI->op_end(); OI != E; ++OI) { 232 if (ConstantInt *CI = dyn_cast<ConstantInt>(*OI)) { 233 if (!CI->isZero()) { 234 hasConstantIndex = true; 235 break; 236 } 237 } else { 238 hasVariableIndex = true; 239 } 240 } 241 242 // If this is a "GEP X, 0, 0, 0", turn this into a cast. 243 if (!hasConstantIndex && !hasVariableIndex) { 244 /// The GEP operand must be a pointer, so must its result -> BitCast 245 Value *NC = new BitCastInst(GEPI->getOperand(0), GEPI->getType(), 246 GEPI->getName(), GEPI); 247 GEPI->replaceAllUsesWith(NC); 248 GEPI->eraseFromParent(); 249 return true; 250 } 251 252 // If this is a GEP &Alloca, 0, 0, forward subst the frame index into uses. 253 if (!hasConstantIndex && !isa<AllocaInst>(GEPI->getOperand(0))) 254 return false; 255 256 // If we don't have target lowering info, we can't lower the GEP. 257 if (!TLI) return false; 258 const TargetData *TD = TLI->getTargetData(); 259 260 // Otherwise, decompose the GEP instruction into multiplies and adds. Sum the 261 // constant offset (which we now know is non-zero) and deal with it later. 262 uint64_t ConstantOffset = 0; 263 const Type *UIntPtrTy = TD->getIntPtrType(); 264 Value *Ptr = new PtrToIntInst(GEPI->getOperand(0), UIntPtrTy, "", GEPI); 265 const Type *Ty = GEPI->getOperand(0)->getType(); 266 267 for (GetElementPtrInst::op_iterator OI = GEPI->op_begin()+1, 268 E = GEPI->op_end(); OI != E; ++OI) { 269 Value *Idx = *OI; 270 if (const StructType *StTy = dyn_cast<StructType>(Ty)) { 271 unsigned Field = cast<ConstantInt>(Idx)->getZExtValue(); 272 if (Field) 273 ConstantOffset += TD->getStructLayout(StTy)->getElementOffset(Field); 274 Ty = StTy->getElementType(Field); 275 } else { 276 Ty = cast<SequentialType>(Ty)->getElementType(); 277 278 // Handle constant subscripts. 279 if (ConstantInt *CI = dyn_cast<ConstantInt>(Idx)) { 280 if (CI->getZExtValue() == 0) continue; 281 ConstantOffset += (int64_t)TD->getTypeSize(Ty)*CI->getSExtValue(); 282 continue; 283 } 284 285 // Ptr = Ptr + Idx * ElementSize; 286 287 // Cast Idx to UIntPtrTy if needed. 288 Idx = CastInst::createIntegerCast(Idx, UIntPtrTy, true/*SExt*/, "", GEPI); 289 290 uint64_t ElementSize = TD->getTypeSize(Ty); 291 // Mask off bits that should not be set. 292 ElementSize &= ~0ULL >> (64-UIntPtrTy->getPrimitiveSizeInBits()); 293 Constant *SizeCst = ConstantInt::get(UIntPtrTy, ElementSize); 294 295 // Multiply by the element size and add to the base. 296 Idx = BinaryOperator::createMul(Idx, SizeCst, "", GEPI); 297 Ptr = BinaryOperator::createAdd(Ptr, Idx, "", GEPI); 298 } 299 } 300 301 // Make sure that the offset fits in uintptr_t. 302 ConstantOffset &= ~0ULL >> (64-UIntPtrTy->getPrimitiveSizeInBits()); 303 Constant *PtrOffset = ConstantInt::get(UIntPtrTy, ConstantOffset); 304 305 // Okay, we have now emitted all of the variable index parts to the BB that 306 // the GEP is defined in. Loop over all of the using instructions, inserting 307 // an "add Ptr, ConstantOffset" into each block that uses it and update the 308 // instruction to use the newly computed value, making GEPI dead. When the 309 // user is a load or store instruction address, we emit the add into the user 310 // block, otherwise we use a canonical version right next to the gep (these 311 // won't be foldable as addresses, so we might as well share the computation). 312 313 std::map<BasicBlock*,Instruction*> InsertedExprs; 314 ReplaceUsesOfGEPInst(GEPI, Ptr, PtrOffset, DefBB, GEPI, InsertedExprs); 315 316 // Finally, the GEP is dead, remove it. 317 GEPI->eraseFromParent(); 318 319 return true; 320} 321 322/// SinkInvariantGEPIndex - If a GEP instruction has a variable index that has 323/// been hoisted out of the loop by LICM pass, sink it back into the use BB 324/// if it can be determined that the index computation can be folded into the 325/// addressing mode of the load / store uses. 326static bool SinkInvariantGEPIndex(BinaryOperator *BinOp, 327 const TargetLowering &TLI) { 328 // Only look at Add. 329 if (BinOp->getOpcode() != Instruction::Add) 330 return false; 331 332 // DestBBs - These are the blocks where a copy of BinOp will be inserted. 333 SmallSet<BasicBlock*, 8> DestBBs; 334 BasicBlock *DefBB = BinOp->getParent(); 335 bool MadeChange = false; 336 for (Value::use_iterator UI = BinOp->use_begin(), E = BinOp->use_end(); 337 UI != E; ++UI) { 338 Instruction *GEPI = cast<Instruction>(*UI); 339 // Only look for GEP use in another block. 340 if (GEPI->getParent() == DefBB) continue; 341 342 if (isa<GetElementPtrInst>(GEPI)) { 343 // If the GEP has another variable index, abondon. 344 bool hasVariableIndex = false; 345 for (GetElementPtrInst::op_iterator OI = GEPI->op_begin()+1, 346 OE = GEPI->op_end(); OI != OE; ++OI) 347 if (*OI != BinOp && !isa<ConstantInt>(*OI)) { 348 hasVariableIndex = true; 349 break; 350 } 351 if (hasVariableIndex) 352 break; 353 354 BasicBlock *GEPIBB = GEPI->getParent(); 355 for (Value::use_iterator UUI = GEPI->use_begin(), UE = GEPI->use_end(); 356 UUI != UE; ++UUI) { 357 Instruction *GEPIUser = cast<Instruction>(*UUI); 358 const Type *UseTy = NULL; 359 if (LoadInst *Load = dyn_cast<LoadInst>(GEPIUser)) 360 UseTy = Load->getType(); 361 else if (StoreInst *Store = dyn_cast<StoreInst>(GEPIUser)) 362 UseTy = Store->getOperand(0)->getType(); 363 364 // Check if it is possible to fold the expression to address mode. 365 if (UseTy && isa<ConstantInt>(BinOp->getOperand(1))) { 366 uint64_t Scale = TLI.getTargetData()->getTypeSize(UseTy); 367 int64_t Cst = cast<ConstantInt>(BinOp->getOperand(1))->getSExtValue(); 368 // e.g. load (gep i32 * %P, (X+42)) => load (%P + X*4 + 168). 369 if (TLI.isLegalAddressImmediate(Cst*Scale, UseTy) && 370 (Scale == 1 || TLI.isLegalAddressScale(Scale, UseTy))) { 371 DestBBs.insert(GEPIBB); 372 MadeChange = true; 373 break; 374 } 375 } 376 } 377 } 378 } 379 380 // Nothing to do. 381 if (!MadeChange) 382 return false; 383 384 /// InsertedOps - Only insert a duplicate in each block once. 385 std::map<BasicBlock*, BinaryOperator*> InsertedOps; 386 for (Value::use_iterator UI = BinOp->use_begin(), E = BinOp->use_end(); 387 UI != E; ) { 388 Instruction *User = cast<Instruction>(*UI); 389 BasicBlock *UserBB = User->getParent(); 390 391 // Preincrement use iterator so we don't invalidate it. 392 ++UI; 393 394 // If any user in this BB wants it, replace all the uses in the BB. 395 if (DestBBs.count(UserBB)) { 396 // Sink it into user block. 397 BinaryOperator *&InsertedOp = InsertedOps[UserBB]; 398 if (!InsertedOp) { 399 BasicBlock::iterator InsertPt = UserBB->begin(); 400 while (isa<PHINode>(InsertPt)) ++InsertPt; 401 402 InsertedOp = 403 BinaryOperator::create(BinOp->getOpcode(), BinOp->getOperand(0), 404 BinOp->getOperand(1), "", InsertPt); 405 } 406 407 User->replaceUsesOfWith(BinOp, InsertedOp); 408 } 409 } 410 411 if (BinOp->use_empty()) 412 BinOp->eraseFromParent(); 413 414 return true; 415} 416 417/// OptimizeNoopCopyExpression - We have determined that the specified cast 418/// instruction is a noop copy (e.g. it's casting from one pointer type to 419/// another, int->uint, or int->sbyte on PPC. 420/// 421/// Return true if any changes are made. 422static bool OptimizeNoopCopyExpression(CastInst *CI) { 423 BasicBlock *DefBB = CI->getParent(); 424 425 /// InsertedCasts - Only insert a cast in each block once. 426 std::map<BasicBlock*, CastInst*> InsertedCasts; 427 428 bool MadeChange = false; 429 for (Value::use_iterator UI = CI->use_begin(), E = CI->use_end(); 430 UI != E; ) { 431 Use &TheUse = UI.getUse(); 432 Instruction *User = cast<Instruction>(*UI); 433 434 // Figure out which BB this cast is used in. For PHI's this is the 435 // appropriate predecessor block. 436 BasicBlock *UserBB = User->getParent(); 437 if (PHINode *PN = dyn_cast<PHINode>(User)) { 438 unsigned OpVal = UI.getOperandNo()/2; 439 UserBB = PN->getIncomingBlock(OpVal); 440 } 441 442 // Preincrement use iterator so we don't invalidate it. 443 ++UI; 444 445 // If this user is in the same block as the cast, don't change the cast. 446 if (UserBB == DefBB) continue; 447 448 // If we have already inserted a cast into this block, use it. 449 CastInst *&InsertedCast = InsertedCasts[UserBB]; 450 451 if (!InsertedCast) { 452 BasicBlock::iterator InsertPt = UserBB->begin(); 453 while (isa<PHINode>(InsertPt)) ++InsertPt; 454 455 InsertedCast = 456 CastInst::create(CI->getOpcode(), CI->getOperand(0), CI->getType(), "", 457 InsertPt); 458 MadeChange = true; 459 } 460 461 // Replace a use of the cast with a use of the new casat. 462 TheUse = InsertedCast; 463 } 464 465 // If we removed all uses, nuke the cast. 466 if (CI->use_empty()) 467 CI->eraseFromParent(); 468 469 return MadeChange; 470} 471 472 473 474// In this pass we look for GEP and cast instructions that are used 475// across basic blocks and rewrite them to improve basic-block-at-a-time 476// selection. 477bool CodeGenPrepare::OptimizeBlock(BasicBlock &BB) { 478 bool MadeChange = false; 479 480 // Split all critical edges where the dest block has a PHI and where the phi 481 // has shared immediate operands. 482 TerminatorInst *BBTI = BB.getTerminator(); 483 if (BBTI->getNumSuccessors() > 1) { 484 for (unsigned i = 0, e = BBTI->getNumSuccessors(); i != e; ++i) 485 if (isa<PHINode>(BBTI->getSuccessor(i)->begin()) && 486 isCriticalEdge(BBTI, i, true)) 487 SplitEdgeNicely(BBTI, i, this); 488 } 489 490 491 for (BasicBlock::iterator BBI = BB.begin(), E = BB.end(); BBI != E; ) { 492 Instruction *I = BBI++; 493 494 if (CallInst *CI = dyn_cast<CallInst>(I)) { 495 // If we found an inline asm expession, and if the target knows how to 496 // lower it to normal LLVM code, do so now. 497 if (TLI && isa<InlineAsm>(CI->getCalledValue())) 498 if (const TargetAsmInfo *TAI = 499 TLI->getTargetMachine().getTargetAsmInfo()) { 500 if (TAI->ExpandInlineAsm(CI)) 501 BBI = BB.begin(); 502 } 503 } else if (GetElementPtrInst *GEPI = dyn_cast<GetElementPtrInst>(I)) { 504 MadeChange |= OptimizeGEPExpression(GEPI); 505 } else if (CastInst *CI = dyn_cast<CastInst>(I)) { 506 // If the source of the cast is a constant, then this should have 507 // already been constant folded. The only reason NOT to constant fold 508 // it is if something (e.g. LSR) was careful to place the constant 509 // evaluation in a block other than then one that uses it (e.g. to hoist 510 // the address of globals out of a loop). If this is the case, we don't 511 // want to forward-subst the cast. 512 if (isa<Constant>(CI->getOperand(0))) 513 continue; 514 515 if (!TLI) continue; 516 517 // If this is a noop copy, sink it into user blocks to reduce the number 518 // of virtual registers that must be created and coallesced. 519 MVT::ValueType SrcVT = TLI->getValueType(CI->getOperand(0)->getType()); 520 MVT::ValueType DstVT = TLI->getValueType(CI->getType()); 521 522 // This is an fp<->int conversion? 523 if (MVT::isInteger(SrcVT) != MVT::isInteger(DstVT)) 524 continue; 525 526 // If this is an extension, it will be a zero or sign extension, which 527 // isn't a noop. 528 if (SrcVT < DstVT) continue; 529 530 // If these values will be promoted, find out what they will be promoted 531 // to. This helps us consider truncates on PPC as noop copies when they 532 // are. 533 if (TLI->getTypeAction(SrcVT) == TargetLowering::Promote) 534 SrcVT = TLI->getTypeToTransformTo(SrcVT); 535 if (TLI->getTypeAction(DstVT) == TargetLowering::Promote) 536 DstVT = TLI->getTypeToTransformTo(DstVT); 537 538 // If, after promotion, these are the same types, this is a noop copy. 539 if (SrcVT == DstVT) 540 MadeChange |= OptimizeNoopCopyExpression(CI); 541 } else if (BinaryOperator *BinOp = dyn_cast<BinaryOperator>(I)) { 542 if (TLI) 543 MadeChange |= SinkInvariantGEPIndex(BinOp, *TLI); 544 } 545 } 546 return MadeChange; 547} 548 549