1 //===- SCCP.cpp - Sparse Conditional Constant Propagation -----------------===// 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 file implements sparse conditional constant propagation and merging: 11 // 12 // Specifically, this: 13 // * Assumes values are constant unless proven otherwise 14 // * Assumes BasicBlocks are dead unless proven otherwise 15 // * Proves values to be constant, and replaces them with constants 16 // * Proves conditional branches to be unconditional 17 // 18 //===----------------------------------------------------------------------===// 19 20 #include "llvm/Transforms/Scalar.h" 21 #include "llvm/ADT/DenseMap.h" 22 #include "llvm/ADT/DenseSet.h" 23 #include "llvm/ADT/PointerIntPair.h" 24 #include "llvm/ADT/SmallPtrSet.h" 25 #include "llvm/ADT/SmallVector.h" 26 #include "llvm/ADT/Statistic.h" 27 #include "llvm/Analysis/ConstantFolding.h" 28 #include "llvm/IR/CallSite.h" 29 #include "llvm/IR/Constants.h" 30 #include "llvm/IR/DataLayout.h" 31 #include "llvm/IR/DerivedTypes.h" 32 #include "llvm/IR/InstVisitor.h" 33 #include "llvm/IR/Instructions.h" 34 #include "llvm/Pass.h" 35 #include "llvm/Support/Debug.h" 36 #include "llvm/Support/ErrorHandling.h" 37 #include "llvm/Support/raw_ostream.h" 38 #include "llvm/Target/TargetLibraryInfo.h" 39 #include "llvm/Transforms/IPO.h" 40 #include "llvm/Transforms/Utils/Local.h" 41 #include <algorithm> 42 using namespace llvm; 43 44 #define DEBUG_TYPE "sccp" 45 46 STATISTIC(NumInstRemoved, "Number of instructions removed"); 47 STATISTIC(NumDeadBlocks , "Number of basic blocks unreachable"); 48 49 STATISTIC(IPNumInstRemoved, "Number of instructions removed by IPSCCP"); 50 STATISTIC(IPNumArgsElimed ,"Number of arguments constant propagated by IPSCCP"); 51 STATISTIC(IPNumGlobalConst, "Number of globals found to be constant by IPSCCP"); 52 53 namespace { 54 /// LatticeVal class - This class represents the different lattice values that 55 /// an LLVM value may occupy. It is a simple class with value semantics. 56 /// 57 class LatticeVal { 58 enum LatticeValueTy { 59 /// undefined - This LLVM Value has no known value yet. 60 undefined, 61 62 /// constant - This LLVM Value has a specific constant value. 63 constant, 64 65 /// forcedconstant - This LLVM Value was thought to be undef until 66 /// ResolvedUndefsIn. This is treated just like 'constant', but if merged 67 /// with another (different) constant, it goes to overdefined, instead of 68 /// asserting. 69 forcedconstant, 70 71 /// overdefined - This instruction is not known to be constant, and we know 72 /// it has a value. 73 overdefined 74 }; 75 76 /// Val: This stores the current lattice value along with the Constant* for 77 /// the constant if this is a 'constant' or 'forcedconstant' value. 78 PointerIntPair<Constant *, 2, LatticeValueTy> Val; 79 80 LatticeValueTy getLatticeValue() const { 81 return Val.getInt(); 82 } 83 84 public: 85 LatticeVal() : Val(nullptr, undefined) {} 86 87 bool isUndefined() const { return getLatticeValue() == undefined; } 88 bool isConstant() const { 89 return getLatticeValue() == constant || getLatticeValue() == forcedconstant; 90 } 91 bool isOverdefined() const { return getLatticeValue() == overdefined; } 92 93 Constant *getConstant() const { 94 assert(isConstant() && "Cannot get the constant of a non-constant!"); 95 return Val.getPointer(); 96 } 97 98 /// markOverdefined - Return true if this is a change in status. 99 bool markOverdefined() { 100 if (isOverdefined()) 101 return false; 102 103 Val.setInt(overdefined); 104 return true; 105 } 106 107 /// markConstant - Return true if this is a change in status. 108 bool markConstant(Constant *V) { 109 if (getLatticeValue() == constant) { // Constant but not forcedconstant. 110 assert(getConstant() == V && "Marking constant with different value"); 111 return false; 112 } 113 114 if (isUndefined()) { 115 Val.setInt(constant); 116 assert(V && "Marking constant with NULL"); 117 Val.setPointer(V); 118 } else { 119 assert(getLatticeValue() == forcedconstant && 120 "Cannot move from overdefined to constant!"); 121 // Stay at forcedconstant if the constant is the same. 122 if (V == getConstant()) return false; 123 124 // Otherwise, we go to overdefined. Assumptions made based on the 125 // forced value are possibly wrong. Assuming this is another constant 126 // could expose a contradiction. 127 Val.setInt(overdefined); 128 } 129 return true; 130 } 131 132 /// getConstantInt - If this is a constant with a ConstantInt value, return it 133 /// otherwise return null. 134 ConstantInt *getConstantInt() const { 135 if (isConstant()) 136 return dyn_cast<ConstantInt>(getConstant()); 137 return nullptr; 138 } 139 140 void markForcedConstant(Constant *V) { 141 assert(isUndefined() && "Can't force a defined value!"); 142 Val.setInt(forcedconstant); 143 Val.setPointer(V); 144 } 145 }; 146 } // end anonymous namespace. 147 148 149 namespace { 150 151 //===----------------------------------------------------------------------===// 152 // 153 /// SCCPSolver - This class is a general purpose solver for Sparse Conditional 154 /// Constant Propagation. 155 /// 156 class SCCPSolver : public InstVisitor<SCCPSolver> { 157 const DataLayout *DL; 158 const TargetLibraryInfo *TLI; 159 SmallPtrSet<BasicBlock*, 8> BBExecutable; // The BBs that are executable. 160 DenseMap<Value*, LatticeVal> ValueState; // The state each value is in. 161 162 /// StructValueState - This maintains ValueState for values that have 163 /// StructType, for example for formal arguments, calls, insertelement, etc. 164 /// 165 DenseMap<std::pair<Value*, unsigned>, LatticeVal> StructValueState; 166 167 /// GlobalValue - If we are tracking any values for the contents of a global 168 /// variable, we keep a mapping from the constant accessor to the element of 169 /// the global, to the currently known value. If the value becomes 170 /// overdefined, it's entry is simply removed from this map. 171 DenseMap<GlobalVariable*, LatticeVal> TrackedGlobals; 172 173 /// TrackedRetVals - If we are tracking arguments into and the return 174 /// value out of a function, it will have an entry in this map, indicating 175 /// what the known return value for the function is. 176 DenseMap<Function*, LatticeVal> TrackedRetVals; 177 178 /// TrackedMultipleRetVals - Same as TrackedRetVals, but used for functions 179 /// that return multiple values. 180 DenseMap<std::pair<Function*, unsigned>, LatticeVal> TrackedMultipleRetVals; 181 182 /// MRVFunctionsTracked - Each function in TrackedMultipleRetVals is 183 /// represented here for efficient lookup. 184 SmallPtrSet<Function*, 16> MRVFunctionsTracked; 185 186 /// TrackingIncomingArguments - This is the set of functions for whose 187 /// arguments we make optimistic assumptions about and try to prove as 188 /// constants. 189 SmallPtrSet<Function*, 16> TrackingIncomingArguments; 190 191 /// The reason for two worklists is that overdefined is the lowest state 192 /// on the lattice, and moving things to overdefined as fast as possible 193 /// makes SCCP converge much faster. 194 /// 195 /// By having a separate worklist, we accomplish this because everything 196 /// possibly overdefined will become overdefined at the soonest possible 197 /// point. 198 SmallVector<Value*, 64> OverdefinedInstWorkList; 199 SmallVector<Value*, 64> InstWorkList; 200 201 202 SmallVector<BasicBlock*, 64> BBWorkList; // The BasicBlock work list 203 204 /// KnownFeasibleEdges - Entries in this set are edges which have already had 205 /// PHI nodes retriggered. 206 typedef std::pair<BasicBlock*, BasicBlock*> Edge; 207 DenseSet<Edge> KnownFeasibleEdges; 208 public: 209 SCCPSolver(const DataLayout *DL, const TargetLibraryInfo *tli) 210 : DL(DL), TLI(tli) {} 211 212 /// MarkBlockExecutable - This method can be used by clients to mark all of 213 /// the blocks that are known to be intrinsically live in the processed unit. 214 /// 215 /// This returns true if the block was not considered live before. 216 bool MarkBlockExecutable(BasicBlock *BB) { 217 if (!BBExecutable.insert(BB)) return false; 218 DEBUG(dbgs() << "Marking Block Executable: " << BB->getName() << '\n'); 219 BBWorkList.push_back(BB); // Add the block to the work list! 220 return true; 221 } 222 223 /// TrackValueOfGlobalVariable - Clients can use this method to 224 /// inform the SCCPSolver that it should track loads and stores to the 225 /// specified global variable if it can. This is only legal to call if 226 /// performing Interprocedural SCCP. 227 void TrackValueOfGlobalVariable(GlobalVariable *GV) { 228 // We only track the contents of scalar globals. 229 if (GV->getType()->getElementType()->isSingleValueType()) { 230 LatticeVal &IV = TrackedGlobals[GV]; 231 if (!isa<UndefValue>(GV->getInitializer())) 232 IV.markConstant(GV->getInitializer()); 233 } 234 } 235 236 /// AddTrackedFunction - If the SCCP solver is supposed to track calls into 237 /// and out of the specified function (which cannot have its address taken), 238 /// this method must be called. 239 void AddTrackedFunction(Function *F) { 240 // Add an entry, F -> undef. 241 if (StructType *STy = dyn_cast<StructType>(F->getReturnType())) { 242 MRVFunctionsTracked.insert(F); 243 for (unsigned i = 0, e = STy->getNumElements(); i != e; ++i) 244 TrackedMultipleRetVals.insert(std::make_pair(std::make_pair(F, i), 245 LatticeVal())); 246 } else 247 TrackedRetVals.insert(std::make_pair(F, LatticeVal())); 248 } 249 250 void AddArgumentTrackedFunction(Function *F) { 251 TrackingIncomingArguments.insert(F); 252 } 253 254 /// Solve - Solve for constants and executable blocks. 255 /// 256 void Solve(); 257 258 /// ResolvedUndefsIn - While solving the dataflow for a function, we assume 259 /// that branches on undef values cannot reach any of their successors. 260 /// However, this is not a safe assumption. After we solve dataflow, this 261 /// method should be use to handle this. If this returns true, the solver 262 /// should be rerun. 263 bool ResolvedUndefsIn(Function &F); 264 265 bool isBlockExecutable(BasicBlock *BB) const { 266 return BBExecutable.count(BB); 267 } 268 269 LatticeVal getLatticeValueFor(Value *V) const { 270 DenseMap<Value*, LatticeVal>::const_iterator I = ValueState.find(V); 271 assert(I != ValueState.end() && "V is not in valuemap!"); 272 return I->second; 273 } 274 275 /// getTrackedRetVals - Get the inferred return value map. 276 /// 277 const DenseMap<Function*, LatticeVal> &getTrackedRetVals() { 278 return TrackedRetVals; 279 } 280 281 /// getTrackedGlobals - Get and return the set of inferred initializers for 282 /// global variables. 283 const DenseMap<GlobalVariable*, LatticeVal> &getTrackedGlobals() { 284 return TrackedGlobals; 285 } 286 287 void markOverdefined(Value *V) { 288 assert(!V->getType()->isStructTy() && "Should use other method"); 289 markOverdefined(ValueState[V], V); 290 } 291 292 /// markAnythingOverdefined - Mark the specified value overdefined. This 293 /// works with both scalars and structs. 294 void markAnythingOverdefined(Value *V) { 295 if (StructType *STy = dyn_cast<StructType>(V->getType())) 296 for (unsigned i = 0, e = STy->getNumElements(); i != e; ++i) 297 markOverdefined(getStructValueState(V, i), V); 298 else 299 markOverdefined(V); 300 } 301 302 private: 303 // markConstant - Make a value be marked as "constant". If the value 304 // is not already a constant, add it to the instruction work list so that 305 // the users of the instruction are updated later. 306 // 307 void markConstant(LatticeVal &IV, Value *V, Constant *C) { 308 if (!IV.markConstant(C)) return; 309 DEBUG(dbgs() << "markConstant: " << *C << ": " << *V << '\n'); 310 if (IV.isOverdefined()) 311 OverdefinedInstWorkList.push_back(V); 312 else 313 InstWorkList.push_back(V); 314 } 315 316 void markConstant(Value *V, Constant *C) { 317 assert(!V->getType()->isStructTy() && "Should use other method"); 318 markConstant(ValueState[V], V, C); 319 } 320 321 void markForcedConstant(Value *V, Constant *C) { 322 assert(!V->getType()->isStructTy() && "Should use other method"); 323 LatticeVal &IV = ValueState[V]; 324 IV.markForcedConstant(C); 325 DEBUG(dbgs() << "markForcedConstant: " << *C << ": " << *V << '\n'); 326 if (IV.isOverdefined()) 327 OverdefinedInstWorkList.push_back(V); 328 else 329 InstWorkList.push_back(V); 330 } 331 332 333 // markOverdefined - Make a value be marked as "overdefined". If the 334 // value is not already overdefined, add it to the overdefined instruction 335 // work list so that the users of the instruction are updated later. 336 void markOverdefined(LatticeVal &IV, Value *V) { 337 if (!IV.markOverdefined()) return; 338 339 DEBUG(dbgs() << "markOverdefined: "; 340 if (Function *F = dyn_cast<Function>(V)) 341 dbgs() << "Function '" << F->getName() << "'\n"; 342 else 343 dbgs() << *V << '\n'); 344 // Only instructions go on the work list 345 OverdefinedInstWorkList.push_back(V); 346 } 347 348 void mergeInValue(LatticeVal &IV, Value *V, LatticeVal MergeWithV) { 349 if (IV.isOverdefined() || MergeWithV.isUndefined()) 350 return; // Noop. 351 if (MergeWithV.isOverdefined()) 352 markOverdefined(IV, V); 353 else if (IV.isUndefined()) 354 markConstant(IV, V, MergeWithV.getConstant()); 355 else if (IV.getConstant() != MergeWithV.getConstant()) 356 markOverdefined(IV, V); 357 } 358 359 void mergeInValue(Value *V, LatticeVal MergeWithV) { 360 assert(!V->getType()->isStructTy() && "Should use other method"); 361 mergeInValue(ValueState[V], V, MergeWithV); 362 } 363 364 365 /// getValueState - Return the LatticeVal object that corresponds to the 366 /// value. This function handles the case when the value hasn't been seen yet 367 /// by properly seeding constants etc. 368 LatticeVal &getValueState(Value *V) { 369 assert(!V->getType()->isStructTy() && "Should use getStructValueState"); 370 371 std::pair<DenseMap<Value*, LatticeVal>::iterator, bool> I = 372 ValueState.insert(std::make_pair(V, LatticeVal())); 373 LatticeVal &LV = I.first->second; 374 375 if (!I.second) 376 return LV; // Common case, already in the map. 377 378 if (Constant *C = dyn_cast<Constant>(V)) { 379 // Undef values remain undefined. 380 if (!isa<UndefValue>(V)) 381 LV.markConstant(C); // Constants are constant 382 } 383 384 // All others are underdefined by default. 385 return LV; 386 } 387 388 /// getStructValueState - Return the LatticeVal object that corresponds to the 389 /// value/field pair. This function handles the case when the value hasn't 390 /// been seen yet by properly seeding constants etc. 391 LatticeVal &getStructValueState(Value *V, unsigned i) { 392 assert(V->getType()->isStructTy() && "Should use getValueState"); 393 assert(i < cast<StructType>(V->getType())->getNumElements() && 394 "Invalid element #"); 395 396 std::pair<DenseMap<std::pair<Value*, unsigned>, LatticeVal>::iterator, 397 bool> I = StructValueState.insert( 398 std::make_pair(std::make_pair(V, i), LatticeVal())); 399 LatticeVal &LV = I.first->second; 400 401 if (!I.second) 402 return LV; // Common case, already in the map. 403 404 if (Constant *C = dyn_cast<Constant>(V)) { 405 Constant *Elt = C->getAggregateElement(i); 406 407 if (!Elt) 408 LV.markOverdefined(); // Unknown sort of constant. 409 else if (isa<UndefValue>(Elt)) 410 ; // Undef values remain undefined. 411 else 412 LV.markConstant(Elt); // Constants are constant. 413 } 414 415 // All others are underdefined by default. 416 return LV; 417 } 418 419 420 /// markEdgeExecutable - Mark a basic block as executable, adding it to the BB 421 /// work list if it is not already executable. 422 void markEdgeExecutable(BasicBlock *Source, BasicBlock *Dest) { 423 if (!KnownFeasibleEdges.insert(Edge(Source, Dest)).second) 424 return; // This edge is already known to be executable! 425 426 if (!MarkBlockExecutable(Dest)) { 427 // If the destination is already executable, we just made an *edge* 428 // feasible that wasn't before. Revisit the PHI nodes in the block 429 // because they have potentially new operands. 430 DEBUG(dbgs() << "Marking Edge Executable: " << Source->getName() 431 << " -> " << Dest->getName() << '\n'); 432 433 PHINode *PN; 434 for (BasicBlock::iterator I = Dest->begin(); 435 (PN = dyn_cast<PHINode>(I)); ++I) 436 visitPHINode(*PN); 437 } 438 } 439 440 // getFeasibleSuccessors - Return a vector of booleans to indicate which 441 // successors are reachable from a given terminator instruction. 442 // 443 void getFeasibleSuccessors(TerminatorInst &TI, SmallVectorImpl<bool> &Succs); 444 445 // isEdgeFeasible - Return true if the control flow edge from the 'From' basic 446 // block to the 'To' basic block is currently feasible. 447 // 448 bool isEdgeFeasible(BasicBlock *From, BasicBlock *To); 449 450 // OperandChangedState - This method is invoked on all of the users of an 451 // instruction that was just changed state somehow. Based on this 452 // information, we need to update the specified user of this instruction. 453 // 454 void OperandChangedState(Instruction *I) { 455 if (BBExecutable.count(I->getParent())) // Inst is executable? 456 visit(*I); 457 } 458 459 private: 460 friend class InstVisitor<SCCPSolver>; 461 462 // visit implementations - Something changed in this instruction. Either an 463 // operand made a transition, or the instruction is newly executable. Change 464 // the value type of I to reflect these changes if appropriate. 465 void visitPHINode(PHINode &I); 466 467 // Terminators 468 void visitReturnInst(ReturnInst &I); 469 void visitTerminatorInst(TerminatorInst &TI); 470 471 void visitCastInst(CastInst &I); 472 void visitSelectInst(SelectInst &I); 473 void visitBinaryOperator(Instruction &I); 474 void visitCmpInst(CmpInst &I); 475 void visitExtractElementInst(ExtractElementInst &I); 476 void visitInsertElementInst(InsertElementInst &I); 477 void visitShuffleVectorInst(ShuffleVectorInst &I); 478 void visitExtractValueInst(ExtractValueInst &EVI); 479 void visitInsertValueInst(InsertValueInst &IVI); 480 void visitLandingPadInst(LandingPadInst &I) { markAnythingOverdefined(&I); } 481 482 // Instructions that cannot be folded away. 483 void visitStoreInst (StoreInst &I); 484 void visitLoadInst (LoadInst &I); 485 void visitGetElementPtrInst(GetElementPtrInst &I); 486 void visitCallInst (CallInst &I) { 487 visitCallSite(&I); 488 } 489 void visitInvokeInst (InvokeInst &II) { 490 visitCallSite(&II); 491 visitTerminatorInst(II); 492 } 493 void visitCallSite (CallSite CS); 494 void visitResumeInst (TerminatorInst &I) { /*returns void*/ } 495 void visitUnreachableInst(TerminatorInst &I) { /*returns void*/ } 496 void visitFenceInst (FenceInst &I) { /*returns void*/ } 497 void visitAtomicCmpXchgInst(AtomicCmpXchgInst &I) { 498 markAnythingOverdefined(&I); 499 } 500 void visitAtomicRMWInst (AtomicRMWInst &I) { markOverdefined(&I); } 501 void visitAllocaInst (Instruction &I) { markOverdefined(&I); } 502 void visitVAArgInst (Instruction &I) { markAnythingOverdefined(&I); } 503 504 void visitInstruction(Instruction &I) { 505 // If a new instruction is added to LLVM that we don't handle. 506 dbgs() << "SCCP: Don't know how to handle: " << I << '\n'; 507 markAnythingOverdefined(&I); // Just in case 508 } 509 }; 510 511 } // end anonymous namespace 512 513 514 // getFeasibleSuccessors - Return a vector of booleans to indicate which 515 // successors are reachable from a given terminator instruction. 516 // 517 void SCCPSolver::getFeasibleSuccessors(TerminatorInst &TI, 518 SmallVectorImpl<bool> &Succs) { 519 Succs.resize(TI.getNumSuccessors()); 520 if (BranchInst *BI = dyn_cast<BranchInst>(&TI)) { 521 if (BI->isUnconditional()) { 522 Succs[0] = true; 523 return; 524 } 525 526 LatticeVal BCValue = getValueState(BI->getCondition()); 527 ConstantInt *CI = BCValue.getConstantInt(); 528 if (!CI) { 529 // Overdefined condition variables, and branches on unfoldable constant 530 // conditions, mean the branch could go either way. 531 if (!BCValue.isUndefined()) 532 Succs[0] = Succs[1] = true; 533 return; 534 } 535 536 // Constant condition variables mean the branch can only go a single way. 537 Succs[CI->isZero()] = true; 538 return; 539 } 540 541 if (isa<InvokeInst>(TI)) { 542 // Invoke instructions successors are always executable. 543 Succs[0] = Succs[1] = true; 544 return; 545 } 546 547 if (SwitchInst *SI = dyn_cast<SwitchInst>(&TI)) { 548 if (!SI->getNumCases()) { 549 Succs[0] = true; 550 return; 551 } 552 LatticeVal SCValue = getValueState(SI->getCondition()); 553 ConstantInt *CI = SCValue.getConstantInt(); 554 555 if (!CI) { // Overdefined or undefined condition? 556 // All destinations are executable! 557 if (!SCValue.isUndefined()) 558 Succs.assign(TI.getNumSuccessors(), true); 559 return; 560 } 561 562 Succs[SI->findCaseValue(CI).getSuccessorIndex()] = true; 563 return; 564 } 565 566 // TODO: This could be improved if the operand is a [cast of a] BlockAddress. 567 if (isa<IndirectBrInst>(&TI)) { 568 // Just mark all destinations executable! 569 Succs.assign(TI.getNumSuccessors(), true); 570 return; 571 } 572 573 #ifndef NDEBUG 574 dbgs() << "Unknown terminator instruction: " << TI << '\n'; 575 #endif 576 llvm_unreachable("SCCP: Don't know how to handle this terminator!"); 577 } 578 579 580 // isEdgeFeasible - Return true if the control flow edge from the 'From' basic 581 // block to the 'To' basic block is currently feasible. 582 // 583 bool SCCPSolver::isEdgeFeasible(BasicBlock *From, BasicBlock *To) { 584 assert(BBExecutable.count(To) && "Dest should always be alive!"); 585 586 // Make sure the source basic block is executable!! 587 if (!BBExecutable.count(From)) return false; 588 589 // Check to make sure this edge itself is actually feasible now. 590 TerminatorInst *TI = From->getTerminator(); 591 if (BranchInst *BI = dyn_cast<BranchInst>(TI)) { 592 if (BI->isUnconditional()) 593 return true; 594 595 LatticeVal BCValue = getValueState(BI->getCondition()); 596 597 // Overdefined condition variables mean the branch could go either way, 598 // undef conditions mean that neither edge is feasible yet. 599 ConstantInt *CI = BCValue.getConstantInt(); 600 if (!CI) 601 return !BCValue.isUndefined(); 602 603 // Constant condition variables mean the branch can only go a single way. 604 return BI->getSuccessor(CI->isZero()) == To; 605 } 606 607 // Invoke instructions successors are always executable. 608 if (isa<InvokeInst>(TI)) 609 return true; 610 611 if (SwitchInst *SI = dyn_cast<SwitchInst>(TI)) { 612 if (SI->getNumCases() < 1) 613 return true; 614 615 LatticeVal SCValue = getValueState(SI->getCondition()); 616 ConstantInt *CI = SCValue.getConstantInt(); 617 618 if (!CI) 619 return !SCValue.isUndefined(); 620 621 return SI->findCaseValue(CI).getCaseSuccessor() == To; 622 } 623 624 // Just mark all destinations executable! 625 // TODO: This could be improved if the operand is a [cast of a] BlockAddress. 626 if (isa<IndirectBrInst>(TI)) 627 return true; 628 629 #ifndef NDEBUG 630 dbgs() << "Unknown terminator instruction: " << *TI << '\n'; 631 #endif 632 llvm_unreachable(nullptr); 633 } 634 635 // visit Implementations - Something changed in this instruction, either an 636 // operand made a transition, or the instruction is newly executable. Change 637 // the value type of I to reflect these changes if appropriate. This method 638 // makes sure to do the following actions: 639 // 640 // 1. If a phi node merges two constants in, and has conflicting value coming 641 // from different branches, or if the PHI node merges in an overdefined 642 // value, then the PHI node becomes overdefined. 643 // 2. If a phi node merges only constants in, and they all agree on value, the 644 // PHI node becomes a constant value equal to that. 645 // 3. If V <- x (op) y && isConstant(x) && isConstant(y) V = Constant 646 // 4. If V <- x (op) y && (isOverdefined(x) || isOverdefined(y)) V = Overdefined 647 // 5. If V <- MEM or V <- CALL or V <- (unknown) then V = Overdefined 648 // 6. If a conditional branch has a value that is constant, make the selected 649 // destination executable 650 // 7. If a conditional branch has a value that is overdefined, make all 651 // successors executable. 652 // 653 void SCCPSolver::visitPHINode(PHINode &PN) { 654 // If this PN returns a struct, just mark the result overdefined. 655 // TODO: We could do a lot better than this if code actually uses this. 656 if (PN.getType()->isStructTy()) 657 return markAnythingOverdefined(&PN); 658 659 if (getValueState(&PN).isOverdefined()) 660 return; // Quick exit 661 662 // Super-extra-high-degree PHI nodes are unlikely to ever be marked constant, 663 // and slow us down a lot. Just mark them overdefined. 664 if (PN.getNumIncomingValues() > 64) 665 return markOverdefined(&PN); 666 667 // Look at all of the executable operands of the PHI node. If any of them 668 // are overdefined, the PHI becomes overdefined as well. If they are all 669 // constant, and they agree with each other, the PHI becomes the identical 670 // constant. If they are constant and don't agree, the PHI is overdefined. 671 // If there are no executable operands, the PHI remains undefined. 672 // 673 Constant *OperandVal = nullptr; 674 for (unsigned i = 0, e = PN.getNumIncomingValues(); i != e; ++i) { 675 LatticeVal IV = getValueState(PN.getIncomingValue(i)); 676 if (IV.isUndefined()) continue; // Doesn't influence PHI node. 677 678 if (!isEdgeFeasible(PN.getIncomingBlock(i), PN.getParent())) 679 continue; 680 681 if (IV.isOverdefined()) // PHI node becomes overdefined! 682 return markOverdefined(&PN); 683 684 if (!OperandVal) { // Grab the first value. 685 OperandVal = IV.getConstant(); 686 continue; 687 } 688 689 // There is already a reachable operand. If we conflict with it, 690 // then the PHI node becomes overdefined. If we agree with it, we 691 // can continue on. 692 693 // Check to see if there are two different constants merging, if so, the PHI 694 // node is overdefined. 695 if (IV.getConstant() != OperandVal) 696 return markOverdefined(&PN); 697 } 698 699 // If we exited the loop, this means that the PHI node only has constant 700 // arguments that agree with each other(and OperandVal is the constant) or 701 // OperandVal is null because there are no defined incoming arguments. If 702 // this is the case, the PHI remains undefined. 703 // 704 if (OperandVal) 705 markConstant(&PN, OperandVal); // Acquire operand value 706 } 707 708 void SCCPSolver::visitReturnInst(ReturnInst &I) { 709 if (I.getNumOperands() == 0) return; // ret void 710 711 Function *F = I.getParent()->getParent(); 712 Value *ResultOp = I.getOperand(0); 713 714 // If we are tracking the return value of this function, merge it in. 715 if (!TrackedRetVals.empty() && !ResultOp->getType()->isStructTy()) { 716 DenseMap<Function*, LatticeVal>::iterator TFRVI = 717 TrackedRetVals.find(F); 718 if (TFRVI != TrackedRetVals.end()) { 719 mergeInValue(TFRVI->second, F, getValueState(ResultOp)); 720 return; 721 } 722 } 723 724 // Handle functions that return multiple values. 725 if (!TrackedMultipleRetVals.empty()) { 726 if (StructType *STy = dyn_cast<StructType>(ResultOp->getType())) 727 if (MRVFunctionsTracked.count(F)) 728 for (unsigned i = 0, e = STy->getNumElements(); i != e; ++i) 729 mergeInValue(TrackedMultipleRetVals[std::make_pair(F, i)], F, 730 getStructValueState(ResultOp, i)); 731 732 } 733 } 734 735 void SCCPSolver::visitTerminatorInst(TerminatorInst &TI) { 736 SmallVector<bool, 16> SuccFeasible; 737 getFeasibleSuccessors(TI, SuccFeasible); 738 739 BasicBlock *BB = TI.getParent(); 740 741 // Mark all feasible successors executable. 742 for (unsigned i = 0, e = SuccFeasible.size(); i != e; ++i) 743 if (SuccFeasible[i]) 744 markEdgeExecutable(BB, TI.getSuccessor(i)); 745 } 746 747 void SCCPSolver::visitCastInst(CastInst &I) { 748 LatticeVal OpSt = getValueState(I.getOperand(0)); 749 if (OpSt.isOverdefined()) // Inherit overdefinedness of operand 750 markOverdefined(&I); 751 else if (OpSt.isConstant()) // Propagate constant value 752 markConstant(&I, ConstantExpr::getCast(I.getOpcode(), 753 OpSt.getConstant(), I.getType())); 754 } 755 756 757 void SCCPSolver::visitExtractValueInst(ExtractValueInst &EVI) { 758 // If this returns a struct, mark all elements over defined, we don't track 759 // structs in structs. 760 if (EVI.getType()->isStructTy()) 761 return markAnythingOverdefined(&EVI); 762 763 // If this is extracting from more than one level of struct, we don't know. 764 if (EVI.getNumIndices() != 1) 765 return markOverdefined(&EVI); 766 767 Value *AggVal = EVI.getAggregateOperand(); 768 if (AggVal->getType()->isStructTy()) { 769 unsigned i = *EVI.idx_begin(); 770 LatticeVal EltVal = getStructValueState(AggVal, i); 771 mergeInValue(getValueState(&EVI), &EVI, EltVal); 772 } else { 773 // Otherwise, must be extracting from an array. 774 return markOverdefined(&EVI); 775 } 776 } 777 778 void SCCPSolver::visitInsertValueInst(InsertValueInst &IVI) { 779 StructType *STy = dyn_cast<StructType>(IVI.getType()); 780 if (!STy) 781 return markOverdefined(&IVI); 782 783 // If this has more than one index, we can't handle it, drive all results to 784 // undef. 785 if (IVI.getNumIndices() != 1) 786 return markAnythingOverdefined(&IVI); 787 788 Value *Aggr = IVI.getAggregateOperand(); 789 unsigned Idx = *IVI.idx_begin(); 790 791 // Compute the result based on what we're inserting. 792 for (unsigned i = 0, e = STy->getNumElements(); i != e; ++i) { 793 // This passes through all values that aren't the inserted element. 794 if (i != Idx) { 795 LatticeVal EltVal = getStructValueState(Aggr, i); 796 mergeInValue(getStructValueState(&IVI, i), &IVI, EltVal); 797 continue; 798 } 799 800 Value *Val = IVI.getInsertedValueOperand(); 801 if (Val->getType()->isStructTy()) 802 // We don't track structs in structs. 803 markOverdefined(getStructValueState(&IVI, i), &IVI); 804 else { 805 LatticeVal InVal = getValueState(Val); 806 mergeInValue(getStructValueState(&IVI, i), &IVI, InVal); 807 } 808 } 809 } 810 811 void SCCPSolver::visitSelectInst(SelectInst &I) { 812 // If this select returns a struct, just mark the result overdefined. 813 // TODO: We could do a lot better than this if code actually uses this. 814 if (I.getType()->isStructTy()) 815 return markAnythingOverdefined(&I); 816 817 LatticeVal CondValue = getValueState(I.getCondition()); 818 if (CondValue.isUndefined()) 819 return; 820 821 if (ConstantInt *CondCB = CondValue.getConstantInt()) { 822 Value *OpVal = CondCB->isZero() ? I.getFalseValue() : I.getTrueValue(); 823 mergeInValue(&I, getValueState(OpVal)); 824 return; 825 } 826 827 // Otherwise, the condition is overdefined or a constant we can't evaluate. 828 // See if we can produce something better than overdefined based on the T/F 829 // value. 830 LatticeVal TVal = getValueState(I.getTrueValue()); 831 LatticeVal FVal = getValueState(I.getFalseValue()); 832 833 // select ?, C, C -> C. 834 if (TVal.isConstant() && FVal.isConstant() && 835 TVal.getConstant() == FVal.getConstant()) 836 return markConstant(&I, FVal.getConstant()); 837 838 if (TVal.isUndefined()) // select ?, undef, X -> X. 839 return mergeInValue(&I, FVal); 840 if (FVal.isUndefined()) // select ?, X, undef -> X. 841 return mergeInValue(&I, TVal); 842 markOverdefined(&I); 843 } 844 845 // Handle Binary Operators. 846 void SCCPSolver::visitBinaryOperator(Instruction &I) { 847 LatticeVal V1State = getValueState(I.getOperand(0)); 848 LatticeVal V2State = getValueState(I.getOperand(1)); 849 850 LatticeVal &IV = ValueState[&I]; 851 if (IV.isOverdefined()) return; 852 853 if (V1State.isConstant() && V2State.isConstant()) 854 return markConstant(IV, &I, 855 ConstantExpr::get(I.getOpcode(), V1State.getConstant(), 856 V2State.getConstant())); 857 858 // If something is undef, wait for it to resolve. 859 if (!V1State.isOverdefined() && !V2State.isOverdefined()) 860 return; 861 862 // Otherwise, one of our operands is overdefined. Try to produce something 863 // better than overdefined with some tricks. 864 865 // If this is an AND or OR with 0 or -1, it doesn't matter that the other 866 // operand is overdefined. 867 if (I.getOpcode() == Instruction::And || I.getOpcode() == Instruction::Or) { 868 LatticeVal *NonOverdefVal = nullptr; 869 if (!V1State.isOverdefined()) 870 NonOverdefVal = &V1State; 871 else if (!V2State.isOverdefined()) 872 NonOverdefVal = &V2State; 873 874 if (NonOverdefVal) { 875 if (NonOverdefVal->isUndefined()) { 876 // Could annihilate value. 877 if (I.getOpcode() == Instruction::And) 878 markConstant(IV, &I, Constant::getNullValue(I.getType())); 879 else if (VectorType *PT = dyn_cast<VectorType>(I.getType())) 880 markConstant(IV, &I, Constant::getAllOnesValue(PT)); 881 else 882 markConstant(IV, &I, 883 Constant::getAllOnesValue(I.getType())); 884 return; 885 } 886 887 if (I.getOpcode() == Instruction::And) { 888 // X and 0 = 0 889 if (NonOverdefVal->getConstant()->isNullValue()) 890 return markConstant(IV, &I, NonOverdefVal->getConstant()); 891 } else { 892 if (ConstantInt *CI = NonOverdefVal->getConstantInt()) 893 if (CI->isAllOnesValue()) // X or -1 = -1 894 return markConstant(IV, &I, NonOverdefVal->getConstant()); 895 } 896 } 897 } 898 899 900 markOverdefined(&I); 901 } 902 903 // Handle ICmpInst instruction. 904 void SCCPSolver::visitCmpInst(CmpInst &I) { 905 LatticeVal V1State = getValueState(I.getOperand(0)); 906 LatticeVal V2State = getValueState(I.getOperand(1)); 907 908 LatticeVal &IV = ValueState[&I]; 909 if (IV.isOverdefined()) return; 910 911 if (V1State.isConstant() && V2State.isConstant()) 912 return markConstant(IV, &I, ConstantExpr::getCompare(I.getPredicate(), 913 V1State.getConstant(), 914 V2State.getConstant())); 915 916 // If operands are still undefined, wait for it to resolve. 917 if (!V1State.isOverdefined() && !V2State.isOverdefined()) 918 return; 919 920 markOverdefined(&I); 921 } 922 923 void SCCPSolver::visitExtractElementInst(ExtractElementInst &I) { 924 // TODO : SCCP does not handle vectors properly. 925 return markOverdefined(&I); 926 927 #if 0 928 LatticeVal &ValState = getValueState(I.getOperand(0)); 929 LatticeVal &IdxState = getValueState(I.getOperand(1)); 930 931 if (ValState.isOverdefined() || IdxState.isOverdefined()) 932 markOverdefined(&I); 933 else if(ValState.isConstant() && IdxState.isConstant()) 934 markConstant(&I, ConstantExpr::getExtractElement(ValState.getConstant(), 935 IdxState.getConstant())); 936 #endif 937 } 938 939 void SCCPSolver::visitInsertElementInst(InsertElementInst &I) { 940 // TODO : SCCP does not handle vectors properly. 941 return markOverdefined(&I); 942 #if 0 943 LatticeVal &ValState = getValueState(I.getOperand(0)); 944 LatticeVal &EltState = getValueState(I.getOperand(1)); 945 LatticeVal &IdxState = getValueState(I.getOperand(2)); 946 947 if (ValState.isOverdefined() || EltState.isOverdefined() || 948 IdxState.isOverdefined()) 949 markOverdefined(&I); 950 else if(ValState.isConstant() && EltState.isConstant() && 951 IdxState.isConstant()) 952 markConstant(&I, ConstantExpr::getInsertElement(ValState.getConstant(), 953 EltState.getConstant(), 954 IdxState.getConstant())); 955 else if (ValState.isUndefined() && EltState.isConstant() && 956 IdxState.isConstant()) 957 markConstant(&I,ConstantExpr::getInsertElement(UndefValue::get(I.getType()), 958 EltState.getConstant(), 959 IdxState.getConstant())); 960 #endif 961 } 962 963 void SCCPSolver::visitShuffleVectorInst(ShuffleVectorInst &I) { 964 // TODO : SCCP does not handle vectors properly. 965 return markOverdefined(&I); 966 #if 0 967 LatticeVal &V1State = getValueState(I.getOperand(0)); 968 LatticeVal &V2State = getValueState(I.getOperand(1)); 969 LatticeVal &MaskState = getValueState(I.getOperand(2)); 970 971 if (MaskState.isUndefined() || 972 (V1State.isUndefined() && V2State.isUndefined())) 973 return; // Undefined output if mask or both inputs undefined. 974 975 if (V1State.isOverdefined() || V2State.isOverdefined() || 976 MaskState.isOverdefined()) { 977 markOverdefined(&I); 978 } else { 979 // A mix of constant/undef inputs. 980 Constant *V1 = V1State.isConstant() ? 981 V1State.getConstant() : UndefValue::get(I.getType()); 982 Constant *V2 = V2State.isConstant() ? 983 V2State.getConstant() : UndefValue::get(I.getType()); 984 Constant *Mask = MaskState.isConstant() ? 985 MaskState.getConstant() : UndefValue::get(I.getOperand(2)->getType()); 986 markConstant(&I, ConstantExpr::getShuffleVector(V1, V2, Mask)); 987 } 988 #endif 989 } 990 991 // Handle getelementptr instructions. If all operands are constants then we 992 // can turn this into a getelementptr ConstantExpr. 993 // 994 void SCCPSolver::visitGetElementPtrInst(GetElementPtrInst &I) { 995 if (ValueState[&I].isOverdefined()) return; 996 997 SmallVector<Constant*, 8> Operands; 998 Operands.reserve(I.getNumOperands()); 999 1000 for (unsigned i = 0, e = I.getNumOperands(); i != e; ++i) { 1001 LatticeVal State = getValueState(I.getOperand(i)); 1002 if (State.isUndefined()) 1003 return; // Operands are not resolved yet. 1004 1005 if (State.isOverdefined()) 1006 return markOverdefined(&I); 1007 1008 assert(State.isConstant() && "Unknown state!"); 1009 Operands.push_back(State.getConstant()); 1010 } 1011 1012 Constant *Ptr = Operands[0]; 1013 ArrayRef<Constant *> Indices(Operands.begin() + 1, Operands.end()); 1014 markConstant(&I, ConstantExpr::getGetElementPtr(Ptr, Indices)); 1015 } 1016 1017 void SCCPSolver::visitStoreInst(StoreInst &SI) { 1018 // If this store is of a struct, ignore it. 1019 if (SI.getOperand(0)->getType()->isStructTy()) 1020 return; 1021 1022 if (TrackedGlobals.empty() || !isa<GlobalVariable>(SI.getOperand(1))) 1023 return; 1024 1025 GlobalVariable *GV = cast<GlobalVariable>(SI.getOperand(1)); 1026 DenseMap<GlobalVariable*, LatticeVal>::iterator I = TrackedGlobals.find(GV); 1027 if (I == TrackedGlobals.end() || I->second.isOverdefined()) return; 1028 1029 // Get the value we are storing into the global, then merge it. 1030 mergeInValue(I->second, GV, getValueState(SI.getOperand(0))); 1031 if (I->second.isOverdefined()) 1032 TrackedGlobals.erase(I); // No need to keep tracking this! 1033 } 1034 1035 1036 // Handle load instructions. If the operand is a constant pointer to a constant 1037 // global, we can replace the load with the loaded constant value! 1038 void SCCPSolver::visitLoadInst(LoadInst &I) { 1039 // If this load is of a struct, just mark the result overdefined. 1040 if (I.getType()->isStructTy()) 1041 return markAnythingOverdefined(&I); 1042 1043 LatticeVal PtrVal = getValueState(I.getOperand(0)); 1044 if (PtrVal.isUndefined()) return; // The pointer is not resolved yet! 1045 1046 LatticeVal &IV = ValueState[&I]; 1047 if (IV.isOverdefined()) return; 1048 1049 if (!PtrVal.isConstant() || I.isVolatile()) 1050 return markOverdefined(IV, &I); 1051 1052 Constant *Ptr = PtrVal.getConstant(); 1053 1054 // load null -> null 1055 if (isa<ConstantPointerNull>(Ptr) && I.getPointerAddressSpace() == 0) 1056 return markConstant(IV, &I, Constant::getNullValue(I.getType())); 1057 1058 // Transform load (constant global) into the value loaded. 1059 if (GlobalVariable *GV = dyn_cast<GlobalVariable>(Ptr)) { 1060 if (!TrackedGlobals.empty()) { 1061 // If we are tracking this global, merge in the known value for it. 1062 DenseMap<GlobalVariable*, LatticeVal>::iterator It = 1063 TrackedGlobals.find(GV); 1064 if (It != TrackedGlobals.end()) { 1065 mergeInValue(IV, &I, It->second); 1066 return; 1067 } 1068 } 1069 } 1070 1071 // Transform load from a constant into a constant if possible. 1072 if (Constant *C = ConstantFoldLoadFromConstPtr(Ptr, DL)) 1073 return markConstant(IV, &I, C); 1074 1075 // Otherwise we cannot say for certain what value this load will produce. 1076 // Bail out. 1077 markOverdefined(IV, &I); 1078 } 1079 1080 void SCCPSolver::visitCallSite(CallSite CS) { 1081 Function *F = CS.getCalledFunction(); 1082 Instruction *I = CS.getInstruction(); 1083 1084 // The common case is that we aren't tracking the callee, either because we 1085 // are not doing interprocedural analysis or the callee is indirect, or is 1086 // external. Handle these cases first. 1087 if (!F || F->isDeclaration()) { 1088 CallOverdefined: 1089 // Void return and not tracking callee, just bail. 1090 if (I->getType()->isVoidTy()) return; 1091 1092 // Otherwise, if we have a single return value case, and if the function is 1093 // a declaration, maybe we can constant fold it. 1094 if (F && F->isDeclaration() && !I->getType()->isStructTy() && 1095 canConstantFoldCallTo(F)) { 1096 1097 SmallVector<Constant*, 8> Operands; 1098 for (CallSite::arg_iterator AI = CS.arg_begin(), E = CS.arg_end(); 1099 AI != E; ++AI) { 1100 LatticeVal State = getValueState(*AI); 1101 1102 if (State.isUndefined()) 1103 return; // Operands are not resolved yet. 1104 if (State.isOverdefined()) 1105 return markOverdefined(I); 1106 assert(State.isConstant() && "Unknown state!"); 1107 Operands.push_back(State.getConstant()); 1108 } 1109 1110 // If we can constant fold this, mark the result of the call as a 1111 // constant. 1112 if (Constant *C = ConstantFoldCall(F, Operands, TLI)) 1113 return markConstant(I, C); 1114 } 1115 1116 // Otherwise, we don't know anything about this call, mark it overdefined. 1117 return markAnythingOverdefined(I); 1118 } 1119 1120 // If this is a local function that doesn't have its address taken, mark its 1121 // entry block executable and merge in the actual arguments to the call into 1122 // the formal arguments of the function. 1123 if (!TrackingIncomingArguments.empty() && TrackingIncomingArguments.count(F)){ 1124 MarkBlockExecutable(F->begin()); 1125 1126 // Propagate information from this call site into the callee. 1127 CallSite::arg_iterator CAI = CS.arg_begin(); 1128 for (Function::arg_iterator AI = F->arg_begin(), E = F->arg_end(); 1129 AI != E; ++AI, ++CAI) { 1130 // If this argument is byval, and if the function is not readonly, there 1131 // will be an implicit copy formed of the input aggregate. 1132 if (AI->hasByValAttr() && !F->onlyReadsMemory()) { 1133 markOverdefined(AI); 1134 continue; 1135 } 1136 1137 if (StructType *STy = dyn_cast<StructType>(AI->getType())) { 1138 for (unsigned i = 0, e = STy->getNumElements(); i != e; ++i) { 1139 LatticeVal CallArg = getStructValueState(*CAI, i); 1140 mergeInValue(getStructValueState(AI, i), AI, CallArg); 1141 } 1142 } else { 1143 mergeInValue(AI, getValueState(*CAI)); 1144 } 1145 } 1146 } 1147 1148 // If this is a single/zero retval case, see if we're tracking the function. 1149 if (StructType *STy = dyn_cast<StructType>(F->getReturnType())) { 1150 if (!MRVFunctionsTracked.count(F)) 1151 goto CallOverdefined; // Not tracking this callee. 1152 1153 // If we are tracking this callee, propagate the result of the function 1154 // into this call site. 1155 for (unsigned i = 0, e = STy->getNumElements(); i != e; ++i) 1156 mergeInValue(getStructValueState(I, i), I, 1157 TrackedMultipleRetVals[std::make_pair(F, i)]); 1158 } else { 1159 DenseMap<Function*, LatticeVal>::iterator TFRVI = TrackedRetVals.find(F); 1160 if (TFRVI == TrackedRetVals.end()) 1161 goto CallOverdefined; // Not tracking this callee. 1162 1163 // If so, propagate the return value of the callee into this call result. 1164 mergeInValue(I, TFRVI->second); 1165 } 1166 } 1167 1168 void SCCPSolver::Solve() { 1169 // Process the work lists until they are empty! 1170 while (!BBWorkList.empty() || !InstWorkList.empty() || 1171 !OverdefinedInstWorkList.empty()) { 1172 // Process the overdefined instruction's work list first, which drives other 1173 // things to overdefined more quickly. 1174 while (!OverdefinedInstWorkList.empty()) { 1175 Value *I = OverdefinedInstWorkList.pop_back_val(); 1176 1177 DEBUG(dbgs() << "\nPopped off OI-WL: " << *I << '\n'); 1178 1179 // "I" got into the work list because it either made the transition from 1180 // bottom to constant, or to overdefined. 1181 // 1182 // Anything on this worklist that is overdefined need not be visited 1183 // since all of its users will have already been marked as overdefined 1184 // Update all of the users of this instruction's value. 1185 // 1186 for (User *U : I->users()) 1187 if (Instruction *UI = dyn_cast<Instruction>(U)) 1188 OperandChangedState(UI); 1189 } 1190 1191 // Process the instruction work list. 1192 while (!InstWorkList.empty()) { 1193 Value *I = InstWorkList.pop_back_val(); 1194 1195 DEBUG(dbgs() << "\nPopped off I-WL: " << *I << '\n'); 1196 1197 // "I" got into the work list because it made the transition from undef to 1198 // constant. 1199 // 1200 // Anything on this worklist that is overdefined need not be visited 1201 // since all of its users will have already been marked as overdefined. 1202 // Update all of the users of this instruction's value. 1203 // 1204 if (I->getType()->isStructTy() || !getValueState(I).isOverdefined()) 1205 for (User *U : I->users()) 1206 if (Instruction *UI = dyn_cast<Instruction>(U)) 1207 OperandChangedState(UI); 1208 } 1209 1210 // Process the basic block work list. 1211 while (!BBWorkList.empty()) { 1212 BasicBlock *BB = BBWorkList.back(); 1213 BBWorkList.pop_back(); 1214 1215 DEBUG(dbgs() << "\nPopped off BBWL: " << *BB << '\n'); 1216 1217 // Notify all instructions in this basic block that they are newly 1218 // executable. 1219 visit(BB); 1220 } 1221 } 1222 } 1223 1224 /// ResolvedUndefsIn - While solving the dataflow for a function, we assume 1225 /// that branches on undef values cannot reach any of their successors. 1226 /// However, this is not a safe assumption. After we solve dataflow, this 1227 /// method should be use to handle this. If this returns true, the solver 1228 /// should be rerun. 1229 /// 1230 /// This method handles this by finding an unresolved branch and marking it one 1231 /// of the edges from the block as being feasible, even though the condition 1232 /// doesn't say it would otherwise be. This allows SCCP to find the rest of the 1233 /// CFG and only slightly pessimizes the analysis results (by marking one, 1234 /// potentially infeasible, edge feasible). This cannot usefully modify the 1235 /// constraints on the condition of the branch, as that would impact other users 1236 /// of the value. 1237 /// 1238 /// This scan also checks for values that use undefs, whose results are actually 1239 /// defined. For example, 'zext i8 undef to i32' should produce all zeros 1240 /// conservatively, as "(zext i8 X -> i32) & 0xFF00" must always return zero, 1241 /// even if X isn't defined. 1242 bool SCCPSolver::ResolvedUndefsIn(Function &F) { 1243 for (Function::iterator BB = F.begin(), E = F.end(); BB != E; ++BB) { 1244 if (!BBExecutable.count(BB)) 1245 continue; 1246 1247 for (BasicBlock::iterator I = BB->begin(), E = BB->end(); I != E; ++I) { 1248 // Look for instructions which produce undef values. 1249 if (I->getType()->isVoidTy()) continue; 1250 1251 if (StructType *STy = dyn_cast<StructType>(I->getType())) { 1252 // Only a few things that can be structs matter for undef. 1253 1254 // Tracked calls must never be marked overdefined in ResolvedUndefsIn. 1255 if (CallSite CS = CallSite(I)) 1256 if (Function *F = CS.getCalledFunction()) 1257 if (MRVFunctionsTracked.count(F)) 1258 continue; 1259 1260 // extractvalue and insertvalue don't need to be marked; they are 1261 // tracked as precisely as their operands. 1262 if (isa<ExtractValueInst>(I) || isa<InsertValueInst>(I)) 1263 continue; 1264 1265 // Send the results of everything else to overdefined. We could be 1266 // more precise than this but it isn't worth bothering. 1267 for (unsigned i = 0, e = STy->getNumElements(); i != e; ++i) { 1268 LatticeVal &LV = getStructValueState(I, i); 1269 if (LV.isUndefined()) 1270 markOverdefined(LV, I); 1271 } 1272 continue; 1273 } 1274 1275 LatticeVal &LV = getValueState(I); 1276 if (!LV.isUndefined()) continue; 1277 1278 // extractvalue is safe; check here because the argument is a struct. 1279 if (isa<ExtractValueInst>(I)) 1280 continue; 1281 1282 // Compute the operand LatticeVals, for convenience below. 1283 // Anything taking a struct is conservatively assumed to require 1284 // overdefined markings. 1285 if (I->getOperand(0)->getType()->isStructTy()) { 1286 markOverdefined(I); 1287 return true; 1288 } 1289 LatticeVal Op0LV = getValueState(I->getOperand(0)); 1290 LatticeVal Op1LV; 1291 if (I->getNumOperands() == 2) { 1292 if (I->getOperand(1)->getType()->isStructTy()) { 1293 markOverdefined(I); 1294 return true; 1295 } 1296 1297 Op1LV = getValueState(I->getOperand(1)); 1298 } 1299 // If this is an instructions whose result is defined even if the input is 1300 // not fully defined, propagate the information. 1301 Type *ITy = I->getType(); 1302 switch (I->getOpcode()) { 1303 case Instruction::Add: 1304 case Instruction::Sub: 1305 case Instruction::Trunc: 1306 case Instruction::FPTrunc: 1307 case Instruction::BitCast: 1308 break; // Any undef -> undef 1309 case Instruction::FSub: 1310 case Instruction::FAdd: 1311 case Instruction::FMul: 1312 case Instruction::FDiv: 1313 case Instruction::FRem: 1314 // Floating-point binary operation: be conservative. 1315 if (Op0LV.isUndefined() && Op1LV.isUndefined()) 1316 markForcedConstant(I, Constant::getNullValue(ITy)); 1317 else 1318 markOverdefined(I); 1319 return true; 1320 case Instruction::ZExt: 1321 case Instruction::SExt: 1322 case Instruction::FPToUI: 1323 case Instruction::FPToSI: 1324 case Instruction::FPExt: 1325 case Instruction::PtrToInt: 1326 case Instruction::IntToPtr: 1327 case Instruction::SIToFP: 1328 case Instruction::UIToFP: 1329 // undef -> 0; some outputs are impossible 1330 markForcedConstant(I, Constant::getNullValue(ITy)); 1331 return true; 1332 case Instruction::Mul: 1333 case Instruction::And: 1334 // Both operands undef -> undef 1335 if (Op0LV.isUndefined() && Op1LV.isUndefined()) 1336 break; 1337 // undef * X -> 0. X could be zero. 1338 // undef & X -> 0. X could be zero. 1339 markForcedConstant(I, Constant::getNullValue(ITy)); 1340 return true; 1341 1342 case Instruction::Or: 1343 // Both operands undef -> undef 1344 if (Op0LV.isUndefined() && Op1LV.isUndefined()) 1345 break; 1346 // undef | X -> -1. X could be -1. 1347 markForcedConstant(I, Constant::getAllOnesValue(ITy)); 1348 return true; 1349 1350 case Instruction::Xor: 1351 // undef ^ undef -> 0; strictly speaking, this is not strictly 1352 // necessary, but we try to be nice to people who expect this 1353 // behavior in simple cases 1354 if (Op0LV.isUndefined() && Op1LV.isUndefined()) { 1355 markForcedConstant(I, Constant::getNullValue(ITy)); 1356 return true; 1357 } 1358 // undef ^ X -> undef 1359 break; 1360 1361 case Instruction::SDiv: 1362 case Instruction::UDiv: 1363 case Instruction::SRem: 1364 case Instruction::URem: 1365 // X / undef -> undef. No change. 1366 // X % undef -> undef. No change. 1367 if (Op1LV.isUndefined()) break; 1368 1369 // undef / X -> 0. X could be maxint. 1370 // undef % X -> 0. X could be 1. 1371 markForcedConstant(I, Constant::getNullValue(ITy)); 1372 return true; 1373 1374 case Instruction::AShr: 1375 // X >>a undef -> undef. 1376 if (Op1LV.isUndefined()) break; 1377 1378 // undef >>a X -> all ones 1379 markForcedConstant(I, Constant::getAllOnesValue(ITy)); 1380 return true; 1381 case Instruction::LShr: 1382 case Instruction::Shl: 1383 // X << undef -> undef. 1384 // X >> undef -> undef. 1385 if (Op1LV.isUndefined()) break; 1386 1387 // undef << X -> 0 1388 // undef >> X -> 0 1389 markForcedConstant(I, Constant::getNullValue(ITy)); 1390 return true; 1391 case Instruction::Select: 1392 Op1LV = getValueState(I->getOperand(1)); 1393 // undef ? X : Y -> X or Y. There could be commonality between X/Y. 1394 if (Op0LV.isUndefined()) { 1395 if (!Op1LV.isConstant()) // Pick the constant one if there is any. 1396 Op1LV = getValueState(I->getOperand(2)); 1397 } else if (Op1LV.isUndefined()) { 1398 // c ? undef : undef -> undef. No change. 1399 Op1LV = getValueState(I->getOperand(2)); 1400 if (Op1LV.isUndefined()) 1401 break; 1402 // Otherwise, c ? undef : x -> x. 1403 } else { 1404 // Leave Op1LV as Operand(1)'s LatticeValue. 1405 } 1406 1407 if (Op1LV.isConstant()) 1408 markForcedConstant(I, Op1LV.getConstant()); 1409 else 1410 markOverdefined(I); 1411 return true; 1412 case Instruction::Load: 1413 // A load here means one of two things: a load of undef from a global, 1414 // a load from an unknown pointer. Either way, having it return undef 1415 // is okay. 1416 break; 1417 case Instruction::ICmp: 1418 // X == undef -> undef. Other comparisons get more complicated. 1419 if (cast<ICmpInst>(I)->isEquality()) 1420 break; 1421 markOverdefined(I); 1422 return true; 1423 case Instruction::Call: 1424 case Instruction::Invoke: { 1425 // There are two reasons a call can have an undef result 1426 // 1. It could be tracked. 1427 // 2. It could be constant-foldable. 1428 // Because of the way we solve return values, tracked calls must 1429 // never be marked overdefined in ResolvedUndefsIn. 1430 if (Function *F = CallSite(I).getCalledFunction()) 1431 if (TrackedRetVals.count(F)) 1432 break; 1433 1434 // If the call is constant-foldable, we mark it overdefined because 1435 // we do not know what return values are valid. 1436 markOverdefined(I); 1437 return true; 1438 } 1439 default: 1440 // If we don't know what should happen here, conservatively mark it 1441 // overdefined. 1442 markOverdefined(I); 1443 return true; 1444 } 1445 } 1446 1447 // Check to see if we have a branch or switch on an undefined value. If so 1448 // we force the branch to go one way or the other to make the successor 1449 // values live. It doesn't really matter which way we force it. 1450 TerminatorInst *TI = BB->getTerminator(); 1451 if (BranchInst *BI = dyn_cast<BranchInst>(TI)) { 1452 if (!BI->isConditional()) continue; 1453 if (!getValueState(BI->getCondition()).isUndefined()) 1454 continue; 1455 1456 // If the input to SCCP is actually branch on undef, fix the undef to 1457 // false. 1458 if (isa<UndefValue>(BI->getCondition())) { 1459 BI->setCondition(ConstantInt::getFalse(BI->getContext())); 1460 markEdgeExecutable(BB, TI->getSuccessor(1)); 1461 return true; 1462 } 1463 1464 // Otherwise, it is a branch on a symbolic value which is currently 1465 // considered to be undef. Handle this by forcing the input value to the 1466 // branch to false. 1467 markForcedConstant(BI->getCondition(), 1468 ConstantInt::getFalse(TI->getContext())); 1469 return true; 1470 } 1471 1472 if (SwitchInst *SI = dyn_cast<SwitchInst>(TI)) { 1473 if (!SI->getNumCases()) 1474 continue; 1475 if (!getValueState(SI->getCondition()).isUndefined()) 1476 continue; 1477 1478 // If the input to SCCP is actually switch on undef, fix the undef to 1479 // the first constant. 1480 if (isa<UndefValue>(SI->getCondition())) { 1481 SI->setCondition(SI->case_begin().getCaseValue()); 1482 markEdgeExecutable(BB, SI->case_begin().getCaseSuccessor()); 1483 return true; 1484 } 1485 1486 markForcedConstant(SI->getCondition(), SI->case_begin().getCaseValue()); 1487 return true; 1488 } 1489 } 1490 1491 return false; 1492 } 1493 1494 1495 namespace { 1496 //===--------------------------------------------------------------------===// 1497 // 1498 /// SCCP Class - This class uses the SCCPSolver to implement a per-function 1499 /// Sparse Conditional Constant Propagator. 1500 /// 1501 struct SCCP : public FunctionPass { 1502 void getAnalysisUsage(AnalysisUsage &AU) const override { 1503 AU.addRequired<TargetLibraryInfo>(); 1504 } 1505 static char ID; // Pass identification, replacement for typeid 1506 SCCP() : FunctionPass(ID) { 1507 initializeSCCPPass(*PassRegistry::getPassRegistry()); 1508 } 1509 1510 // runOnFunction - Run the Sparse Conditional Constant Propagation 1511 // algorithm, and return true if the function was modified. 1512 // 1513 bool runOnFunction(Function &F) override; 1514 }; 1515 } // end anonymous namespace 1516 1517 char SCCP::ID = 0; 1518 INITIALIZE_PASS(SCCP, "sccp", 1519 "Sparse Conditional Constant Propagation", false, false) 1520 1521 // createSCCPPass - This is the public interface to this file. 1522 FunctionPass *llvm::createSCCPPass() { 1523 return new SCCP(); 1524 } 1525 1526 static void DeleteInstructionInBlock(BasicBlock *BB) { 1527 DEBUG(dbgs() << " BasicBlock Dead:" << *BB); 1528 ++NumDeadBlocks; 1529 1530 // Check to see if there are non-terminating instructions to delete. 1531 if (isa<TerminatorInst>(BB->begin())) 1532 return; 1533 1534 // Delete the instructions backwards, as it has a reduced likelihood of having 1535 // to update as many def-use and use-def chains. 1536 Instruction *EndInst = BB->getTerminator(); // Last not to be deleted. 1537 while (EndInst != BB->begin()) { 1538 // Delete the next to last instruction. 1539 BasicBlock::iterator I = EndInst; 1540 Instruction *Inst = --I; 1541 if (!Inst->use_empty()) 1542 Inst->replaceAllUsesWith(UndefValue::get(Inst->getType())); 1543 if (isa<LandingPadInst>(Inst)) { 1544 EndInst = Inst; 1545 continue; 1546 } 1547 BB->getInstList().erase(Inst); 1548 ++NumInstRemoved; 1549 } 1550 } 1551 1552 // runOnFunction() - Run the Sparse Conditional Constant Propagation algorithm, 1553 // and return true if the function was modified. 1554 // 1555 bool SCCP::runOnFunction(Function &F) { 1556 if (skipOptnoneFunction(F)) 1557 return false; 1558 1559 DEBUG(dbgs() << "SCCP on function '" << F.getName() << "'\n"); 1560 const DataLayoutPass *DLP = getAnalysisIfAvailable<DataLayoutPass>(); 1561 const DataLayout *DL = DLP ? &DLP->getDataLayout() : nullptr; 1562 const TargetLibraryInfo *TLI = &getAnalysis<TargetLibraryInfo>(); 1563 SCCPSolver Solver(DL, TLI); 1564 1565 // Mark the first block of the function as being executable. 1566 Solver.MarkBlockExecutable(F.begin()); 1567 1568 // Mark all arguments to the function as being overdefined. 1569 for (Function::arg_iterator AI = F.arg_begin(), E = F.arg_end(); AI != E;++AI) 1570 Solver.markAnythingOverdefined(AI); 1571 1572 // Solve for constants. 1573 bool ResolvedUndefs = true; 1574 while (ResolvedUndefs) { 1575 Solver.Solve(); 1576 DEBUG(dbgs() << "RESOLVING UNDEFs\n"); 1577 ResolvedUndefs = Solver.ResolvedUndefsIn(F); 1578 } 1579 1580 bool MadeChanges = false; 1581 1582 // If we decided that there are basic blocks that are dead in this function, 1583 // delete their contents now. Note that we cannot actually delete the blocks, 1584 // as we cannot modify the CFG of the function. 1585 1586 for (Function::iterator BB = F.begin(), E = F.end(); BB != E; ++BB) { 1587 if (!Solver.isBlockExecutable(BB)) { 1588 DeleteInstructionInBlock(BB); 1589 MadeChanges = true; 1590 continue; 1591 } 1592 1593 // Iterate over all of the instructions in a function, replacing them with 1594 // constants if we have found them to be of constant values. 1595 // 1596 for (BasicBlock::iterator BI = BB->begin(), E = BB->end(); BI != E; ) { 1597 Instruction *Inst = BI++; 1598 if (Inst->getType()->isVoidTy() || isa<TerminatorInst>(Inst)) 1599 continue; 1600 1601 // TODO: Reconstruct structs from their elements. 1602 if (Inst->getType()->isStructTy()) 1603 continue; 1604 1605 LatticeVal IV = Solver.getLatticeValueFor(Inst); 1606 if (IV.isOverdefined()) 1607 continue; 1608 1609 Constant *Const = IV.isConstant() 1610 ? IV.getConstant() : UndefValue::get(Inst->getType()); 1611 DEBUG(dbgs() << " Constant: " << *Const << " = " << *Inst << '\n'); 1612 1613 // Replaces all of the uses of a variable with uses of the constant. 1614 Inst->replaceAllUsesWith(Const); 1615 1616 // Delete the instruction. 1617 Inst->eraseFromParent(); 1618 1619 // Hey, we just changed something! 1620 MadeChanges = true; 1621 ++NumInstRemoved; 1622 } 1623 } 1624 1625 return MadeChanges; 1626 } 1627 1628 namespace { 1629 //===--------------------------------------------------------------------===// 1630 // 1631 /// IPSCCP Class - This class implements interprocedural Sparse Conditional 1632 /// Constant Propagation. 1633 /// 1634 struct IPSCCP : public ModulePass { 1635 void getAnalysisUsage(AnalysisUsage &AU) const override { 1636 AU.addRequired<TargetLibraryInfo>(); 1637 } 1638 static char ID; 1639 IPSCCP() : ModulePass(ID) { 1640 initializeIPSCCPPass(*PassRegistry::getPassRegistry()); 1641 } 1642 bool runOnModule(Module &M) override; 1643 }; 1644 } // end anonymous namespace 1645 1646 char IPSCCP::ID = 0; 1647 INITIALIZE_PASS_BEGIN(IPSCCP, "ipsccp", 1648 "Interprocedural Sparse Conditional Constant Propagation", 1649 false, false) 1650 INITIALIZE_PASS_DEPENDENCY(TargetLibraryInfo) 1651 INITIALIZE_PASS_END(IPSCCP, "ipsccp", 1652 "Interprocedural Sparse Conditional Constant Propagation", 1653 false, false) 1654 1655 // createIPSCCPPass - This is the public interface to this file. 1656 ModulePass *llvm::createIPSCCPPass() { 1657 return new IPSCCP(); 1658 } 1659 1660 1661 static bool AddressIsTaken(const GlobalValue *GV) { 1662 // Delete any dead constantexpr klingons. 1663 GV->removeDeadConstantUsers(); 1664 1665 for (const Use &U : GV->uses()) { 1666 const User *UR = U.getUser(); 1667 if (const StoreInst *SI = dyn_cast<StoreInst>(UR)) { 1668 if (SI->getOperand(0) == GV || SI->isVolatile()) 1669 return true; // Storing addr of GV. 1670 } else if (isa<InvokeInst>(UR) || isa<CallInst>(UR)) { 1671 // Make sure we are calling the function, not passing the address. 1672 ImmutableCallSite CS(cast<Instruction>(UR)); 1673 if (!CS.isCallee(&U)) 1674 return true; 1675 } else if (const LoadInst *LI = dyn_cast<LoadInst>(UR)) { 1676 if (LI->isVolatile()) 1677 return true; 1678 } else if (isa<BlockAddress>(UR)) { 1679 // blockaddress doesn't take the address of the function, it takes addr 1680 // of label. 1681 } else { 1682 return true; 1683 } 1684 } 1685 return false; 1686 } 1687 1688 bool IPSCCP::runOnModule(Module &M) { 1689 DataLayoutPass *DLP = getAnalysisIfAvailable<DataLayoutPass>(); 1690 const DataLayout *DL = DLP ? &DLP->getDataLayout() : nullptr; 1691 const TargetLibraryInfo *TLI = &getAnalysis<TargetLibraryInfo>(); 1692 SCCPSolver Solver(DL, TLI); 1693 1694 // AddressTakenFunctions - This set keeps track of the address-taken functions 1695 // that are in the input. As IPSCCP runs through and simplifies code, 1696 // functions that were address taken can end up losing their 1697 // address-taken-ness. Because of this, we keep track of their addresses from 1698 // the first pass so we can use them for the later simplification pass. 1699 SmallPtrSet<Function*, 32> AddressTakenFunctions; 1700 1701 // Loop over all functions, marking arguments to those with their addresses 1702 // taken or that are external as overdefined. 1703 // 1704 for (Module::iterator F = M.begin(), E = M.end(); F != E; ++F) { 1705 if (F->isDeclaration()) 1706 continue; 1707 1708 // If this is a strong or ODR definition of this function, then we can 1709 // propagate information about its result into callsites of it. 1710 if (!F->mayBeOverridden()) 1711 Solver.AddTrackedFunction(F); 1712 1713 // If this function only has direct calls that we can see, we can track its 1714 // arguments and return value aggressively, and can assume it is not called 1715 // unless we see evidence to the contrary. 1716 if (F->hasLocalLinkage()) { 1717 if (AddressIsTaken(F)) 1718 AddressTakenFunctions.insert(F); 1719 else { 1720 Solver.AddArgumentTrackedFunction(F); 1721 continue; 1722 } 1723 } 1724 1725 // Assume the function is called. 1726 Solver.MarkBlockExecutable(F->begin()); 1727 1728 // Assume nothing about the incoming arguments. 1729 for (Function::arg_iterator AI = F->arg_begin(), E = F->arg_end(); 1730 AI != E; ++AI) 1731 Solver.markAnythingOverdefined(AI); 1732 } 1733 1734 // Loop over global variables. We inform the solver about any internal global 1735 // variables that do not have their 'addresses taken'. If they don't have 1736 // their addresses taken, we can propagate constants through them. 1737 for (Module::global_iterator G = M.global_begin(), E = M.global_end(); 1738 G != E; ++G) 1739 if (!G->isConstant() && G->hasLocalLinkage() && !AddressIsTaken(G)) 1740 Solver.TrackValueOfGlobalVariable(G); 1741 1742 // Solve for constants. 1743 bool ResolvedUndefs = true; 1744 while (ResolvedUndefs) { 1745 Solver.Solve(); 1746 1747 DEBUG(dbgs() << "RESOLVING UNDEFS\n"); 1748 ResolvedUndefs = false; 1749 for (Module::iterator F = M.begin(), E = M.end(); F != E; ++F) 1750 ResolvedUndefs |= Solver.ResolvedUndefsIn(*F); 1751 } 1752 1753 bool MadeChanges = false; 1754 1755 // Iterate over all of the instructions in the module, replacing them with 1756 // constants if we have found them to be of constant values. 1757 // 1758 SmallVector<BasicBlock*, 512> BlocksToErase; 1759 1760 for (Module::iterator F = M.begin(), E = M.end(); F != E; ++F) { 1761 if (Solver.isBlockExecutable(F->begin())) { 1762 for (Function::arg_iterator AI = F->arg_begin(), E = F->arg_end(); 1763 AI != E; ++AI) { 1764 if (AI->use_empty() || AI->getType()->isStructTy()) continue; 1765 1766 // TODO: Could use getStructLatticeValueFor to find out if the entire 1767 // result is a constant and replace it entirely if so. 1768 1769 LatticeVal IV = Solver.getLatticeValueFor(AI); 1770 if (IV.isOverdefined()) continue; 1771 1772 Constant *CST = IV.isConstant() ? 1773 IV.getConstant() : UndefValue::get(AI->getType()); 1774 DEBUG(dbgs() << "*** Arg " << *AI << " = " << *CST <<"\n"); 1775 1776 // Replaces all of the uses of a variable with uses of the 1777 // constant. 1778 AI->replaceAllUsesWith(CST); 1779 ++IPNumArgsElimed; 1780 } 1781 } 1782 1783 for (Function::iterator BB = F->begin(), E = F->end(); BB != E; ++BB) { 1784 if (!Solver.isBlockExecutable(BB)) { 1785 DeleteInstructionInBlock(BB); 1786 MadeChanges = true; 1787 1788 TerminatorInst *TI = BB->getTerminator(); 1789 for (unsigned i = 0, e = TI->getNumSuccessors(); i != e; ++i) { 1790 BasicBlock *Succ = TI->getSuccessor(i); 1791 if (!Succ->empty() && isa<PHINode>(Succ->begin())) 1792 TI->getSuccessor(i)->removePredecessor(BB); 1793 } 1794 if (!TI->use_empty()) 1795 TI->replaceAllUsesWith(UndefValue::get(TI->getType())); 1796 TI->eraseFromParent(); 1797 1798 if (&*BB != &F->front()) 1799 BlocksToErase.push_back(BB); 1800 else 1801 new UnreachableInst(M.getContext(), BB); 1802 continue; 1803 } 1804 1805 for (BasicBlock::iterator BI = BB->begin(), E = BB->end(); BI != E; ) { 1806 Instruction *Inst = BI++; 1807 if (Inst->getType()->isVoidTy() || Inst->getType()->isStructTy()) 1808 continue; 1809 1810 // TODO: Could use getStructLatticeValueFor to find out if the entire 1811 // result is a constant and replace it entirely if so. 1812 1813 LatticeVal IV = Solver.getLatticeValueFor(Inst); 1814 if (IV.isOverdefined()) 1815 continue; 1816 1817 Constant *Const = IV.isConstant() 1818 ? IV.getConstant() : UndefValue::get(Inst->getType()); 1819 DEBUG(dbgs() << " Constant: " << *Const << " = " << *Inst << '\n'); 1820 1821 // Replaces all of the uses of a variable with uses of the 1822 // constant. 1823 Inst->replaceAllUsesWith(Const); 1824 1825 // Delete the instruction. 1826 if (!isa<CallInst>(Inst) && !isa<TerminatorInst>(Inst)) 1827 Inst->eraseFromParent(); 1828 1829 // Hey, we just changed something! 1830 MadeChanges = true; 1831 ++IPNumInstRemoved; 1832 } 1833 } 1834 1835 // Now that all instructions in the function are constant folded, erase dead 1836 // blocks, because we can now use ConstantFoldTerminator to get rid of 1837 // in-edges. 1838 for (unsigned i = 0, e = BlocksToErase.size(); i != e; ++i) { 1839 // If there are any PHI nodes in this successor, drop entries for BB now. 1840 BasicBlock *DeadBB = BlocksToErase[i]; 1841 for (Value::user_iterator UI = DeadBB->user_begin(), 1842 UE = DeadBB->user_end(); 1843 UI != UE;) { 1844 // Grab the user and then increment the iterator early, as the user 1845 // will be deleted. Step past all adjacent uses from the same user. 1846 Instruction *I = dyn_cast<Instruction>(*UI); 1847 do { ++UI; } while (UI != UE && *UI == I); 1848 1849 // Ignore blockaddress users; BasicBlock's dtor will handle them. 1850 if (!I) continue; 1851 1852 bool Folded = ConstantFoldTerminator(I->getParent()); 1853 if (!Folded) { 1854 // The constant folder may not have been able to fold the terminator 1855 // if this is a branch or switch on undef. Fold it manually as a 1856 // branch to the first successor. 1857 #ifndef NDEBUG 1858 if (BranchInst *BI = dyn_cast<BranchInst>(I)) { 1859 assert(BI->isConditional() && isa<UndefValue>(BI->getCondition()) && 1860 "Branch should be foldable!"); 1861 } else if (SwitchInst *SI = dyn_cast<SwitchInst>(I)) { 1862 assert(isa<UndefValue>(SI->getCondition()) && "Switch should fold"); 1863 } else { 1864 llvm_unreachable("Didn't fold away reference to block!"); 1865 } 1866 #endif 1867 1868 // Make this an uncond branch to the first successor. 1869 TerminatorInst *TI = I->getParent()->getTerminator(); 1870 BranchInst::Create(TI->getSuccessor(0), TI); 1871 1872 // Remove entries in successor phi nodes to remove edges. 1873 for (unsigned i = 1, e = TI->getNumSuccessors(); i != e; ++i) 1874 TI->getSuccessor(i)->removePredecessor(TI->getParent()); 1875 1876 // Remove the old terminator. 1877 TI->eraseFromParent(); 1878 } 1879 } 1880 1881 // Finally, delete the basic block. 1882 F->getBasicBlockList().erase(DeadBB); 1883 } 1884 BlocksToErase.clear(); 1885 } 1886 1887 // If we inferred constant or undef return values for a function, we replaced 1888 // all call uses with the inferred value. This means we don't need to bother 1889 // actually returning anything from the function. Replace all return 1890 // instructions with return undef. 1891 // 1892 // Do this in two stages: first identify the functions we should process, then 1893 // actually zap their returns. This is important because we can only do this 1894 // if the address of the function isn't taken. In cases where a return is the 1895 // last use of a function, the order of processing functions would affect 1896 // whether other functions are optimizable. 1897 SmallVector<ReturnInst*, 8> ReturnsToZap; 1898 1899 // TODO: Process multiple value ret instructions also. 1900 const DenseMap<Function*, LatticeVal> &RV = Solver.getTrackedRetVals(); 1901 for (DenseMap<Function*, LatticeVal>::const_iterator I = RV.begin(), 1902 E = RV.end(); I != E; ++I) { 1903 Function *F = I->first; 1904 if (I->second.isOverdefined() || F->getReturnType()->isVoidTy()) 1905 continue; 1906 1907 // We can only do this if we know that nothing else can call the function. 1908 if (!F->hasLocalLinkage() || AddressTakenFunctions.count(F)) 1909 continue; 1910 1911 for (Function::iterator BB = F->begin(), E = F->end(); BB != E; ++BB) 1912 if (ReturnInst *RI = dyn_cast<ReturnInst>(BB->getTerminator())) 1913 if (!isa<UndefValue>(RI->getOperand(0))) 1914 ReturnsToZap.push_back(RI); 1915 } 1916 1917 // Zap all returns which we've identified as zap to change. 1918 for (unsigned i = 0, e = ReturnsToZap.size(); i != e; ++i) { 1919 Function *F = ReturnsToZap[i]->getParent()->getParent(); 1920 ReturnsToZap[i]->setOperand(0, UndefValue::get(F->getReturnType())); 1921 } 1922 1923 // If we inferred constant or undef values for globals variables, we can 1924 // delete the global and any stores that remain to it. 1925 const DenseMap<GlobalVariable*, LatticeVal> &TG = Solver.getTrackedGlobals(); 1926 for (DenseMap<GlobalVariable*, LatticeVal>::const_iterator I = TG.begin(), 1927 E = TG.end(); I != E; ++I) { 1928 GlobalVariable *GV = I->first; 1929 assert(!I->second.isOverdefined() && 1930 "Overdefined values should have been taken out of the map!"); 1931 DEBUG(dbgs() << "Found that GV '" << GV->getName() << "' is constant!\n"); 1932 while (!GV->use_empty()) { 1933 StoreInst *SI = cast<StoreInst>(GV->user_back()); 1934 SI->eraseFromParent(); 1935 } 1936 M.getGlobalList().erase(GV); 1937 ++IPNumGlobalConst; 1938 } 1939 1940 return MadeChanges; 1941 } 1942