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