1 //===- SCCP.cpp - Sparse Conditional Constant Propogation -----------------===// 2 // 3 // This file implements sparse conditional constant propogation and merging: 4 // 5 // Specifically, this: 6 // * Assumes values are constant unless proven otherwise 7 // * Assumes BasicBlocks are dead unless proven otherwise 8 // * Proves values to be constant, and replaces them with constants 9 // . Proves conditional branches constant, and unconditionalizes them 10 // * Folds multiple identical constants in the constant pool together 11 // 12 // Notice that: 13 // * This pass has a habit of making definitions be dead. It is a good idea 14 // to to run a DCE pass sometime after running this pass. 15 // 16 //===----------------------------------------------------------------------===// 17 18 #include "llvm/Optimizations/ConstantProp.h" 19 #include "llvm/Optimizations/ConstantHandling.h" 20 #include "llvm/Method.h" 21 #include "llvm/BasicBlock.h" 22 #include "llvm/ConstPoolVals.h" 23 #include "llvm/ConstantPool.h" 24 #include "llvm/InstrTypes.h" 25 #include "llvm/iOther.h" 26 #include "llvm/iMemory.h" 27 #include "llvm/iTerminators.h" 28 #include "llvm/Tools/STLExtras.h" 29 #include "llvm/Assembly/Writer.h" 30 #include <algorithm> 31 #include <map> 32 #include <set> 33 34 // InstVal class - This class represents the different lattice values that an 35 // instruction may occupy. It is a simple class with value semantics. The 36 // potential constant value that is pointed to is owned by the constant pool 37 // for the method being optimized. 38 // 39 class InstVal { 40 enum { 41 Undefined, // This instruction has no known value 42 Constant, // This instruction has a constant value 43 // Range, // This instruction is known to fall within a range 44 Overdefined // This instruction has an unknown value 45 } LatticeValue; // The current lattice position 46 ConstPoolVal *ConstantVal; // If Constant value, the current value 47 public: 48 inline InstVal() : LatticeValue(Undefined), ConstantVal(0) {} 49 50 // markOverdefined - Return true if this is a new status to be in... 51 inline bool markOverdefined() { 52 if (LatticeValue != Overdefined) { 53 LatticeValue = Overdefined; 54 return true; 55 } 56 return false; 57 } 58 59 // markConstant - Return true if this is a new status for us... 60 inline bool markConstant(ConstPoolVal *V) { 61 if (LatticeValue != Constant) { 62 LatticeValue = Constant; 63 ConstantVal = V; 64 return true; 65 } else { 66 assert(ConstantVal->equals(V) && "Marking constant with different value"); 67 } 68 return false; 69 } 70 71 inline bool isUndefined() const { return LatticeValue == Undefined; } 72 inline bool isConstant() const { return LatticeValue == Constant; } 73 inline bool isOverdefined() const { return LatticeValue == Overdefined; } 74 75 inline ConstPoolVal *getConstant() const { return ConstantVal; } 76 }; 77 78 79 80 //===----------------------------------------------------------------------===// 81 // SCCP Class 82 // 83 // This class does all of the work of Sparse Conditional Constant Propogation. 84 // It's public interface consists of a constructor and a doSCCP() method. 85 // 86 class SCCP { 87 Method *M; // The method that we are working on... 88 89 set<BasicBlock*> BBExecutable; // The basic blocks that are executable 90 map<Value*, InstVal> ValueState; // The state each value is in... 91 92 vector<Instruction*> InstWorkList; // The instruction work list 93 vector<BasicBlock*> BBWorkList; // The BasicBlock work list 94 95 //===--------------------------------------------------------------------===// 96 // The public interface for this class 97 // 98 public: 99 100 // SCCP Ctor - Save the method to operate on... 101 inline SCCP(Method *m) : M(m) {} 102 103 // doSCCP() - Run the Sparse Conditional Constant Propogation algorithm, and 104 // return true if the method was modified. 105 bool doSCCP(); 106 107 //===--------------------------------------------------------------------===// 108 // The implementation of this class 109 // 110 private: 111 112 // markValueOverdefined - Make a value be marked as "constant". If the value 113 // is not already a constant, add it to the instruction work list so that 114 // the users of the instruction are updated later. 115 // 116 inline bool markConstant(Instruction *I, ConstPoolVal *V) { 117 //cerr << "markConstant: " << V << " = " << I; 118 if (ValueState[I].markConstant(V)) { 119 InstWorkList.push_back(I); 120 return true; 121 } 122 return false; 123 } 124 125 // markValueOverdefined - Make a value be marked as "overdefined". If the 126 // value is not already overdefined, add it to the instruction work list so 127 // that the users of the instruction are updated later. 128 // 129 inline bool markOverdefined(Value *V) { 130 if (ValueState[V].markOverdefined()) { 131 if (Instruction *I = V->castInstruction()) { 132 //cerr << "markOverdefined: " << V; 133 InstWorkList.push_back(I); // Only instructions go on the work list 134 } 135 return true; 136 } 137 return false; 138 } 139 140 // getValueState - Return the InstVal object that corresponds to the value. 141 // This function is neccesary because not all values should start out in the 142 // underdefined state... MethodArgument's should be overdefined, and constants 143 // should be marked as constants. If a value is not known to be an 144 // Instruction object, then use this accessor to get its value from the map. 145 // 146 inline InstVal &getValueState(Value *V) { 147 map<Value*, InstVal>::iterator I = ValueState.find(V); 148 if (I != ValueState.end()) return I->second; // Common case, in the map 149 150 if (ConstPoolVal *CPV = V->castConstant()) { // Constants are constant 151 ValueState[CPV].markConstant(CPV); 152 } else if (V->isMethodArgument()) { // MethodArgs are overdefined 153 ValueState[V].markOverdefined(); 154 } 155 // All others are underdefined by default... 156 return ValueState[V]; 157 } 158 159 // markExecutable - Mark a basic block as executable, adding it to the BB 160 // work list if it is not already executable... 161 // 162 void markExecutable(BasicBlock *BB) { 163 if (BBExecutable.count(BB)) return; 164 //cerr << "Marking BB Executable: " << BB; 165 BBExecutable.insert(BB); // Basic block is executable! 166 BBWorkList.push_back(BB); // Add the block to the work list! 167 } 168 169 170 // UpdateInstruction - Something changed in this instruction... Either an 171 // operand made a transition, or the instruction is newly executable. Change 172 // the value type of I to reflect these changes if appropriate. 173 // 174 void UpdateInstruction(Instruction *I); 175 176 // OperandChangedState - This method is invoked on all of the users of an 177 // instruction that was just changed state somehow.... Based on this 178 // information, we need to update the specified user of this instruction. 179 // 180 void OperandChangedState(User *U); 181 }; 182 183 184 //===----------------------------------------------------------------------===// 185 // SCCP Class Implementation 186 187 188 // doSCCP() - Run the Sparse Conditional Constant Propogation algorithm, and 189 // return true if the method was modified. 190 // 191 bool SCCP::doSCCP() { 192 // Mark the first block of the method as being executable... 193 markExecutable(M->front()); 194 195 // Process the work lists until their are empty! 196 while (!BBWorkList.empty() || !InstWorkList.empty()) { 197 // Process the instruction work list... 198 while (!InstWorkList.empty()) { 199 Instruction *I = InstWorkList.back(); 200 InstWorkList.pop_back(); 201 202 //cerr << "\nPopped off I-WL: " << I; 203 204 205 // "I" got into the work list because it either made the transition from 206 // bottom to constant, or to Overdefined. 207 // 208 // Update all of the users of this instruction's value... 209 // 210 for_each(I->use_begin(), I->use_end(), 211 bind_obj(this, &SCCP::OperandChangedState)); 212 } 213 214 // Process the basic block work list... 215 while (!BBWorkList.empty()) { 216 BasicBlock *BB = BBWorkList.back(); 217 BBWorkList.pop_back(); 218 219 //cerr << "\nPopped off BBWL: " << BB; 220 221 // If this block only has a single successor, mark it as executable as 222 // well... if not, terminate the do loop. 223 // 224 if (BB->getTerminator()->getNumSuccessors() == 1) 225 markExecutable(BB->getTerminator()->getSuccessor(0)); 226 227 // Loop over all of the instructions and notify them that they are newly 228 // executable... 229 for_each(BB->begin(), BB->end(), 230 bind_obj(this, &SCCP::UpdateInstruction)); 231 } 232 } 233 234 #if 0 235 for (Method::iterator BBI = M->begin(), BBEnd = M->end(); BBI != BBEnd; ++BBI) 236 if (!BBExecutable.count(*BBI)) 237 cerr << "BasicBlock Dead:" << *BBI; 238 #endif 239 240 241 // Iterate over all of the instructions in a method, replacing them with 242 // constants if we have found them to be of constant values. 243 // 244 bool MadeChanges = false; 245 for (Method::inst_iterator II = M->inst_begin(); II != M->inst_end(); ) { 246 Instruction *Inst = *II; 247 InstVal &IV = ValueState[Inst]; 248 if (IV.isConstant()) { 249 ConstPoolVal *Const = IV.getConstant(); 250 // cerr << "Constant: " << Inst << " is: " << Const; 251 252 // Replaces all of the uses of a variable with uses of the constant. 253 Inst->replaceAllUsesWith(Const); 254 255 // Remove the operator from the list of definitions... 256 Inst->getParent()->getInstList().remove(II.getInstructionIterator()); 257 258 // The new constant inherits the old name of the operator... 259 if (Inst->hasName() && !Const->hasName()) 260 Const->setName(Inst->getName()); 261 262 // Delete the operator now... 263 delete Inst; 264 265 // Incrementing the iterator in an unchecked manner could mess up the 266 // internals of 'II'. To make sure everything is happy, tell it we might 267 // have broken it. 268 II.resyncInstructionIterator(); 269 270 // Hey, we just changed something! 271 MadeChanges = true; 272 continue; // Skip the ++II at the end of the loop here... 273 } else if (Inst->isTerminator()) { 274 MadeChanges |= opt::ConstantFoldTerminator((TerminatorInst*)Inst); 275 } 276 277 ++II; 278 } 279 280 // Merge identical constants last: this is important because we may have just 281 // introduced constants that already exist, and we don't want to pollute later 282 // stages with extraneous constants. 283 // 284 return MadeChanges | opt::DoConstantPoolMerging(M->getConstantPool()); 285 } 286 287 288 // UpdateInstruction - Something changed in this instruction... Either an 289 // operand made a transition, or the instruction is newly executable. Change 290 // the value type of I to reflect these changes if appropriate. This method 291 // makes sure to do the following actions: 292 // 293 // 1. If a phi node merges two constants in, and has conflicting value coming 294 // from different branches, or if the PHI node merges in an overdefined 295 // value, then the PHI node becomes overdefined. 296 // 2. If a phi node merges only constants in, and they all agree on value, the 297 // PHI node becomes a constant value equal to that. 298 // 3. If V <- x (op) y && isConstant(x) && isConstant(y) V = Constant 299 // 4. If V <- x (op) y && (isOverdefined(x) || isOverdefined(y)) V = Overdefined 300 // 5. If V <- MEM or V <- CALL or V <- (unknown) then V = Overdefined 301 // 6. If a conditional branch has a value that is constant, make the selected 302 // destination executable 303 // 7. If a conditional branch has a value that is overdefined, make all 304 // successors executable. 305 // 306 void SCCP::UpdateInstruction(Instruction *I) { 307 InstVal &IValue = ValueState[I]; 308 if (IValue.isOverdefined()) 309 return; // If already overdefined, we aren't going to effect anything 310 311 switch (I->getOpcode()) { 312 //===-----------------------------------------------------------------===// 313 // Handle PHI nodes... 314 // 315 case Instruction::PHINode: { 316 PHINode *PN = (PHINode*)I; 317 unsigned NumValues = PN->getNumIncomingValues(), i; 318 InstVal *OperandIV = 0; 319 320 // Look at all of the executable operands of the PHI node. If any of them 321 // are overdefined, the PHI becomes overdefined as well. If they are all 322 // constant, and they agree with each other, the PHI becomes the identical 323 // constant. If they are constant and don't agree, the PHI is overdefined. 324 // If there are no executable operands, the PHI remains undefined. 325 // 326 for (i = 0; i < NumValues; ++i) { 327 if (BBExecutable.count(PN->getIncomingBlock(i))) { 328 InstVal &IV = getValueState(PN->getIncomingValue(i)); 329 if (IV.isUndefined()) continue; // Doesn't influence PHI node. 330 if (IV.isOverdefined()) { // PHI node becomes overdefined! 331 markOverdefined(PN); 332 return; 333 } 334 335 if (OperandIV == 0) { // Grab the first value... 336 OperandIV = &IV; 337 } else { // Another value is being merged in! 338 // There is already a reachable operand. If we conflict with it, 339 // then the PHI node becomes overdefined. If we agree with it, we 340 // can continue on. 341 342 // Check to see if there are two different constants merging... 343 if (!IV.getConstant()->equals(OperandIV->getConstant())) { 344 // Yes there is. This means the PHI node is not constant. 345 // You must be overdefined poor PHI. 346 // 347 markOverdefined(I); // The PHI node now becomes overdefined 348 return; // I'm done analyzing you 349 } 350 } 351 } 352 } 353 354 // If we exited the loop, this means that the PHI node only has constant 355 // arguments that agree with each other(and OperandIV is a pointer to one 356 // of their InstVal's) or OperandIV is null because there are no defined 357 // incoming arguments. If this is the case, the PHI remains undefined. 358 // 359 if (OperandIV) { 360 assert(OperandIV->isConstant() && "Should only be here for constants!"); 361 markConstant(I, OperandIV->getConstant()); // Aquire operand value 362 } 363 return; 364 } 365 366 //===-----------------------------------------------------------------===// 367 // Handle instructions that unconditionally provide overdefined values... 368 // 369 case Instruction::Malloc: 370 case Instruction::Free: 371 case Instruction::Alloca: 372 case Instruction::Load: 373 case Instruction::Store: 374 // TODO: getfield/putfield? 375 case Instruction::Call: 376 markOverdefined(I); // Memory and call's are all overdefined 377 return; 378 379 //===-----------------------------------------------------------------===// 380 // Handle Terminator instructions... 381 // 382 case Instruction::Ret: return; // Method return doesn't affect anything 383 case Instruction::Br: { // Handle conditional branches... 384 BranchInst *BI = (BranchInst*)I; 385 if (BI->isUnconditional()) 386 return; // Unconditional branches are already handled! 387 388 InstVal &BCValue = getValueState(BI->getCondition()); 389 if (BCValue.isOverdefined()) { 390 // Overdefined condition variables mean the branch could go either way. 391 markExecutable(BI->getSuccessor(0)); 392 markExecutable(BI->getSuccessor(1)); 393 } else if (BCValue.isConstant()) { 394 // Constant condition variables mean the branch can only go a single way. 395 ConstPoolBool *CPB = (ConstPoolBool*)BCValue.getConstant(); 396 if (CPB->getValue()) // If the branch condition is TRUE... 397 markExecutable(BI->getSuccessor(0)); 398 else // Else if the br cond is FALSE... 399 markExecutable(BI->getSuccessor(1)); 400 } 401 return; 402 } 403 404 case Instruction::Switch: { 405 SwitchInst *SI = (SwitchInst*)I; 406 InstVal &SCValue = getValueState(SI->getCondition()); 407 if (SCValue.isOverdefined()) { // Overdefined condition? All dests are exe 408 for(unsigned i = 0; BasicBlock *Succ = SI->getSuccessor(i); ++i) 409 markExecutable(Succ); 410 } else if (SCValue.isConstant()) { 411 ConstPoolVal *CPV = SCValue.getConstant(); 412 // Make sure to skip the "default value" which isn't a value 413 for (unsigned i = 1, E = SI->getNumSuccessors(); i != E; ++i) { 414 if (SI->getSuccessorValue(i)->equals(CPV)) {// Found the right branch... 415 markExecutable(SI->getSuccessor(i)); 416 return; 417 } 418 } 419 420 // Constant value not equal to any of the branches... must execute 421 // default branch then... 422 markExecutable(SI->getDefaultDest()); 423 } 424 return; 425 } 426 427 default: break; // Handle math operators as groups. 428 } // end switch(I->getOpcode()) 429 430 431 //===-------------------------------------------------------------------===// 432 // Handle Unary instructions... 433 // Also treated as unary here, are cast instructions and getelementptr 434 // instructions on struct* operands. 435 // 436 if (I->isUnaryOp() || I->getOpcode() == Instruction::Cast || 437 (I->getOpcode() == Instruction::GetElementPtr && 438 ((GetElementPtrInst*)I)->isStructSelector())) { 439 440 Value *V = I->getOperand(0); 441 InstVal &VState = getValueState(V); 442 if (VState.isOverdefined()) { // Inherit overdefinedness of operand 443 markOverdefined(I); 444 } else if (VState.isConstant()) { // Propogate constant value 445 ConstPoolVal *Result = 446 opt::ConstantFoldUnaryInstruction(I->getOpcode(), 447 VState.getConstant()); 448 449 if (Result) { 450 // This instruction constant folds! The only problem is that the value 451 // returned is newly allocated. Make sure to stick it into the methods 452 // constant pool... 453 M->getConstantPool().insert(Result); 454 markConstant(I, Result); 455 } else { 456 markOverdefined(I); // Don't know how to fold this instruction. :( 457 } 458 } 459 return; 460 } 461 462 //===-----------------------------------------------------------------===// 463 // Handle Binary instructions... 464 // 465 if (I->isBinaryOp() || I->getOpcode() == Instruction::Shl || 466 I->getOpcode() == Instruction::Shr) { 467 Value *V1 = I->getOperand(0); 468 Value *V2 = I->getOperand(1); 469 470 InstVal &V1State = getValueState(V1); 471 InstVal &V2State = getValueState(V2); 472 if (V1State.isOverdefined() || V2State.isOverdefined()) { 473 markOverdefined(I); 474 } else if (V1State.isConstant() && V2State.isConstant()) { 475 ConstPoolVal *Result = 476 opt::ConstantFoldBinaryInstruction(I->getOpcode(), 477 V1State.getConstant(), 478 V2State.getConstant()); 479 if (Result) { 480 // This instruction constant folds! The only problem is that the value 481 // returned is newly allocated. Make sure to stick it into the methods 482 // constant pool... 483 M->getConstantPool().insert(Result); 484 markConstant(I, Result); 485 } else { 486 markOverdefined(I); // Don't know how to fold this instruction. :( 487 } 488 } 489 return; 490 } 491 492 // Shouldn't get here... either the switch statement or one of the group 493 // handlers should have kicked in... 494 // 495 cerr << "SCCP: Don't know how to handle: " << I; 496 markOverdefined(I); // Just in case 497 } 498 499 500 501 // OperandChangedState - This method is invoked on all of the users of an 502 // instruction that was just changed state somehow.... Based on this 503 // information, we need to update the specified user of this instruction. 504 // 505 void SCCP::OperandChangedState(User *U) { 506 // Only instructions use other variable values! 507 Instruction *I = U->castInstructionAsserting(); 508 if (!BBExecutable.count(I->getParent())) return; // Inst not executable yet! 509 510 UpdateInstruction(I); 511 } 512 513 514 // DoSparseConditionalConstantProp - Use Sparse Conditional Constant Propogation 515 // to prove whether a value is constant and whether blocks are used. 516 // 517 bool opt::DoSCCP(Method *M) { 518 SCCP S(M); 519 return S.doSCCP(); 520 } 521