SCCP.cpp revision 968ddc921e70d098923a6dc585f86b6ebc3fd13e
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/ConstantHandling.h" 20#include "llvm/Function.h" 21#include "llvm/BasicBlock.h" 22#include "llvm/ConstantVals.h" 23#include "llvm/iPHINode.h" 24#include "llvm/iMemory.h" 25#include "llvm/iTerminators.h" 26#include "llvm/iOther.h" 27#include "llvm/Pass.h" 28#include "llvm/Assembly/Writer.h" 29#include "Support/STLExtras.h" 30#include <algorithm> 31#include <map> 32#include <set> 33#include <iostream> 34using std::cerr; 35 36// InstVal class - This class represents the different lattice values that an 37// instruction may occupy. It is a simple class with value semantics. The 38// potential constant value that is pointed to is owned by the constant pool 39// for the method being optimized. 40// 41class InstVal { 42 enum { 43 undefined, // This instruction has no known value 44 constant, // This instruction has a constant value 45 // Range, // This instruction is known to fall within a range 46 overdefined // This instruction has an unknown value 47 } LatticeValue; // The current lattice position 48 Constant *ConstantVal; // If Constant value, the current value 49public: 50 inline InstVal() : LatticeValue(undefined), ConstantVal(0) {} 51 52 // markOverdefined - Return true if this is a new status to be in... 53 inline bool markOverdefined() { 54 if (LatticeValue != overdefined) { 55 LatticeValue = overdefined; 56 return true; 57 } 58 return false; 59 } 60 61 // markConstant - Return true if this is a new status for us... 62 inline bool markConstant(Constant *V) { 63 if (LatticeValue != constant) { 64 LatticeValue = constant; 65 ConstantVal = V; 66 return true; 67 } else { 68 assert(ConstantVal == V && "Marking constant with different value"); 69 } 70 return false; 71 } 72 73 inline bool isUndefined() const { return LatticeValue == undefined; } 74 inline bool isConstant() const { return LatticeValue == constant; } 75 inline bool isOverdefined() const { return LatticeValue == overdefined; } 76 77 inline Constant *getConstant() const { return ConstantVal; } 78}; 79 80 81 82//===----------------------------------------------------------------------===// 83// SCCP Class 84// 85// This class does all of the work of Sparse Conditional Constant Propogation. 86// It's public interface consists of a constructor and a doSCCP() method. 87// 88class SCCP { 89 Function *M; // The function that we are working on 90 91 std::set<BasicBlock*> BBExecutable;// The basic blocks that are executable 92 std::map<Value*, InstVal> ValueState; // The state each value is in... 93 94 std::vector<Instruction*> InstWorkList;// The instruction work list 95 std::vector<BasicBlock*> BBWorkList; // The BasicBlock work list 96 97 //===--------------------------------------------------------------------===// 98 // The public interface for this class 99 // 100public: 101 102 // SCCP Ctor - Save the method to operate on... 103 inline SCCP(Function *f) : M(f) {} 104 105 // doSCCP() - Run the Sparse Conditional Constant Propogation algorithm, and 106 // return true if the method was modified. 107 bool doSCCP(); 108 109 //===--------------------------------------------------------------------===// 110 // The implementation of this class 111 // 112private: 113 114 // markValueOverdefined - Make a value be marked as "constant". If the value 115 // is not already a constant, add it to the instruction work list so that 116 // the users of the instruction are updated later. 117 // 118 inline bool markConstant(Instruction *I, Constant *V) { 119 //cerr << "markConstant: " << V << " = " << I; 120 if (ValueState[I].markConstant(V)) { 121 InstWorkList.push_back(I); 122 return true; 123 } 124 return false; 125 } 126 127 // markValueOverdefined - Make a value be marked as "overdefined". If the 128 // value is not already overdefined, add it to the instruction work list so 129 // that the users of the instruction are updated later. 130 // 131 inline bool markOverdefined(Value *V) { 132 if (ValueState[V].markOverdefined()) { 133 if (Instruction *I = dyn_cast<Instruction>(V)) { 134 //cerr << "markOverdefined: " << V; 135 InstWorkList.push_back(I); // Only instructions go on the work list 136 } 137 return true; 138 } 139 return false; 140 } 141 142 // getValueState - Return the InstVal object that corresponds to the value. 143 // This function is neccesary because not all values should start out in the 144 // underdefined state... FunctionArgument's should be overdefined, and 145 // constants should be marked as constants. If a value is not known to be an 146 // Instruction object, then use this accessor to get its value from the map. 147 // 148 inline InstVal &getValueState(Value *V) { 149 std::map<Value*, InstVal>::iterator I = ValueState.find(V); 150 if (I != ValueState.end()) return I->second; // Common case, in the map 151 152 if (Constant *CPV = dyn_cast<Constant>(V)) { // Constants are constant 153 ValueState[CPV].markConstant(CPV); 154 } else if (isa<FunctionArgument>(V)) { // FuncArgs are overdefined 155 ValueState[V].markOverdefined(); 156 } 157 // All others are underdefined by default... 158 return ValueState[V]; 159 } 160 161 // markExecutable - Mark a basic block as executable, adding it to the BB 162 // work list if it is not already executable... 163 // 164 void markExecutable(BasicBlock *BB) { 165 if (BBExecutable.count(BB)) return; 166 //cerr << "Marking BB Executable: " << BB; 167 BBExecutable.insert(BB); // Basic block is executable! 168 BBWorkList.push_back(BB); // Add the block to the work list! 169 } 170 171 172 // UpdateInstruction - Something changed in this instruction... Either an 173 // operand made a transition, or the instruction is newly executable. Change 174 // the value type of I to reflect these changes if appropriate. 175 // 176 void UpdateInstruction(Instruction *I); 177 178 // OperandChangedState - This method is invoked on all of the users of an 179 // instruction that was just changed state somehow.... Based on this 180 // information, we need to update the specified user of this instruction. 181 // 182 void OperandChangedState(User *U); 183}; 184 185 186//===----------------------------------------------------------------------===// 187// SCCP Class Implementation 188 189 190// doSCCP() - Run the Sparse Conditional Constant Propogation algorithm, and 191// return true if the method was modified. 192// 193bool SCCP::doSCCP() { 194 // Mark the first block of the method as being executable... 195 markExecutable(M->front()); 196 197 // Process the work lists until their are empty! 198 while (!BBWorkList.empty() || !InstWorkList.empty()) { 199 // Process the instruction work list... 200 while (!InstWorkList.empty()) { 201 Instruction *I = InstWorkList.back(); 202 InstWorkList.pop_back(); 203 204 //cerr << "\nPopped off I-WL: " << I; 205 206 207 // "I" got into the work list because it either made the transition from 208 // bottom to constant, or to Overdefined. 209 // 210 // Update all of the users of this instruction's value... 211 // 212 for_each(I->use_begin(), I->use_end(), 213 bind_obj(this, &SCCP::OperandChangedState)); 214 } 215 216 // Process the basic block work list... 217 while (!BBWorkList.empty()) { 218 BasicBlock *BB = BBWorkList.back(); 219 BBWorkList.pop_back(); 220 221 //cerr << "\nPopped off BBWL: " << BB; 222 223 // If this block only has a single successor, mark it as executable as 224 // well... if not, terminate the do loop. 225 // 226 if (BB->getTerminator()->getNumSuccessors() == 1) 227 markExecutable(BB->getTerminator()->getSuccessor(0)); 228 229 // Loop over all of the instructions and notify them that they are newly 230 // executable... 231 for_each(BB->begin(), BB->end(), 232 bind_obj(this, &SCCP::UpdateInstruction)); 233 } 234 } 235 236#if 0 237 for (Function::iterator BBI = M->begin(), BBEnd = M->end(); 238 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 (Function::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(BB, BI, 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; // Function 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(Function *F) { 513 SCCP S(F); 514 return S.doSCCP(); 515 } 516 }; 517} 518 519Pass *createSCCPPass() { 520 return new SCCPPass(); 521} 522