ConstantProp.cpp revision 081c34b725980f995be9080eaec24cd3dfaaf065
182c89b9f3a9b88bb63ce13b09b4f27fbb72f66fcMisha Brukman//===- ConstantProp.cpp - Code to perform Simple Constant Propagation -----===// 2fd93908ae8b9684fe71c239e3c6cfe13ff6a2663Misha Brukman// 3b576c94c15af9a440f69d9d03c2afead7971118cJohn Criswell// The LLVM Compiler Infrastructure 4b576c94c15af9a440f69d9d03c2afead7971118cJohn Criswell// 54ee451de366474b9c228b4e5fa573795a715216dChris Lattner// This file is distributed under the University of Illinois Open Source 64ee451de366474b9c228b4e5fa573795a715216dChris Lattner// License. See LICENSE.TXT for details. 7fd93908ae8b9684fe71c239e3c6cfe13ff6a2663Misha Brukman// 8b576c94c15af9a440f69d9d03c2afead7971118cJohn Criswell//===----------------------------------------------------------------------===// 9009505452b713ed2e3a8e99c5545a6e721c65495Chris Lattner// 1082c89b9f3a9b88bb63ce13b09b4f27fbb72f66fcMisha Brukman// This file implements constant propagation and merging: 11009505452b713ed2e3a8e99c5545a6e721c65495Chris Lattner// 12009505452b713ed2e3a8e99c5545a6e721c65495Chris Lattner// Specifically, this: 1389df1b58a968506af2abba9e6f7d73c1e43b5d57Chris Lattner// * Converts instructions like "add int 1, 2" into 3 14009505452b713ed2e3a8e99c5545a6e721c65495Chris Lattner// 15009505452b713ed2e3a8e99c5545a6e721c65495Chris Lattner// Notice that: 16009505452b713ed2e3a8e99c5545a6e721c65495Chris Lattner// * This pass has a habit of making definitions be dead. It is a good idea 1758921feaa9340fb32e2a01ef3cdca6caf8b71e1cDuncan Sands// to run a DIE pass sometime after running this pass. 18009505452b713ed2e3a8e99c5545a6e721c65495Chris Lattner// 19009505452b713ed2e3a8e99c5545a6e721c65495Chris Lattner//===----------------------------------------------------------------------===// 20009505452b713ed2e3a8e99c5545a6e721c65495Chris Lattner 210e5f499638c8d277b9dc4a4385712177c53b5681Chris Lattner#define DEBUG_TYPE "constprop" 22022103b3f33febb7e54b8fdf2c9bc461eea78cbaChris Lattner#include "llvm/Transforms/Scalar.h" 2379066fa6acce02c97c714a5a6e151ed8a249721cChris Lattner#include "llvm/Analysis/ConstantFolding.h" 24b6ac8bc586f7d7a2c07e3d3141a77c8e0cc1bb5dChris Lattner#include "llvm/Constant.h" 252ed01d8f0bdb8aa73d893a8beb23b1838422fa32Chris Lattner#include "llvm/Instruction.h" 26bd0ef77cde9c9e82f2b4ad33e4982c46274d6540Chris Lattner#include "llvm/Pass.h" 2789df1b58a968506af2abba9e6f7d73c1e43b5d57Chris Lattner#include "llvm/Support/InstIterator.h" 28551ccae044b0ff658fe629dd67edd5ffe75d10e8Reid Spencer#include "llvm/ADT/Statistic.h" 2989df1b58a968506af2abba9e6f7d73c1e43b5d57Chris Lattner#include <set> 30d7456026629fc1760a45e6e955e9834246493147Chris Lattnerusing namespace llvm; 31d0fde30ce850b78371fd1386338350591f9ff494Brian Gaeke 320e5f499638c8d277b9dc4a4385712177c53b5681Chris LattnerSTATISTIC(NumInstKilled, "Number of instructions killed"); 33a92f696b74a99325026ebbdbffd2a44317e0c10bChris Lattner 340e5f499638c8d277b9dc4a4385712177c53b5681Chris Lattnernamespace { 353e8b6631e67e01e4960a7ba4668a50c596607473Chris Lattner struct ConstantPropagation : public FunctionPass { 36ecd94c804a563f2a86572dcf1d2e81f397e19daaNick Lewycky static char ID; // Pass identification, replacement for typeid 37081c34b725980f995be9080eaec24cd3dfaaf065Owen Anderson ConstantPropagation() : FunctionPass(ID) { 38081c34b725980f995be9080eaec24cd3dfaaf065Owen Anderson initializeConstantPropagationPass(*PassRegistry::getPassRegistry()); 39081c34b725980f995be9080eaec24cd3dfaaf065Owen Anderson } 40794fd75c67a2cdc128d67342c6d88a504d186896Devang Patel 417e70829632f82de15db187845666aaca6e04b792Chris Lattner bool runOnFunction(Function &F); 4297e52e43361e77963145b95a576db11b4d14d309Chris Lattner 4397e52e43361e77963145b95a576db11b4d14d309Chris Lattner virtual void getAnalysisUsage(AnalysisUsage &AU) const { 44cb2610ea037a17115ef3a01a6bdaab4e3cfdca27Chris Lattner AU.setPreservesCFG(); 4597e52e43361e77963145b95a576db11b4d14d309Chris Lattner } 46bd0ef77cde9c9e82f2b4ad33e4982c46274d6540Chris Lattner }; 47bd0ef77cde9c9e82f2b4ad33e4982c46274d6540Chris Lattner} 48009505452b713ed2e3a8e99c5545a6e721c65495Chris Lattner 49844731a7f1909f55935e3514c9e713a62d67662eDan Gohmanchar ConstantPropagation::ID = 0; 50d13db2c59cc94162d6cf0a04187d408bfef6d4a7Owen AndersonINITIALIZE_PASS(ConstantPropagation, "constprop", 51ce665bd2e2b581ab0858d1afe359192bac96b868Owen Anderson "Simple constant propagation", false, false) 52844731a7f1909f55935e3514c9e713a62d67662eDan Gohman 534b5015604908e9296800991a7c538a255356428fChris LattnerFunctionPass *llvm::createConstantPropagationPass() { 5482c89b9f3a9b88bb63ce13b09b4f27fbb72f66fcMisha Brukman return new ConstantPropagation(); 55009505452b713ed2e3a8e99c5545a6e721c65495Chris Lattner} 56bd0ef77cde9c9e82f2b4ad33e4982c46274d6540Chris Lattner 5789df1b58a968506af2abba9e6f7d73c1e43b5d57Chris Lattner 5882c89b9f3a9b88bb63ce13b09b4f27fbb72f66fcMisha Brukmanbool ConstantPropagation::runOnFunction(Function &F) { 5989df1b58a968506af2abba9e6f7d73c1e43b5d57Chris Lattner // Initialize the worklist to all of the instructions ready to process... 606ffe551f657c948d6a473a198ecbd1188bf9ce45Chris Lattner std::set<Instruction*> WorkList; 616ffe551f657c948d6a473a198ecbd1188bf9ce45Chris Lattner for(inst_iterator i = inst_begin(F), e = inst_end(F); i != e; ++i) { 626ffe551f657c948d6a473a198ecbd1188bf9ce45Chris Lattner WorkList.insert(&*i); 636ffe551f657c948d6a473a198ecbd1188bf9ce45Chris Lattner } 6489df1b58a968506af2abba9e6f7d73c1e43b5d57Chris Lattner bool Changed = false; 6589df1b58a968506af2abba9e6f7d73c1e43b5d57Chris Lattner 6689df1b58a968506af2abba9e6f7d73c1e43b5d57Chris Lattner while (!WorkList.empty()) { 6789df1b58a968506af2abba9e6f7d73c1e43b5d57Chris Lattner Instruction *I = *WorkList.begin(); 6889df1b58a968506af2abba9e6f7d73c1e43b5d57Chris Lattner WorkList.erase(WorkList.begin()); // Get an element from the worklist... 6989df1b58a968506af2abba9e6f7d73c1e43b5d57Chris Lattner 7089df1b58a968506af2abba9e6f7d73c1e43b5d57Chris Lattner if (!I->use_empty()) // Don't muck with dead instructions... 717b550ccfc5a3346c17e0390a59e2d6d19bc52705Chris Lattner if (Constant *C = ConstantFoldInstruction(I)) { 7289df1b58a968506af2abba9e6f7d73c1e43b5d57Chris Lattner // Add all of the users of this instruction to the worklist, they might 7382c89b9f3a9b88bb63ce13b09b4f27fbb72f66fcMisha Brukman // be constant propagatable now... 7489df1b58a968506af2abba9e6f7d73c1e43b5d57Chris Lattner for (Value::use_iterator UI = I->use_begin(), UE = I->use_end(); 7589df1b58a968506af2abba9e6f7d73c1e43b5d57Chris Lattner UI != UE; ++UI) 7689df1b58a968506af2abba9e6f7d73c1e43b5d57Chris Lattner WorkList.insert(cast<Instruction>(*UI)); 77fd93908ae8b9684fe71c239e3c6cfe13ff6a2663Misha Brukman 7889df1b58a968506af2abba9e6f7d73c1e43b5d57Chris Lattner // Replace all of the uses of a variable with uses of the constant. 7989df1b58a968506af2abba9e6f7d73c1e43b5d57Chris Lattner I->replaceAllUsesWith(C); 803dec1f272219ee1f8e1499929cdf53f5bc3c2272Chris Lattner 814647b7cd6929990ff174f0dd7cbfda5ab40df850Chris Lattner // Remove the dead instruction. 824647b7cd6929990ff174f0dd7cbfda5ab40df850Chris Lattner WorkList.erase(I); 831adec83ae84031bfa9f0bf209c5ee6c64906a1ffDan Gohman I->eraseFromParent(); 844647b7cd6929990ff174f0dd7cbfda5ab40df850Chris Lattner 8589df1b58a968506af2abba9e6f7d73c1e43b5d57Chris Lattner // We made a change to the function... 8689df1b58a968506af2abba9e6f7d73c1e43b5d57Chris Lattner Changed = true; 873dec1f272219ee1f8e1499929cdf53f5bc3c2272Chris Lattner ++NumInstKilled; 8889df1b58a968506af2abba9e6f7d73c1e43b5d57Chris Lattner } 8989df1b58a968506af2abba9e6f7d73c1e43b5d57Chris Lattner } 9089df1b58a968506af2abba9e6f7d73c1e43b5d57Chris Lattner return Changed; 9189df1b58a968506af2abba9e6f7d73c1e43b5d57Chris Lattner} 92