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