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 21022103b3f33febb7e54b8fdf2c9bc461eea78cbaChris Lattner#include "llvm/Transforms/Scalar.h" 22d04a8d4b33ff316ca4cf961e06c9e312eff8e64fChandler Carruth#include "llvm/ADT/Statistic.h" 2379066fa6acce02c97c714a5a6e151ed8a249721cChris Lattner#include "llvm/Analysis/ConstantFolding.h" 240b8c9a80f20772c3793201ab5b251d3520b9cea3Chandler Carruth#include "llvm/IR/Constant.h" 250b8c9a80f20772c3793201ab5b251d3520b9cea3Chandler Carruth#include "llvm/IR/DataLayout.h" 2636b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines#include "llvm/IR/InstIterator.h" 270b8c9a80f20772c3793201ab5b251d3520b9cea3Chandler Carruth#include "llvm/IR/Instruction.h" 28bd0ef77cde9c9e82f2b4ad33e4982c46274d6540Chris Lattner#include "llvm/Pass.h" 29d04a8d4b33ff316ca4cf961e06c9e312eff8e64fChandler Carruth#include "llvm/Target/TargetLibraryInfo.h" 3089df1b58a968506af2abba9e6f7d73c1e43b5d57Chris Lattner#include <set> 31d7456026629fc1760a45e6e955e9834246493147Chris Lattnerusing namespace llvm; 32d0fde30ce850b78371fd1386338350591f9ff494Brian Gaeke 33dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines#define DEBUG_TYPE "constprop" 34dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines 350e5f499638c8d277b9dc4a4385712177c53b5681Chris LattnerSTATISTIC(NumInstKilled, "Number of instructions killed"); 36a92f696b74a99325026ebbdbffd2a44317e0c10bChris Lattner 370e5f499638c8d277b9dc4a4385712177c53b5681Chris Lattnernamespace { 383e8b6631e67e01e4960a7ba4668a50c596607473Chris Lattner struct ConstantPropagation : public FunctionPass { 39ecd94c804a563f2a86572dcf1d2e81f397e19daaNick Lewycky static char ID; // Pass identification, replacement for typeid 40081c34b725980f995be9080eaec24cd3dfaaf065Owen Anderson ConstantPropagation() : FunctionPass(ID) { 41081c34b725980f995be9080eaec24cd3dfaaf065Owen Anderson initializeConstantPropagationPass(*PassRegistry::getPassRegistry()); 42081c34b725980f995be9080eaec24cd3dfaaf065Owen Anderson } 43794fd75c67a2cdc128d67342c6d88a504d186896Devang Patel 4436b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines bool runOnFunction(Function &F) override; 4597e52e43361e77963145b95a576db11b4d14d309Chris Lattner 4636b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines void getAnalysisUsage(AnalysisUsage &AU) const override { 47cb2610ea037a17115ef3a01a6bdaab4e3cfdca27Chris Lattner AU.setPreservesCFG(); 4800737bdb488cc7157ca5f7a40d6cd8467ad09a79Chad Rosier AU.addRequired<TargetLibraryInfo>(); 4997e52e43361e77963145b95a576db11b4d14d309Chris Lattner } 50bd0ef77cde9c9e82f2b4ad33e4982c46274d6540Chris Lattner }; 51bd0ef77cde9c9e82f2b4ad33e4982c46274d6540Chris Lattner} 52009505452b713ed2e3a8e99c5545a6e721c65495Chris Lattner 53844731a7f1909f55935e3514c9e713a62d67662eDan Gohmanchar ConstantPropagation::ID = 0; 5400737bdb488cc7157ca5f7a40d6cd8467ad09a79Chad RosierINITIALIZE_PASS_BEGIN(ConstantPropagation, "constprop", 5500737bdb488cc7157ca5f7a40d6cd8467ad09a79Chad Rosier "Simple constant propagation", false, false) 5600737bdb488cc7157ca5f7a40d6cd8467ad09a79Chad RosierINITIALIZE_PASS_DEPENDENCY(TargetLibraryInfo) 5700737bdb488cc7157ca5f7a40d6cd8467ad09a79Chad RosierINITIALIZE_PASS_END(ConstantPropagation, "constprop", 58ce665bd2e2b581ab0858d1afe359192bac96b868Owen Anderson "Simple constant propagation", false, false) 59844731a7f1909f55935e3514c9e713a62d67662eDan Gohman 604b5015604908e9296800991a7c538a255356428fChris LattnerFunctionPass *llvm::createConstantPropagationPass() { 6182c89b9f3a9b88bb63ce13b09b4f27fbb72f66fcMisha Brukman return new ConstantPropagation(); 62009505452b713ed2e3a8e99c5545a6e721c65495Chris Lattner} 63bd0ef77cde9c9e82f2b4ad33e4982c46274d6540Chris Lattner 6482c89b9f3a9b88bb63ce13b09b4f27fbb72f66fcMisha Brukmanbool ConstantPropagation::runOnFunction(Function &F) { 6589df1b58a968506af2abba9e6f7d73c1e43b5d57Chris Lattner // Initialize the worklist to all of the instructions ready to process... 666ffe551f657c948d6a473a198ecbd1188bf9ce45Chris Lattner std::set<Instruction*> WorkList; 676ffe551f657c948d6a473a198ecbd1188bf9ce45Chris Lattner for(inst_iterator i = inst_begin(F), e = inst_end(F); i != e; ++i) { 686ffe551f657c948d6a473a198ecbd1188bf9ce45Chris Lattner WorkList.insert(&*i); 696ffe551f657c948d6a473a198ecbd1188bf9ce45Chris Lattner } 7089df1b58a968506af2abba9e6f7d73c1e43b5d57Chris Lattner bool Changed = false; 7136b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines DataLayoutPass *DLP = getAnalysisIfAvailable<DataLayoutPass>(); 72dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines const DataLayout *DL = DLP ? &DLP->getDataLayout() : nullptr; 7300737bdb488cc7157ca5f7a40d6cd8467ad09a79Chad Rosier TargetLibraryInfo *TLI = &getAnalysis<TargetLibraryInfo>(); 7489df1b58a968506af2abba9e6f7d73c1e43b5d57Chris Lattner 7589df1b58a968506af2abba9e6f7d73c1e43b5d57Chris Lattner while (!WorkList.empty()) { 7689df1b58a968506af2abba9e6f7d73c1e43b5d57Chris Lattner Instruction *I = *WorkList.begin(); 7789df1b58a968506af2abba9e6f7d73c1e43b5d57Chris Lattner WorkList.erase(WorkList.begin()); // Get an element from the worklist... 7889df1b58a968506af2abba9e6f7d73c1e43b5d57Chris Lattner 7989df1b58a968506af2abba9e6f7d73c1e43b5d57Chris Lattner if (!I->use_empty()) // Don't muck with dead instructions... 8036b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines if (Constant *C = ConstantFoldInstruction(I, DL, TLI)) { 8189df1b58a968506af2abba9e6f7d73c1e43b5d57Chris Lattner // Add all of the users of this instruction to the worklist, they might 8282c89b9f3a9b88bb63ce13b09b4f27fbb72f66fcMisha Brukman // be constant propagatable now... 8336b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines for (User *U : I->users()) 8436b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines WorkList.insert(cast<Instruction>(U)); 85fd93908ae8b9684fe71c239e3c6cfe13ff6a2663Misha Brukman 8689df1b58a968506af2abba9e6f7d73c1e43b5d57Chris Lattner // Replace all of the uses of a variable with uses of the constant. 8789df1b58a968506af2abba9e6f7d73c1e43b5d57Chris Lattner I->replaceAllUsesWith(C); 883dec1f272219ee1f8e1499929cdf53f5bc3c2272Chris Lattner 894647b7cd6929990ff174f0dd7cbfda5ab40df850Chris Lattner // Remove the dead instruction. 904647b7cd6929990ff174f0dd7cbfda5ab40df850Chris Lattner WorkList.erase(I); 911adec83ae84031bfa9f0bf209c5ee6c64906a1ffDan Gohman I->eraseFromParent(); 924647b7cd6929990ff174f0dd7cbfda5ab40df850Chris Lattner 9389df1b58a968506af2abba9e6f7d73c1e43b5d57Chris Lattner // We made a change to the function... 9489df1b58a968506af2abba9e6f7d73c1e43b5d57Chris Lattner Changed = true; 953dec1f272219ee1f8e1499929cdf53f5bc3c2272Chris Lattner ++NumInstKilled; 9689df1b58a968506af2abba9e6f7d73c1e43b5d57Chris Lattner } 9789df1b58a968506af2abba9e6f7d73c1e43b5d57Chris Lattner } 9889df1b58a968506af2abba9e6f7d73c1e43b5d57Chris Lattner return Changed; 9989df1b58a968506af2abba9e6f7d73c1e43b5d57Chris Lattner} 100