1 //===- CodeGenPrepare.cpp - Prepare a function for code generation --------===// 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 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/InlineAsm.h" 22 #include "llvm/Instructions.h" 23 #include "llvm/IntrinsicInst.h" 24 #include "llvm/Pass.h" 25 #include "llvm/Analysis/Dominators.h" 26 #include "llvm/Analysis/InstructionSimplify.h" 27 #include "llvm/Analysis/ProfileInfo.h" 28 #include "llvm/Target/TargetData.h" 29 #include "llvm/Target/TargetLowering.h" 30 #include "llvm/Transforms/Utils/AddrModeMatcher.h" 31 #include "llvm/Transforms/Utils/BasicBlockUtils.h" 32 #include "llvm/Transforms/Utils/Local.h" 33 #include "llvm/Transforms/Utils/BuildLibCalls.h" 34 #include "llvm/ADT/DenseMap.h" 35 #include "llvm/ADT/SmallSet.h" 36 #include "llvm/ADT/Statistic.h" 37 #include "llvm/Assembly/Writer.h" 38 #include "llvm/Support/CallSite.h" 39 #include "llvm/Support/CommandLine.h" 40 #include "llvm/Support/Debug.h" 41 #include "llvm/Support/GetElementPtrTypeIterator.h" 42 #include "llvm/Support/PatternMatch.h" 43 #include "llvm/Support/raw_ostream.h" 44 #include "llvm/Support/IRBuilder.h" 45 #include "llvm/Support/ValueHandle.h" 46 using namespace llvm; 47 using namespace llvm::PatternMatch; 48 49 STATISTIC(NumBlocksElim, "Number of blocks eliminated"); 50 STATISTIC(NumPHIsElim, "Number of trivial PHIs eliminated"); 51 STATISTIC(NumGEPsElim, "Number of GEPs converted to casts"); 52 STATISTIC(NumCmpUses, "Number of uses of Cmp expressions replaced with uses of " 53 "sunken Cmps"); 54 STATISTIC(NumCastUses, "Number of uses of Cast expressions replaced with uses " 55 "of sunken Casts"); 56 STATISTIC(NumMemoryInsts, "Number of memory instructions whose address " 57 "computations were sunk"); 58 STATISTIC(NumExtsMoved, "Number of [s|z]ext instructions combined with loads"); 59 STATISTIC(NumExtUses, "Number of uses of [s|z]ext instructions optimized"); 60 STATISTIC(NumRetsDup, "Number of return instructions duplicated"); 61 STATISTIC(NumDbgValueMoved, "Number of debug value instructions moved"); 62 63 static cl::opt<bool> DisableBranchOpts( 64 "disable-cgp-branch-opts", cl::Hidden, cl::init(false), 65 cl::desc("Disable branch optimizations in CodeGenPrepare")); 66 67 namespace { 68 class CodeGenPrepare : public FunctionPass { 69 /// TLI - Keep a pointer of a TargetLowering to consult for determining 70 /// transformation profitability. 71 const TargetLowering *TLI; 72 DominatorTree *DT; 73 ProfileInfo *PFI; 74 75 /// CurInstIterator - As we scan instructions optimizing them, this is the 76 /// next instruction to optimize. Xforms that can invalidate this should 77 /// update it. 78 BasicBlock::iterator CurInstIterator; 79 80 /// Keeps track of non-local addresses that have been sunk into a block. 81 /// This allows us to avoid inserting duplicate code for blocks with 82 /// multiple load/stores of the same address. 83 DenseMap<Value*, Value*> SunkAddrs; 84 85 /// ModifiedDT - If CFG is modified in anyway, dominator tree may need to 86 /// be updated. 87 bool ModifiedDT; 88 89 public: 90 static char ID; // Pass identification, replacement for typeid 91 explicit CodeGenPrepare(const TargetLowering *tli = 0) 92 : FunctionPass(ID), TLI(tli) { 93 initializeCodeGenPreparePass(*PassRegistry::getPassRegistry()); 94 } 95 bool runOnFunction(Function &F); 96 97 virtual void getAnalysisUsage(AnalysisUsage &AU) const { 98 AU.addPreserved<DominatorTree>(); 99 AU.addPreserved<ProfileInfo>(); 100 } 101 102 private: 103 bool EliminateMostlyEmptyBlocks(Function &F); 104 bool CanMergeBlocks(const BasicBlock *BB, const BasicBlock *DestBB) const; 105 void EliminateMostlyEmptyBlock(BasicBlock *BB); 106 bool OptimizeBlock(BasicBlock &BB); 107 bool OptimizeInst(Instruction *I); 108 bool OptimizeMemoryInst(Instruction *I, Value *Addr, Type *AccessTy); 109 bool OptimizeInlineAsmInst(CallInst *CS); 110 bool OptimizeCallInst(CallInst *CI); 111 bool MoveExtToFormExtLoad(Instruction *I); 112 bool OptimizeExtUses(Instruction *I); 113 bool DupRetToEnableTailCallOpts(ReturnInst *RI); 114 bool PlaceDbgValues(Function &F); 115 }; 116 } 117 118 char CodeGenPrepare::ID = 0; 119 INITIALIZE_PASS(CodeGenPrepare, "codegenprepare", 120 "Optimize for code generation", false, false) 121 122 FunctionPass *llvm::createCodeGenPreparePass(const TargetLowering *TLI) { 123 return new CodeGenPrepare(TLI); 124 } 125 126 bool CodeGenPrepare::runOnFunction(Function &F) { 127 bool EverMadeChange = false; 128 129 ModifiedDT = false; 130 DT = getAnalysisIfAvailable<DominatorTree>(); 131 PFI = getAnalysisIfAvailable<ProfileInfo>(); 132 133 // First pass, eliminate blocks that contain only PHI nodes and an 134 // unconditional branch. 135 EverMadeChange |= EliminateMostlyEmptyBlocks(F); 136 137 // llvm.dbg.value is far away from the value then iSel may not be able 138 // handle it properly. iSel will drop llvm.dbg.value if it can not 139 // find a node corresponding to the value. 140 EverMadeChange |= PlaceDbgValues(F); 141 142 bool MadeChange = true; 143 while (MadeChange) { 144 MadeChange = false; 145 for (Function::iterator I = F.begin(), E = F.end(); I != E; ) { 146 BasicBlock *BB = I++; 147 MadeChange |= OptimizeBlock(*BB); 148 } 149 EverMadeChange |= MadeChange; 150 } 151 152 SunkAddrs.clear(); 153 154 if (!DisableBranchOpts) { 155 MadeChange = false; 156 for (Function::iterator BB = F.begin(), E = F.end(); BB != E; ++BB) 157 MadeChange |= ConstantFoldTerminator(BB, true); 158 159 if (MadeChange) 160 ModifiedDT = true; 161 EverMadeChange |= MadeChange; 162 } 163 164 if (ModifiedDT && DT) 165 DT->DT->recalculate(F); 166 167 return EverMadeChange; 168 } 169 170 /// EliminateMostlyEmptyBlocks - eliminate blocks that contain only PHI nodes, 171 /// debug info directives, and an unconditional branch. Passes before isel 172 /// (e.g. LSR/loopsimplify) often split edges in ways that are non-optimal for 173 /// isel. Start by eliminating these blocks so we can split them the way we 174 /// want them. 175 bool CodeGenPrepare::EliminateMostlyEmptyBlocks(Function &F) { 176 bool MadeChange = false; 177 // Note that this intentionally skips the entry block. 178 for (Function::iterator I = ++F.begin(), E = F.end(); I != E; ) { 179 BasicBlock *BB = I++; 180 181 // If this block doesn't end with an uncond branch, ignore it. 182 BranchInst *BI = dyn_cast<BranchInst>(BB->getTerminator()); 183 if (!BI || !BI->isUnconditional()) 184 continue; 185 186 // If the instruction before the branch (skipping debug info) isn't a phi 187 // node, then other stuff is happening here. 188 BasicBlock::iterator BBI = BI; 189 if (BBI != BB->begin()) { 190 --BBI; 191 while (isa<DbgInfoIntrinsic>(BBI)) { 192 if (BBI == BB->begin()) 193 break; 194 --BBI; 195 } 196 if (!isa<DbgInfoIntrinsic>(BBI) && !isa<PHINode>(BBI)) 197 continue; 198 } 199 200 // Do not break infinite loops. 201 BasicBlock *DestBB = BI->getSuccessor(0); 202 if (DestBB == BB) 203 continue; 204 205 if (!CanMergeBlocks(BB, DestBB)) 206 continue; 207 208 EliminateMostlyEmptyBlock(BB); 209 MadeChange = true; 210 } 211 return MadeChange; 212 } 213 214 /// CanMergeBlocks - Return true if we can merge BB into DestBB if there is a 215 /// single uncond branch between them, and BB contains no other non-phi 216 /// instructions. 217 bool CodeGenPrepare::CanMergeBlocks(const BasicBlock *BB, 218 const BasicBlock *DestBB) const { 219 // We only want to eliminate blocks whose phi nodes are used by phi nodes in 220 // the successor. If there are more complex condition (e.g. preheaders), 221 // don't mess around with them. 222 BasicBlock::const_iterator BBI = BB->begin(); 223 while (const PHINode *PN = dyn_cast<PHINode>(BBI++)) { 224 for (Value::const_use_iterator UI = PN->use_begin(), E = PN->use_end(); 225 UI != E; ++UI) { 226 const Instruction *User = cast<Instruction>(*UI); 227 if (User->getParent() != DestBB || !isa<PHINode>(User)) 228 return false; 229 // If User is inside DestBB block and it is a PHINode then check 230 // incoming value. If incoming value is not from BB then this is 231 // a complex condition (e.g. preheaders) we want to avoid here. 232 if (User->getParent() == DestBB) { 233 if (const PHINode *UPN = dyn_cast<PHINode>(User)) 234 for (unsigned I = 0, E = UPN->getNumIncomingValues(); I != E; ++I) { 235 Instruction *Insn = dyn_cast<Instruction>(UPN->getIncomingValue(I)); 236 if (Insn && Insn->getParent() == BB && 237 Insn->getParent() != UPN->getIncomingBlock(I)) 238 return false; 239 } 240 } 241 } 242 } 243 244 // If BB and DestBB contain any common predecessors, then the phi nodes in BB 245 // and DestBB may have conflicting incoming values for the block. If so, we 246 // can't merge the block. 247 const PHINode *DestBBPN = dyn_cast<PHINode>(DestBB->begin()); 248 if (!DestBBPN) return true; // no conflict. 249 250 // Collect the preds of BB. 251 SmallPtrSet<const BasicBlock*, 16> BBPreds; 252 if (const PHINode *BBPN = dyn_cast<PHINode>(BB->begin())) { 253 // It is faster to get preds from a PHI than with pred_iterator. 254 for (unsigned i = 0, e = BBPN->getNumIncomingValues(); i != e; ++i) 255 BBPreds.insert(BBPN->getIncomingBlock(i)); 256 } else { 257 BBPreds.insert(pred_begin(BB), pred_end(BB)); 258 } 259 260 // Walk the preds of DestBB. 261 for (unsigned i = 0, e = DestBBPN->getNumIncomingValues(); i != e; ++i) { 262 BasicBlock *Pred = DestBBPN->getIncomingBlock(i); 263 if (BBPreds.count(Pred)) { // Common predecessor? 264 BBI = DestBB->begin(); 265 while (const PHINode *PN = dyn_cast<PHINode>(BBI++)) { 266 const Value *V1 = PN->getIncomingValueForBlock(Pred); 267 const Value *V2 = PN->getIncomingValueForBlock(BB); 268 269 // If V2 is a phi node in BB, look up what the mapped value will be. 270 if (const PHINode *V2PN = dyn_cast<PHINode>(V2)) 271 if (V2PN->getParent() == BB) 272 V2 = V2PN->getIncomingValueForBlock(Pred); 273 274 // If there is a conflict, bail out. 275 if (V1 != V2) return false; 276 } 277 } 278 } 279 280 return true; 281 } 282 283 284 /// EliminateMostlyEmptyBlock - Eliminate a basic block that have only phi's and 285 /// an unconditional branch in it. 286 void CodeGenPrepare::EliminateMostlyEmptyBlock(BasicBlock *BB) { 287 BranchInst *BI = cast<BranchInst>(BB->getTerminator()); 288 BasicBlock *DestBB = BI->getSuccessor(0); 289 290 DEBUG(dbgs() << "MERGING MOSTLY EMPTY BLOCKS - BEFORE:\n" << *BB << *DestBB); 291 292 // If the destination block has a single pred, then this is a trivial edge, 293 // just collapse it. 294 if (BasicBlock *SinglePred = DestBB->getSinglePredecessor()) { 295 if (SinglePred != DestBB) { 296 // Remember if SinglePred was the entry block of the function. If so, we 297 // will need to move BB back to the entry position. 298 bool isEntry = SinglePred == &SinglePred->getParent()->getEntryBlock(); 299 MergeBasicBlockIntoOnlyPred(DestBB, this); 300 301 if (isEntry && BB != &BB->getParent()->getEntryBlock()) 302 BB->moveBefore(&BB->getParent()->getEntryBlock()); 303 304 DEBUG(dbgs() << "AFTER:\n" << *DestBB << "\n\n\n"); 305 return; 306 } 307 } 308 309 // Otherwise, we have multiple predecessors of BB. Update the PHIs in DestBB 310 // to handle the new incoming edges it is about to have. 311 PHINode *PN; 312 for (BasicBlock::iterator BBI = DestBB->begin(); 313 (PN = dyn_cast<PHINode>(BBI)); ++BBI) { 314 // Remove the incoming value for BB, and remember it. 315 Value *InVal = PN->removeIncomingValue(BB, false); 316 317 // Two options: either the InVal is a phi node defined in BB or it is some 318 // value that dominates BB. 319 PHINode *InValPhi = dyn_cast<PHINode>(InVal); 320 if (InValPhi && InValPhi->getParent() == BB) { 321 // Add all of the input values of the input PHI as inputs of this phi. 322 for (unsigned i = 0, e = InValPhi->getNumIncomingValues(); i != e; ++i) 323 PN->addIncoming(InValPhi->getIncomingValue(i), 324 InValPhi->getIncomingBlock(i)); 325 } else { 326 // Otherwise, add one instance of the dominating value for each edge that 327 // we will be adding. 328 if (PHINode *BBPN = dyn_cast<PHINode>(BB->begin())) { 329 for (unsigned i = 0, e = BBPN->getNumIncomingValues(); i != e; ++i) 330 PN->addIncoming(InVal, BBPN->getIncomingBlock(i)); 331 } else { 332 for (pred_iterator PI = pred_begin(BB), E = pred_end(BB); PI != E; ++PI) 333 PN->addIncoming(InVal, *PI); 334 } 335 } 336 } 337 338 // The PHIs are now updated, change everything that refers to BB to use 339 // DestBB and remove BB. 340 BB->replaceAllUsesWith(DestBB); 341 if (DT && !ModifiedDT) { 342 BasicBlock *BBIDom = DT->getNode(BB)->getIDom()->getBlock(); 343 BasicBlock *DestBBIDom = DT->getNode(DestBB)->getIDom()->getBlock(); 344 BasicBlock *NewIDom = DT->findNearestCommonDominator(BBIDom, DestBBIDom); 345 DT->changeImmediateDominator(DestBB, NewIDom); 346 DT->eraseNode(BB); 347 } 348 if (PFI) { 349 PFI->replaceAllUses(BB, DestBB); 350 PFI->removeEdge(ProfileInfo::getEdge(BB, DestBB)); 351 } 352 BB->eraseFromParent(); 353 ++NumBlocksElim; 354 355 DEBUG(dbgs() << "AFTER:\n" << *DestBB << "\n\n\n"); 356 } 357 358 /// OptimizeNoopCopyExpression - If the specified cast instruction is a noop 359 /// copy (e.g. it's casting from one pointer type to another, i32->i8 on PPC), 360 /// sink it into user blocks to reduce the number of virtual 361 /// registers that must be created and coalesced. 362 /// 363 /// Return true if any changes are made. 364 /// 365 static bool OptimizeNoopCopyExpression(CastInst *CI, const TargetLowering &TLI){ 366 // If this is a noop copy, 367 EVT SrcVT = TLI.getValueType(CI->getOperand(0)->getType()); 368 EVT DstVT = TLI.getValueType(CI->getType()); 369 370 // This is an fp<->int conversion? 371 if (SrcVT.isInteger() != DstVT.isInteger()) 372 return false; 373 374 // If this is an extension, it will be a zero or sign extension, which 375 // isn't a noop. 376 if (SrcVT.bitsLT(DstVT)) return false; 377 378 // If these values will be promoted, find out what they will be promoted 379 // to. This helps us consider truncates on PPC as noop copies when they 380 // are. 381 if (TLI.getTypeAction(CI->getContext(), SrcVT) == 382 TargetLowering::TypePromoteInteger) 383 SrcVT = TLI.getTypeToTransformTo(CI->getContext(), SrcVT); 384 if (TLI.getTypeAction(CI->getContext(), DstVT) == 385 TargetLowering::TypePromoteInteger) 386 DstVT = TLI.getTypeToTransformTo(CI->getContext(), DstVT); 387 388 // If, after promotion, these are the same types, this is a noop copy. 389 if (SrcVT != DstVT) 390 return false; 391 392 BasicBlock *DefBB = CI->getParent(); 393 394 /// InsertedCasts - Only insert a cast in each block once. 395 DenseMap<BasicBlock*, CastInst*> InsertedCasts; 396 397 bool MadeChange = false; 398 for (Value::use_iterator UI = CI->use_begin(), E = CI->use_end(); 399 UI != E; ) { 400 Use &TheUse = UI.getUse(); 401 Instruction *User = cast<Instruction>(*UI); 402 403 // Figure out which BB this cast is used in. For PHI's this is the 404 // appropriate predecessor block. 405 BasicBlock *UserBB = User->getParent(); 406 if (PHINode *PN = dyn_cast<PHINode>(User)) { 407 UserBB = PN->getIncomingBlock(UI); 408 } 409 410 // Preincrement use iterator so we don't invalidate it. 411 ++UI; 412 413 // If this user is in the same block as the cast, don't change the cast. 414 if (UserBB == DefBB) continue; 415 416 // If we have already inserted a cast into this block, use it. 417 CastInst *&InsertedCast = InsertedCasts[UserBB]; 418 419 if (!InsertedCast) { 420 BasicBlock::iterator InsertPt = UserBB->getFirstInsertionPt(); 421 InsertedCast = 422 CastInst::Create(CI->getOpcode(), CI->getOperand(0), CI->getType(), "", 423 InsertPt); 424 MadeChange = true; 425 } 426 427 // Replace a use of the cast with a use of the new cast. 428 TheUse = InsertedCast; 429 ++NumCastUses; 430 } 431 432 // If we removed all uses, nuke the cast. 433 if (CI->use_empty()) { 434 CI->eraseFromParent(); 435 MadeChange = true; 436 } 437 438 return MadeChange; 439 } 440 441 /// OptimizeCmpExpression - sink the given CmpInst into user blocks to reduce 442 /// the number of virtual registers that must be created and coalesced. This is 443 /// a clear win except on targets with multiple condition code registers 444 /// (PowerPC), where it might lose; some adjustment may be wanted there. 445 /// 446 /// Return true if any changes are made. 447 static bool OptimizeCmpExpression(CmpInst *CI) { 448 BasicBlock *DefBB = CI->getParent(); 449 450 /// InsertedCmp - Only insert a cmp in each block once. 451 DenseMap<BasicBlock*, CmpInst*> InsertedCmps; 452 453 bool MadeChange = false; 454 for (Value::use_iterator UI = CI->use_begin(), E = CI->use_end(); 455 UI != E; ) { 456 Use &TheUse = UI.getUse(); 457 Instruction *User = cast<Instruction>(*UI); 458 459 // Preincrement use iterator so we don't invalidate it. 460 ++UI; 461 462 // Don't bother for PHI nodes. 463 if (isa<PHINode>(User)) 464 continue; 465 466 // Figure out which BB this cmp is used in. 467 BasicBlock *UserBB = User->getParent(); 468 469 // If this user is in the same block as the cmp, don't change the cmp. 470 if (UserBB == DefBB) continue; 471 472 // If we have already inserted a cmp into this block, use it. 473 CmpInst *&InsertedCmp = InsertedCmps[UserBB]; 474 475 if (!InsertedCmp) { 476 BasicBlock::iterator InsertPt = UserBB->getFirstInsertionPt(); 477 InsertedCmp = 478 CmpInst::Create(CI->getOpcode(), 479 CI->getPredicate(), CI->getOperand(0), 480 CI->getOperand(1), "", InsertPt); 481 MadeChange = true; 482 } 483 484 // Replace a use of the cmp with a use of the new cmp. 485 TheUse = InsertedCmp; 486 ++NumCmpUses; 487 } 488 489 // If we removed all uses, nuke the cmp. 490 if (CI->use_empty()) 491 CI->eraseFromParent(); 492 493 return MadeChange; 494 } 495 496 namespace { 497 class CodeGenPrepareFortifiedLibCalls : public SimplifyFortifiedLibCalls { 498 protected: 499 void replaceCall(Value *With) { 500 CI->replaceAllUsesWith(With); 501 CI->eraseFromParent(); 502 } 503 bool isFoldable(unsigned SizeCIOp, unsigned, bool) const { 504 if (ConstantInt *SizeCI = 505 dyn_cast<ConstantInt>(CI->getArgOperand(SizeCIOp))) 506 return SizeCI->isAllOnesValue(); 507 return false; 508 } 509 }; 510 } // end anonymous namespace 511 512 bool CodeGenPrepare::OptimizeCallInst(CallInst *CI) { 513 BasicBlock *BB = CI->getParent(); 514 515 // Lower inline assembly if we can. 516 // If we found an inline asm expession, and if the target knows how to 517 // lower it to normal LLVM code, do so now. 518 if (TLI && isa<InlineAsm>(CI->getCalledValue())) { 519 if (TLI->ExpandInlineAsm(CI)) { 520 // Avoid invalidating the iterator. 521 CurInstIterator = BB->begin(); 522 // Avoid processing instructions out of order, which could cause 523 // reuse before a value is defined. 524 SunkAddrs.clear(); 525 return true; 526 } 527 // Sink address computing for memory operands into the block. 528 if (OptimizeInlineAsmInst(CI)) 529 return true; 530 } 531 532 // Lower all uses of llvm.objectsize.* 533 IntrinsicInst *II = dyn_cast<IntrinsicInst>(CI); 534 if (II && II->getIntrinsicID() == Intrinsic::objectsize) { 535 bool Min = (cast<ConstantInt>(II->getArgOperand(1))->getZExtValue() == 1); 536 Type *ReturnTy = CI->getType(); 537 Constant *RetVal = ConstantInt::get(ReturnTy, Min ? 0 : -1ULL); 538 539 // Substituting this can cause recursive simplifications, which can 540 // invalidate our iterator. Use a WeakVH to hold onto it in case this 541 // happens. 542 WeakVH IterHandle(CurInstIterator); 543 544 ReplaceAndSimplifyAllUses(CI, RetVal, TLI ? TLI->getTargetData() : 0, 545 ModifiedDT ? 0 : DT); 546 547 // If the iterator instruction was recursively deleted, start over at the 548 // start of the block. 549 if (IterHandle != CurInstIterator) { 550 CurInstIterator = BB->begin(); 551 SunkAddrs.clear(); 552 } 553 return true; 554 } 555 556 // From here on out we're working with named functions. 557 if (CI->getCalledFunction() == 0) return false; 558 559 // We'll need TargetData from here on out. 560 const TargetData *TD = TLI ? TLI->getTargetData() : 0; 561 if (!TD) return false; 562 563 // Lower all default uses of _chk calls. This is very similar 564 // to what InstCombineCalls does, but here we are only lowering calls 565 // that have the default "don't know" as the objectsize. Anything else 566 // should be left alone. 567 CodeGenPrepareFortifiedLibCalls Simplifier; 568 return Simplifier.fold(CI, TD); 569 } 570 571 /// DupRetToEnableTailCallOpts - Look for opportunities to duplicate return 572 /// instructions to the predecessor to enable tail call optimizations. The 573 /// case it is currently looking for is: 574 /// bb0: 575 /// %tmp0 = tail call i32 @f0() 576 /// br label %return 577 /// bb1: 578 /// %tmp1 = tail call i32 @f1() 579 /// br label %return 580 /// bb2: 581 /// %tmp2 = tail call i32 @f2() 582 /// br label %return 583 /// return: 584 /// %retval = phi i32 [ %tmp0, %bb0 ], [ %tmp1, %bb1 ], [ %tmp2, %bb2 ] 585 /// ret i32 %retval 586 /// 587 /// => 588 /// 589 /// bb0: 590 /// %tmp0 = tail call i32 @f0() 591 /// ret i32 %tmp0 592 /// bb1: 593 /// %tmp1 = tail call i32 @f1() 594 /// ret i32 %tmp1 595 /// bb2: 596 /// %tmp2 = tail call i32 @f2() 597 /// ret i32 %tmp2 598 /// 599 bool CodeGenPrepare::DupRetToEnableTailCallOpts(ReturnInst *RI) { 600 if (!TLI) 601 return false; 602 603 Value *V = RI->getReturnValue(); 604 PHINode *PN = V ? dyn_cast<PHINode>(V) : NULL; 605 if (V && !PN) 606 return false; 607 608 BasicBlock *BB = RI->getParent(); 609 if (PN && PN->getParent() != BB) 610 return false; 611 612 // It's not safe to eliminate the sign / zero extension of the return value. 613 // See llvm::isInTailCallPosition(). 614 const Function *F = BB->getParent(); 615 unsigned CallerRetAttr = F->getAttributes().getRetAttributes(); 616 if ((CallerRetAttr & Attribute::ZExt) || (CallerRetAttr & Attribute::SExt)) 617 return false; 618 619 // Make sure there are no instructions between the PHI and return, or that the 620 // return is the first instruction in the block. 621 if (PN) { 622 BasicBlock::iterator BI = BB->begin(); 623 do { ++BI; } while (isa<DbgInfoIntrinsic>(BI)); 624 if (&*BI != RI) 625 return false; 626 } else { 627 BasicBlock::iterator BI = BB->begin(); 628 while (isa<DbgInfoIntrinsic>(BI)) ++BI; 629 if (&*BI != RI) 630 return false; 631 } 632 633 /// Only dup the ReturnInst if the CallInst is likely to be emitted as a tail 634 /// call. 635 SmallVector<CallInst*, 4> TailCalls; 636 if (PN) { 637 for (unsigned I = 0, E = PN->getNumIncomingValues(); I != E; ++I) { 638 CallInst *CI = dyn_cast<CallInst>(PN->getIncomingValue(I)); 639 // Make sure the phi value is indeed produced by the tail call. 640 if (CI && CI->hasOneUse() && CI->getParent() == PN->getIncomingBlock(I) && 641 TLI->mayBeEmittedAsTailCall(CI)) 642 TailCalls.push_back(CI); 643 } 644 } else { 645 SmallPtrSet<BasicBlock*, 4> VisitedBBs; 646 for (pred_iterator PI = pred_begin(BB), PE = pred_end(BB); PI != PE; ++PI) { 647 if (!VisitedBBs.insert(*PI)) 648 continue; 649 650 BasicBlock::InstListType &InstList = (*PI)->getInstList(); 651 BasicBlock::InstListType::reverse_iterator RI = InstList.rbegin(); 652 BasicBlock::InstListType::reverse_iterator RE = InstList.rend(); 653 do { ++RI; } while (RI != RE && isa<DbgInfoIntrinsic>(&*RI)); 654 if (RI == RE) 655 continue; 656 657 CallInst *CI = dyn_cast<CallInst>(&*RI); 658 if (CI && CI->use_empty() && TLI->mayBeEmittedAsTailCall(CI)) 659 TailCalls.push_back(CI); 660 } 661 } 662 663 bool Changed = false; 664 for (unsigned i = 0, e = TailCalls.size(); i != e; ++i) { 665 CallInst *CI = TailCalls[i]; 666 CallSite CS(CI); 667 668 // Conservatively require the attributes of the call to match those of the 669 // return. Ignore noalias because it doesn't affect the call sequence. 670 unsigned CalleeRetAttr = CS.getAttributes().getRetAttributes(); 671 if ((CalleeRetAttr ^ CallerRetAttr) & ~Attribute::NoAlias) 672 continue; 673 674 // Make sure the call instruction is followed by an unconditional branch to 675 // the return block. 676 BasicBlock *CallBB = CI->getParent(); 677 BranchInst *BI = dyn_cast<BranchInst>(CallBB->getTerminator()); 678 if (!BI || !BI->isUnconditional() || BI->getSuccessor(0) != BB) 679 continue; 680 681 // Duplicate the return into CallBB. 682 (void)FoldReturnIntoUncondBranch(RI, BB, CallBB); 683 ModifiedDT = Changed = true; 684 ++NumRetsDup; 685 } 686 687 // If we eliminated all predecessors of the block, delete the block now. 688 if (Changed && pred_begin(BB) == pred_end(BB)) 689 BB->eraseFromParent(); 690 691 return Changed; 692 } 693 694 //===----------------------------------------------------------------------===// 695 // Memory Optimization 696 //===----------------------------------------------------------------------===// 697 698 /// IsNonLocalValue - Return true if the specified values are defined in a 699 /// different basic block than BB. 700 static bool IsNonLocalValue(Value *V, BasicBlock *BB) { 701 if (Instruction *I = dyn_cast<Instruction>(V)) 702 return I->getParent() != BB; 703 return false; 704 } 705 706 /// OptimizeMemoryInst - Load and Store Instructions often have 707 /// addressing modes that can do significant amounts of computation. As such, 708 /// instruction selection will try to get the load or store to do as much 709 /// computation as possible for the program. The problem is that isel can only 710 /// see within a single block. As such, we sink as much legal addressing mode 711 /// stuff into the block as possible. 712 /// 713 /// This method is used to optimize both load/store and inline asms with memory 714 /// operands. 715 bool CodeGenPrepare::OptimizeMemoryInst(Instruction *MemoryInst, Value *Addr, 716 Type *AccessTy) { 717 Value *Repl = Addr; 718 719 // Try to collapse single-value PHI nodes. This is necessary to undo 720 // unprofitable PRE transformations. 721 SmallVector<Value*, 8> worklist; 722 SmallPtrSet<Value*, 16> Visited; 723 worklist.push_back(Addr); 724 725 // Use a worklist to iteratively look through PHI nodes, and ensure that 726 // the addressing mode obtained from the non-PHI roots of the graph 727 // are equivalent. 728 Value *Consensus = 0; 729 unsigned NumUsesConsensus = 0; 730 bool IsNumUsesConsensusValid = false; 731 SmallVector<Instruction*, 16> AddrModeInsts; 732 ExtAddrMode AddrMode; 733 while (!worklist.empty()) { 734 Value *V = worklist.back(); 735 worklist.pop_back(); 736 737 // Break use-def graph loops. 738 if (!Visited.insert(V)) { 739 Consensus = 0; 740 break; 741 } 742 743 // For a PHI node, push all of its incoming values. 744 if (PHINode *P = dyn_cast<PHINode>(V)) { 745 for (unsigned i = 0, e = P->getNumIncomingValues(); i != e; ++i) 746 worklist.push_back(P->getIncomingValue(i)); 747 continue; 748 } 749 750 // For non-PHIs, determine the addressing mode being computed. 751 SmallVector<Instruction*, 16> NewAddrModeInsts; 752 ExtAddrMode NewAddrMode = 753 AddressingModeMatcher::Match(V, AccessTy, MemoryInst, 754 NewAddrModeInsts, *TLI); 755 756 // This check is broken into two cases with very similar code to avoid using 757 // getNumUses() as much as possible. Some values have a lot of uses, so 758 // calling getNumUses() unconditionally caused a significant compile-time 759 // regression. 760 if (!Consensus) { 761 Consensus = V; 762 AddrMode = NewAddrMode; 763 AddrModeInsts = NewAddrModeInsts; 764 continue; 765 } else if (NewAddrMode == AddrMode) { 766 if (!IsNumUsesConsensusValid) { 767 NumUsesConsensus = Consensus->getNumUses(); 768 IsNumUsesConsensusValid = true; 769 } 770 771 // Ensure that the obtained addressing mode is equivalent to that obtained 772 // for all other roots of the PHI traversal. Also, when choosing one 773 // such root as representative, select the one with the most uses in order 774 // to keep the cost modeling heuristics in AddressingModeMatcher 775 // applicable. 776 unsigned NumUses = V->getNumUses(); 777 if (NumUses > NumUsesConsensus) { 778 Consensus = V; 779 NumUsesConsensus = NumUses; 780 AddrModeInsts = NewAddrModeInsts; 781 } 782 continue; 783 } 784 785 Consensus = 0; 786 break; 787 } 788 789 // If the addressing mode couldn't be determined, or if multiple different 790 // ones were determined, bail out now. 791 if (!Consensus) return false; 792 793 // Check to see if any of the instructions supersumed by this addr mode are 794 // non-local to I's BB. 795 bool AnyNonLocal = false; 796 for (unsigned i = 0, e = AddrModeInsts.size(); i != e; ++i) { 797 if (IsNonLocalValue(AddrModeInsts[i], MemoryInst->getParent())) { 798 AnyNonLocal = true; 799 break; 800 } 801 } 802 803 // If all the instructions matched are already in this BB, don't do anything. 804 if (!AnyNonLocal) { 805 DEBUG(dbgs() << "CGP: Found local addrmode: " << AddrMode << "\n"); 806 return false; 807 } 808 809 // Insert this computation right after this user. Since our caller is 810 // scanning from the top of the BB to the bottom, reuse of the expr are 811 // guaranteed to happen later. 812 IRBuilder<> Builder(MemoryInst); 813 814 // Now that we determined the addressing expression we want to use and know 815 // that we have to sink it into this block. Check to see if we have already 816 // done this for some other load/store instr in this block. If so, reuse the 817 // computation. 818 Value *&SunkAddr = SunkAddrs[Addr]; 819 if (SunkAddr) { 820 DEBUG(dbgs() << "CGP: Reusing nonlocal addrmode: " << AddrMode << " for " 821 << *MemoryInst); 822 if (SunkAddr->getType() != Addr->getType()) 823 SunkAddr = Builder.CreateBitCast(SunkAddr, Addr->getType()); 824 } else { 825 DEBUG(dbgs() << "CGP: SINKING nonlocal addrmode: " << AddrMode << " for " 826 << *MemoryInst); 827 Type *IntPtrTy = 828 TLI->getTargetData()->getIntPtrType(AccessTy->getContext()); 829 830 Value *Result = 0; 831 832 // Start with the base register. Do this first so that subsequent address 833 // matching finds it last, which will prevent it from trying to match it 834 // as the scaled value in case it happens to be a mul. That would be 835 // problematic if we've sunk a different mul for the scale, because then 836 // we'd end up sinking both muls. 837 if (AddrMode.BaseReg) { 838 Value *V = AddrMode.BaseReg; 839 if (V->getType()->isPointerTy()) 840 V = Builder.CreatePtrToInt(V, IntPtrTy, "sunkaddr"); 841 if (V->getType() != IntPtrTy) 842 V = Builder.CreateIntCast(V, IntPtrTy, /*isSigned=*/true, "sunkaddr"); 843 Result = V; 844 } 845 846 // Add the scale value. 847 if (AddrMode.Scale) { 848 Value *V = AddrMode.ScaledReg; 849 if (V->getType() == IntPtrTy) { 850 // done. 851 } else if (V->getType()->isPointerTy()) { 852 V = Builder.CreatePtrToInt(V, IntPtrTy, "sunkaddr"); 853 } else if (cast<IntegerType>(IntPtrTy)->getBitWidth() < 854 cast<IntegerType>(V->getType())->getBitWidth()) { 855 V = Builder.CreateTrunc(V, IntPtrTy, "sunkaddr"); 856 } else { 857 V = Builder.CreateSExt(V, IntPtrTy, "sunkaddr"); 858 } 859 if (AddrMode.Scale != 1) 860 V = Builder.CreateMul(V, ConstantInt::get(IntPtrTy, AddrMode.Scale), 861 "sunkaddr"); 862 if (Result) 863 Result = Builder.CreateAdd(Result, V, "sunkaddr"); 864 else 865 Result = V; 866 } 867 868 // Add in the BaseGV if present. 869 if (AddrMode.BaseGV) { 870 Value *V = Builder.CreatePtrToInt(AddrMode.BaseGV, IntPtrTy, "sunkaddr"); 871 if (Result) 872 Result = Builder.CreateAdd(Result, V, "sunkaddr"); 873 else 874 Result = V; 875 } 876 877 // Add in the Base Offset if present. 878 if (AddrMode.BaseOffs) { 879 Value *V = ConstantInt::get(IntPtrTy, AddrMode.BaseOffs); 880 if (Result) 881 Result = Builder.CreateAdd(Result, V, "sunkaddr"); 882 else 883 Result = V; 884 } 885 886 if (Result == 0) 887 SunkAddr = Constant::getNullValue(Addr->getType()); 888 else 889 SunkAddr = Builder.CreateIntToPtr(Result, Addr->getType(), "sunkaddr"); 890 } 891 892 MemoryInst->replaceUsesOfWith(Repl, SunkAddr); 893 894 // If we have no uses, recursively delete the value and all dead instructions 895 // using it. 896 if (Repl->use_empty()) { 897 // This can cause recursive deletion, which can invalidate our iterator. 898 // Use a WeakVH to hold onto it in case this happens. 899 WeakVH IterHandle(CurInstIterator); 900 BasicBlock *BB = CurInstIterator->getParent(); 901 902 RecursivelyDeleteTriviallyDeadInstructions(Repl); 903 904 if (IterHandle != CurInstIterator) { 905 // If the iterator instruction was recursively deleted, start over at the 906 // start of the block. 907 CurInstIterator = BB->begin(); 908 SunkAddrs.clear(); 909 } else { 910 // This address is now available for reassignment, so erase the table 911 // entry; we don't want to match some completely different instruction. 912 SunkAddrs[Addr] = 0; 913 } 914 } 915 ++NumMemoryInsts; 916 return true; 917 } 918 919 /// OptimizeInlineAsmInst - If there are any memory operands, use 920 /// OptimizeMemoryInst to sink their address computing into the block when 921 /// possible / profitable. 922 bool CodeGenPrepare::OptimizeInlineAsmInst(CallInst *CS) { 923 bool MadeChange = false; 924 925 TargetLowering::AsmOperandInfoVector 926 TargetConstraints = TLI->ParseConstraints(CS); 927 unsigned ArgNo = 0; 928 for (unsigned i = 0, e = TargetConstraints.size(); i != e; ++i) { 929 TargetLowering::AsmOperandInfo &OpInfo = TargetConstraints[i]; 930 931 // Compute the constraint code and ConstraintType to use. 932 TLI->ComputeConstraintToUse(OpInfo, SDValue()); 933 934 if (OpInfo.ConstraintType == TargetLowering::C_Memory && 935 OpInfo.isIndirect) { 936 Value *OpVal = CS->getArgOperand(ArgNo++); 937 MadeChange |= OptimizeMemoryInst(CS, OpVal, OpVal->getType()); 938 } else if (OpInfo.Type == InlineAsm::isInput) 939 ArgNo++; 940 } 941 942 return MadeChange; 943 } 944 945 /// MoveExtToFormExtLoad - Move a zext or sext fed by a load into the same 946 /// basic block as the load, unless conditions are unfavorable. This allows 947 /// SelectionDAG to fold the extend into the load. 948 /// 949 bool CodeGenPrepare::MoveExtToFormExtLoad(Instruction *I) { 950 // Look for a load being extended. 951 LoadInst *LI = dyn_cast<LoadInst>(I->getOperand(0)); 952 if (!LI) return false; 953 954 // If they're already in the same block, there's nothing to do. 955 if (LI->getParent() == I->getParent()) 956 return false; 957 958 // If the load has other users and the truncate is not free, this probably 959 // isn't worthwhile. 960 if (!LI->hasOneUse() && 961 TLI && (TLI->isTypeLegal(TLI->getValueType(LI->getType())) || 962 !TLI->isTypeLegal(TLI->getValueType(I->getType()))) && 963 !TLI->isTruncateFree(I->getType(), LI->getType())) 964 return false; 965 966 // Check whether the target supports casts folded into loads. 967 unsigned LType; 968 if (isa<ZExtInst>(I)) 969 LType = ISD::ZEXTLOAD; 970 else { 971 assert(isa<SExtInst>(I) && "Unexpected ext type!"); 972 LType = ISD::SEXTLOAD; 973 } 974 if (TLI && !TLI->isLoadExtLegal(LType, TLI->getValueType(LI->getType()))) 975 return false; 976 977 // Move the extend into the same block as the load, so that SelectionDAG 978 // can fold it. 979 I->removeFromParent(); 980 I->insertAfter(LI); 981 ++NumExtsMoved; 982 return true; 983 } 984 985 bool CodeGenPrepare::OptimizeExtUses(Instruction *I) { 986 BasicBlock *DefBB = I->getParent(); 987 988 // If the result of a {s|z}ext and its source are both live out, rewrite all 989 // other uses of the source with result of extension. 990 Value *Src = I->getOperand(0); 991 if (Src->hasOneUse()) 992 return false; 993 994 // Only do this xform if truncating is free. 995 if (TLI && !TLI->isTruncateFree(I->getType(), Src->getType())) 996 return false; 997 998 // Only safe to perform the optimization if the source is also defined in 999 // this block. 1000 if (!isa<Instruction>(Src) || DefBB != cast<Instruction>(Src)->getParent()) 1001 return false; 1002 1003 bool DefIsLiveOut = false; 1004 for (Value::use_iterator UI = I->use_begin(), E = I->use_end(); 1005 UI != E; ++UI) { 1006 Instruction *User = cast<Instruction>(*UI); 1007 1008 // Figure out which BB this ext is used in. 1009 BasicBlock *UserBB = User->getParent(); 1010 if (UserBB == DefBB) continue; 1011 DefIsLiveOut = true; 1012 break; 1013 } 1014 if (!DefIsLiveOut) 1015 return false; 1016 1017 // Make sure non of the uses are PHI nodes. 1018 for (Value::use_iterator UI = Src->use_begin(), E = Src->use_end(); 1019 UI != E; ++UI) { 1020 Instruction *User = cast<Instruction>(*UI); 1021 BasicBlock *UserBB = User->getParent(); 1022 if (UserBB == DefBB) continue; 1023 // Be conservative. We don't want this xform to end up introducing 1024 // reloads just before load / store instructions. 1025 if (isa<PHINode>(User) || isa<LoadInst>(User) || isa<StoreInst>(User)) 1026 return false; 1027 } 1028 1029 // InsertedTruncs - Only insert one trunc in each block once. 1030 DenseMap<BasicBlock*, Instruction*> InsertedTruncs; 1031 1032 bool MadeChange = false; 1033 for (Value::use_iterator UI = Src->use_begin(), E = Src->use_end(); 1034 UI != E; ++UI) { 1035 Use &TheUse = UI.getUse(); 1036 Instruction *User = cast<Instruction>(*UI); 1037 1038 // Figure out which BB this ext is used in. 1039 BasicBlock *UserBB = User->getParent(); 1040 if (UserBB == DefBB) continue; 1041 1042 // Both src and def are live in this block. Rewrite the use. 1043 Instruction *&InsertedTrunc = InsertedTruncs[UserBB]; 1044 1045 if (!InsertedTrunc) { 1046 BasicBlock::iterator InsertPt = UserBB->getFirstInsertionPt(); 1047 InsertedTrunc = new TruncInst(I, Src->getType(), "", InsertPt); 1048 } 1049 1050 // Replace a use of the {s|z}ext source with a use of the result. 1051 TheUse = InsertedTrunc; 1052 ++NumExtUses; 1053 MadeChange = true; 1054 } 1055 1056 return MadeChange; 1057 } 1058 1059 bool CodeGenPrepare::OptimizeInst(Instruction *I) { 1060 if (PHINode *P = dyn_cast<PHINode>(I)) { 1061 // It is possible for very late stage optimizations (such as SimplifyCFG) 1062 // to introduce PHI nodes too late to be cleaned up. If we detect such a 1063 // trivial PHI, go ahead and zap it here. 1064 if (Value *V = SimplifyInstruction(P)) { 1065 P->replaceAllUsesWith(V); 1066 P->eraseFromParent(); 1067 ++NumPHIsElim; 1068 return true; 1069 } 1070 return false; 1071 } 1072 1073 if (CastInst *CI = dyn_cast<CastInst>(I)) { 1074 // If the source of the cast is a constant, then this should have 1075 // already been constant folded. The only reason NOT to constant fold 1076 // it is if something (e.g. LSR) was careful to place the constant 1077 // evaluation in a block other than then one that uses it (e.g. to hoist 1078 // the address of globals out of a loop). If this is the case, we don't 1079 // want to forward-subst the cast. 1080 if (isa<Constant>(CI->getOperand(0))) 1081 return false; 1082 1083 if (TLI && OptimizeNoopCopyExpression(CI, *TLI)) 1084 return true; 1085 1086 if (isa<ZExtInst>(I) || isa<SExtInst>(I)) { 1087 bool MadeChange = MoveExtToFormExtLoad(I); 1088 return MadeChange | OptimizeExtUses(I); 1089 } 1090 return false; 1091 } 1092 1093 if (CmpInst *CI = dyn_cast<CmpInst>(I)) 1094 return OptimizeCmpExpression(CI); 1095 1096 if (LoadInst *LI = dyn_cast<LoadInst>(I)) { 1097 if (TLI) 1098 return OptimizeMemoryInst(I, I->getOperand(0), LI->getType()); 1099 return false; 1100 } 1101 1102 if (StoreInst *SI = dyn_cast<StoreInst>(I)) { 1103 if (TLI) 1104 return OptimizeMemoryInst(I, SI->getOperand(1), 1105 SI->getOperand(0)->getType()); 1106 return false; 1107 } 1108 1109 if (GetElementPtrInst *GEPI = dyn_cast<GetElementPtrInst>(I)) { 1110 if (GEPI->hasAllZeroIndices()) { 1111 /// The GEP operand must be a pointer, so must its result -> BitCast 1112 Instruction *NC = new BitCastInst(GEPI->getOperand(0), GEPI->getType(), 1113 GEPI->getName(), GEPI); 1114 GEPI->replaceAllUsesWith(NC); 1115 GEPI->eraseFromParent(); 1116 ++NumGEPsElim; 1117 OptimizeInst(NC); 1118 return true; 1119 } 1120 return false; 1121 } 1122 1123 if (CallInst *CI = dyn_cast<CallInst>(I)) 1124 return OptimizeCallInst(CI); 1125 1126 if (ReturnInst *RI = dyn_cast<ReturnInst>(I)) 1127 return DupRetToEnableTailCallOpts(RI); 1128 1129 return false; 1130 } 1131 1132 // In this pass we look for GEP and cast instructions that are used 1133 // across basic blocks and rewrite them to improve basic-block-at-a-time 1134 // selection. 1135 bool CodeGenPrepare::OptimizeBlock(BasicBlock &BB) { 1136 SunkAddrs.clear(); 1137 bool MadeChange = false; 1138 1139 CurInstIterator = BB.begin(); 1140 for (BasicBlock::iterator E = BB.end(); CurInstIterator != E; ) 1141 MadeChange |= OptimizeInst(CurInstIterator++); 1142 1143 return MadeChange; 1144 } 1145 1146 // llvm.dbg.value is far away from the value then iSel may not be able 1147 // handle it properly. iSel will drop llvm.dbg.value if it can not 1148 // find a node corresponding to the value. 1149 bool CodeGenPrepare::PlaceDbgValues(Function &F) { 1150 bool MadeChange = false; 1151 for (Function::iterator I = F.begin(), E = F.end(); I != E; ++I) { 1152 Instruction *PrevNonDbgInst = NULL; 1153 for (BasicBlock::iterator BI = I->begin(), BE = I->end(); BI != BE;) { 1154 Instruction *Insn = BI; ++BI; 1155 DbgValueInst *DVI = dyn_cast<DbgValueInst>(Insn); 1156 if (!DVI) { 1157 PrevNonDbgInst = Insn; 1158 continue; 1159 } 1160 1161 Instruction *VI = dyn_cast_or_null<Instruction>(DVI->getValue()); 1162 if (VI && VI != PrevNonDbgInst && !VI->isTerminator()) { 1163 DEBUG(dbgs() << "Moving Debug Value before :\n" << *DVI << ' ' << *VI); 1164 DVI->removeFromParent(); 1165 if (isa<PHINode>(VI)) 1166 DVI->insertBefore(VI->getParent()->getFirstInsertionPt()); 1167 else 1168 DVI->insertAfter(VI); 1169 MadeChange = true; 1170 ++NumDbgValueMoved; 1171 } 1172 } 1173 } 1174 return MadeChange; 1175 } 1176