CodeGenPrepare.cpp revision 7579609bfe0d915b6c2d8dc094a132d793ec8855
1dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner//===- CodeGenPrepare.cpp - Prepare a function for code generation --------===// 2dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner// 3dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner// The LLVM Compiler Infrastructure 4dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner// 54ee451de366474b9c228b4e5fa573795a715216dChris Lattner// This file is distributed under the University of Illinois Open Source 64ee451de366474b9c228b4e5fa573795a715216dChris Lattner// License. See LICENSE.TXT for details. 7dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner// 8dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner//===----------------------------------------------------------------------===// 9dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner// 10dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner// This pass munges the code in the input function to better prepare it for 11a8a118b68fa3ca1632e7280cd6994aa0f8f1eec1Gordon Henriksen// SelectionDAG-based code generation. This works around limitations in it's 12a8a118b68fa3ca1632e7280cd6994aa0f8f1eec1Gordon Henriksen// basic-block-at-a-time approach. It should eventually be removed. 13dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner// 14dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner//===----------------------------------------------------------------------===// 15dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner 16dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner#define DEBUG_TYPE "codegenprepare" 17dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner#include "llvm/Transforms/Scalar.h" 18dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner#include "llvm/Constants.h" 19dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner#include "llvm/DerivedTypes.h" 20dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner#include "llvm/Function.h" 219bf12b5583104c810cfadcdce91edf9efad79973Evan Cheng#include "llvm/InlineAsm.h" 22dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner#include "llvm/Instructions.h" 236aae1d6582fe8519c42d9774d670bb93c78e9637Dale Johannesen#include "llvm/IntrinsicInst.h" 24dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner#include "llvm/Pass.h" 2580f6a507d4e11ba066ad0e53e12ad25ad8cf07baCameron Zwarich#include "llvm/Analysis/Dominators.h" 26d5f8684b16057df73771b23e293b400cb327e079Owen Anderson#include "llvm/Analysis/InstructionSimplify.h" 27ad80981a106c9d0ec83351e63ee3ac75ed646bf4Andreas Neustifter#include "llvm/Analysis/ProfileInfo.h" 28dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner#include "llvm/Target/TargetData.h" 29dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner#include "llvm/Target/TargetLowering.h" 30a1fd5b386dd8eb4c86bfd2b9659c219a1c4f56dbEvan Cheng#include "llvm/Transforms/Utils/AddrModeMatcher.h" 31dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner#include "llvm/Transforms/Utils/BasicBlockUtils.h" 32dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner#include "llvm/Transforms/Utils/Local.h" 33040056fd11693ffc41ce9b777281c71705d0dc1fEric Christopher#include "llvm/Transforms/Utils/BuildLibCalls.h" 34dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner#include "llvm/ADT/DenseMap.h" 35dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner#include "llvm/ADT/SmallSet.h" 367eb589d3f9294dbfe4d5205045bd8119a9666532Jakob Stoklund Olesen#include "llvm/ADT/Statistic.h" 3703ce042d70c423a41edca0714112a0e06b16493bDan Gohman#include "llvm/Assembly/Writer.h" 389bf12b5583104c810cfadcdce91edf9efad79973Evan Cheng#include "llvm/Support/CallSite.h" 39e1bcb440dc0ca3c41fda1c0c581abfc4f38ca170Evan Cheng#include "llvm/Support/CommandLine.h" 40bdcb726fcad1e3fddc70847a2b91d4d4f9396938Evan Cheng#include "llvm/Support/Debug.h" 41dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner#include "llvm/Support/GetElementPtrTypeIterator.h" 42088a1e84ea985a22efcf907d7789064fee3a97b9Chris Lattner#include "llvm/Support/PatternMatch.h" 436c1980b3357207c4d756255bc5e32323eac278dcDan Gohman#include "llvm/Support/raw_ostream.h" 44040056fd11693ffc41ce9b777281c71705d0dc1fEric Christopher#include "llvm/Support/IRBuilder.h" 45dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattnerusing namespace llvm; 46088a1e84ea985a22efcf907d7789064fee3a97b9Chris Lattnerusing namespace llvm::PatternMatch; 47dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner 4831ff1333e0651192212cee6e090df2ff57d19b53Cameron ZwarichSTATISTIC(NumBlocksElim, "Number of blocks eliminated"); 49073057f0d0a1e21ab020fa71ff4bd11543faa6d0Cameron ZwarichSTATISTIC(NumPHIsElim, "Number of trivial PHIs eliminated"); 50073057f0d0a1e21ab020fa71ff4bd11543faa6d0Cameron ZwarichSTATISTIC(NumGEPsElim, "Number of GEPs converted to casts"); 5131ff1333e0651192212cee6e090df2ff57d19b53Cameron ZwarichSTATISTIC(NumCmpUses, "Number of uses of Cmp expressions replaced with uses of " 5231ff1333e0651192212cee6e090df2ff57d19b53Cameron Zwarich "sunken Cmps"); 5331ff1333e0651192212cee6e090df2ff57d19b53Cameron ZwarichSTATISTIC(NumCastUses, "Number of uses of Cast expressions replaced with uses " 5431ff1333e0651192212cee6e090df2ff57d19b53Cameron Zwarich "of sunken Casts"); 5531ff1333e0651192212cee6e090df2ff57d19b53Cameron ZwarichSTATISTIC(NumMemoryInsts, "Number of memory instructions whose address " 5631ff1333e0651192212cee6e090df2ff57d19b53Cameron Zwarich "computations were sunk"); 5731ff1333e0651192212cee6e090df2ff57d19b53Cameron ZwarichSTATISTIC(NumExtsMoved, "Number of [s|z]ext instructions combined with loads"); 5831ff1333e0651192212cee6e090df2ff57d19b53Cameron ZwarichSTATISTIC(NumExtUses, "Number of uses of [s|z]ext instructions optimized"); 597eb589d3f9294dbfe4d5205045bd8119a9666532Jakob Stoklund Olesen 60e1bcb440dc0ca3c41fda1c0c581abfc4f38ca170Evan Chengstatic cl::opt<bool> 61e1bcb440dc0ca3c41fda1c0c581abfc4f38ca170Evan ChengCriticalEdgeSplit("cgp-critical-edge-splitting", 62e1bcb440dc0ca3c41fda1c0c581abfc4f38ca170Evan Cheng cl::desc("Split critical edges during codegen prepare"), 637eb589d3f9294dbfe4d5205045bd8119a9666532Jakob Stoklund Olesen cl::init(false), cl::Hidden); 64e1bcb440dc0ca3c41fda1c0c581abfc4f38ca170Evan Cheng 65692bf6b85e0eaed549cd47d67289ab7b28e32651Eric Christophernamespace { 663e8b6631e67e01e4960a7ba4668a50c596607473Chris Lattner class CodeGenPrepare : public FunctionPass { 67dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner /// TLI - Keep a pointer of a TargetLowering to consult for determining 68dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner /// transformation profitability. 69dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner const TargetLowering *TLI; 7080f6a507d4e11ba066ad0e53e12ad25ad8cf07baCameron Zwarich DominatorTree *DT; 7104149f7ffd033773adfe85e4acf3f560e29bd47dEvan Cheng ProfileInfo *PFI; 727579609bfe0d915b6c2d8dc094a132d793ec8855Chris Lattner 737579609bfe0d915b6c2d8dc094a132d793ec8855Chris Lattner /// CurInstIterator - As we scan instructions optimizing them, this is the 747579609bfe0d915b6c2d8dc094a132d793ec8855Chris Lattner /// next instruction to optimize. Xforms that can invalidate this should 757579609bfe0d915b6c2d8dc094a132d793ec8855Chris Lattner /// update it. 767579609bfe0d915b6c2d8dc094a132d793ec8855Chris Lattner BasicBlock::iterator CurInstIterator; 77ab63152871f4144050d0a58d592a95e089fe40d4Evan Cheng 78ab63152871f4144050d0a58d592a95e089fe40d4Evan Cheng /// BackEdges - Keep a set of all the loop back edges. 79ab63152871f4144050d0a58d592a95e089fe40d4Evan Cheng /// 80fe095f39e7009c51d1c86769792ccbcad8cdd2ecMike Stump SmallSet<std::pair<const BasicBlock*, const BasicBlock*>, 8> BackEdges; 818c3527e7a475dd3369a485a4f610d56f7005b7b5Cameron Zwarich 828c3527e7a475dd3369a485a4f610d56f7005b7b5Cameron Zwarich // Keeps track of non-local addresses that have been sunk into a block. This 838c3527e7a475dd3369a485a4f610d56f7005b7b5Cameron Zwarich // allows us to avoid inserting duplicate code for blocks with multiple 848c3527e7a475dd3369a485a4f610d56f7005b7b5Cameron Zwarich // load/stores of the same address. 858c3527e7a475dd3369a485a4f610d56f7005b7b5Cameron Zwarich DenseMap<Value*, Value*> SunkAddrs; 868c3527e7a475dd3369a485a4f610d56f7005b7b5Cameron Zwarich 87dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner public: 88ecd94c804a563f2a86572dcf1d2e81f397e19daaNick Lewycky static char ID; // Pass identification, replacement for typeid 89c2bbfc18e9adbbdcf5b3375d8d25e2452f7df7f1Dan Gohman explicit CodeGenPrepare(const TargetLowering *tli = 0) 90081c34b725980f995be9080eaec24cd3dfaaf065Owen Anderson : FunctionPass(ID), TLI(tli) { 91081c34b725980f995be9080eaec24cd3dfaaf065Owen Anderson initializeCodeGenPreparePass(*PassRegistry::getPassRegistry()); 92081c34b725980f995be9080eaec24cd3dfaaf065Owen Anderson } 93dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner bool runOnFunction(Function &F); 94692bf6b85e0eaed549cd47d67289ab7b28e32651Eric Christopher 95ad80981a106c9d0ec83351e63ee3ac75ed646bf4Andreas Neustifter virtual void getAnalysisUsage(AnalysisUsage &AU) const { 9680f6a507d4e11ba066ad0e53e12ad25ad8cf07baCameron Zwarich AU.addPreserved<DominatorTree>(); 97ad80981a106c9d0ec83351e63ee3ac75ed646bf4Andreas Neustifter AU.addPreserved<ProfileInfo>(); 98ad80981a106c9d0ec83351e63ee3ac75ed646bf4Andreas Neustifter } 99ad80981a106c9d0ec83351e63ee3ac75ed646bf4Andreas Neustifter 100aa0e52328747d982d6c6e501a205832ad724ff62Dan Gohman virtual void releaseMemory() { 101aa0e52328747d982d6c6e501a205832ad724ff62Dan Gohman BackEdges.clear(); 102aa0e52328747d982d6c6e501a205832ad724ff62Dan Gohman } 103aa0e52328747d982d6c6e501a205832ad724ff62Dan Gohman 104dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner private: 105d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner bool EliminateMostlyEmptyBlocks(Function &F); 106d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner bool CanMergeBlocks(const BasicBlock *BB, const BasicBlock *DestBB) const; 107d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner void EliminateMostlyEmptyBlock(BasicBlock *BB); 108dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner bool OptimizeBlock(BasicBlock &BB); 109c061101e03ef6d2ca550f8fe71594a5e1c02e348Cameron Zwarich bool OptimizeInst(Instruction *I); 11088a5c832ac71eb31d2b1bc143817af9248f4c549Chris Lattner bool OptimizeMemoryInst(Instruction *I, Value *Addr, const Type *AccessTy, 11188a5c832ac71eb31d2b1bc143817af9248f4c549Chris Lattner DenseMap<Value*,Value*> &SunkAddrs); 1127579609bfe0d915b6c2d8dc094a132d793ec8855Chris Lattner bool OptimizeInlineAsmInst(CallInst *CS); 113040056fd11693ffc41ce9b777281c71705d0dc1fEric Christopher bool OptimizeCallInst(CallInst *CI); 114b00f236b03ea57520f94823780896ebdbc5d8bdcDan Gohman bool MoveExtToFormExtLoad(Instruction *I); 115bdcb726fcad1e3fddc70847a2b91d4d4f9396938Evan Cheng bool OptimizeExtUses(Instruction *I); 116fe095f39e7009c51d1c86769792ccbcad8cdd2ecMike Stump void findLoopBackEdges(const Function &F); 117dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner }; 118dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner} 119794fd75c67a2cdc128d67342c6d88a504d186896Devang Patel 1201997473cf72957d0e70322e2fe6fe2ab141c58a6Devang Patelchar CodeGenPrepare::ID = 0; 121d13db2c59cc94162d6cf0a04187d408bfef6d4a7Owen AndersonINITIALIZE_PASS(CodeGenPrepare, "codegenprepare", 122ce665bd2e2b581ab0858d1afe359192bac96b868Owen Anderson "Optimize for code generation", false, false) 123dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner 124dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris LattnerFunctionPass *llvm::createCodeGenPreparePass(const TargetLowering *TLI) { 125dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner return new CodeGenPrepare(TLI); 126dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner} 127dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner 128ab63152871f4144050d0a58d592a95e089fe40d4Evan Cheng/// findLoopBackEdges - Do a DFS walk to find loop back edges. 129ab63152871f4144050d0a58d592a95e089fe40d4Evan Cheng/// 130fe095f39e7009c51d1c86769792ccbcad8cdd2ecMike Stumpvoid CodeGenPrepare::findLoopBackEdges(const Function &F) { 131fe095f39e7009c51d1c86769792ccbcad8cdd2ecMike Stump SmallVector<std::pair<const BasicBlock*,const BasicBlock*>, 32> Edges; 132fe095f39e7009c51d1c86769792ccbcad8cdd2ecMike Stump FindFunctionBackedges(F, Edges); 133fe095f39e7009c51d1c86769792ccbcad8cdd2ecMike Stump 134fe095f39e7009c51d1c86769792ccbcad8cdd2ecMike Stump BackEdges.insert(Edges.begin(), Edges.end()); 135ab63152871f4144050d0a58d592a95e089fe40d4Evan Cheng} 136ab63152871f4144050d0a58d592a95e089fe40d4Evan Cheng 137dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner 138dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattnerbool CodeGenPrepare::runOnFunction(Function &F) { 139dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner bool EverMadeChange = false; 140692bf6b85e0eaed549cd47d67289ab7b28e32651Eric Christopher 14180f6a507d4e11ba066ad0e53e12ad25ad8cf07baCameron Zwarich DT = getAnalysisIfAvailable<DominatorTree>(); 14204149f7ffd033773adfe85e4acf3f560e29bd47dEvan Cheng PFI = getAnalysisIfAvailable<ProfileInfo>(); 143d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner // First pass, eliminate blocks that contain only PHI nodes and an 144d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner // unconditional branch. 145d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner EverMadeChange |= EliminateMostlyEmptyBlocks(F); 146692bf6b85e0eaed549cd47d67289ab7b28e32651Eric Christopher 14795bb00414eba82cc1c058b558cd28bc28134c561Cameron Zwarich // Now find loop back edges, but only if they are being used to decide which 14895bb00414eba82cc1c058b558cd28bc28134c561Cameron Zwarich // critical edges to split. 14995bb00414eba82cc1c058b558cd28bc28134c561Cameron Zwarich if (CriticalEdgeSplit) 15095bb00414eba82cc1c058b558cd28bc28134c561Cameron Zwarich findLoopBackEdges(F); 1517e66c0d43aefce78948f0b73422f6e5bb28e2077Evan Cheng 152d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner bool MadeChange = true; 153dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner while (MadeChange) { 154dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner MadeChange = false; 155dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner for (Function::iterator BB = F.begin(), E = F.end(); BB != E; ++BB) 156dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner MadeChange |= OptimizeBlock(*BB); 157dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner EverMadeChange |= MadeChange; 158dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner } 1598c3527e7a475dd3369a485a4f610d56f7005b7b5Cameron Zwarich 1608c3527e7a475dd3369a485a4f610d56f7005b7b5Cameron Zwarich SunkAddrs.clear(); 1618c3527e7a475dd3369a485a4f610d56f7005b7b5Cameron Zwarich 162dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner return EverMadeChange; 163dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner} 164dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner 1652d69724938e67ec248e0ba42f86287923b3a5171Dale Johannesen/// EliminateMostlyEmptyBlocks - eliminate blocks that contain only PHI nodes, 1662d69724938e67ec248e0ba42f86287923b3a5171Dale Johannesen/// debug info directives, and an unconditional branch. Passes before isel 1672d69724938e67ec248e0ba42f86287923b3a5171Dale Johannesen/// (e.g. LSR/loopsimplify) often split edges in ways that are non-optimal for 1682d69724938e67ec248e0ba42f86287923b3a5171Dale Johannesen/// isel. Start by eliminating these blocks so we can split them the way we 1692d69724938e67ec248e0ba42f86287923b3a5171Dale Johannesen/// want them. 170d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattnerbool CodeGenPrepare::EliminateMostlyEmptyBlocks(Function &F) { 171d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner bool MadeChange = false; 172d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner // Note that this intentionally skips the entry block. 173d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner for (Function::iterator I = ++F.begin(), E = F.end(); I != E; ) { 174d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner BasicBlock *BB = I++; 175d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner 176d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner // If this block doesn't end with an uncond branch, ignore it. 177d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner BranchInst *BI = dyn_cast<BranchInst>(BB->getTerminator()); 178d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner if (!BI || !BI->isUnconditional()) 179d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner continue; 180692bf6b85e0eaed549cd47d67289ab7b28e32651Eric Christopher 1812d69724938e67ec248e0ba42f86287923b3a5171Dale Johannesen // If the instruction before the branch (skipping debug info) isn't a phi 1822d69724938e67ec248e0ba42f86287923b3a5171Dale Johannesen // node, then other stuff is happening here. 183d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner BasicBlock::iterator BBI = BI; 184d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner if (BBI != BB->begin()) { 185d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner --BBI; 1862d69724938e67ec248e0ba42f86287923b3a5171Dale Johannesen while (isa<DbgInfoIntrinsic>(BBI)) { 1872d69724938e67ec248e0ba42f86287923b3a5171Dale Johannesen if (BBI == BB->begin()) 1882d69724938e67ec248e0ba42f86287923b3a5171Dale Johannesen break; 1892d69724938e67ec248e0ba42f86287923b3a5171Dale Johannesen --BBI; 1902d69724938e67ec248e0ba42f86287923b3a5171Dale Johannesen } 1912d69724938e67ec248e0ba42f86287923b3a5171Dale Johannesen if (!isa<DbgInfoIntrinsic>(BBI) && !isa<PHINode>(BBI)) 1922d69724938e67ec248e0ba42f86287923b3a5171Dale Johannesen continue; 193d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner } 194692bf6b85e0eaed549cd47d67289ab7b28e32651Eric Christopher 195d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner // Do not break infinite loops. 196d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner BasicBlock *DestBB = BI->getSuccessor(0); 197d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner if (DestBB == BB) 198d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner continue; 199692bf6b85e0eaed549cd47d67289ab7b28e32651Eric Christopher 200d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner if (!CanMergeBlocks(BB, DestBB)) 201d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner continue; 202692bf6b85e0eaed549cd47d67289ab7b28e32651Eric Christopher 203d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner EliminateMostlyEmptyBlock(BB); 204d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner MadeChange = true; 205d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner } 206d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner return MadeChange; 207d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner} 208d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner 209d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner/// CanMergeBlocks - Return true if we can merge BB into DestBB if there is a 210d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner/// single uncond branch between them, and BB contains no other non-phi 211d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner/// instructions. 212d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattnerbool CodeGenPrepare::CanMergeBlocks(const BasicBlock *BB, 213d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner const BasicBlock *DestBB) const { 214d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner // We only want to eliminate blocks whose phi nodes are used by phi nodes in 215d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner // the successor. If there are more complex condition (e.g. preheaders), 216d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner // don't mess around with them. 217d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner BasicBlock::const_iterator BBI = BB->begin(); 218d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner while (const PHINode *PN = dyn_cast<PHINode>(BBI++)) { 21960ad781c61815ca5b8dc2a45a102e1c8af65992fGabor Greif for (Value::const_use_iterator UI = PN->use_begin(), E = PN->use_end(); 220d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner UI != E; ++UI) { 221d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner const Instruction *User = cast<Instruction>(*UI); 222d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner if (User->getParent() != DestBB || !isa<PHINode>(User)) 223d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner return false; 224692bf6b85e0eaed549cd47d67289ab7b28e32651Eric Christopher // If User is inside DestBB block and it is a PHINode then check 225692bf6b85e0eaed549cd47d67289ab7b28e32651Eric Christopher // incoming value. If incoming value is not from BB then this is 22675abc1ed0618048c3cf6c5b71c9868c10d6c1478Devang Patel // a complex condition (e.g. preheaders) we want to avoid here. 22775abc1ed0618048c3cf6c5b71c9868c10d6c1478Devang Patel if (User->getParent() == DestBB) { 22875abc1ed0618048c3cf6c5b71c9868c10d6c1478Devang Patel if (const PHINode *UPN = dyn_cast<PHINode>(User)) 22975abc1ed0618048c3cf6c5b71c9868c10d6c1478Devang Patel for (unsigned I = 0, E = UPN->getNumIncomingValues(); I != E; ++I) { 23075abc1ed0618048c3cf6c5b71c9868c10d6c1478Devang Patel Instruction *Insn = dyn_cast<Instruction>(UPN->getIncomingValue(I)); 23175abc1ed0618048c3cf6c5b71c9868c10d6c1478Devang Patel if (Insn && Insn->getParent() == BB && 23275abc1ed0618048c3cf6c5b71c9868c10d6c1478Devang Patel Insn->getParent() != UPN->getIncomingBlock(I)) 23375abc1ed0618048c3cf6c5b71c9868c10d6c1478Devang Patel return false; 23475abc1ed0618048c3cf6c5b71c9868c10d6c1478Devang Patel } 23575abc1ed0618048c3cf6c5b71c9868c10d6c1478Devang Patel } 236d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner } 237d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner } 238692bf6b85e0eaed549cd47d67289ab7b28e32651Eric Christopher 239d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner // If BB and DestBB contain any common predecessors, then the phi nodes in BB 240d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner // and DestBB may have conflicting incoming values for the block. If so, we 241d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner // can't merge the block. 242d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner const PHINode *DestBBPN = dyn_cast<PHINode>(DestBB->begin()); 243d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner if (!DestBBPN) return true; // no conflict. 244692bf6b85e0eaed549cd47d67289ab7b28e32651Eric Christopher 245d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner // Collect the preds of BB. 246f67f73a519eac94b6c1f98dbce7d251a3a4aea07Chris Lattner SmallPtrSet<const BasicBlock*, 16> BBPreds; 247d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner if (const PHINode *BBPN = dyn_cast<PHINode>(BB->begin())) { 248d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner // It is faster to get preds from a PHI than with pred_iterator. 249d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner for (unsigned i = 0, e = BBPN->getNumIncomingValues(); i != e; ++i) 250d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner BBPreds.insert(BBPN->getIncomingBlock(i)); 251d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner } else { 252d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner BBPreds.insert(pred_begin(BB), pred_end(BB)); 253d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner } 254692bf6b85e0eaed549cd47d67289ab7b28e32651Eric Christopher 255d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner // Walk the preds of DestBB. 256d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner for (unsigned i = 0, e = DestBBPN->getNumIncomingValues(); i != e; ++i) { 257d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner BasicBlock *Pred = DestBBPN->getIncomingBlock(i); 258d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner if (BBPreds.count(Pred)) { // Common predecessor? 259d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner BBI = DestBB->begin(); 260d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner while (const PHINode *PN = dyn_cast<PHINode>(BBI++)) { 261d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner const Value *V1 = PN->getIncomingValueForBlock(Pred); 262d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner const Value *V2 = PN->getIncomingValueForBlock(BB); 263692bf6b85e0eaed549cd47d67289ab7b28e32651Eric Christopher 264d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner // If V2 is a phi node in BB, look up what the mapped value will be. 265d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner if (const PHINode *V2PN = dyn_cast<PHINode>(V2)) 266d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner if (V2PN->getParent() == BB) 267d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner V2 = V2PN->getIncomingValueForBlock(Pred); 268692bf6b85e0eaed549cd47d67289ab7b28e32651Eric Christopher 269d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner // If there is a conflict, bail out. 270d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner if (V1 != V2) return false; 271d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner } 272d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner } 273d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner } 274d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner 275d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner return true; 276d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner} 277d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner 278d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner 279d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner/// EliminateMostlyEmptyBlock - Eliminate a basic block that have only phi's and 280d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner/// an unconditional branch in it. 281d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattnervoid CodeGenPrepare::EliminateMostlyEmptyBlock(BasicBlock *BB) { 282d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner BranchInst *BI = cast<BranchInst>(BB->getTerminator()); 283d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner BasicBlock *DestBB = BI->getSuccessor(0); 284692bf6b85e0eaed549cd47d67289ab7b28e32651Eric Christopher 28568d67fdf203ff2d5b0eeb925befd0866bce3aceeDavid Greene DEBUG(dbgs() << "MERGING MOSTLY EMPTY BLOCKS - BEFORE:\n" << *BB << *DestBB); 286692bf6b85e0eaed549cd47d67289ab7b28e32651Eric Christopher 287d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner // If the destination block has a single pred, then this is a trivial edge, 288d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner // just collapse it. 2899918fb5631974f2201a640384b7ebe672c749e43Chris Lattner if (BasicBlock *SinglePred = DestBB->getSinglePredecessor()) { 290f5102a0f088e7c96f7028bf7ca1c24975c314fffChris Lattner if (SinglePred != DestBB) { 291f5102a0f088e7c96f7028bf7ca1c24975c314fffChris Lattner // Remember if SinglePred was the entry block of the function. If so, we 292f5102a0f088e7c96f7028bf7ca1c24975c314fffChris Lattner // will need to move BB back to the entry position. 293f5102a0f088e7c96f7028bf7ca1c24975c314fffChris Lattner bool isEntry = SinglePred == &SinglePred->getParent()->getEntryBlock(); 294ad80981a106c9d0ec83351e63ee3ac75ed646bf4Andreas Neustifter MergeBasicBlockIntoOnlyPred(DestBB, this); 295f5102a0f088e7c96f7028bf7ca1c24975c314fffChris Lattner 296f5102a0f088e7c96f7028bf7ca1c24975c314fffChris Lattner if (isEntry && BB != &BB->getParent()->getEntryBlock()) 297f5102a0f088e7c96f7028bf7ca1c24975c314fffChris Lattner BB->moveBefore(&BB->getParent()->getEntryBlock()); 298f5102a0f088e7c96f7028bf7ca1c24975c314fffChris Lattner 29968d67fdf203ff2d5b0eeb925befd0866bce3aceeDavid Greene DEBUG(dbgs() << "AFTER:\n" << *DestBB << "\n\n\n"); 300f5102a0f088e7c96f7028bf7ca1c24975c314fffChris Lattner return; 301f5102a0f088e7c96f7028bf7ca1c24975c314fffChris Lattner } 302d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner } 303692bf6b85e0eaed549cd47d67289ab7b28e32651Eric Christopher 304d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner // Otherwise, we have multiple predecessors of BB. Update the PHIs in DestBB 305d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner // to handle the new incoming edges it is about to have. 306d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner PHINode *PN; 307d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner for (BasicBlock::iterator BBI = DestBB->begin(); 308d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner (PN = dyn_cast<PHINode>(BBI)); ++BBI) { 309d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner // Remove the incoming value for BB, and remember it. 310d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner Value *InVal = PN->removeIncomingValue(BB, false); 311692bf6b85e0eaed549cd47d67289ab7b28e32651Eric Christopher 312d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner // Two options: either the InVal is a phi node defined in BB or it is some 313d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner // value that dominates BB. 314d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner PHINode *InValPhi = dyn_cast<PHINode>(InVal); 315d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner if (InValPhi && InValPhi->getParent() == BB) { 316d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner // Add all of the input values of the input PHI as inputs of this phi. 317d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner for (unsigned i = 0, e = InValPhi->getNumIncomingValues(); i != e; ++i) 318d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner PN->addIncoming(InValPhi->getIncomingValue(i), 319d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner InValPhi->getIncomingBlock(i)); 320d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner } else { 321d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner // Otherwise, add one instance of the dominating value for each edge that 322d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner // we will be adding. 323d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner if (PHINode *BBPN = dyn_cast<PHINode>(BB->begin())) { 324d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner for (unsigned i = 0, e = BBPN->getNumIncomingValues(); i != e; ++i) 325d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner PN->addIncoming(InVal, BBPN->getIncomingBlock(i)); 326d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner } else { 327d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner for (pred_iterator PI = pred_begin(BB), E = pred_end(BB); PI != E; ++PI) 328d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner PN->addIncoming(InVal, *PI); 329d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner } 330d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner } 331d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner } 332692bf6b85e0eaed549cd47d67289ab7b28e32651Eric Christopher 333d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner // The PHIs are now updated, change everything that refers to BB to use 334d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner // DestBB and remove BB. 335d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner BB->replaceAllUsesWith(DestBB); 33680f6a507d4e11ba066ad0e53e12ad25ad8cf07baCameron Zwarich if (DT) { 33780f6a507d4e11ba066ad0e53e12ad25ad8cf07baCameron Zwarich BasicBlock *BBIDom = DT->getNode(BB)->getIDom()->getBlock(); 33880f6a507d4e11ba066ad0e53e12ad25ad8cf07baCameron Zwarich BasicBlock *DestBBIDom = DT->getNode(DestBB)->getIDom()->getBlock(); 33980f6a507d4e11ba066ad0e53e12ad25ad8cf07baCameron Zwarich BasicBlock *NewIDom = DT->findNearestCommonDominator(BBIDom, DestBBIDom); 34080f6a507d4e11ba066ad0e53e12ad25ad8cf07baCameron Zwarich DT->changeImmediateDominator(DestBB, NewIDom); 34180f6a507d4e11ba066ad0e53e12ad25ad8cf07baCameron Zwarich DT->eraseNode(BB); 34280f6a507d4e11ba066ad0e53e12ad25ad8cf07baCameron Zwarich } 34304149f7ffd033773adfe85e4acf3f560e29bd47dEvan Cheng if (PFI) { 34404149f7ffd033773adfe85e4acf3f560e29bd47dEvan Cheng PFI->replaceAllUses(BB, DestBB); 34504149f7ffd033773adfe85e4acf3f560e29bd47dEvan Cheng PFI->removeEdge(ProfileInfo::getEdge(BB, DestBB)); 346ad80981a106c9d0ec83351e63ee3ac75ed646bf4Andreas Neustifter } 347d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner BB->eraseFromParent(); 34831ff1333e0651192212cee6e090df2ff57d19b53Cameron Zwarich ++NumBlocksElim; 349692bf6b85e0eaed549cd47d67289ab7b28e32651Eric Christopher 35068d67fdf203ff2d5b0eeb925befd0866bce3aceeDavid Greene DEBUG(dbgs() << "AFTER:\n" << *DestBB << "\n\n\n"); 351d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner} 352d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner 35398d5c3141eddc84a8bcf7db57332967695585e42Chris Lattner/// FindReusablePredBB - Check all of the predecessors of the block DestPHI 35498d5c3141eddc84a8bcf7db57332967695585e42Chris Lattner/// lives in to see if there is a block that we can reuse as a critical edge 35598d5c3141eddc84a8bcf7db57332967695585e42Chris Lattner/// from TIBB. 35698d5c3141eddc84a8bcf7db57332967695585e42Chris Lattnerstatic BasicBlock *FindReusablePredBB(PHINode *DestPHI, BasicBlock *TIBB) { 35798d5c3141eddc84a8bcf7db57332967695585e42Chris Lattner BasicBlock *Dest = DestPHI->getParent(); 35898d5c3141eddc84a8bcf7db57332967695585e42Chris Lattner 35998d5c3141eddc84a8bcf7db57332967695585e42Chris Lattner /// TIPHIValues - This array is lazily computed to determine the values of 36098d5c3141eddc84a8bcf7db57332967695585e42Chris Lattner /// PHIs in Dest that TI would provide. 36198d5c3141eddc84a8bcf7db57332967695585e42Chris Lattner SmallVector<Value*, 32> TIPHIValues; 36298d5c3141eddc84a8bcf7db57332967695585e42Chris Lattner 36398d5c3141eddc84a8bcf7db57332967695585e42Chris Lattner /// TIBBEntryNo - This is a cache to speed up pred queries for TIBB. 36498d5c3141eddc84a8bcf7db57332967695585e42Chris Lattner unsigned TIBBEntryNo = 0; 36598d5c3141eddc84a8bcf7db57332967695585e42Chris Lattner 36698d5c3141eddc84a8bcf7db57332967695585e42Chris Lattner // Check to see if Dest has any blocks that can be used as a split edge for 36798d5c3141eddc84a8bcf7db57332967695585e42Chris Lattner // this terminator. 36898d5c3141eddc84a8bcf7db57332967695585e42Chris Lattner for (unsigned pi = 0, e = DestPHI->getNumIncomingValues(); pi != e; ++pi) { 36998d5c3141eddc84a8bcf7db57332967695585e42Chris Lattner BasicBlock *Pred = DestPHI->getIncomingBlock(pi); 37098d5c3141eddc84a8bcf7db57332967695585e42Chris Lattner // To be usable, the pred has to end with an uncond branch to the dest. 37198d5c3141eddc84a8bcf7db57332967695585e42Chris Lattner BranchInst *PredBr = dyn_cast<BranchInst>(Pred->getTerminator()); 37298d5c3141eddc84a8bcf7db57332967695585e42Chris Lattner if (!PredBr || !PredBr->isUnconditional()) 37398d5c3141eddc84a8bcf7db57332967695585e42Chris Lattner continue; 37498d5c3141eddc84a8bcf7db57332967695585e42Chris Lattner // Must be empty other than the branch and debug info. 37598d5c3141eddc84a8bcf7db57332967695585e42Chris Lattner BasicBlock::iterator I = Pred->begin(); 37698d5c3141eddc84a8bcf7db57332967695585e42Chris Lattner while (isa<DbgInfoIntrinsic>(I)) 37798d5c3141eddc84a8bcf7db57332967695585e42Chris Lattner I++; 37898d5c3141eddc84a8bcf7db57332967695585e42Chris Lattner if (&*I != PredBr) 37998d5c3141eddc84a8bcf7db57332967695585e42Chris Lattner continue; 38098d5c3141eddc84a8bcf7db57332967695585e42Chris Lattner // Cannot be the entry block; its label does not get emitted. 38198d5c3141eddc84a8bcf7db57332967695585e42Chris Lattner if (Pred == &Dest->getParent()->getEntryBlock()) 38298d5c3141eddc84a8bcf7db57332967695585e42Chris Lattner continue; 38398d5c3141eddc84a8bcf7db57332967695585e42Chris Lattner 38498d5c3141eddc84a8bcf7db57332967695585e42Chris Lattner // Finally, since we know that Dest has phi nodes in it, we have to make 38598d5c3141eddc84a8bcf7db57332967695585e42Chris Lattner // sure that jumping to Pred will have the same effect as going to Dest in 38698d5c3141eddc84a8bcf7db57332967695585e42Chris Lattner // terms of PHI values. 38798d5c3141eddc84a8bcf7db57332967695585e42Chris Lattner PHINode *PN; 38898d5c3141eddc84a8bcf7db57332967695585e42Chris Lattner unsigned PHINo = 0; 38998d5c3141eddc84a8bcf7db57332967695585e42Chris Lattner unsigned PredEntryNo = pi; 39098d5c3141eddc84a8bcf7db57332967695585e42Chris Lattner 39198d5c3141eddc84a8bcf7db57332967695585e42Chris Lattner bool FoundMatch = true; 39298d5c3141eddc84a8bcf7db57332967695585e42Chris Lattner for (BasicBlock::iterator I = Dest->begin(); 39398d5c3141eddc84a8bcf7db57332967695585e42Chris Lattner (PN = dyn_cast<PHINode>(I)); ++I, ++PHINo) { 39498d5c3141eddc84a8bcf7db57332967695585e42Chris Lattner if (PHINo == TIPHIValues.size()) { 39598d5c3141eddc84a8bcf7db57332967695585e42Chris Lattner if (PN->getIncomingBlock(TIBBEntryNo) != TIBB) 39698d5c3141eddc84a8bcf7db57332967695585e42Chris Lattner TIBBEntryNo = PN->getBasicBlockIndex(TIBB); 39798d5c3141eddc84a8bcf7db57332967695585e42Chris Lattner TIPHIValues.push_back(PN->getIncomingValue(TIBBEntryNo)); 39898d5c3141eddc84a8bcf7db57332967695585e42Chris Lattner } 39998d5c3141eddc84a8bcf7db57332967695585e42Chris Lattner 40098d5c3141eddc84a8bcf7db57332967695585e42Chris Lattner // If the PHI entry doesn't work, we can't use this pred. 40198d5c3141eddc84a8bcf7db57332967695585e42Chris Lattner if (PN->getIncomingBlock(PredEntryNo) != Pred) 40298d5c3141eddc84a8bcf7db57332967695585e42Chris Lattner PredEntryNo = PN->getBasicBlockIndex(Pred); 40398d5c3141eddc84a8bcf7db57332967695585e42Chris Lattner 40498d5c3141eddc84a8bcf7db57332967695585e42Chris Lattner if (TIPHIValues[PHINo] != PN->getIncomingValue(PredEntryNo)) { 40598d5c3141eddc84a8bcf7db57332967695585e42Chris Lattner FoundMatch = false; 40698d5c3141eddc84a8bcf7db57332967695585e42Chris Lattner break; 40798d5c3141eddc84a8bcf7db57332967695585e42Chris Lattner } 40898d5c3141eddc84a8bcf7db57332967695585e42Chris Lattner } 40998d5c3141eddc84a8bcf7db57332967695585e42Chris Lattner 41098d5c3141eddc84a8bcf7db57332967695585e42Chris Lattner // If we found a workable predecessor, change TI to branch to Succ. 41198d5c3141eddc84a8bcf7db57332967695585e42Chris Lattner if (FoundMatch) 41298d5c3141eddc84a8bcf7db57332967695585e42Chris Lattner return Pred; 41398d5c3141eddc84a8bcf7db57332967695585e42Chris Lattner } 41498d5c3141eddc84a8bcf7db57332967695585e42Chris Lattner return 0; 41598d5c3141eddc84a8bcf7db57332967695585e42Chris Lattner} 41698d5c3141eddc84a8bcf7db57332967695585e42Chris Lattner 417d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner 418ebe807597f3ee67f6c5f9cd462ba325b579a2680Chris Lattner/// SplitEdgeNicely - Split the critical edge from TI to its specified 419dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner/// successor if it will improve codegen. We only do this if the successor has 420dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner/// phi nodes (otherwise critical edges are ok). If there is already another 421dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner/// predecessor of the succ that is empty (and thus has no phi nodes), use it 422dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner/// instead of introducing a new block. 423ab63152871f4144050d0a58d592a95e089fe40d4Evan Chengstatic void SplitEdgeNicely(TerminatorInst *TI, unsigned SuccNum, 424fe095f39e7009c51d1c86769792ccbcad8cdd2ecMike Stump SmallSet<std::pair<const BasicBlock*, 425fe095f39e7009c51d1c86769792ccbcad8cdd2ecMike Stump const BasicBlock*>, 8> &BackEdges, 426ab63152871f4144050d0a58d592a95e089fe40d4Evan Cheng Pass *P) { 427dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner BasicBlock *TIBB = TI->getParent(); 428dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner BasicBlock *Dest = TI->getSuccessor(SuccNum); 429dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner assert(isa<PHINode>(Dest->begin()) && 430dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner "This should only be called if Dest has a PHI!"); 4313f65b5e733e01faeb9db825515ca00e544fb988aChris Lattner PHINode *DestPHI = cast<PHINode>(Dest->begin()); 432692bf6b85e0eaed549cd47d67289ab7b28e32651Eric Christopher 433fc0b80d9746e5fd4b45057ab814c67371fb0f9eaEvan Cheng // Do not split edges to EH landing pads. 4343f65b5e733e01faeb9db825515ca00e544fb988aChris Lattner if (InvokeInst *Invoke = dyn_cast<InvokeInst>(TI)) 435fc0b80d9746e5fd4b45057ab814c67371fb0f9eaEvan Cheng if (Invoke->getSuccessor(1) == Dest) 436fc0b80d9746e5fd4b45057ab814c67371fb0f9eaEvan Cheng return; 437fc0b80d9746e5fd4b45057ab814c67371fb0f9eaEvan Cheng 438ebe807597f3ee67f6c5f9cd462ba325b579a2680Chris Lattner // As a hack, never split backedges of loops. Even though the copy for any 439ebe807597f3ee67f6c5f9cd462ba325b579a2680Chris Lattner // PHIs inserted on the backedge would be dead for exits from the loop, we 440ebe807597f3ee67f6c5f9cd462ba325b579a2680Chris Lattner // assume that the cost of *splitting* the backedge would be too high. 441ab63152871f4144050d0a58d592a95e089fe40d4Evan Cheng if (BackEdges.count(std::make_pair(TIBB, Dest))) 442ebe807597f3ee67f6c5f9cd462ba325b579a2680Chris Lattner return; 443692bf6b85e0eaed549cd47d67289ab7b28e32651Eric Christopher 444c09687bb7ea35e0dc9d709460c83a58e6076e4d2Chris Lattner if (BasicBlock *ReuseBB = FindReusablePredBB(DestPHI, TIBB)) { 445c09687bb7ea35e0dc9d709460c83a58e6076e4d2Chris Lattner ProfileInfo *PFI = P->getAnalysisIfAvailable<ProfileInfo>(); 446c09687bb7ea35e0dc9d709460c83a58e6076e4d2Chris Lattner if (PFI) 447c09687bb7ea35e0dc9d709460c83a58e6076e4d2Chris Lattner PFI->splitEdge(TIBB, Dest, ReuseBB); 448c09687bb7ea35e0dc9d709460c83a58e6076e4d2Chris Lattner Dest->removePredecessor(TIBB); 449c09687bb7ea35e0dc9d709460c83a58e6076e4d2Chris Lattner TI->setSuccessor(SuccNum, ReuseBB); 450ab63152871f4144050d0a58d592a95e089fe40d4Evan Cheng return; 451ab63152871f4144050d0a58d592a95e089fe40d4Evan Cheng } 452ab63152871f4144050d0a58d592a95e089fe40d4Evan Cheng 453c09687bb7ea35e0dc9d709460c83a58e6076e4d2Chris Lattner SplitCriticalEdge(TI, SuccNum, P, true); 454dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner} 455dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner 456ab63152871f4144050d0a58d592a95e089fe40d4Evan Cheng 457dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner/// OptimizeNoopCopyExpression - If the specified cast instruction is a noop 458a119de86a064414622562cfe32953de7f9b0ee40Dan Gohman/// copy (e.g. it's casting from one pointer type to another, i32->i8 on PPC), 459a119de86a064414622562cfe32953de7f9b0ee40Dan Gohman/// sink it into user blocks to reduce the number of virtual 460ce0b23721e434789f9600c0fd13f0ca17444264fDale Johannesen/// registers that must be created and coalesced. 461dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner/// 462dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner/// Return true if any changes are made. 46385fa13c02d383bb87dd9b8b9081a4d34a3e9c52cChris Lattner/// 464dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattnerstatic bool OptimizeNoopCopyExpression(CastInst *CI, const TargetLowering &TLI){ 465692bf6b85e0eaed549cd47d67289ab7b28e32651Eric Christopher // If this is a noop copy, 466e50ed30282bb5b4a9ed952580523f2dda16215acOwen Anderson EVT SrcVT = TLI.getValueType(CI->getOperand(0)->getType()); 467e50ed30282bb5b4a9ed952580523f2dda16215acOwen Anderson EVT DstVT = TLI.getValueType(CI->getType()); 468692bf6b85e0eaed549cd47d67289ab7b28e32651Eric Christopher 469dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner // This is an fp<->int conversion? 47083ec4b6711980242ef3c55a4fa36b2d7a39c1bfbDuncan Sands if (SrcVT.isInteger() != DstVT.isInteger()) 471dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner return false; 4728e4eb09b1e3571965f49edcdfb56b1375b1b7551Duncan Sands 473dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner // If this is an extension, it will be a zero or sign extension, which 474dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner // isn't a noop. 4758e4eb09b1e3571965f49edcdfb56b1375b1b7551Duncan Sands if (SrcVT.bitsLT(DstVT)) return false; 476692bf6b85e0eaed549cd47d67289ab7b28e32651Eric Christopher 477dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner // If these values will be promoted, find out what they will be promoted 478dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner // to. This helps us consider truncates on PPC as noop copies when they 479dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner // are. 480aafe626c7fa9f99150cccd27d0151a2cf7c8c00bChris Lattner if (TLI.getTypeAction(SrcVT) == TargetLowering::Promote) 48123b9b19b1a5a00faa9fce0788155c7dbfd00bfb1Owen Anderson SrcVT = TLI.getTypeToTransformTo(CI->getContext(), SrcVT); 482aafe626c7fa9f99150cccd27d0151a2cf7c8c00bChris Lattner if (TLI.getTypeAction(DstVT) == TargetLowering::Promote) 48323b9b19b1a5a00faa9fce0788155c7dbfd00bfb1Owen Anderson DstVT = TLI.getTypeToTransformTo(CI->getContext(), DstVT); 484692bf6b85e0eaed549cd47d67289ab7b28e32651Eric Christopher 485dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner // If, after promotion, these are the same types, this is a noop copy. 486dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner if (SrcVT != DstVT) 487dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner return false; 488692bf6b85e0eaed549cd47d67289ab7b28e32651Eric Christopher 489dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner BasicBlock *DefBB = CI->getParent(); 490692bf6b85e0eaed549cd47d67289ab7b28e32651Eric Christopher 491dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner /// InsertedCasts - Only insert a cast in each block once. 492ce0b23721e434789f9600c0fd13f0ca17444264fDale Johannesen DenseMap<BasicBlock*, CastInst*> InsertedCasts; 493692bf6b85e0eaed549cd47d67289ab7b28e32651Eric Christopher 494dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner bool MadeChange = false; 495692bf6b85e0eaed549cd47d67289ab7b28e32651Eric Christopher for (Value::use_iterator UI = CI->use_begin(), E = CI->use_end(); 496dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner UI != E; ) { 497dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner Use &TheUse = UI.getUse(); 498dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner Instruction *User = cast<Instruction>(*UI); 499692bf6b85e0eaed549cd47d67289ab7b28e32651Eric Christopher 500dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner // Figure out which BB this cast is used in. For PHI's this is the 501dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner // appropriate predecessor block. 502dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner BasicBlock *UserBB = User->getParent(); 503dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner if (PHINode *PN = dyn_cast<PHINode>(User)) { 504a36791da41cf4f635e50077b290676b873836bdaGabor Greif UserBB = PN->getIncomingBlock(UI); 505dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner } 506692bf6b85e0eaed549cd47d67289ab7b28e32651Eric Christopher 507dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner // Preincrement use iterator so we don't invalidate it. 508dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner ++UI; 509692bf6b85e0eaed549cd47d67289ab7b28e32651Eric Christopher 510dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner // If this user is in the same block as the cast, don't change the cast. 511dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner if (UserBB == DefBB) continue; 512692bf6b85e0eaed549cd47d67289ab7b28e32651Eric Christopher 513dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner // If we have already inserted a cast into this block, use it. 514dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner CastInst *&InsertedCast = InsertedCasts[UserBB]; 515dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner 516dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner if (!InsertedCast) { 51702dea8b39f3acad5de1df36273444d149145e7fcDan Gohman BasicBlock::iterator InsertPt = UserBB->getFirstNonPHI(); 518692bf6b85e0eaed549cd47d67289ab7b28e32651Eric Christopher 519692bf6b85e0eaed549cd47d67289ab7b28e32651Eric Christopher InsertedCast = 520692bf6b85e0eaed549cd47d67289ab7b28e32651Eric Christopher CastInst::Create(CI->getOpcode(), CI->getOperand(0), CI->getType(), "", 521dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner InsertPt); 522dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner MadeChange = true; 523dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner } 524692bf6b85e0eaed549cd47d67289ab7b28e32651Eric Christopher 525ce0b23721e434789f9600c0fd13f0ca17444264fDale Johannesen // Replace a use of the cast with a use of the new cast. 526dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner TheUse = InsertedCast; 52731ff1333e0651192212cee6e090df2ff57d19b53Cameron Zwarich ++NumCastUses; 528dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner } 529692bf6b85e0eaed549cd47d67289ab7b28e32651Eric Christopher 530dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner // If we removed all uses, nuke the cast. 531e003813e9613f41ff2c6a10cb1d3ae3a5b8eab1fDuncan Sands if (CI->use_empty()) { 532dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner CI->eraseFromParent(); 533e003813e9613f41ff2c6a10cb1d3ae3a5b8eab1fDuncan Sands MadeChange = true; 534e003813e9613f41ff2c6a10cb1d3ae3a5b8eab1fDuncan Sands } 535692bf6b85e0eaed549cd47d67289ab7b28e32651Eric Christopher 536dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner return MadeChange; 537dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner} 538dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner 539692bf6b85e0eaed549cd47d67289ab7b28e32651Eric Christopher/// OptimizeCmpExpression - sink the given CmpInst into user blocks to reduce 540ce0b23721e434789f9600c0fd13f0ca17444264fDale Johannesen/// the number of virtual registers that must be created and coalesced. This is 541684b22df79c51114a12289e10a4063d5f02259a9Chris Lattner/// a clear win except on targets with multiple condition code registers 542684b22df79c51114a12289e10a4063d5f02259a9Chris Lattner/// (PowerPC), where it might lose; some adjustment may be wanted there. 543ce0b23721e434789f9600c0fd13f0ca17444264fDale Johannesen/// 544ce0b23721e434789f9600c0fd13f0ca17444264fDale Johannesen/// Return true if any changes are made. 54585fa13c02d383bb87dd9b8b9081a4d34a3e9c52cChris Lattnerstatic bool OptimizeCmpExpression(CmpInst *CI) { 546ce0b23721e434789f9600c0fd13f0ca17444264fDale Johannesen BasicBlock *DefBB = CI->getParent(); 547692bf6b85e0eaed549cd47d67289ab7b28e32651Eric Christopher 548ce0b23721e434789f9600c0fd13f0ca17444264fDale Johannesen /// InsertedCmp - Only insert a cmp in each block once. 549ce0b23721e434789f9600c0fd13f0ca17444264fDale Johannesen DenseMap<BasicBlock*, CmpInst*> InsertedCmps; 550692bf6b85e0eaed549cd47d67289ab7b28e32651Eric Christopher 551ce0b23721e434789f9600c0fd13f0ca17444264fDale Johannesen bool MadeChange = false; 552692bf6b85e0eaed549cd47d67289ab7b28e32651Eric Christopher for (Value::use_iterator UI = CI->use_begin(), E = CI->use_end(); 553ce0b23721e434789f9600c0fd13f0ca17444264fDale Johannesen UI != E; ) { 554ce0b23721e434789f9600c0fd13f0ca17444264fDale Johannesen Use &TheUse = UI.getUse(); 555ce0b23721e434789f9600c0fd13f0ca17444264fDale Johannesen Instruction *User = cast<Instruction>(*UI); 556692bf6b85e0eaed549cd47d67289ab7b28e32651Eric Christopher 557ce0b23721e434789f9600c0fd13f0ca17444264fDale Johannesen // Preincrement use iterator so we don't invalidate it. 558ce0b23721e434789f9600c0fd13f0ca17444264fDale Johannesen ++UI; 559692bf6b85e0eaed549cd47d67289ab7b28e32651Eric Christopher 560ce0b23721e434789f9600c0fd13f0ca17444264fDale Johannesen // Don't bother for PHI nodes. 561ce0b23721e434789f9600c0fd13f0ca17444264fDale Johannesen if (isa<PHINode>(User)) 562ce0b23721e434789f9600c0fd13f0ca17444264fDale Johannesen continue; 563ce0b23721e434789f9600c0fd13f0ca17444264fDale Johannesen 564ce0b23721e434789f9600c0fd13f0ca17444264fDale Johannesen // Figure out which BB this cmp is used in. 565ce0b23721e434789f9600c0fd13f0ca17444264fDale Johannesen BasicBlock *UserBB = User->getParent(); 566692bf6b85e0eaed549cd47d67289ab7b28e32651Eric Christopher 567ce0b23721e434789f9600c0fd13f0ca17444264fDale Johannesen // If this user is in the same block as the cmp, don't change the cmp. 568ce0b23721e434789f9600c0fd13f0ca17444264fDale Johannesen if (UserBB == DefBB) continue; 569692bf6b85e0eaed549cd47d67289ab7b28e32651Eric Christopher 570ce0b23721e434789f9600c0fd13f0ca17444264fDale Johannesen // If we have already inserted a cmp into this block, use it. 571ce0b23721e434789f9600c0fd13f0ca17444264fDale Johannesen CmpInst *&InsertedCmp = InsertedCmps[UserBB]; 572ce0b23721e434789f9600c0fd13f0ca17444264fDale Johannesen 573ce0b23721e434789f9600c0fd13f0ca17444264fDale Johannesen if (!InsertedCmp) { 57402dea8b39f3acad5de1df36273444d149145e7fcDan Gohman BasicBlock::iterator InsertPt = UserBB->getFirstNonPHI(); 575692bf6b85e0eaed549cd47d67289ab7b28e32651Eric Christopher 576692bf6b85e0eaed549cd47d67289ab7b28e32651Eric Christopher InsertedCmp = 5771c8a23c440b1665ba422778cdc74a0c59ecaf39eDan Gohman CmpInst::Create(CI->getOpcode(), 578333c40096561218bc3597cf153c0a3895274414cOwen Anderson CI->getPredicate(), CI->getOperand(0), 579ce0b23721e434789f9600c0fd13f0ca17444264fDale Johannesen CI->getOperand(1), "", InsertPt); 580ce0b23721e434789f9600c0fd13f0ca17444264fDale Johannesen MadeChange = true; 581ce0b23721e434789f9600c0fd13f0ca17444264fDale Johannesen } 582692bf6b85e0eaed549cd47d67289ab7b28e32651Eric Christopher 583ce0b23721e434789f9600c0fd13f0ca17444264fDale Johannesen // Replace a use of the cmp with a use of the new cmp. 584ce0b23721e434789f9600c0fd13f0ca17444264fDale Johannesen TheUse = InsertedCmp; 58531ff1333e0651192212cee6e090df2ff57d19b53Cameron Zwarich ++NumCmpUses; 586ce0b23721e434789f9600c0fd13f0ca17444264fDale Johannesen } 587692bf6b85e0eaed549cd47d67289ab7b28e32651Eric Christopher 588ce0b23721e434789f9600c0fd13f0ca17444264fDale Johannesen // If we removed all uses, nuke the cmp. 589ce0b23721e434789f9600c0fd13f0ca17444264fDale Johannesen if (CI->use_empty()) 590ce0b23721e434789f9600c0fd13f0ca17444264fDale Johannesen CI->eraseFromParent(); 591692bf6b85e0eaed549cd47d67289ab7b28e32651Eric Christopher 592ce0b23721e434789f9600c0fd13f0ca17444264fDale Johannesen return MadeChange; 593ce0b23721e434789f9600c0fd13f0ca17444264fDale Johannesen} 594ce0b23721e434789f9600c0fd13f0ca17444264fDale Johannesen 5950b6cb507385c8bd10b6a51b5e45a9b99d8d94798Benjamin Kramernamespace { 5960b6cb507385c8bd10b6a51b5e45a9b99d8d94798Benjamin Kramerclass CodeGenPrepareFortifiedLibCalls : public SimplifyFortifiedLibCalls { 5970b6cb507385c8bd10b6a51b5e45a9b99d8d94798Benjamin Kramerprotected: 5980b6cb507385c8bd10b6a51b5e45a9b99d8d94798Benjamin Kramer void replaceCall(Value *With) { 5990b6cb507385c8bd10b6a51b5e45a9b99d8d94798Benjamin Kramer CI->replaceAllUsesWith(With); 6000b6cb507385c8bd10b6a51b5e45a9b99d8d94798Benjamin Kramer CI->eraseFromParent(); 6010b6cb507385c8bd10b6a51b5e45a9b99d8d94798Benjamin Kramer } 6020b6cb507385c8bd10b6a51b5e45a9b99d8d94798Benjamin Kramer bool isFoldable(unsigned SizeCIOp, unsigned, bool) const { 603a6aac4c5bc22bb10c7adb11eee3f82c703af7002Gabor Greif if (ConstantInt *SizeCI = 604a6aac4c5bc22bb10c7adb11eee3f82c703af7002Gabor Greif dyn_cast<ConstantInt>(CI->getArgOperand(SizeCIOp))) 605a6aac4c5bc22bb10c7adb11eee3f82c703af7002Gabor Greif return SizeCI->isAllOnesValue(); 6060b6cb507385c8bd10b6a51b5e45a9b99d8d94798Benjamin Kramer return false; 6070b6cb507385c8bd10b6a51b5e45a9b99d8d94798Benjamin Kramer } 6080b6cb507385c8bd10b6a51b5e45a9b99d8d94798Benjamin Kramer}; 6090b6cb507385c8bd10b6a51b5e45a9b99d8d94798Benjamin Kramer} // end anonymous namespace 6100b6cb507385c8bd10b6a51b5e45a9b99d8d94798Benjamin Kramer 611040056fd11693ffc41ce9b777281c71705d0dc1fEric Christopherbool CodeGenPrepare::OptimizeCallInst(CallInst *CI) { 6127579609bfe0d915b6c2d8dc094a132d793ec8855Chris Lattner BasicBlock *BB = CI->getParent(); 6137579609bfe0d915b6c2d8dc094a132d793ec8855Chris Lattner 6147579609bfe0d915b6c2d8dc094a132d793ec8855Chris Lattner // Lower inline assembly if we can. 6157579609bfe0d915b6c2d8dc094a132d793ec8855Chris Lattner // If we found an inline asm expession, and if the target knows how to 6167579609bfe0d915b6c2d8dc094a132d793ec8855Chris Lattner // lower it to normal LLVM code, do so now. 6177579609bfe0d915b6c2d8dc094a132d793ec8855Chris Lattner if (TLI && isa<InlineAsm>(CI->getCalledValue())) { 6187579609bfe0d915b6c2d8dc094a132d793ec8855Chris Lattner if (TLI->ExpandInlineAsm(CI)) { 6197579609bfe0d915b6c2d8dc094a132d793ec8855Chris Lattner // Avoid invalidating the iterator. 6207579609bfe0d915b6c2d8dc094a132d793ec8855Chris Lattner CurInstIterator = BB->begin(); 6217579609bfe0d915b6c2d8dc094a132d793ec8855Chris Lattner // Avoid processing instructions out of order, which could cause 6227579609bfe0d915b6c2d8dc094a132d793ec8855Chris Lattner // reuse before a value is defined. 6237579609bfe0d915b6c2d8dc094a132d793ec8855Chris Lattner SunkAddrs.clear(); 6247579609bfe0d915b6c2d8dc094a132d793ec8855Chris Lattner return true; 6257579609bfe0d915b6c2d8dc094a132d793ec8855Chris Lattner } 6267579609bfe0d915b6c2d8dc094a132d793ec8855Chris Lattner // Sink address computing for memory operands into the block. 6277579609bfe0d915b6c2d8dc094a132d793ec8855Chris Lattner if (OptimizeInlineAsmInst(CI)) 6287579609bfe0d915b6c2d8dc094a132d793ec8855Chris Lattner return true; 6297579609bfe0d915b6c2d8dc094a132d793ec8855Chris Lattner } 6307579609bfe0d915b6c2d8dc094a132d793ec8855Chris Lattner 631040056fd11693ffc41ce9b777281c71705d0dc1fEric Christopher // Lower all uses of llvm.objectsize.* 632040056fd11693ffc41ce9b777281c71705d0dc1fEric Christopher IntrinsicInst *II = dyn_cast<IntrinsicInst>(CI); 633040056fd11693ffc41ce9b777281c71705d0dc1fEric Christopher if (II && II->getIntrinsicID() == Intrinsic::objectsize) { 634de9f5452d3ae894bb7fdd455cec5af50e2560aa5Gabor Greif bool Min = (cast<ConstantInt>(II->getArgOperand(1))->getZExtValue() == 1); 635040056fd11693ffc41ce9b777281c71705d0dc1fEric Christopher const Type *ReturnTy = CI->getType(); 636040056fd11693ffc41ce9b777281c71705d0dc1fEric Christopher Constant *RetVal = ConstantInt::get(ReturnTy, Min ? 0 : -1ULL); 637040056fd11693ffc41ce9b777281c71705d0dc1fEric Christopher CI->replaceAllUsesWith(RetVal); 638040056fd11693ffc41ce9b777281c71705d0dc1fEric Christopher CI->eraseFromParent(); 639040056fd11693ffc41ce9b777281c71705d0dc1fEric Christopher return true; 640040056fd11693ffc41ce9b777281c71705d0dc1fEric Christopher } 641040056fd11693ffc41ce9b777281c71705d0dc1fEric Christopher 642040056fd11693ffc41ce9b777281c71705d0dc1fEric Christopher // From here on out we're working with named functions. 643040056fd11693ffc41ce9b777281c71705d0dc1fEric Christopher if (CI->getCalledFunction() == 0) return false; 644040056fd11693ffc41ce9b777281c71705d0dc1fEric Christopher 645040056fd11693ffc41ce9b777281c71705d0dc1fEric Christopher // We'll need TargetData from here on out. 646040056fd11693ffc41ce9b777281c71705d0dc1fEric Christopher const TargetData *TD = TLI ? TLI->getTargetData() : 0; 647040056fd11693ffc41ce9b777281c71705d0dc1fEric Christopher if (!TD) return false; 648040056fd11693ffc41ce9b777281c71705d0dc1fEric Christopher 6490b6cb507385c8bd10b6a51b5e45a9b99d8d94798Benjamin Kramer // Lower all default uses of _chk calls. This is very similar 6500b6cb507385c8bd10b6a51b5e45a9b99d8d94798Benjamin Kramer // to what InstCombineCalls does, but here we are only lowering calls 651040056fd11693ffc41ce9b777281c71705d0dc1fEric Christopher // that have the default "don't know" as the objectsize. Anything else 652040056fd11693ffc41ce9b777281c71705d0dc1fEric Christopher // should be left alone. 6530b6cb507385c8bd10b6a51b5e45a9b99d8d94798Benjamin Kramer CodeGenPrepareFortifiedLibCalls Simplifier; 6540b6cb507385c8bd10b6a51b5e45a9b99d8d94798Benjamin Kramer return Simplifier.fold(CI, TD); 655040056fd11693ffc41ce9b777281c71705d0dc1fEric Christopher} 65688a5c832ac71eb31d2b1bc143817af9248f4c549Chris Lattner//===----------------------------------------------------------------------===// 65788a5c832ac71eb31d2b1bc143817af9248f4c549Chris Lattner// Memory Optimization 65888a5c832ac71eb31d2b1bc143817af9248f4c549Chris Lattner//===----------------------------------------------------------------------===// 65988a5c832ac71eb31d2b1bc143817af9248f4c549Chris Lattner 660dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner/// IsNonLocalValue - Return true if the specified values are defined in a 661dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner/// different basic block than BB. 662dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattnerstatic bool IsNonLocalValue(Value *V, BasicBlock *BB) { 663dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner if (Instruction *I = dyn_cast<Instruction>(V)) 664dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner return I->getParent() != BB; 665dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner return false; 666dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner} 667dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner 6684a8ee23a8181f668dc294b417f67e1675ad391abBob Wilson/// OptimizeMemoryInst - Load and Store Instructions often have 669dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner/// addressing modes that can do significant amounts of computation. As such, 670dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner/// instruction selection will try to get the load or store to do as much 671dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner/// computation as possible for the program. The problem is that isel can only 672dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner/// see within a single block. As such, we sink as much legal addressing mode 673dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner/// stuff into the block as possible. 67488a5c832ac71eb31d2b1bc143817af9248f4c549Chris Lattner/// 67588a5c832ac71eb31d2b1bc143817af9248f4c549Chris Lattner/// This method is used to optimize both load/store and inline asms with memory 67688a5c832ac71eb31d2b1bc143817af9248f4c549Chris Lattner/// operands. 677896617b776e7b015346160645b19be776cbe3805Chris Lattnerbool CodeGenPrepare::OptimizeMemoryInst(Instruction *MemoryInst, Value *Addr, 67888a5c832ac71eb31d2b1bc143817af9248f4c549Chris Lattner const Type *AccessTy, 67988a5c832ac71eb31d2b1bc143817af9248f4c549Chris Lattner DenseMap<Value*,Value*> &SunkAddrs) { 68035bf4d6d8018160557a92b86181acbcef76f86ebOwen Anderson Value *Repl = Addr; 68135bf4d6d8018160557a92b86181acbcef76f86ebOwen Anderson 682d2f4174fcc69a3328076734fa3256b31e5b7f734Owen Anderson // Try to collapse single-value PHI nodes. This is necessary to undo 683d2f4174fcc69a3328076734fa3256b31e5b7f734Owen Anderson // unprofitable PRE transformations. 6847cb4fa20b5534decf527a6bfcc74bd79ea11cbb1Cameron Zwarich SmallVector<Value*, 8> worklist; 6857cb4fa20b5534decf527a6bfcc74bd79ea11cbb1Cameron Zwarich SmallPtrSet<Value*, 16> Visited; 68635bf4d6d8018160557a92b86181acbcef76f86ebOwen Anderson worklist.push_back(Addr); 68735bf4d6d8018160557a92b86181acbcef76f86ebOwen Anderson 68835bf4d6d8018160557a92b86181acbcef76f86ebOwen Anderson // Use a worklist to iteratively look through PHI nodes, and ensure that 68935bf4d6d8018160557a92b86181acbcef76f86ebOwen Anderson // the addressing mode obtained from the non-PHI roots of the graph 69035bf4d6d8018160557a92b86181acbcef76f86ebOwen Anderson // are equivalent. 69135bf4d6d8018160557a92b86181acbcef76f86ebOwen Anderson Value *Consensus = 0; 69235bf4d6d8018160557a92b86181acbcef76f86ebOwen Anderson unsigned NumUses = 0; 69335bf4d6d8018160557a92b86181acbcef76f86ebOwen Anderson SmallVector<Instruction*, 16> AddrModeInsts; 69435bf4d6d8018160557a92b86181acbcef76f86ebOwen Anderson ExtAddrMode AddrMode; 69535bf4d6d8018160557a92b86181acbcef76f86ebOwen Anderson while (!worklist.empty()) { 69635bf4d6d8018160557a92b86181acbcef76f86ebOwen Anderson Value *V = worklist.back(); 69735bf4d6d8018160557a92b86181acbcef76f86ebOwen Anderson worklist.pop_back(); 69835bf4d6d8018160557a92b86181acbcef76f86ebOwen Anderson 69935bf4d6d8018160557a92b86181acbcef76f86ebOwen Anderson // Break use-def graph loops. 70035bf4d6d8018160557a92b86181acbcef76f86ebOwen Anderson if (Visited.count(V)) { 70135bf4d6d8018160557a92b86181acbcef76f86ebOwen Anderson Consensus = 0; 70235bf4d6d8018160557a92b86181acbcef76f86ebOwen Anderson break; 70335bf4d6d8018160557a92b86181acbcef76f86ebOwen Anderson } 70435bf4d6d8018160557a92b86181acbcef76f86ebOwen Anderson 70535bf4d6d8018160557a92b86181acbcef76f86ebOwen Anderson Visited.insert(V); 70635bf4d6d8018160557a92b86181acbcef76f86ebOwen Anderson 70735bf4d6d8018160557a92b86181acbcef76f86ebOwen Anderson // For a PHI node, push all of its incoming values. 70835bf4d6d8018160557a92b86181acbcef76f86ebOwen Anderson if (PHINode *P = dyn_cast<PHINode>(V)) { 70935bf4d6d8018160557a92b86181acbcef76f86ebOwen Anderson for (unsigned i = 0, e = P->getNumIncomingValues(); i != e; ++i) 71035bf4d6d8018160557a92b86181acbcef76f86ebOwen Anderson worklist.push_back(P->getIncomingValue(i)); 71135bf4d6d8018160557a92b86181acbcef76f86ebOwen Anderson continue; 71235bf4d6d8018160557a92b86181acbcef76f86ebOwen Anderson } 71335bf4d6d8018160557a92b86181acbcef76f86ebOwen Anderson 71435bf4d6d8018160557a92b86181acbcef76f86ebOwen Anderson // For non-PHIs, determine the addressing mode being computed. 71535bf4d6d8018160557a92b86181acbcef76f86ebOwen Anderson SmallVector<Instruction*, 16> NewAddrModeInsts; 71635bf4d6d8018160557a92b86181acbcef76f86ebOwen Anderson ExtAddrMode NewAddrMode = 71735bf4d6d8018160557a92b86181acbcef76f86ebOwen Anderson AddressingModeMatcher::Match(V, AccessTy,MemoryInst, 71835bf4d6d8018160557a92b86181acbcef76f86ebOwen Anderson NewAddrModeInsts, *TLI); 71935bf4d6d8018160557a92b86181acbcef76f86ebOwen Anderson 72035bf4d6d8018160557a92b86181acbcef76f86ebOwen Anderson // Ensure that the obtained addressing mode is equivalent to that obtained 72135bf4d6d8018160557a92b86181acbcef76f86ebOwen Anderson // for all other roots of the PHI traversal. Also, when choosing one 72235bf4d6d8018160557a92b86181acbcef76f86ebOwen Anderson // such root as representative, select the one with the most uses in order 72335bf4d6d8018160557a92b86181acbcef76f86ebOwen Anderson // to keep the cost modeling heuristics in AddressingModeMatcher applicable. 72435bf4d6d8018160557a92b86181acbcef76f86ebOwen Anderson if (!Consensus || NewAddrMode == AddrMode) { 72535bf4d6d8018160557a92b86181acbcef76f86ebOwen Anderson if (V->getNumUses() > NumUses) { 72635bf4d6d8018160557a92b86181acbcef76f86ebOwen Anderson Consensus = V; 72735bf4d6d8018160557a92b86181acbcef76f86ebOwen Anderson NumUses = V->getNumUses(); 72835bf4d6d8018160557a92b86181acbcef76f86ebOwen Anderson AddrMode = NewAddrMode; 72935bf4d6d8018160557a92b86181acbcef76f86ebOwen Anderson AddrModeInsts = NewAddrModeInsts; 730d2f4174fcc69a3328076734fa3256b31e5b7f734Owen Anderson } 73135bf4d6d8018160557a92b86181acbcef76f86ebOwen Anderson continue; 732d2f4174fcc69a3328076734fa3256b31e5b7f734Owen Anderson } 733d2f4174fcc69a3328076734fa3256b31e5b7f734Owen Anderson 73435bf4d6d8018160557a92b86181acbcef76f86ebOwen Anderson Consensus = 0; 73535bf4d6d8018160557a92b86181acbcef76f86ebOwen Anderson break; 736d2f4174fcc69a3328076734fa3256b31e5b7f734Owen Anderson } 737d2f4174fcc69a3328076734fa3256b31e5b7f734Owen Anderson 73835bf4d6d8018160557a92b86181acbcef76f86ebOwen Anderson // If the addressing mode couldn't be determined, or if multiple different 73935bf4d6d8018160557a92b86181acbcef76f86ebOwen Anderson // ones were determined, bail out now. 74035bf4d6d8018160557a92b86181acbcef76f86ebOwen Anderson if (!Consensus) return false; 74135bf4d6d8018160557a92b86181acbcef76f86ebOwen Anderson 742dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner // Check to see if any of the instructions supersumed by this addr mode are 743dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner // non-local to I's BB. 744dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner bool AnyNonLocal = false; 745dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner for (unsigned i = 0, e = AddrModeInsts.size(); i != e; ++i) { 746896617b776e7b015346160645b19be776cbe3805Chris Lattner if (IsNonLocalValue(AddrModeInsts[i], MemoryInst->getParent())) { 747dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner AnyNonLocal = true; 748dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner break; 749dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner } 750dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner } 751692bf6b85e0eaed549cd47d67289ab7b28e32651Eric Christopher 752dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner // If all the instructions matched are already in this BB, don't do anything. 753dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner if (!AnyNonLocal) { 75468d67fdf203ff2d5b0eeb925befd0866bce3aceeDavid Greene DEBUG(dbgs() << "CGP: Found local addrmode: " << AddrMode << "\n"); 755dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner return false; 756dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner } 757692bf6b85e0eaed549cd47d67289ab7b28e32651Eric Christopher 758dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner // Insert this computation right after this user. Since our caller is 759dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner // scanning from the top of the BB to the bottom, reuse of the expr are 760dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner // guaranteed to happen later. 761896617b776e7b015346160645b19be776cbe3805Chris Lattner BasicBlock::iterator InsertPt = MemoryInst; 762692bf6b85e0eaed549cd47d67289ab7b28e32651Eric Christopher 763dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner // Now that we determined the addressing expression we want to use and know 764dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner // that we have to sink it into this block. Check to see if we have already 765dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner // done this for some other load/store instr in this block. If so, reuse the 766dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner // computation. 767dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner Value *&SunkAddr = SunkAddrs[Addr]; 768dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner if (SunkAddr) { 76968d67fdf203ff2d5b0eeb925befd0866bce3aceeDavid Greene DEBUG(dbgs() << "CGP: Reusing nonlocal addrmode: " << AddrMode << " for " 7706c1980b3357207c4d756255bc5e32323eac278dcDan Gohman << *MemoryInst); 771dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner if (SunkAddr->getType() != Addr->getType()) 772dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner SunkAddr = new BitCastInst(SunkAddr, Addr->getType(), "tmp", InsertPt); 773dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner } else { 77468d67fdf203ff2d5b0eeb925befd0866bce3aceeDavid Greene DEBUG(dbgs() << "CGP: SINKING nonlocal addrmode: " << AddrMode << " for " 7756c1980b3357207c4d756255bc5e32323eac278dcDan Gohman << *MemoryInst); 7761d0be15f89cb5056e20e2d24faa8d6afb1573bcaOwen Anderson const Type *IntPtrTy = 7771d0be15f89cb5056e20e2d24faa8d6afb1573bcaOwen Anderson TLI->getTargetData()->getIntPtrType(AccessTy->getContext()); 778692bf6b85e0eaed549cd47d67289ab7b28e32651Eric Christopher 779dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner Value *Result = 0; 780d8d0b6a42c09f1c5b00a4e7029b08074a3da5acdDan Gohman 781d8d0b6a42c09f1c5b00a4e7029b08074a3da5acdDan Gohman // Start with the base register. Do this first so that subsequent address 782d8d0b6a42c09f1c5b00a4e7029b08074a3da5acdDan Gohman // matching finds it last, which will prevent it from trying to match it 783d8d0b6a42c09f1c5b00a4e7029b08074a3da5acdDan Gohman // as the scaled value in case it happens to be a mul. That would be 784d8d0b6a42c09f1c5b00a4e7029b08074a3da5acdDan Gohman // problematic if we've sunk a different mul for the scale, because then 785d8d0b6a42c09f1c5b00a4e7029b08074a3da5acdDan Gohman // we'd end up sinking both muls. 786d8d0b6a42c09f1c5b00a4e7029b08074a3da5acdDan Gohman if (AddrMode.BaseReg) { 787d8d0b6a42c09f1c5b00a4e7029b08074a3da5acdDan Gohman Value *V = AddrMode.BaseReg; 7881df9859c40492511b8aa4321eb76496005d3b75bDuncan Sands if (V->getType()->isPointerTy()) 789d8d0b6a42c09f1c5b00a4e7029b08074a3da5acdDan Gohman V = new PtrToIntInst(V, IntPtrTy, "sunkaddr", InsertPt); 790d8d0b6a42c09f1c5b00a4e7029b08074a3da5acdDan Gohman if (V->getType() != IntPtrTy) 791d8d0b6a42c09f1c5b00a4e7029b08074a3da5acdDan Gohman V = CastInst::CreateIntegerCast(V, IntPtrTy, /*isSigned=*/true, 792d8d0b6a42c09f1c5b00a4e7029b08074a3da5acdDan Gohman "sunkaddr", InsertPt); 793d8d0b6a42c09f1c5b00a4e7029b08074a3da5acdDan Gohman Result = V; 794d8d0b6a42c09f1c5b00a4e7029b08074a3da5acdDan Gohman } 795d8d0b6a42c09f1c5b00a4e7029b08074a3da5acdDan Gohman 796d8d0b6a42c09f1c5b00a4e7029b08074a3da5acdDan Gohman // Add the scale value. 797dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner if (AddrMode.Scale) { 798dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner Value *V = AddrMode.ScaledReg; 799dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner if (V->getType() == IntPtrTy) { 800dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner // done. 8011df9859c40492511b8aa4321eb76496005d3b75bDuncan Sands } else if (V->getType()->isPointerTy()) { 802dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner V = new PtrToIntInst(V, IntPtrTy, "sunkaddr", InsertPt); 803dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner } else if (cast<IntegerType>(IntPtrTy)->getBitWidth() < 804dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner cast<IntegerType>(V->getType())->getBitWidth()) { 805dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner V = new TruncInst(V, IntPtrTy, "sunkaddr", InsertPt); 806dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner } else { 807dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner V = new SExtInst(V, IntPtrTy, "sunkaddr", InsertPt); 808dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner } 809dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner if (AddrMode.Scale != 1) 810eed707b1e6097aac2bb6b3d47271f6300ace7f2eOwen Anderson V = BinaryOperator::CreateMul(V, ConstantInt::get(IntPtrTy, 811d672ecb0178c6247a5eaa5b0fb0c3b23cd25bd7cOwen Anderson AddrMode.Scale), 812dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner "sunkaddr", InsertPt); 813dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner if (Result) 8147cbd8a3e92221437048b484d5ef9c0a22d0f8c58Gabor Greif Result = BinaryOperator::CreateAdd(Result, V, "sunkaddr", InsertPt); 815dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner else 816dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner Result = V; 817dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner } 818692bf6b85e0eaed549cd47d67289ab7b28e32651Eric Christopher 819dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner // Add in the BaseGV if present. 820dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner if (AddrMode.BaseGV) { 821dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner Value *V = new PtrToIntInst(AddrMode.BaseGV, IntPtrTy, "sunkaddr", 822dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner InsertPt); 823dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner if (Result) 8247cbd8a3e92221437048b484d5ef9c0a22d0f8c58Gabor Greif Result = BinaryOperator::CreateAdd(Result, V, "sunkaddr", InsertPt); 825dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner else 826dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner Result = V; 827dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner } 828692bf6b85e0eaed549cd47d67289ab7b28e32651Eric Christopher 829dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner // Add in the Base Offset if present. 830dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner if (AddrMode.BaseOffs) { 831eed707b1e6097aac2bb6b3d47271f6300ace7f2eOwen Anderson Value *V = ConstantInt::get(IntPtrTy, AddrMode.BaseOffs); 832dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner if (Result) 8337cbd8a3e92221437048b484d5ef9c0a22d0f8c58Gabor Greif Result = BinaryOperator::CreateAdd(Result, V, "sunkaddr", InsertPt); 834dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner else 835dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner Result = V; 836dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner } 837dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner 838dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner if (Result == 0) 839a7235ea7245028a0723e8ab7fd011386b3900777Owen Anderson SunkAddr = Constant::getNullValue(Addr->getType()); 840dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner else 841dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner SunkAddr = new IntToPtrInst(Result, Addr->getType(), "sunkaddr",InsertPt); 842dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner } 843692bf6b85e0eaed549cd47d67289ab7b28e32651Eric Christopher 844d2f4174fcc69a3328076734fa3256b31e5b7f734Owen Anderson MemoryInst->replaceUsesOfWith(Repl, SunkAddr); 845692bf6b85e0eaed549cd47d67289ab7b28e32651Eric Christopher 846d2f4174fcc69a3328076734fa3256b31e5b7f734Owen Anderson if (Repl->use_empty()) { 847d2f4174fcc69a3328076734fa3256b31e5b7f734Owen Anderson RecursivelyDeleteTriviallyDeadInstructions(Repl); 848536d31b5b391ee76eae33f4756f6442bf10b2d72Dale Johannesen // This address is now available for reassignment, so erase the table entry; 849536d31b5b391ee76eae33f4756f6442bf10b2d72Dale Johannesen // we don't want to match some completely different instruction. 850536d31b5b391ee76eae33f4756f6442bf10b2d72Dale Johannesen SunkAddrs[Addr] = 0; 851536d31b5b391ee76eae33f4756f6442bf10b2d72Dale Johannesen } 85231ff1333e0651192212cee6e090df2ff57d19b53Cameron Zwarich ++NumMemoryInsts; 853dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner return true; 854dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner} 855dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner 8569bf12b5583104c810cfadcdce91edf9efad79973Evan Cheng/// OptimizeInlineAsmInst - If there are any memory operands, use 85788a5c832ac71eb31d2b1bc143817af9248f4c549Chris Lattner/// OptimizeMemoryInst to sink their address computing into the block when 8589bf12b5583104c810cfadcdce91edf9efad79973Evan Cheng/// possible / profitable. 8597579609bfe0d915b6c2d8dc094a132d793ec8855Chris Lattnerbool CodeGenPrepare::OptimizeInlineAsmInst(CallInst *CS) { 8609bf12b5583104c810cfadcdce91edf9efad79973Evan Cheng bool MadeChange = false; 8619bf12b5583104c810cfadcdce91edf9efad79973Evan Cheng 8627579609bfe0d915b6c2d8dc094a132d793ec8855Chris Lattner TargetLowering::AsmOperandInfoVector 8637579609bfe0d915b6c2d8dc094a132d793ec8855Chris Lattner TargetConstraints = TLI->ParseConstraints(CS); 864677c6ecd0804c247eb727a830b50cd6537a6c12cDale Johannesen unsigned ArgNo = 0; 865eac6e1d0c748afc3d1496be0753ffbe5f5a4279bJohn Thompson for (unsigned i = 0, e = TargetConstraints.size(); i != e; ++i) { 866eac6e1d0c748afc3d1496be0753ffbe5f5a4279bJohn Thompson TargetLowering::AsmOperandInfo &OpInfo = TargetConstraints[i]; 867eac6e1d0c748afc3d1496be0753ffbe5f5a4279bJohn Thompson 8689bf12b5583104c810cfadcdce91edf9efad79973Evan Cheng // Compute the constraint code and ConstraintType to use. 8691784d160e4efa75782884d451d0788b9457e67dcDale Johannesen TLI->ComputeConstraintToUse(OpInfo, SDValue()); 8709bf12b5583104c810cfadcdce91edf9efad79973Evan Cheng 8719ec8095485c994522c9a50e16fc029de94c20476Eli Friedman if (OpInfo.ConstraintType == TargetLowering::C_Memory && 8729ec8095485c994522c9a50e16fc029de94c20476Eli Friedman OpInfo.isIndirect) { 8737579609bfe0d915b6c2d8dc094a132d793ec8855Chris Lattner Value *OpVal = CS->getArgOperand(ArgNo++); 8747579609bfe0d915b6c2d8dc094a132d793ec8855Chris Lattner MadeChange |= OptimizeMemoryInst(CS, OpVal, OpVal->getType(), SunkAddrs); 875677c6ecd0804c247eb727a830b50cd6537a6c12cDale Johannesen } else if (OpInfo.Type == InlineAsm::isInput) 876677c6ecd0804c247eb727a830b50cd6537a6c12cDale Johannesen ArgNo++; 8779bf12b5583104c810cfadcdce91edf9efad79973Evan Cheng } 8789bf12b5583104c810cfadcdce91edf9efad79973Evan Cheng 8799bf12b5583104c810cfadcdce91edf9efad79973Evan Cheng return MadeChange; 8809bf12b5583104c810cfadcdce91edf9efad79973Evan Cheng} 8819bf12b5583104c810cfadcdce91edf9efad79973Evan Cheng 882b00f236b03ea57520f94823780896ebdbc5d8bdcDan Gohman/// MoveExtToFormExtLoad - Move a zext or sext fed by a load into the same 883b00f236b03ea57520f94823780896ebdbc5d8bdcDan Gohman/// basic block as the load, unless conditions are unfavorable. This allows 884b00f236b03ea57520f94823780896ebdbc5d8bdcDan Gohman/// SelectionDAG to fold the extend into the load. 885b00f236b03ea57520f94823780896ebdbc5d8bdcDan Gohman/// 886b00f236b03ea57520f94823780896ebdbc5d8bdcDan Gohmanbool CodeGenPrepare::MoveExtToFormExtLoad(Instruction *I) { 887b00f236b03ea57520f94823780896ebdbc5d8bdcDan Gohman // Look for a load being extended. 888b00f236b03ea57520f94823780896ebdbc5d8bdcDan Gohman LoadInst *LI = dyn_cast<LoadInst>(I->getOperand(0)); 889b00f236b03ea57520f94823780896ebdbc5d8bdcDan Gohman if (!LI) return false; 890b00f236b03ea57520f94823780896ebdbc5d8bdcDan Gohman 891b00f236b03ea57520f94823780896ebdbc5d8bdcDan Gohman // If they're already in the same block, there's nothing to do. 892b00f236b03ea57520f94823780896ebdbc5d8bdcDan Gohman if (LI->getParent() == I->getParent()) 893b00f236b03ea57520f94823780896ebdbc5d8bdcDan Gohman return false; 894b00f236b03ea57520f94823780896ebdbc5d8bdcDan Gohman 895b00f236b03ea57520f94823780896ebdbc5d8bdcDan Gohman // If the load has other users and the truncate is not free, this probably 896b00f236b03ea57520f94823780896ebdbc5d8bdcDan Gohman // isn't worthwhile. 897b00f236b03ea57520f94823780896ebdbc5d8bdcDan Gohman if (!LI->hasOneUse() && 898ec57a1acec7803fff2faa54c6ea8fec2be01aeb9Bob Wilson TLI && (TLI->isTypeLegal(TLI->getValueType(LI->getType())) || 899ec57a1acec7803fff2faa54c6ea8fec2be01aeb9Bob Wilson !TLI->isTypeLegal(TLI->getValueType(I->getType()))) && 90071dc4d96ed39fadcdccf8c578d49a1afdae0c6baBob Wilson !TLI->isTruncateFree(I->getType(), LI->getType())) 901b00f236b03ea57520f94823780896ebdbc5d8bdcDan Gohman return false; 902b00f236b03ea57520f94823780896ebdbc5d8bdcDan Gohman 903b00f236b03ea57520f94823780896ebdbc5d8bdcDan Gohman // Check whether the target supports casts folded into loads. 904b00f236b03ea57520f94823780896ebdbc5d8bdcDan Gohman unsigned LType; 905b00f236b03ea57520f94823780896ebdbc5d8bdcDan Gohman if (isa<ZExtInst>(I)) 906b00f236b03ea57520f94823780896ebdbc5d8bdcDan Gohman LType = ISD::ZEXTLOAD; 907b00f236b03ea57520f94823780896ebdbc5d8bdcDan Gohman else { 908b00f236b03ea57520f94823780896ebdbc5d8bdcDan Gohman assert(isa<SExtInst>(I) && "Unexpected ext type!"); 909b00f236b03ea57520f94823780896ebdbc5d8bdcDan Gohman LType = ISD::SEXTLOAD; 910b00f236b03ea57520f94823780896ebdbc5d8bdcDan Gohman } 911b00f236b03ea57520f94823780896ebdbc5d8bdcDan Gohman if (TLI && !TLI->isLoadExtLegal(LType, TLI->getValueType(LI->getType()))) 912b00f236b03ea57520f94823780896ebdbc5d8bdcDan Gohman return false; 913b00f236b03ea57520f94823780896ebdbc5d8bdcDan Gohman 914b00f236b03ea57520f94823780896ebdbc5d8bdcDan Gohman // Move the extend into the same block as the load, so that SelectionDAG 915b00f236b03ea57520f94823780896ebdbc5d8bdcDan Gohman // can fold it. 916b00f236b03ea57520f94823780896ebdbc5d8bdcDan Gohman I->removeFromParent(); 917b00f236b03ea57520f94823780896ebdbc5d8bdcDan Gohman I->insertAfter(LI); 91831ff1333e0651192212cee6e090df2ff57d19b53Cameron Zwarich ++NumExtsMoved; 919b00f236b03ea57520f94823780896ebdbc5d8bdcDan Gohman return true; 920b00f236b03ea57520f94823780896ebdbc5d8bdcDan Gohman} 921b00f236b03ea57520f94823780896ebdbc5d8bdcDan Gohman 922bdcb726fcad1e3fddc70847a2b91d4d4f9396938Evan Chengbool CodeGenPrepare::OptimizeExtUses(Instruction *I) { 923bdcb726fcad1e3fddc70847a2b91d4d4f9396938Evan Cheng BasicBlock *DefBB = I->getParent(); 924bdcb726fcad1e3fddc70847a2b91d4d4f9396938Evan Cheng 9259120f5c35b756e0b9d7747616e97df8f30edfcc8Bob Wilson // If the result of a {s|z}ext and its source are both live out, rewrite all 926bdcb726fcad1e3fddc70847a2b91d4d4f9396938Evan Cheng // other uses of the source with result of extension. 927bdcb726fcad1e3fddc70847a2b91d4d4f9396938Evan Cheng Value *Src = I->getOperand(0); 928bdcb726fcad1e3fddc70847a2b91d4d4f9396938Evan Cheng if (Src->hasOneUse()) 929bdcb726fcad1e3fddc70847a2b91d4d4f9396938Evan Cheng return false; 930bdcb726fcad1e3fddc70847a2b91d4d4f9396938Evan Cheng 931696e5c047bd06bf6b7b5471b3f4dec319b43628bEvan Cheng // Only do this xform if truncating is free. 93253bdbd756581a9a1d6d381059f103c5f3c687bb6Gabor Greif if (TLI && !TLI->isTruncateFree(I->getType(), Src->getType())) 933f9785f92b630e69262c395b2fc0893451169d68bEvan Cheng return false; 934f9785f92b630e69262c395b2fc0893451169d68bEvan Cheng 935772de516b6851e679d3da9e5171712b9c3122019Evan Cheng // Only safe to perform the optimization if the source is also defined in 936765dff258545f019502023045b471443ff9ef6c4Evan Cheng // this block. 937765dff258545f019502023045b471443ff9ef6c4Evan Cheng if (!isa<Instruction>(Src) || DefBB != cast<Instruction>(Src)->getParent()) 938772de516b6851e679d3da9e5171712b9c3122019Evan Cheng return false; 939772de516b6851e679d3da9e5171712b9c3122019Evan Cheng 940bdcb726fcad1e3fddc70847a2b91d4d4f9396938Evan Cheng bool DefIsLiveOut = false; 941692bf6b85e0eaed549cd47d67289ab7b28e32651Eric Christopher for (Value::use_iterator UI = I->use_begin(), E = I->use_end(); 942bdcb726fcad1e3fddc70847a2b91d4d4f9396938Evan Cheng UI != E; ++UI) { 943bdcb726fcad1e3fddc70847a2b91d4d4f9396938Evan Cheng Instruction *User = cast<Instruction>(*UI); 944bdcb726fcad1e3fddc70847a2b91d4d4f9396938Evan Cheng 945bdcb726fcad1e3fddc70847a2b91d4d4f9396938Evan Cheng // Figure out which BB this ext is used in. 946bdcb726fcad1e3fddc70847a2b91d4d4f9396938Evan Cheng BasicBlock *UserBB = User->getParent(); 947bdcb726fcad1e3fddc70847a2b91d4d4f9396938Evan Cheng if (UserBB == DefBB) continue; 948bdcb726fcad1e3fddc70847a2b91d4d4f9396938Evan Cheng DefIsLiveOut = true; 949bdcb726fcad1e3fddc70847a2b91d4d4f9396938Evan Cheng break; 950bdcb726fcad1e3fddc70847a2b91d4d4f9396938Evan Cheng } 951bdcb726fcad1e3fddc70847a2b91d4d4f9396938Evan Cheng if (!DefIsLiveOut) 952bdcb726fcad1e3fddc70847a2b91d4d4f9396938Evan Cheng return false; 953bdcb726fcad1e3fddc70847a2b91d4d4f9396938Evan Cheng 954765dff258545f019502023045b471443ff9ef6c4Evan Cheng // Make sure non of the uses are PHI nodes. 955692bf6b85e0eaed549cd47d67289ab7b28e32651Eric Christopher for (Value::use_iterator UI = Src->use_begin(), E = Src->use_end(); 956765dff258545f019502023045b471443ff9ef6c4Evan Cheng UI != E; ++UI) { 957765dff258545f019502023045b471443ff9ef6c4Evan Cheng Instruction *User = cast<Instruction>(*UI); 958f9785f92b630e69262c395b2fc0893451169d68bEvan Cheng BasicBlock *UserBB = User->getParent(); 959f9785f92b630e69262c395b2fc0893451169d68bEvan Cheng if (UserBB == DefBB) continue; 960f9785f92b630e69262c395b2fc0893451169d68bEvan Cheng // Be conservative. We don't want this xform to end up introducing 961f9785f92b630e69262c395b2fc0893451169d68bEvan Cheng // reloads just before load / store instructions. 962f9785f92b630e69262c395b2fc0893451169d68bEvan Cheng if (isa<PHINode>(User) || isa<LoadInst>(User) || isa<StoreInst>(User)) 963765dff258545f019502023045b471443ff9ef6c4Evan Cheng return false; 964765dff258545f019502023045b471443ff9ef6c4Evan Cheng } 965765dff258545f019502023045b471443ff9ef6c4Evan Cheng 966bdcb726fcad1e3fddc70847a2b91d4d4f9396938Evan Cheng // InsertedTruncs - Only insert one trunc in each block once. 967bdcb726fcad1e3fddc70847a2b91d4d4f9396938Evan Cheng DenseMap<BasicBlock*, Instruction*> InsertedTruncs; 968bdcb726fcad1e3fddc70847a2b91d4d4f9396938Evan Cheng 969bdcb726fcad1e3fddc70847a2b91d4d4f9396938Evan Cheng bool MadeChange = false; 970692bf6b85e0eaed549cd47d67289ab7b28e32651Eric Christopher for (Value::use_iterator UI = Src->use_begin(), E = Src->use_end(); 971bdcb726fcad1e3fddc70847a2b91d4d4f9396938Evan Cheng UI != E; ++UI) { 972bdcb726fcad1e3fddc70847a2b91d4d4f9396938Evan Cheng Use &TheUse = UI.getUse(); 973bdcb726fcad1e3fddc70847a2b91d4d4f9396938Evan Cheng Instruction *User = cast<Instruction>(*UI); 974bdcb726fcad1e3fddc70847a2b91d4d4f9396938Evan Cheng 975bdcb726fcad1e3fddc70847a2b91d4d4f9396938Evan Cheng // Figure out which BB this ext is used in. 976bdcb726fcad1e3fddc70847a2b91d4d4f9396938Evan Cheng BasicBlock *UserBB = User->getParent(); 977bdcb726fcad1e3fddc70847a2b91d4d4f9396938Evan Cheng if (UserBB == DefBB) continue; 978bdcb726fcad1e3fddc70847a2b91d4d4f9396938Evan Cheng 979bdcb726fcad1e3fddc70847a2b91d4d4f9396938Evan Cheng // Both src and def are live in this block. Rewrite the use. 980bdcb726fcad1e3fddc70847a2b91d4d4f9396938Evan Cheng Instruction *&InsertedTrunc = InsertedTruncs[UserBB]; 981bdcb726fcad1e3fddc70847a2b91d4d4f9396938Evan Cheng 982bdcb726fcad1e3fddc70847a2b91d4d4f9396938Evan Cheng if (!InsertedTrunc) { 98302dea8b39f3acad5de1df36273444d149145e7fcDan Gohman BasicBlock::iterator InsertPt = UserBB->getFirstNonPHI(); 984692bf6b85e0eaed549cd47d67289ab7b28e32651Eric Christopher 985bdcb726fcad1e3fddc70847a2b91d4d4f9396938Evan Cheng InsertedTrunc = new TruncInst(I, Src->getType(), "", InsertPt); 986bdcb726fcad1e3fddc70847a2b91d4d4f9396938Evan Cheng } 987bdcb726fcad1e3fddc70847a2b91d4d4f9396938Evan Cheng 988bdcb726fcad1e3fddc70847a2b91d4d4f9396938Evan Cheng // Replace a use of the {s|z}ext source with a use of the result. 989bdcb726fcad1e3fddc70847a2b91d4d4f9396938Evan Cheng TheUse = InsertedTrunc; 99031ff1333e0651192212cee6e090df2ff57d19b53Cameron Zwarich ++NumExtUses; 991bdcb726fcad1e3fddc70847a2b91d4d4f9396938Evan Cheng MadeChange = true; 992bdcb726fcad1e3fddc70847a2b91d4d4f9396938Evan Cheng } 993bdcb726fcad1e3fddc70847a2b91d4d4f9396938Evan Cheng 994bdcb726fcad1e3fddc70847a2b91d4d4f9396938Evan Cheng return MadeChange; 995bdcb726fcad1e3fddc70847a2b91d4d4f9396938Evan Cheng} 996bdcb726fcad1e3fddc70847a2b91d4d4f9396938Evan Cheng 997c061101e03ef6d2ca550f8fe71594a5e1c02e348Cameron Zwarichbool CodeGenPrepare::OptimizeInst(Instruction *I) { 998c061101e03ef6d2ca550f8fe71594a5e1c02e348Cameron Zwarich bool MadeChange = false; 999c061101e03ef6d2ca550f8fe71594a5e1c02e348Cameron Zwarich 1000c061101e03ef6d2ca550f8fe71594a5e1c02e348Cameron Zwarich if (PHINode *P = dyn_cast<PHINode>(I)) { 1001c061101e03ef6d2ca550f8fe71594a5e1c02e348Cameron Zwarich // It is possible for very late stage optimizations (such as SimplifyCFG) 1002c061101e03ef6d2ca550f8fe71594a5e1c02e348Cameron Zwarich // to introduce PHI nodes too late to be cleaned up. If we detect such a 1003c061101e03ef6d2ca550f8fe71594a5e1c02e348Cameron Zwarich // trivial PHI, go ahead and zap it here. 1004c061101e03ef6d2ca550f8fe71594a5e1c02e348Cameron Zwarich if (Value *V = SimplifyInstruction(P)) { 1005c061101e03ef6d2ca550f8fe71594a5e1c02e348Cameron Zwarich P->replaceAllUsesWith(V); 1006c061101e03ef6d2ca550f8fe71594a5e1c02e348Cameron Zwarich P->eraseFromParent(); 1007c061101e03ef6d2ca550f8fe71594a5e1c02e348Cameron Zwarich ++NumPHIsElim; 1008c061101e03ef6d2ca550f8fe71594a5e1c02e348Cameron Zwarich } 1009c061101e03ef6d2ca550f8fe71594a5e1c02e348Cameron Zwarich } else if (CastInst *CI = dyn_cast<CastInst>(I)) { 1010c061101e03ef6d2ca550f8fe71594a5e1c02e348Cameron Zwarich // If the source of the cast is a constant, then this should have 1011c061101e03ef6d2ca550f8fe71594a5e1c02e348Cameron Zwarich // already been constant folded. The only reason NOT to constant fold 1012c061101e03ef6d2ca550f8fe71594a5e1c02e348Cameron Zwarich // it is if something (e.g. LSR) was careful to place the constant 1013c061101e03ef6d2ca550f8fe71594a5e1c02e348Cameron Zwarich // evaluation in a block other than then one that uses it (e.g. to hoist 1014c061101e03ef6d2ca550f8fe71594a5e1c02e348Cameron Zwarich // the address of globals out of a loop). If this is the case, we don't 1015c061101e03ef6d2ca550f8fe71594a5e1c02e348Cameron Zwarich // want to forward-subst the cast. 1016c061101e03ef6d2ca550f8fe71594a5e1c02e348Cameron Zwarich if (isa<Constant>(CI->getOperand(0))) 1017c061101e03ef6d2ca550f8fe71594a5e1c02e348Cameron Zwarich return false; 1018c061101e03ef6d2ca550f8fe71594a5e1c02e348Cameron Zwarich 1019c061101e03ef6d2ca550f8fe71594a5e1c02e348Cameron Zwarich bool Change = false; 1020c061101e03ef6d2ca550f8fe71594a5e1c02e348Cameron Zwarich if (TLI) { 1021c061101e03ef6d2ca550f8fe71594a5e1c02e348Cameron Zwarich Change = OptimizeNoopCopyExpression(CI, *TLI); 1022c061101e03ef6d2ca550f8fe71594a5e1c02e348Cameron Zwarich MadeChange |= Change; 1023c061101e03ef6d2ca550f8fe71594a5e1c02e348Cameron Zwarich } 1024c061101e03ef6d2ca550f8fe71594a5e1c02e348Cameron Zwarich 1025c061101e03ef6d2ca550f8fe71594a5e1c02e348Cameron Zwarich if (!Change && (isa<ZExtInst>(I) || isa<SExtInst>(I))) { 1026c061101e03ef6d2ca550f8fe71594a5e1c02e348Cameron Zwarich MadeChange |= MoveExtToFormExtLoad(I); 1027c061101e03ef6d2ca550f8fe71594a5e1c02e348Cameron Zwarich MadeChange |= OptimizeExtUses(I); 1028c061101e03ef6d2ca550f8fe71594a5e1c02e348Cameron Zwarich } 1029c061101e03ef6d2ca550f8fe71594a5e1c02e348Cameron Zwarich } else if (CmpInst *CI = dyn_cast<CmpInst>(I)) { 1030c061101e03ef6d2ca550f8fe71594a5e1c02e348Cameron Zwarich MadeChange |= OptimizeCmpExpression(CI); 1031c061101e03ef6d2ca550f8fe71594a5e1c02e348Cameron Zwarich } else if (LoadInst *LI = dyn_cast<LoadInst>(I)) { 1032c061101e03ef6d2ca550f8fe71594a5e1c02e348Cameron Zwarich if (TLI) 1033c061101e03ef6d2ca550f8fe71594a5e1c02e348Cameron Zwarich MadeChange |= OptimizeMemoryInst(I, I->getOperand(0), LI->getType(), 1034c061101e03ef6d2ca550f8fe71594a5e1c02e348Cameron Zwarich SunkAddrs); 1035c061101e03ef6d2ca550f8fe71594a5e1c02e348Cameron Zwarich } else if (StoreInst *SI = dyn_cast<StoreInst>(I)) { 1036c061101e03ef6d2ca550f8fe71594a5e1c02e348Cameron Zwarich if (TLI) 1037c061101e03ef6d2ca550f8fe71594a5e1c02e348Cameron Zwarich MadeChange |= OptimizeMemoryInst(I, SI->getOperand(1), 1038c061101e03ef6d2ca550f8fe71594a5e1c02e348Cameron Zwarich SI->getOperand(0)->getType(), 1039c061101e03ef6d2ca550f8fe71594a5e1c02e348Cameron Zwarich SunkAddrs); 1040865ae1a9e77920e07c4a6a992736109c2cd4fe02Cameron Zwarich } else if (GetElementPtrInst *GEPI = dyn_cast<GetElementPtrInst>(I)) { 1041865ae1a9e77920e07c4a6a992736109c2cd4fe02Cameron Zwarich if (GEPI->hasAllZeroIndices()) { 1042865ae1a9e77920e07c4a6a992736109c2cd4fe02Cameron Zwarich /// The GEP operand must be a pointer, so must its result -> BitCast 1043865ae1a9e77920e07c4a6a992736109c2cd4fe02Cameron Zwarich Instruction *NC = new BitCastInst(GEPI->getOperand(0), GEPI->getType(), 1044865ae1a9e77920e07c4a6a992736109c2cd4fe02Cameron Zwarich GEPI->getName(), GEPI); 1045865ae1a9e77920e07c4a6a992736109c2cd4fe02Cameron Zwarich GEPI->replaceAllUsesWith(NC); 1046865ae1a9e77920e07c4a6a992736109c2cd4fe02Cameron Zwarich GEPI->eraseFromParent(); 1047865ae1a9e77920e07c4a6a992736109c2cd4fe02Cameron Zwarich ++NumGEPsElim; 1048865ae1a9e77920e07c4a6a992736109c2cd4fe02Cameron Zwarich MadeChange = true; 1049865ae1a9e77920e07c4a6a992736109c2cd4fe02Cameron Zwarich OptimizeInst(NC); 1050865ae1a9e77920e07c4a6a992736109c2cd4fe02Cameron Zwarich } 10516cf34abe1c99e79565c75cd3e62755239463e574Cameron Zwarich } else if (CallInst *CI = dyn_cast<CallInst>(I)) { 10527579609bfe0d915b6c2d8dc094a132d793ec8855Chris Lattner MadeChange |= OptimizeCallInst(CI); 1053c061101e03ef6d2ca550f8fe71594a5e1c02e348Cameron Zwarich } 1054c061101e03ef6d2ca550f8fe71594a5e1c02e348Cameron Zwarich 1055c061101e03ef6d2ca550f8fe71594a5e1c02e348Cameron Zwarich return MadeChange; 1056c061101e03ef6d2ca550f8fe71594a5e1c02e348Cameron Zwarich} 1057c061101e03ef6d2ca550f8fe71594a5e1c02e348Cameron Zwarich 1058dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner// In this pass we look for GEP and cast instructions that are used 1059dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner// across basic blocks and rewrite them to improve basic-block-at-a-time 1060dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner// selection. 1061dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattnerbool CodeGenPrepare::OptimizeBlock(BasicBlock &BB) { 1062dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner bool MadeChange = false; 1063692bf6b85e0eaed549cd47d67289ab7b28e32651Eric Christopher 1064ab63152871f4144050d0a58d592a95e089fe40d4Evan Cheng // Split all critical edges where the dest block has a PHI. 1065e1bcb440dc0ca3c41fda1c0c581abfc4f38ca170Evan Cheng if (CriticalEdgeSplit) { 1066e1bcb440dc0ca3c41fda1c0c581abfc4f38ca170Evan Cheng TerminatorInst *BBTI = BB.getTerminator(); 1067e1bcb440dc0ca3c41fda1c0c581abfc4f38ca170Evan Cheng if (BBTI->getNumSuccessors() > 1 && !isa<IndirectBrInst>(BBTI)) { 1068e1bcb440dc0ca3c41fda1c0c581abfc4f38ca170Evan Cheng for (unsigned i = 0, e = BBTI->getNumSuccessors(); i != e; ++i) { 1069e1bcb440dc0ca3c41fda1c0c581abfc4f38ca170Evan Cheng BasicBlock *SuccBB = BBTI->getSuccessor(i); 1070e1bcb440dc0ca3c41fda1c0c581abfc4f38ca170Evan Cheng if (isa<PHINode>(SuccBB->begin()) && isCriticalEdge(BBTI, i, true)) 1071e1bcb440dc0ca3c41fda1c0c581abfc4f38ca170Evan Cheng SplitEdgeNicely(BBTI, i, BackEdges, this); 1072e1bcb440dc0ca3c41fda1c0c581abfc4f38ca170Evan Cheng } 1073ab63152871f4144050d0a58d592a95e089fe40d4Evan Cheng } 1074dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner } 1075692bf6b85e0eaed549cd47d67289ab7b28e32651Eric Christopher 10768c3527e7a475dd3369a485a4f610d56f7005b7b5Cameron Zwarich SunkAddrs.clear(); 1077692bf6b85e0eaed549cd47d67289ab7b28e32651Eric Christopher 10787579609bfe0d915b6c2d8dc094a132d793ec8855Chris Lattner CurInstIterator = BB.begin(); 10797579609bfe0d915b6c2d8dc094a132d793ec8855Chris Lattner for (BasicBlock::iterator E = BB.end(); CurInstIterator != E; ) { 10807579609bfe0d915b6c2d8dc094a132d793ec8855Chris Lattner Instruction *I = CurInstIterator++; 10817579609bfe0d915b6c2d8dc094a132d793ec8855Chris Lattner 10827579609bfe0d915b6c2d8dc094a132d793ec8855Chris Lattner if (CallInst *CI = dyn_cast<CallInst>(I)) 10837579609bfe0d915b6c2d8dc094a132d793ec8855Chris Lattner MadeChange |= OptimizeCallInst(CI); 10847579609bfe0d915b6c2d8dc094a132d793ec8855Chris Lattner else 1085c061101e03ef6d2ca550f8fe71594a5e1c02e348Cameron Zwarich MadeChange |= OptimizeInst(I); 1086dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner } 1087692bf6b85e0eaed549cd47d67289ab7b28e32651Eric Christopher 1088dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner return MadeChange; 1089dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner} 1090