SCCP.cpp revision bd0ef77cde9c9e82f2b4ad33e4982c46274d6540
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/Transforms/Scalar/ConstantProp.h" 19#include "llvm/Transforms/Scalar/ConstantHandling.h" 20#include "llvm/Method.h" 21#include "llvm/BasicBlock.h" 22#include "llvm/ConstantVals.h" 23#include "llvm/InstrTypes.h" 24#include "llvm/iPHINode.h" 25#include "llvm/iMemory.h" 26#include "llvm/iTerminators.h" 27#include "llvm/iOther.h" 28#include "llvm/Pass.h" 29#include "llvm/Assembly/Writer.h" 30#include "Support/STLExtras.h" 31#include <algorithm> 32#include <map> 33#include <set> 34#include <iostream> 35using std::cerr; 36 37// InstVal class - This class represents the different lattice values that an 38// instruction may occupy. It is a simple class with value semantics. The 39// potential constant value that is pointed to is owned by the constant pool 40// for the method being optimized. 41// 42class InstVal { 43 enum { 44 undefined, // This instruction has no known value 45 constant, // This instruction has a constant value 46 // Range, // This instruction is known to fall within a range 47 overdefined // This instruction has an unknown value 48 } LatticeValue; // The current lattice position 49 Constant *ConstantVal; // If Constant value, the current value 50public: 51 inline InstVal() : LatticeValue(undefined), ConstantVal(0) {} 52 53 // markOverdefined - Return true if this is a new status to be in... 54 inline bool markOverdefined() { 55 if (LatticeValue != overdefined) { 56 LatticeValue = overdefined; 57 return true; 58 } 59 return false; 60 } 61 62 // markConstant - Return true if this is a new status for us... 63 inline bool markConstant(Constant *V) { 64 if (LatticeValue != constant) { 65 LatticeValue = constant; 66 ConstantVal = V; 67 return true; 68 } else { 69 assert(ConstantVal == V && "Marking constant with different value"); 70 } 71 return false; 72 } 73 74 inline bool isUndefined() const { return LatticeValue == undefined; } 75 inline bool isConstant() const { return LatticeValue == constant; } 76 inline bool isOverdefined() const { return LatticeValue == overdefined; } 77 78 inline Constant *getConstant() const { return ConstantVal; } 79}; 80 81 82 83//===----------------------------------------------------------------------===// 84// SCCP Class 85// 86// This class does all of the work of Sparse Conditional Constant Propogation. 87// It's public interface consists of a constructor and a doSCCP() method. 88// 89class SCCP { 90 Method *M; // The method that we are working on... 91 92 std::set<BasicBlock*> BBExecutable;// The basic blocks that are executable 93 std::map<Value*, InstVal> ValueState; // The state each value is in... 94 95 std::vector<Instruction*> InstWorkList;// The instruction work list 96 std::vector<BasicBlock*> BBWorkList; // The BasicBlock work list 97 98 //===--------------------------------------------------------------------===// 99 // The public interface for this class 100 // 101public: 102 103 // SCCP Ctor - Save the method to operate on... 104 inline SCCP(Method *m) : M(m) {} 105 106 // doSCCP() - Run the Sparse Conditional Constant Propogation algorithm, and 107 // return true if the method was modified. 108 bool doSCCP(); 109 110 //===--------------------------------------------------------------------===// 111 // The implementation of this class 112 // 113private: 114 115 // markValueOverdefined - Make a value be marked as "constant". If the value 116 // is not already a constant, add it to the instruction work list so that 117 // the users of the instruction are updated later. 118 // 119 inline bool markConstant(Instruction *I, Constant *V) { 120 //cerr << "markConstant: " << V << " = " << I; 121 if (ValueState[I].markConstant(V)) { 122 InstWorkList.push_back(I); 123 return true; 124 } 125 return false; 126 } 127 128 // markValueOverdefined - Make a value be marked as "overdefined". If the 129 // value is not already overdefined, add it to the instruction work list so 130 // that the users of the instruction are updated later. 131 // 132 inline bool markOverdefined(Value *V) { 133 if (ValueState[V].markOverdefined()) { 134 if (Instruction *I = dyn_cast<Instruction>(V)) { 135 //cerr << "markOverdefined: " << V; 136 InstWorkList.push_back(I); // Only instructions go on the work list 137 } 138 return true; 139 } 140 return false; 141 } 142 143 // getValueState - Return the InstVal object that corresponds to the value. 144 // This function is neccesary because not all values should start out in the 145 // underdefined state... MethodArgument's should be overdefined, and constants 146 // should be marked as constants. If a value is not known to be an 147 // Instruction object, then use this accessor to get its value from the map. 148 // 149 inline InstVal &getValueState(Value *V) { 150 std::map<Value*, InstVal>::iterator I = ValueState.find(V); 151 if (I != ValueState.end()) return I->second; // Common case, in the map 152 153 if (Constant *CPV = dyn_cast<Constant>(V)) { // Constants are constant 154 ValueState[CPV].markConstant(CPV); 155 } else if (isa<MethodArgument>(V)) { // MethodArgs are overdefined 156 ValueState[V].markOverdefined(); 157 } 158 // All others are underdefined by default... 159 return ValueState[V]; 160 } 161 162 // markExecutable - Mark a basic block as executable, adding it to the BB 163 // work list if it is not already executable... 164 // 165 void markExecutable(BasicBlock *BB) { 166 if (BBExecutable.count(BB)) return; 167 //cerr << "Marking BB Executable: " << BB; 168 BBExecutable.insert(BB); // Basic block is executable! 169 BBWorkList.push_back(BB); // Add the block to the work list! 170 } 171 172 173 // UpdateInstruction - Something changed in this instruction... Either an 174 // operand made a transition, or the instruction is newly executable. Change 175 // the value type of I to reflect these changes if appropriate. 176 // 177 void UpdateInstruction(Instruction *I); 178 179 // OperandChangedState - This method is invoked on all of the users of an 180 // instruction that was just changed state somehow.... Based on this 181 // information, we need to update the specified user of this instruction. 182 // 183 void OperandChangedState(User *U); 184}; 185 186 187//===----------------------------------------------------------------------===// 188// SCCP Class Implementation 189 190 191// doSCCP() - Run the Sparse Conditional Constant Propogation algorithm, and 192// return true if the method was modified. 193// 194bool SCCP::doSCCP() { 195 // Mark the first block of the method as being executable... 196 markExecutable(M->front()); 197 198 // Process the work lists until their are empty! 199 while (!BBWorkList.empty() || !InstWorkList.empty()) { 200 // Process the instruction work list... 201 while (!InstWorkList.empty()) { 202 Instruction *I = InstWorkList.back(); 203 InstWorkList.pop_back(); 204 205 //cerr << "\nPopped off I-WL: " << I; 206 207 208 // "I" got into the work list because it either made the transition from 209 // bottom to constant, or to Overdefined. 210 // 211 // Update all of the users of this instruction's value... 212 // 213 for_each(I->use_begin(), I->use_end(), 214 bind_obj(this, &SCCP::OperandChangedState)); 215 } 216 217 // Process the basic block work list... 218 while (!BBWorkList.empty()) { 219 BasicBlock *BB = BBWorkList.back(); 220 BBWorkList.pop_back(); 221 222 //cerr << "\nPopped off BBWL: " << BB; 223 224 // If this block only has a single successor, mark it as executable as 225 // well... if not, terminate the do loop. 226 // 227 if (BB->getTerminator()->getNumSuccessors() == 1) 228 markExecutable(BB->getTerminator()->getSuccessor(0)); 229 230 // Loop over all of the instructions and notify them that they are newly 231 // executable... 232 for_each(BB->begin(), BB->end(), 233 bind_obj(this, &SCCP::UpdateInstruction)); 234 } 235 } 236 237#if 0 238 for (Method::iterator BBI = M->begin(), BBEnd = M->end(); BBI != BBEnd; ++BBI) 239 if (!BBExecutable.count(*BBI)) 240 cerr << "BasicBlock Dead:" << *BBI; 241#endif 242 243 244 // Iterate over all of the instructions in a method, replacing them with 245 // constants if we have found them to be of constant values. 246 // 247 bool MadeChanges = false; 248 for (Method::iterator MI = M->begin(), ME = M->end(); MI != ME; ++MI) { 249 BasicBlock *BB = *MI; 250 for (BasicBlock::iterator BI = BB->begin(); BI != BB->end();) { 251 Instruction *Inst = *BI; 252 InstVal &IV = ValueState[Inst]; 253 if (IV.isConstant()) { 254 Constant *Const = IV.getConstant(); 255 // cerr << "Constant: " << Inst << " is: " << Const; 256 257 // Replaces all of the uses of a variable with uses of the constant. 258 Inst->replaceAllUsesWith(Const); 259 260 // Remove the operator from the list of definitions... 261 BB->getInstList().remove(BI); 262 263 // The new constant inherits the old name of the operator... 264 if (Inst->hasName() && !Const->hasName()) 265 Const->setName(Inst->getName(), M->getSymbolTableSure()); 266 267 // Delete the operator now... 268 delete Inst; 269 270 // Hey, we just changed something! 271 MadeChanges = true; 272 } else if (TerminatorInst *TI = dyn_cast<TerminatorInst>(Inst)) { 273 MadeChanges |= ConstantFoldTerminator(TI); 274 } 275 276 ++BI; 277 } 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; 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// 306void 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 = cast<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() != 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 375 case Instruction::Call: 376 case Instruction::Invoke: 377 markOverdefined(I); // Memory and call's are all overdefined 378 return; 379 380 //===-----------------------------------------------------------------===// 381 // Handle Terminator instructions... 382 // 383 case Instruction::Ret: return; // Method return doesn't affect anything 384 case Instruction::Br: { // Handle conditional branches... 385 BranchInst *BI = cast<BranchInst>(I); 386 if (BI->isUnconditional()) 387 return; // Unconditional branches are already handled! 388 389 InstVal &BCValue = getValueState(BI->getCondition()); 390 if (BCValue.isOverdefined()) { 391 // Overdefined condition variables mean the branch could go either way. 392 markExecutable(BI->getSuccessor(0)); 393 markExecutable(BI->getSuccessor(1)); 394 } else if (BCValue.isConstant()) { 395 // Constant condition variables mean the branch can only go a single way. 396 ConstantBool *CPB = cast<ConstantBool>(BCValue.getConstant()); 397 if (CPB->getValue()) // If the branch condition is TRUE... 398 markExecutable(BI->getSuccessor(0)); 399 else // Else if the br cond is FALSE... 400 markExecutable(BI->getSuccessor(1)); 401 } 402 return; 403 } 404 405 case Instruction::Switch: { 406 SwitchInst *SI = cast<SwitchInst>(I); 407 InstVal &SCValue = getValueState(SI->getCondition()); 408 if (SCValue.isOverdefined()) { // Overdefined condition? All dests are exe 409 for(unsigned i = 0; BasicBlock *Succ = SI->getSuccessor(i); ++i) 410 markExecutable(Succ); 411 } else if (SCValue.isConstant()) { 412 Constant *CPV = SCValue.getConstant(); 413 // Make sure to skip the "default value" which isn't a value 414 for (unsigned i = 1, E = SI->getNumSuccessors(); i != E; ++i) { 415 if (SI->getSuccessorValue(i) == CPV) {// Found the right branch... 416 markExecutable(SI->getSuccessor(i)); 417 return; 418 } 419 } 420 421 // Constant value not equal to any of the branches... must execute 422 // default branch then... 423 markExecutable(SI->getDefaultDest()); 424 } 425 return; 426 } 427 428 default: break; // Handle math operators as groups. 429 } // end switch(I->getOpcode()) 430 431 432 //===-------------------------------------------------------------------===// 433 // Handle Unary instructions... 434 // Also treated as unary here, are cast instructions and getelementptr 435 // instructions on struct* operands. 436 // 437 if (isa<UnaryOperator>(I) || isa<CastInst>(I) || 438 (isa<GetElementPtrInst>(I) && 439 cast<GetElementPtrInst>(I)->isStructSelector())) { 440 441 Value *V = I->getOperand(0); 442 InstVal &VState = getValueState(V); 443 if (VState.isOverdefined()) { // Inherit overdefinedness of operand 444 markOverdefined(I); 445 } else if (VState.isConstant()) { // Propogate constant value 446 Constant *Result = isa<CastInst>(I) 447 ? ConstantFoldCastInstruction(VState.getConstant(), I->getType()) 448 : ConstantFoldUnaryInstruction(I->getOpcode(), VState.getConstant()); 449 450 if (Result) { 451 // This instruction constant folds! 452 markConstant(I, Result); 453 } else { 454 markOverdefined(I); // Don't know how to fold this instruction. :( 455 } 456 } 457 return; 458 } 459 460 //===-----------------------------------------------------------------===// 461 // Handle Binary instructions... 462 // 463 if (isa<BinaryOperator>(I) || isa<ShiftInst>(I)) { 464 Value *V1 = I->getOperand(0); 465 Value *V2 = I->getOperand(1); 466 467 InstVal &V1State = getValueState(V1); 468 InstVal &V2State = getValueState(V2); 469 if (V1State.isOverdefined() || V2State.isOverdefined()) { 470 markOverdefined(I); 471 } else if (V1State.isConstant() && V2State.isConstant()) { 472 Constant *Result = 473 ConstantFoldBinaryInstruction(I->getOpcode(), 474 V1State.getConstant(), 475 V2State.getConstant()); 476 if (Result) { 477 // This instruction constant folds! 478 markConstant(I, Result); 479 } else { 480 markOverdefined(I); // Don't know how to fold this instruction. :( 481 } 482 } 483 return; 484 } 485 486 // Shouldn't get here... either the switch statement or one of the group 487 // handlers should have kicked in... 488 // 489 cerr << "SCCP: Don't know how to handle: " << I; 490 markOverdefined(I); // Just in case 491} 492 493 494 495// OperandChangedState - This method is invoked on all of the users of an 496// instruction that was just changed state somehow.... Based on this 497// information, we need to update the specified user of this instruction. 498// 499void SCCP::OperandChangedState(User *U) { 500 // Only instructions use other variable values! 501 Instruction *I = cast<Instruction>(U); 502 if (!BBExecutable.count(I->getParent())) return; // Inst not executable yet! 503 504 UpdateInstruction(I); 505} 506 507namespace { 508 // SCCPPass - Use Sparse Conditional Constant Propogation 509 // to prove whether a value is constant and whether blocks are used. 510 // 511 struct SCCPPass : public MethodPass { 512 inline bool runOnMethod(Method *M) { 513 SCCP S(M); 514 return S.doSCCP(); 515 } 516 }; 517} 518 519Pass *createSCCPPass() { 520 return new SCCPPass(); 521} 522