CodeGenPrepare.cpp revision 2048c379dd9e080c3e1bb0c93636da9564d8772c
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" 4594e8e0cfbe13cdbdf7addc6e36df863cab92e4c9Chris Lattner#include "llvm/Support/ValueHandle.h" 46dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattnerusing namespace llvm; 47088a1e84ea985a22efcf907d7789064fee3a97b9Chris Lattnerusing namespace llvm::PatternMatch; 48dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner 4931ff1333e0651192212cee6e090df2ff57d19b53Cameron ZwarichSTATISTIC(NumBlocksElim, "Number of blocks eliminated"); 50485fafc8406db8552ba5e3ff871a6ee32694ad90Evan ChengSTATISTIC(NumPHIsElim, "Number of trivial PHIs eliminated"); 51485fafc8406db8552ba5e3ff871a6ee32694ad90Evan ChengSTATISTIC(NumGEPsElim, "Number of GEPs converted to casts"); 5231ff1333e0651192212cee6e090df2ff57d19b53Cameron ZwarichSTATISTIC(NumCmpUses, "Number of uses of Cmp expressions replaced with uses of " 5331ff1333e0651192212cee6e090df2ff57d19b53Cameron Zwarich "sunken Cmps"); 5431ff1333e0651192212cee6e090df2ff57d19b53Cameron ZwarichSTATISTIC(NumCastUses, "Number of uses of Cast expressions replaced with uses " 5531ff1333e0651192212cee6e090df2ff57d19b53Cameron Zwarich "of sunken Casts"); 5631ff1333e0651192212cee6e090df2ff57d19b53Cameron ZwarichSTATISTIC(NumMemoryInsts, "Number of memory instructions whose address " 5731ff1333e0651192212cee6e090df2ff57d19b53Cameron Zwarich "computations were sunk"); 58485fafc8406db8552ba5e3ff871a6ee32694ad90Evan ChengSTATISTIC(NumExtsMoved, "Number of [s|z]ext instructions combined with loads"); 59485fafc8406db8552ba5e3ff871a6ee32694ad90Evan ChengSTATISTIC(NumExtUses, "Number of uses of [s|z]ext instructions optimized"); 60485fafc8406db8552ba5e3ff871a6ee32694ad90Evan ChengSTATISTIC(NumRetsDup, "Number of return instructions duplicated"); 61f56ea610ed63db0b8a8a9aca95222aa78ce293eeDevang PatelSTATISTIC(NumDbgValueMoved, "Number of debug value instructions moved"); 627eb589d3f9294dbfe4d5205045bd8119a9666532Jakob Stoklund Olesen 63899eaa35696bb0a9a625acd70a14876834af6cc5Cameron Zwarichstatic cl::opt<bool> DisableBranchOpts( 64899eaa35696bb0a9a625acd70a14876834af6cc5Cameron Zwarich "disable-cgp-branch-opts", cl::Hidden, cl::init(false), 65899eaa35696bb0a9a625acd70a14876834af6cc5Cameron Zwarich cl::desc("Disable branch optimizations in CodeGenPrepare")); 66899eaa35696bb0a9a625acd70a14876834af6cc5Cameron Zwarich 67692bf6b85e0eaed549cd47d67289ab7b28e32651Eric Christophernamespace { 683e8b6631e67e01e4960a7ba4668a50c596607473Chris Lattner class CodeGenPrepare : public FunctionPass { 69dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner /// TLI - Keep a pointer of a TargetLowering to consult for determining 70dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner /// transformation profitability. 71dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner const TargetLowering *TLI; 7280f6a507d4e11ba066ad0e53e12ad25ad8cf07baCameron Zwarich DominatorTree *DT; 7304149f7ffd033773adfe85e4acf3f560e29bd47dEvan Cheng ProfileInfo *PFI; 747579609bfe0d915b6c2d8dc094a132d793ec8855Chris Lattner 757579609bfe0d915b6c2d8dc094a132d793ec8855Chris Lattner /// CurInstIterator - As we scan instructions optimizing them, this is the 767579609bfe0d915b6c2d8dc094a132d793ec8855Chris Lattner /// next instruction to optimize. Xforms that can invalidate this should 777579609bfe0d915b6c2d8dc094a132d793ec8855Chris Lattner /// update it. 787579609bfe0d915b6c2d8dc094a132d793ec8855Chris Lattner BasicBlock::iterator CurInstIterator; 79ab63152871f4144050d0a58d592a95e089fe40d4Evan Cheng 80485fafc8406db8552ba5e3ff871a6ee32694ad90Evan Cheng /// Keeps track of non-local addresses that have been sunk into a block. 81485fafc8406db8552ba5e3ff871a6ee32694ad90Evan Cheng /// This allows us to avoid inserting duplicate code for blocks with 82485fafc8406db8552ba5e3ff871a6ee32694ad90Evan Cheng /// multiple load/stores of the same address. 838c3527e7a475dd3369a485a4f610d56f7005b7b5Cameron Zwarich DenseMap<Value*, Value*> SunkAddrs; 848c3527e7a475dd3369a485a4f610d56f7005b7b5Cameron Zwarich 8552e37df8c05eb73e40421f0703c0d89fe854ffeaDevang Patel /// ModifiedDT - If CFG is modified in anyway, dominator tree may need to 86485fafc8406db8552ba5e3ff871a6ee32694ad90Evan Cheng /// be updated. 8752e37df8c05eb73e40421f0703c0d89fe854ffeaDevang Patel bool ModifiedDT; 88485fafc8406db8552ba5e3ff871a6ee32694ad90Evan Cheng 89dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner public: 90ecd94c804a563f2a86572dcf1d2e81f397e19daaNick Lewycky static char ID; // Pass identification, replacement for typeid 91c2bbfc18e9adbbdcf5b3375d8d25e2452f7df7f1Dan Gohman explicit CodeGenPrepare(const TargetLowering *tli = 0) 92081c34b725980f995be9080eaec24cd3dfaaf065Owen Anderson : FunctionPass(ID), TLI(tli) { 93081c34b725980f995be9080eaec24cd3dfaaf065Owen Anderson initializeCodeGenPreparePass(*PassRegistry::getPassRegistry()); 94081c34b725980f995be9080eaec24cd3dfaaf065Owen Anderson } 95dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner bool runOnFunction(Function &F); 96692bf6b85e0eaed549cd47d67289ab7b28e32651Eric Christopher 97ad80981a106c9d0ec83351e63ee3ac75ed646bf4Andreas Neustifter virtual void getAnalysisUsage(AnalysisUsage &AU) const { 9880f6a507d4e11ba066ad0e53e12ad25ad8cf07baCameron Zwarich AU.addPreserved<DominatorTree>(); 99ad80981a106c9d0ec83351e63ee3ac75ed646bf4Andreas Neustifter AU.addPreserved<ProfileInfo>(); 100ad80981a106c9d0ec83351e63ee3ac75ed646bf4Andreas Neustifter } 101ad80981a106c9d0ec83351e63ee3ac75ed646bf4Andreas Neustifter 102dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner private: 103d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner bool EliminateMostlyEmptyBlocks(Function &F); 104d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner bool CanMergeBlocks(const BasicBlock *BB, const BasicBlock *DestBB) const; 105d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner void EliminateMostlyEmptyBlock(BasicBlock *BB); 106dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner bool OptimizeBlock(BasicBlock &BB); 107c061101e03ef6d2ca550f8fe71594a5e1c02e348Cameron Zwarich bool OptimizeInst(Instruction *I); 108db125cfaf57cc83e7dd7453de2d509bc8efd0e5eChris Lattner bool OptimizeMemoryInst(Instruction *I, Value *Addr, Type *AccessTy); 1097579609bfe0d915b6c2d8dc094a132d793ec8855Chris Lattner bool OptimizeInlineAsmInst(CallInst *CS); 110040056fd11693ffc41ce9b777281c71705d0dc1fEric Christopher bool OptimizeCallInst(CallInst *CI); 111b00f236b03ea57520f94823780896ebdbc5d8bdcDan Gohman bool MoveExtToFormExtLoad(Instruction *I); 112bdcb726fcad1e3fddc70847a2b91d4d4f9396938Evan Cheng bool OptimizeExtUses(Instruction *I); 113485fafc8406db8552ba5e3ff871a6ee32694ad90Evan Cheng bool DupRetToEnableTailCallOpts(ReturnInst *RI); 114f56ea610ed63db0b8a8a9aca95222aa78ce293eeDevang Patel bool PlaceDbgValues(Function &F); 115dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner }; 116dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner} 117794fd75c67a2cdc128d67342c6d88a504d186896Devang Patel 1181997473cf72957d0e70322e2fe6fe2ab141c58a6Devang Patelchar CodeGenPrepare::ID = 0; 119d13db2c59cc94162d6cf0a04187d408bfef6d4a7Owen AndersonINITIALIZE_PASS(CodeGenPrepare, "codegenprepare", 120ce665bd2e2b581ab0858d1afe359192bac96b868Owen Anderson "Optimize for code generation", false, false) 121dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner 122dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris LattnerFunctionPass *llvm::createCodeGenPreparePass(const TargetLowering *TLI) { 123dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner return new CodeGenPrepare(TLI); 124dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner} 125dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner 126dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattnerbool CodeGenPrepare::runOnFunction(Function &F) { 127dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner bool EverMadeChange = false; 128692bf6b85e0eaed549cd47d67289ab7b28e32651Eric Christopher 12952e37df8c05eb73e40421f0703c0d89fe854ffeaDevang Patel ModifiedDT = false; 13080f6a507d4e11ba066ad0e53e12ad25ad8cf07baCameron Zwarich DT = getAnalysisIfAvailable<DominatorTree>(); 13104149f7ffd033773adfe85e4acf3f560e29bd47dEvan Cheng PFI = getAnalysisIfAvailable<ProfileInfo>(); 132485fafc8406db8552ba5e3ff871a6ee32694ad90Evan Cheng 133d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner // First pass, eliminate blocks that contain only PHI nodes and an 134d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner // unconditional branch. 135d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner EverMadeChange |= EliminateMostlyEmptyBlocks(F); 136692bf6b85e0eaed549cd47d67289ab7b28e32651Eric Christopher 137f56ea610ed63db0b8a8a9aca95222aa78ce293eeDevang Patel // llvm.dbg.value is far away from the value then iSel may not be able 138f56ea610ed63db0b8a8a9aca95222aa78ce293eeDevang Patel // handle it properly. iSel will drop llvm.dbg.value if it can not 139f56ea610ed63db0b8a8a9aca95222aa78ce293eeDevang Patel // find a node corresponding to the value. 140f56ea610ed63db0b8a8a9aca95222aa78ce293eeDevang Patel EverMadeChange |= PlaceDbgValues(F); 141f56ea610ed63db0b8a8a9aca95222aa78ce293eeDevang Patel 142d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner bool MadeChange = true; 143dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner while (MadeChange) { 144dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner MadeChange = false; 145485fafc8406db8552ba5e3ff871a6ee32694ad90Evan Cheng for (Function::iterator I = F.begin(), E = F.end(); I != E; ) { 146485fafc8406db8552ba5e3ff871a6ee32694ad90Evan Cheng BasicBlock *BB = I++; 147dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner MadeChange |= OptimizeBlock(*BB); 148485fafc8406db8552ba5e3ff871a6ee32694ad90Evan Cheng } 149dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner EverMadeChange |= MadeChange; 150dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner } 1518c3527e7a475dd3369a485a4f610d56f7005b7b5Cameron Zwarich 1528c3527e7a475dd3369a485a4f610d56f7005b7b5Cameron Zwarich SunkAddrs.clear(); 1538c3527e7a475dd3369a485a4f610d56f7005b7b5Cameron Zwarich 154899eaa35696bb0a9a625acd70a14876834af6cc5Cameron Zwarich if (!DisableBranchOpts) { 155899eaa35696bb0a9a625acd70a14876834af6cc5Cameron Zwarich MadeChange = false; 156899eaa35696bb0a9a625acd70a14876834af6cc5Cameron Zwarich for (Function::iterator BB = F.begin(), E = F.end(); BB != E; ++BB) 1575649ba70fb39f2fda4791d255ae8bb373071874fFrits van Bommel MadeChange |= ConstantFoldTerminator(BB, true); 158899eaa35696bb0a9a625acd70a14876834af6cc5Cameron Zwarich 159485fafc8406db8552ba5e3ff871a6ee32694ad90Evan Cheng if (MadeChange) 16052e37df8c05eb73e40421f0703c0d89fe854ffeaDevang Patel ModifiedDT = true; 161899eaa35696bb0a9a625acd70a14876834af6cc5Cameron Zwarich EverMadeChange |= MadeChange; 162899eaa35696bb0a9a625acd70a14876834af6cc5Cameron Zwarich } 163899eaa35696bb0a9a625acd70a14876834af6cc5Cameron Zwarich 16452e37df8c05eb73e40421f0703c0d89fe854ffeaDevang Patel if (ModifiedDT && DT) 165485fafc8406db8552ba5e3ff871a6ee32694ad90Evan Cheng DT->DT->recalculate(F); 166485fafc8406db8552ba5e3ff871a6ee32694ad90Evan Cheng 167dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner return EverMadeChange; 168dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner} 169dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner 1702d69724938e67ec248e0ba42f86287923b3a5171Dale Johannesen/// EliminateMostlyEmptyBlocks - eliminate blocks that contain only PHI nodes, 1712d69724938e67ec248e0ba42f86287923b3a5171Dale Johannesen/// debug info directives, and an unconditional branch. Passes before isel 1722d69724938e67ec248e0ba42f86287923b3a5171Dale Johannesen/// (e.g. LSR/loopsimplify) often split edges in ways that are non-optimal for 1732d69724938e67ec248e0ba42f86287923b3a5171Dale Johannesen/// isel. Start by eliminating these blocks so we can split them the way we 1742d69724938e67ec248e0ba42f86287923b3a5171Dale Johannesen/// want them. 175d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattnerbool CodeGenPrepare::EliminateMostlyEmptyBlocks(Function &F) { 176d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner bool MadeChange = false; 177d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner // Note that this intentionally skips the entry block. 178d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner for (Function::iterator I = ++F.begin(), E = F.end(); I != E; ) { 179d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner BasicBlock *BB = I++; 180d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner 181d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner // If this block doesn't end with an uncond branch, ignore it. 182d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner BranchInst *BI = dyn_cast<BranchInst>(BB->getTerminator()); 183d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner if (!BI || !BI->isUnconditional()) 184d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner continue; 185692bf6b85e0eaed549cd47d67289ab7b28e32651Eric Christopher 1862d69724938e67ec248e0ba42f86287923b3a5171Dale Johannesen // If the instruction before the branch (skipping debug info) isn't a phi 1872d69724938e67ec248e0ba42f86287923b3a5171Dale Johannesen // node, then other stuff is happening here. 188d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner BasicBlock::iterator BBI = BI; 189d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner if (BBI != BB->begin()) { 190d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner --BBI; 1912d69724938e67ec248e0ba42f86287923b3a5171Dale Johannesen while (isa<DbgInfoIntrinsic>(BBI)) { 1922d69724938e67ec248e0ba42f86287923b3a5171Dale Johannesen if (BBI == BB->begin()) 1932d69724938e67ec248e0ba42f86287923b3a5171Dale Johannesen break; 1942d69724938e67ec248e0ba42f86287923b3a5171Dale Johannesen --BBI; 1952d69724938e67ec248e0ba42f86287923b3a5171Dale Johannesen } 1962d69724938e67ec248e0ba42f86287923b3a5171Dale Johannesen if (!isa<DbgInfoIntrinsic>(BBI) && !isa<PHINode>(BBI)) 1972d69724938e67ec248e0ba42f86287923b3a5171Dale Johannesen continue; 198d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner } 199692bf6b85e0eaed549cd47d67289ab7b28e32651Eric Christopher 200d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner // Do not break infinite loops. 201d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner BasicBlock *DestBB = BI->getSuccessor(0); 202d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner if (DestBB == BB) 203d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner continue; 204692bf6b85e0eaed549cd47d67289ab7b28e32651Eric Christopher 205d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner if (!CanMergeBlocks(BB, DestBB)) 206d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner continue; 207692bf6b85e0eaed549cd47d67289ab7b28e32651Eric Christopher 208d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner EliminateMostlyEmptyBlock(BB); 209d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner MadeChange = true; 210d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner } 211d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner return MadeChange; 212d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner} 213d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner 214d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner/// CanMergeBlocks - Return true if we can merge BB into DestBB if there is a 215d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner/// single uncond branch between them, and BB contains no other non-phi 216d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner/// instructions. 217d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattnerbool CodeGenPrepare::CanMergeBlocks(const BasicBlock *BB, 218d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner const BasicBlock *DestBB) const { 219d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner // We only want to eliminate blocks whose phi nodes are used by phi nodes in 220d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner // the successor. If there are more complex condition (e.g. preheaders), 221d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner // don't mess around with them. 222d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner BasicBlock::const_iterator BBI = BB->begin(); 223d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner while (const PHINode *PN = dyn_cast<PHINode>(BBI++)) { 22460ad781c61815ca5b8dc2a45a102e1c8af65992fGabor Greif for (Value::const_use_iterator UI = PN->use_begin(), E = PN->use_end(); 225d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner UI != E; ++UI) { 226d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner const Instruction *User = cast<Instruction>(*UI); 227d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner if (User->getParent() != DestBB || !isa<PHINode>(User)) 228d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner return false; 229692bf6b85e0eaed549cd47d67289ab7b28e32651Eric Christopher // If User is inside DestBB block and it is a PHINode then check 230692bf6b85e0eaed549cd47d67289ab7b28e32651Eric Christopher // incoming value. If incoming value is not from BB then this is 23175abc1ed0618048c3cf6c5b71c9868c10d6c1478Devang Patel // a complex condition (e.g. preheaders) we want to avoid here. 23275abc1ed0618048c3cf6c5b71c9868c10d6c1478Devang Patel if (User->getParent() == DestBB) { 23375abc1ed0618048c3cf6c5b71c9868c10d6c1478Devang Patel if (const PHINode *UPN = dyn_cast<PHINode>(User)) 23475abc1ed0618048c3cf6c5b71c9868c10d6c1478Devang Patel for (unsigned I = 0, E = UPN->getNumIncomingValues(); I != E; ++I) { 23575abc1ed0618048c3cf6c5b71c9868c10d6c1478Devang Patel Instruction *Insn = dyn_cast<Instruction>(UPN->getIncomingValue(I)); 23675abc1ed0618048c3cf6c5b71c9868c10d6c1478Devang Patel if (Insn && Insn->getParent() == BB && 23775abc1ed0618048c3cf6c5b71c9868c10d6c1478Devang Patel Insn->getParent() != UPN->getIncomingBlock(I)) 23875abc1ed0618048c3cf6c5b71c9868c10d6c1478Devang Patel return false; 23975abc1ed0618048c3cf6c5b71c9868c10d6c1478Devang Patel } 24075abc1ed0618048c3cf6c5b71c9868c10d6c1478Devang Patel } 241d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner } 242d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner } 243692bf6b85e0eaed549cd47d67289ab7b28e32651Eric Christopher 244d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner // If BB and DestBB contain any common predecessors, then the phi nodes in BB 245d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner // and DestBB may have conflicting incoming values for the block. If so, we 246d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner // can't merge the block. 247d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner const PHINode *DestBBPN = dyn_cast<PHINode>(DestBB->begin()); 248d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner if (!DestBBPN) return true; // no conflict. 249692bf6b85e0eaed549cd47d67289ab7b28e32651Eric Christopher 250d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner // Collect the preds of BB. 251f67f73a519eac94b6c1f98dbce7d251a3a4aea07Chris Lattner SmallPtrSet<const BasicBlock*, 16> BBPreds; 252d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner if (const PHINode *BBPN = dyn_cast<PHINode>(BB->begin())) { 253d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner // It is faster to get preds from a PHI than with pred_iterator. 254d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner for (unsigned i = 0, e = BBPN->getNumIncomingValues(); i != e; ++i) 255d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner BBPreds.insert(BBPN->getIncomingBlock(i)); 256d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner } else { 257d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner BBPreds.insert(pred_begin(BB), pred_end(BB)); 258d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner } 259692bf6b85e0eaed549cd47d67289ab7b28e32651Eric Christopher 260d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner // Walk the preds of DestBB. 261d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner for (unsigned i = 0, e = DestBBPN->getNumIncomingValues(); i != e; ++i) { 262d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner BasicBlock *Pred = DestBBPN->getIncomingBlock(i); 263d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner if (BBPreds.count(Pred)) { // Common predecessor? 264d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner BBI = DestBB->begin(); 265d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner while (const PHINode *PN = dyn_cast<PHINode>(BBI++)) { 266d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner const Value *V1 = PN->getIncomingValueForBlock(Pred); 267d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner const Value *V2 = PN->getIncomingValueForBlock(BB); 268692bf6b85e0eaed549cd47d67289ab7b28e32651Eric Christopher 269d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner // If V2 is a phi node in BB, look up what the mapped value will be. 270d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner if (const PHINode *V2PN = dyn_cast<PHINode>(V2)) 271d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner if (V2PN->getParent() == BB) 272d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner V2 = V2PN->getIncomingValueForBlock(Pred); 273692bf6b85e0eaed549cd47d67289ab7b28e32651Eric Christopher 274d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner // If there is a conflict, bail out. 275d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner if (V1 != V2) return false; 276d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner } 277d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner } 278d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner } 279d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner 280d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner return true; 281d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner} 282d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner 283d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner 284d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner/// EliminateMostlyEmptyBlock - Eliminate a basic block that have only phi's and 285d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner/// an unconditional branch in it. 286d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattnervoid CodeGenPrepare::EliminateMostlyEmptyBlock(BasicBlock *BB) { 287d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner BranchInst *BI = cast<BranchInst>(BB->getTerminator()); 288d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner BasicBlock *DestBB = BI->getSuccessor(0); 289692bf6b85e0eaed549cd47d67289ab7b28e32651Eric Christopher 29068d67fdf203ff2d5b0eeb925befd0866bce3aceeDavid Greene DEBUG(dbgs() << "MERGING MOSTLY EMPTY BLOCKS - BEFORE:\n" << *BB << *DestBB); 291692bf6b85e0eaed549cd47d67289ab7b28e32651Eric Christopher 292d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner // If the destination block has a single pred, then this is a trivial edge, 293d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner // just collapse it. 2949918fb5631974f2201a640384b7ebe672c749e43Chris Lattner if (BasicBlock *SinglePred = DestBB->getSinglePredecessor()) { 295f5102a0f088e7c96f7028bf7ca1c24975c314fffChris Lattner if (SinglePred != DestBB) { 296f5102a0f088e7c96f7028bf7ca1c24975c314fffChris Lattner // Remember if SinglePred was the entry block of the function. If so, we 297f5102a0f088e7c96f7028bf7ca1c24975c314fffChris Lattner // will need to move BB back to the entry position. 298f5102a0f088e7c96f7028bf7ca1c24975c314fffChris Lattner bool isEntry = SinglePred == &SinglePred->getParent()->getEntryBlock(); 299ad80981a106c9d0ec83351e63ee3ac75ed646bf4Andreas Neustifter MergeBasicBlockIntoOnlyPred(DestBB, this); 300f5102a0f088e7c96f7028bf7ca1c24975c314fffChris Lattner 301f5102a0f088e7c96f7028bf7ca1c24975c314fffChris Lattner if (isEntry && BB != &BB->getParent()->getEntryBlock()) 302f5102a0f088e7c96f7028bf7ca1c24975c314fffChris Lattner BB->moveBefore(&BB->getParent()->getEntryBlock()); 303f5102a0f088e7c96f7028bf7ca1c24975c314fffChris Lattner 30468d67fdf203ff2d5b0eeb925befd0866bce3aceeDavid Greene DEBUG(dbgs() << "AFTER:\n" << *DestBB << "\n\n\n"); 305f5102a0f088e7c96f7028bf7ca1c24975c314fffChris Lattner return; 306f5102a0f088e7c96f7028bf7ca1c24975c314fffChris Lattner } 307d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner } 308692bf6b85e0eaed549cd47d67289ab7b28e32651Eric Christopher 309d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner // Otherwise, we have multiple predecessors of BB. Update the PHIs in DestBB 310d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner // to handle the new incoming edges it is about to have. 311d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner PHINode *PN; 312d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner for (BasicBlock::iterator BBI = DestBB->begin(); 313d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner (PN = dyn_cast<PHINode>(BBI)); ++BBI) { 314d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner // Remove the incoming value for BB, and remember it. 315d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner Value *InVal = PN->removeIncomingValue(BB, false); 316692bf6b85e0eaed549cd47d67289ab7b28e32651Eric Christopher 317d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner // Two options: either the InVal is a phi node defined in BB or it is some 318d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner // value that dominates BB. 319d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner PHINode *InValPhi = dyn_cast<PHINode>(InVal); 320d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner if (InValPhi && InValPhi->getParent() == BB) { 321d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner // Add all of the input values of the input PHI as inputs of this phi. 322d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner for (unsigned i = 0, e = InValPhi->getNumIncomingValues(); i != e; ++i) 323d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner PN->addIncoming(InValPhi->getIncomingValue(i), 324d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner InValPhi->getIncomingBlock(i)); 325d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner } else { 326d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner // Otherwise, add one instance of the dominating value for each edge that 327d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner // we will be adding. 328d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner if (PHINode *BBPN = dyn_cast<PHINode>(BB->begin())) { 329d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner for (unsigned i = 0, e = BBPN->getNumIncomingValues(); i != e; ++i) 330d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner PN->addIncoming(InVal, BBPN->getIncomingBlock(i)); 331d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner } else { 332d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner for (pred_iterator PI = pred_begin(BB), E = pred_end(BB); PI != E; ++PI) 333d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner PN->addIncoming(InVal, *PI); 334d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner } 335d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner } 336d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner } 337692bf6b85e0eaed549cd47d67289ab7b28e32651Eric Christopher 338d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner // The PHIs are now updated, change everything that refers to BB to use 339d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner // DestBB and remove BB. 340d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner BB->replaceAllUsesWith(DestBB); 34152e37df8c05eb73e40421f0703c0d89fe854ffeaDevang Patel if (DT && !ModifiedDT) { 34280f6a507d4e11ba066ad0e53e12ad25ad8cf07baCameron Zwarich BasicBlock *BBIDom = DT->getNode(BB)->getIDom()->getBlock(); 34380f6a507d4e11ba066ad0e53e12ad25ad8cf07baCameron Zwarich BasicBlock *DestBBIDom = DT->getNode(DestBB)->getIDom()->getBlock(); 34480f6a507d4e11ba066ad0e53e12ad25ad8cf07baCameron Zwarich BasicBlock *NewIDom = DT->findNearestCommonDominator(BBIDom, DestBBIDom); 34580f6a507d4e11ba066ad0e53e12ad25ad8cf07baCameron Zwarich DT->changeImmediateDominator(DestBB, NewIDom); 34680f6a507d4e11ba066ad0e53e12ad25ad8cf07baCameron Zwarich DT->eraseNode(BB); 34780f6a507d4e11ba066ad0e53e12ad25ad8cf07baCameron Zwarich } 34804149f7ffd033773adfe85e4acf3f560e29bd47dEvan Cheng if (PFI) { 34904149f7ffd033773adfe85e4acf3f560e29bd47dEvan Cheng PFI->replaceAllUses(BB, DestBB); 35004149f7ffd033773adfe85e4acf3f560e29bd47dEvan Cheng PFI->removeEdge(ProfileInfo::getEdge(BB, DestBB)); 351ad80981a106c9d0ec83351e63ee3ac75ed646bf4Andreas Neustifter } 352d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner BB->eraseFromParent(); 35331ff1333e0651192212cee6e090df2ff57d19b53Cameron Zwarich ++NumBlocksElim; 354692bf6b85e0eaed549cd47d67289ab7b28e32651Eric Christopher 35568d67fdf203ff2d5b0eeb925befd0866bce3aceeDavid Greene DEBUG(dbgs() << "AFTER:\n" << *DestBB << "\n\n\n"); 356d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner} 357d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner 358dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner/// OptimizeNoopCopyExpression - If the specified cast instruction is a noop 359a119de86a064414622562cfe32953de7f9b0ee40Dan Gohman/// copy (e.g. it's casting from one pointer type to another, i32->i8 on PPC), 360a119de86a064414622562cfe32953de7f9b0ee40Dan Gohman/// sink it into user blocks to reduce the number of virtual 361ce0b23721e434789f9600c0fd13f0ca17444264fDale Johannesen/// registers that must be created and coalesced. 362dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner/// 363dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner/// Return true if any changes are made. 36485fa13c02d383bb87dd9b8b9081a4d34a3e9c52cChris Lattner/// 365dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattnerstatic bool OptimizeNoopCopyExpression(CastInst *CI, const TargetLowering &TLI){ 366692bf6b85e0eaed549cd47d67289ab7b28e32651Eric Christopher // If this is a noop copy, 367e50ed30282bb5b4a9ed952580523f2dda16215acOwen Anderson EVT SrcVT = TLI.getValueType(CI->getOperand(0)->getType()); 368e50ed30282bb5b4a9ed952580523f2dda16215acOwen Anderson EVT DstVT = TLI.getValueType(CI->getType()); 369692bf6b85e0eaed549cd47d67289ab7b28e32651Eric Christopher 370dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner // This is an fp<->int conversion? 37183ec4b6711980242ef3c55a4fa36b2d7a39c1bfbDuncan Sands if (SrcVT.isInteger() != DstVT.isInteger()) 372dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner return false; 3738e4eb09b1e3571965f49edcdfb56b1375b1b7551Duncan Sands 374dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner // If this is an extension, it will be a zero or sign extension, which 375dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner // isn't a noop. 3768e4eb09b1e3571965f49edcdfb56b1375b1b7551Duncan Sands if (SrcVT.bitsLT(DstVT)) return false; 377692bf6b85e0eaed549cd47d67289ab7b28e32651Eric Christopher 378dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner // If these values will be promoted, find out what they will be promoted 379dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner // to. This helps us consider truncates on PPC as noop copies when they 380dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner // are. 3810ccc12ae8bab69d4ec8e265fff1865db9553137fNadav Rotem if (TLI.getTypeAction(CI->getContext(), SrcVT) == 3820ccc12ae8bab69d4ec8e265fff1865db9553137fNadav Rotem TargetLowering::TypePromoteInteger) 38323b9b19b1a5a00faa9fce0788155c7dbfd00bfb1Owen Anderson SrcVT = TLI.getTypeToTransformTo(CI->getContext(), SrcVT); 3840ccc12ae8bab69d4ec8e265fff1865db9553137fNadav Rotem if (TLI.getTypeAction(CI->getContext(), DstVT) == 3850ccc12ae8bab69d4ec8e265fff1865db9553137fNadav Rotem TargetLowering::TypePromoteInteger) 38623b9b19b1a5a00faa9fce0788155c7dbfd00bfb1Owen Anderson DstVT = TLI.getTypeToTransformTo(CI->getContext(), DstVT); 387692bf6b85e0eaed549cd47d67289ab7b28e32651Eric Christopher 388dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner // If, after promotion, these are the same types, this is a noop copy. 389dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner if (SrcVT != DstVT) 390dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner return false; 391692bf6b85e0eaed549cd47d67289ab7b28e32651Eric Christopher 392dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner BasicBlock *DefBB = CI->getParent(); 393692bf6b85e0eaed549cd47d67289ab7b28e32651Eric Christopher 394dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner /// InsertedCasts - Only insert a cast in each block once. 395ce0b23721e434789f9600c0fd13f0ca17444264fDale Johannesen DenseMap<BasicBlock*, CastInst*> InsertedCasts; 396692bf6b85e0eaed549cd47d67289ab7b28e32651Eric Christopher 397dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner bool MadeChange = false; 398692bf6b85e0eaed549cd47d67289ab7b28e32651Eric Christopher for (Value::use_iterator UI = CI->use_begin(), E = CI->use_end(); 399dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner UI != E; ) { 400dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner Use &TheUse = UI.getUse(); 401dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner Instruction *User = cast<Instruction>(*UI); 402692bf6b85e0eaed549cd47d67289ab7b28e32651Eric Christopher 403dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner // Figure out which BB this cast is used in. For PHI's this is the 404dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner // appropriate predecessor block. 405dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner BasicBlock *UserBB = User->getParent(); 406dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner if (PHINode *PN = dyn_cast<PHINode>(User)) { 407a36791da41cf4f635e50077b290676b873836bdaGabor Greif UserBB = PN->getIncomingBlock(UI); 408dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner } 409692bf6b85e0eaed549cd47d67289ab7b28e32651Eric Christopher 410dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner // Preincrement use iterator so we don't invalidate it. 411dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner ++UI; 412692bf6b85e0eaed549cd47d67289ab7b28e32651Eric Christopher 413dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner // If this user is in the same block as the cast, don't change the cast. 414dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner if (UserBB == DefBB) continue; 415692bf6b85e0eaed549cd47d67289ab7b28e32651Eric Christopher 416dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner // If we have already inserted a cast into this block, use it. 417dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner CastInst *&InsertedCast = InsertedCasts[UserBB]; 418dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner 419dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner if (!InsertedCast) { 4205b6f42f57e730c2d968c313a27fa505a3c3e5efaBill Wendling BasicBlock::iterator InsertPt = UserBB->getFirstInsertionPt(); 421692bf6b85e0eaed549cd47d67289ab7b28e32651Eric Christopher InsertedCast = 422692bf6b85e0eaed549cd47d67289ab7b28e32651Eric Christopher CastInst::Create(CI->getOpcode(), CI->getOperand(0), CI->getType(), "", 423dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner InsertPt); 424dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner MadeChange = true; 425dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner } 426692bf6b85e0eaed549cd47d67289ab7b28e32651Eric Christopher 427ce0b23721e434789f9600c0fd13f0ca17444264fDale Johannesen // Replace a use of the cast with a use of the new cast. 428dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner TheUse = InsertedCast; 42931ff1333e0651192212cee6e090df2ff57d19b53Cameron Zwarich ++NumCastUses; 430dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner } 431692bf6b85e0eaed549cd47d67289ab7b28e32651Eric Christopher 432dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner // If we removed all uses, nuke the cast. 433e003813e9613f41ff2c6a10cb1d3ae3a5b8eab1fDuncan Sands if (CI->use_empty()) { 434dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner CI->eraseFromParent(); 435e003813e9613f41ff2c6a10cb1d3ae3a5b8eab1fDuncan Sands MadeChange = true; 436e003813e9613f41ff2c6a10cb1d3ae3a5b8eab1fDuncan Sands } 437692bf6b85e0eaed549cd47d67289ab7b28e32651Eric Christopher 438dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner return MadeChange; 439dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner} 440dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner 441692bf6b85e0eaed549cd47d67289ab7b28e32651Eric Christopher/// OptimizeCmpExpression - sink the given CmpInst into user blocks to reduce 442ce0b23721e434789f9600c0fd13f0ca17444264fDale Johannesen/// the number of virtual registers that must be created and coalesced. This is 443684b22df79c51114a12289e10a4063d5f02259a9Chris Lattner/// a clear win except on targets with multiple condition code registers 444684b22df79c51114a12289e10a4063d5f02259a9Chris Lattner/// (PowerPC), where it might lose; some adjustment may be wanted there. 445ce0b23721e434789f9600c0fd13f0ca17444264fDale Johannesen/// 446ce0b23721e434789f9600c0fd13f0ca17444264fDale Johannesen/// Return true if any changes are made. 44785fa13c02d383bb87dd9b8b9081a4d34a3e9c52cChris Lattnerstatic bool OptimizeCmpExpression(CmpInst *CI) { 448ce0b23721e434789f9600c0fd13f0ca17444264fDale Johannesen BasicBlock *DefBB = CI->getParent(); 449692bf6b85e0eaed549cd47d67289ab7b28e32651Eric Christopher 450ce0b23721e434789f9600c0fd13f0ca17444264fDale Johannesen /// InsertedCmp - Only insert a cmp in each block once. 451ce0b23721e434789f9600c0fd13f0ca17444264fDale Johannesen DenseMap<BasicBlock*, CmpInst*> InsertedCmps; 452692bf6b85e0eaed549cd47d67289ab7b28e32651Eric Christopher 453ce0b23721e434789f9600c0fd13f0ca17444264fDale Johannesen bool MadeChange = false; 454692bf6b85e0eaed549cd47d67289ab7b28e32651Eric Christopher for (Value::use_iterator UI = CI->use_begin(), E = CI->use_end(); 455ce0b23721e434789f9600c0fd13f0ca17444264fDale Johannesen UI != E; ) { 456ce0b23721e434789f9600c0fd13f0ca17444264fDale Johannesen Use &TheUse = UI.getUse(); 457ce0b23721e434789f9600c0fd13f0ca17444264fDale Johannesen Instruction *User = cast<Instruction>(*UI); 458692bf6b85e0eaed549cd47d67289ab7b28e32651Eric Christopher 459ce0b23721e434789f9600c0fd13f0ca17444264fDale Johannesen // Preincrement use iterator so we don't invalidate it. 460ce0b23721e434789f9600c0fd13f0ca17444264fDale Johannesen ++UI; 461692bf6b85e0eaed549cd47d67289ab7b28e32651Eric Christopher 462ce0b23721e434789f9600c0fd13f0ca17444264fDale Johannesen // Don't bother for PHI nodes. 463ce0b23721e434789f9600c0fd13f0ca17444264fDale Johannesen if (isa<PHINode>(User)) 464ce0b23721e434789f9600c0fd13f0ca17444264fDale Johannesen continue; 465ce0b23721e434789f9600c0fd13f0ca17444264fDale Johannesen 466ce0b23721e434789f9600c0fd13f0ca17444264fDale Johannesen // Figure out which BB this cmp is used in. 467ce0b23721e434789f9600c0fd13f0ca17444264fDale Johannesen BasicBlock *UserBB = User->getParent(); 468692bf6b85e0eaed549cd47d67289ab7b28e32651Eric Christopher 469ce0b23721e434789f9600c0fd13f0ca17444264fDale Johannesen // If this user is in the same block as the cmp, don't change the cmp. 470ce0b23721e434789f9600c0fd13f0ca17444264fDale Johannesen if (UserBB == DefBB) continue; 471692bf6b85e0eaed549cd47d67289ab7b28e32651Eric Christopher 472ce0b23721e434789f9600c0fd13f0ca17444264fDale Johannesen // If we have already inserted a cmp into this block, use it. 473ce0b23721e434789f9600c0fd13f0ca17444264fDale Johannesen CmpInst *&InsertedCmp = InsertedCmps[UserBB]; 474ce0b23721e434789f9600c0fd13f0ca17444264fDale Johannesen 475ce0b23721e434789f9600c0fd13f0ca17444264fDale Johannesen if (!InsertedCmp) { 4765b6f42f57e730c2d968c313a27fa505a3c3e5efaBill Wendling BasicBlock::iterator InsertPt = UserBB->getFirstInsertionPt(); 477692bf6b85e0eaed549cd47d67289ab7b28e32651Eric Christopher InsertedCmp = 4781c8a23c440b1665ba422778cdc74a0c59ecaf39eDan Gohman CmpInst::Create(CI->getOpcode(), 479333c40096561218bc3597cf153c0a3895274414cOwen Anderson CI->getPredicate(), CI->getOperand(0), 480ce0b23721e434789f9600c0fd13f0ca17444264fDale Johannesen CI->getOperand(1), "", InsertPt); 481ce0b23721e434789f9600c0fd13f0ca17444264fDale Johannesen MadeChange = true; 482ce0b23721e434789f9600c0fd13f0ca17444264fDale Johannesen } 483692bf6b85e0eaed549cd47d67289ab7b28e32651Eric Christopher 484ce0b23721e434789f9600c0fd13f0ca17444264fDale Johannesen // Replace a use of the cmp with a use of the new cmp. 485ce0b23721e434789f9600c0fd13f0ca17444264fDale Johannesen TheUse = InsertedCmp; 48631ff1333e0651192212cee6e090df2ff57d19b53Cameron Zwarich ++NumCmpUses; 487ce0b23721e434789f9600c0fd13f0ca17444264fDale Johannesen } 488692bf6b85e0eaed549cd47d67289ab7b28e32651Eric Christopher 489ce0b23721e434789f9600c0fd13f0ca17444264fDale Johannesen // If we removed all uses, nuke the cmp. 490ce0b23721e434789f9600c0fd13f0ca17444264fDale Johannesen if (CI->use_empty()) 491ce0b23721e434789f9600c0fd13f0ca17444264fDale Johannesen CI->eraseFromParent(); 492692bf6b85e0eaed549cd47d67289ab7b28e32651Eric Christopher 493ce0b23721e434789f9600c0fd13f0ca17444264fDale Johannesen return MadeChange; 494ce0b23721e434789f9600c0fd13f0ca17444264fDale Johannesen} 495ce0b23721e434789f9600c0fd13f0ca17444264fDale Johannesen 4960b6cb507385c8bd10b6a51b5e45a9b99d8d94798Benjamin Kramernamespace { 4970b6cb507385c8bd10b6a51b5e45a9b99d8d94798Benjamin Kramerclass CodeGenPrepareFortifiedLibCalls : public SimplifyFortifiedLibCalls { 4980b6cb507385c8bd10b6a51b5e45a9b99d8d94798Benjamin Kramerprotected: 4990b6cb507385c8bd10b6a51b5e45a9b99d8d94798Benjamin Kramer void replaceCall(Value *With) { 5000b6cb507385c8bd10b6a51b5e45a9b99d8d94798Benjamin Kramer CI->replaceAllUsesWith(With); 5010b6cb507385c8bd10b6a51b5e45a9b99d8d94798Benjamin Kramer CI->eraseFromParent(); 5020b6cb507385c8bd10b6a51b5e45a9b99d8d94798Benjamin Kramer } 5030b6cb507385c8bd10b6a51b5e45a9b99d8d94798Benjamin Kramer bool isFoldable(unsigned SizeCIOp, unsigned, bool) const { 504a6aac4c5bc22bb10c7adb11eee3f82c703af7002Gabor Greif if (ConstantInt *SizeCI = 505a6aac4c5bc22bb10c7adb11eee3f82c703af7002Gabor Greif dyn_cast<ConstantInt>(CI->getArgOperand(SizeCIOp))) 506a6aac4c5bc22bb10c7adb11eee3f82c703af7002Gabor Greif return SizeCI->isAllOnesValue(); 5070b6cb507385c8bd10b6a51b5e45a9b99d8d94798Benjamin Kramer return false; 5080b6cb507385c8bd10b6a51b5e45a9b99d8d94798Benjamin Kramer } 5090b6cb507385c8bd10b6a51b5e45a9b99d8d94798Benjamin Kramer}; 5100b6cb507385c8bd10b6a51b5e45a9b99d8d94798Benjamin Kramer} // end anonymous namespace 5110b6cb507385c8bd10b6a51b5e45a9b99d8d94798Benjamin Kramer 512040056fd11693ffc41ce9b777281c71705d0dc1fEric Christopherbool CodeGenPrepare::OptimizeCallInst(CallInst *CI) { 5137579609bfe0d915b6c2d8dc094a132d793ec8855Chris Lattner BasicBlock *BB = CI->getParent(); 5147579609bfe0d915b6c2d8dc094a132d793ec8855Chris Lattner 5157579609bfe0d915b6c2d8dc094a132d793ec8855Chris Lattner // Lower inline assembly if we can. 5167579609bfe0d915b6c2d8dc094a132d793ec8855Chris Lattner // If we found an inline asm expession, and if the target knows how to 5177579609bfe0d915b6c2d8dc094a132d793ec8855Chris Lattner // lower it to normal LLVM code, do so now. 5187579609bfe0d915b6c2d8dc094a132d793ec8855Chris Lattner if (TLI && isa<InlineAsm>(CI->getCalledValue())) { 5197579609bfe0d915b6c2d8dc094a132d793ec8855Chris Lattner if (TLI->ExpandInlineAsm(CI)) { 5207579609bfe0d915b6c2d8dc094a132d793ec8855Chris Lattner // Avoid invalidating the iterator. 5217579609bfe0d915b6c2d8dc094a132d793ec8855Chris Lattner CurInstIterator = BB->begin(); 5227579609bfe0d915b6c2d8dc094a132d793ec8855Chris Lattner // Avoid processing instructions out of order, which could cause 5237579609bfe0d915b6c2d8dc094a132d793ec8855Chris Lattner // reuse before a value is defined. 5247579609bfe0d915b6c2d8dc094a132d793ec8855Chris Lattner SunkAddrs.clear(); 5257579609bfe0d915b6c2d8dc094a132d793ec8855Chris Lattner return true; 5267579609bfe0d915b6c2d8dc094a132d793ec8855Chris Lattner } 5277579609bfe0d915b6c2d8dc094a132d793ec8855Chris Lattner // Sink address computing for memory operands into the block. 5287579609bfe0d915b6c2d8dc094a132d793ec8855Chris Lattner if (OptimizeInlineAsmInst(CI)) 5297579609bfe0d915b6c2d8dc094a132d793ec8855Chris Lattner return true; 5307579609bfe0d915b6c2d8dc094a132d793ec8855Chris Lattner } 5317579609bfe0d915b6c2d8dc094a132d793ec8855Chris Lattner 532040056fd11693ffc41ce9b777281c71705d0dc1fEric Christopher // Lower all uses of llvm.objectsize.* 533040056fd11693ffc41ce9b777281c71705d0dc1fEric Christopher IntrinsicInst *II = dyn_cast<IntrinsicInst>(CI); 534040056fd11693ffc41ce9b777281c71705d0dc1fEric Christopher if (II && II->getIntrinsicID() == Intrinsic::objectsize) { 535de9f5452d3ae894bb7fdd455cec5af50e2560aa5Gabor Greif bool Min = (cast<ConstantInt>(II->getArgOperand(1))->getZExtValue() == 1); 536db125cfaf57cc83e7dd7453de2d509bc8efd0e5eChris Lattner Type *ReturnTy = CI->getType(); 537040056fd11693ffc41ce9b777281c71705d0dc1fEric Christopher Constant *RetVal = ConstantInt::get(ReturnTy, Min ? 0 : -1ULL); 53894e8e0cfbe13cdbdf7addc6e36df863cab92e4c9Chris Lattner 53994e8e0cfbe13cdbdf7addc6e36df863cab92e4c9Chris Lattner // Substituting this can cause recursive simplifications, which can 54094e8e0cfbe13cdbdf7addc6e36df863cab92e4c9Chris Lattner // invalidate our iterator. Use a WeakVH to hold onto it in case this 54194e8e0cfbe13cdbdf7addc6e36df863cab92e4c9Chris Lattner // happens. 54294e8e0cfbe13cdbdf7addc6e36df863cab92e4c9Chris Lattner WeakVH IterHandle(CurInstIterator); 54394e8e0cfbe13cdbdf7addc6e36df863cab92e4c9Chris Lattner 544680c962ebddca67195463d9c5ff40d3cf888b5b4Cameron Zwarich ReplaceAndSimplifyAllUses(CI, RetVal, TLI ? TLI->getTargetData() : 0, 54552e37df8c05eb73e40421f0703c0d89fe854ffeaDevang Patel ModifiedDT ? 0 : DT); 54694e8e0cfbe13cdbdf7addc6e36df863cab92e4c9Chris Lattner 54794e8e0cfbe13cdbdf7addc6e36df863cab92e4c9Chris Lattner // If the iterator instruction was recursively deleted, start over at the 54894e8e0cfbe13cdbdf7addc6e36df863cab92e4c9Chris Lattner // start of the block. 549435b4d2eba723e9513453f20885244ad1d16e0d4Chris Lattner if (IterHandle != CurInstIterator) { 55094e8e0cfbe13cdbdf7addc6e36df863cab92e4c9Chris Lattner CurInstIterator = BB->begin(); 551435b4d2eba723e9513453f20885244ad1d16e0d4Chris Lattner SunkAddrs.clear(); 552435b4d2eba723e9513453f20885244ad1d16e0d4Chris Lattner } 553040056fd11693ffc41ce9b777281c71705d0dc1fEric Christopher return true; 554040056fd11693ffc41ce9b777281c71705d0dc1fEric Christopher } 555040056fd11693ffc41ce9b777281c71705d0dc1fEric Christopher 556040056fd11693ffc41ce9b777281c71705d0dc1fEric Christopher // From here on out we're working with named functions. 557040056fd11693ffc41ce9b777281c71705d0dc1fEric Christopher if (CI->getCalledFunction() == 0) return false; 55897de92c08d675e5ee5be2e1ebec64cbff86c17f4Devang Patel 559040056fd11693ffc41ce9b777281c71705d0dc1fEric Christopher // We'll need TargetData from here on out. 560040056fd11693ffc41ce9b777281c71705d0dc1fEric Christopher const TargetData *TD = TLI ? TLI->getTargetData() : 0; 561040056fd11693ffc41ce9b777281c71705d0dc1fEric Christopher if (!TD) return false; 562040056fd11693ffc41ce9b777281c71705d0dc1fEric Christopher 5630b6cb507385c8bd10b6a51b5e45a9b99d8d94798Benjamin Kramer // Lower all default uses of _chk calls. This is very similar 5640b6cb507385c8bd10b6a51b5e45a9b99d8d94798Benjamin Kramer // to what InstCombineCalls does, but here we are only lowering calls 565040056fd11693ffc41ce9b777281c71705d0dc1fEric Christopher // that have the default "don't know" as the objectsize. Anything else 566040056fd11693ffc41ce9b777281c71705d0dc1fEric Christopher // should be left alone. 5670b6cb507385c8bd10b6a51b5e45a9b99d8d94798Benjamin Kramer CodeGenPrepareFortifiedLibCalls Simplifier; 5680b6cb507385c8bd10b6a51b5e45a9b99d8d94798Benjamin Kramer return Simplifier.fold(CI, TD); 569040056fd11693ffc41ce9b777281c71705d0dc1fEric Christopher} 57094e8e0cfbe13cdbdf7addc6e36df863cab92e4c9Chris Lattner 571485fafc8406db8552ba5e3ff871a6ee32694ad90Evan Cheng/// DupRetToEnableTailCallOpts - Look for opportunities to duplicate return 572485fafc8406db8552ba5e3ff871a6ee32694ad90Evan Cheng/// instructions to the predecessor to enable tail call optimizations. The 573485fafc8406db8552ba5e3ff871a6ee32694ad90Evan Cheng/// case it is currently looking for is: 574485fafc8406db8552ba5e3ff871a6ee32694ad90Evan Cheng/// bb0: 575485fafc8406db8552ba5e3ff871a6ee32694ad90Evan Cheng/// %tmp0 = tail call i32 @f0() 576485fafc8406db8552ba5e3ff871a6ee32694ad90Evan Cheng/// br label %return 577485fafc8406db8552ba5e3ff871a6ee32694ad90Evan Cheng/// bb1: 578485fafc8406db8552ba5e3ff871a6ee32694ad90Evan Cheng/// %tmp1 = tail call i32 @f1() 579485fafc8406db8552ba5e3ff871a6ee32694ad90Evan Cheng/// br label %return 580485fafc8406db8552ba5e3ff871a6ee32694ad90Evan Cheng/// bb2: 581485fafc8406db8552ba5e3ff871a6ee32694ad90Evan Cheng/// %tmp2 = tail call i32 @f2() 582485fafc8406db8552ba5e3ff871a6ee32694ad90Evan Cheng/// br label %return 583485fafc8406db8552ba5e3ff871a6ee32694ad90Evan Cheng/// return: 584485fafc8406db8552ba5e3ff871a6ee32694ad90Evan Cheng/// %retval = phi i32 [ %tmp0, %bb0 ], [ %tmp1, %bb1 ], [ %tmp2, %bb2 ] 585485fafc8406db8552ba5e3ff871a6ee32694ad90Evan Cheng/// ret i32 %retval 586485fafc8406db8552ba5e3ff871a6ee32694ad90Evan Cheng/// 587485fafc8406db8552ba5e3ff871a6ee32694ad90Evan Cheng/// => 588485fafc8406db8552ba5e3ff871a6ee32694ad90Evan Cheng/// 589485fafc8406db8552ba5e3ff871a6ee32694ad90Evan Cheng/// bb0: 590485fafc8406db8552ba5e3ff871a6ee32694ad90Evan Cheng/// %tmp0 = tail call i32 @f0() 591485fafc8406db8552ba5e3ff871a6ee32694ad90Evan Cheng/// ret i32 %tmp0 592485fafc8406db8552ba5e3ff871a6ee32694ad90Evan Cheng/// bb1: 593485fafc8406db8552ba5e3ff871a6ee32694ad90Evan Cheng/// %tmp1 = tail call i32 @f1() 594485fafc8406db8552ba5e3ff871a6ee32694ad90Evan Cheng/// ret i32 %tmp1 595485fafc8406db8552ba5e3ff871a6ee32694ad90Evan Cheng/// bb2: 596485fafc8406db8552ba5e3ff871a6ee32694ad90Evan Cheng/// %tmp2 = tail call i32 @f2() 597485fafc8406db8552ba5e3ff871a6ee32694ad90Evan Cheng/// ret i32 %tmp2 598485fafc8406db8552ba5e3ff871a6ee32694ad90Evan Cheng/// 599485fafc8406db8552ba5e3ff871a6ee32694ad90Evan Chengbool CodeGenPrepare::DupRetToEnableTailCallOpts(ReturnInst *RI) { 600661a390b830fcdea13ed9daeaf4e6dbd1adcdca6Cameron Zwarich if (!TLI) 601661a390b830fcdea13ed9daeaf4e6dbd1adcdca6Cameron Zwarich return false; 602661a390b830fcdea13ed9daeaf4e6dbd1adcdca6Cameron Zwarich 603485fafc8406db8552ba5e3ff871a6ee32694ad90Evan Cheng Value *V = RI->getReturnValue(); 6046e8ffc1c4d73e6c91aca9ac28ef5859ead26e2b6Cameron Zwarich PHINode *PN = V ? dyn_cast<PHINode>(V) : NULL; 6056e8ffc1c4d73e6c91aca9ac28ef5859ead26e2b6Cameron Zwarich if (V && !PN) 6064bae588c75fbd6d1b8401d83a94ba64fcc381d95Cameron Zwarich return false; 607485fafc8406db8552ba5e3ff871a6ee32694ad90Evan Cheng 6084bae588c75fbd6d1b8401d83a94ba64fcc381d95Cameron Zwarich BasicBlock *BB = RI->getParent(); 6096e8ffc1c4d73e6c91aca9ac28ef5859ead26e2b6Cameron Zwarich if (PN && PN->getParent() != BB) 6104bae588c75fbd6d1b8401d83a94ba64fcc381d95Cameron Zwarich return false; 611485fafc8406db8552ba5e3ff871a6ee32694ad90Evan Cheng 6124bae588c75fbd6d1b8401d83a94ba64fcc381d95Cameron Zwarich // It's not safe to eliminate the sign / zero extension of the return value. 6134bae588c75fbd6d1b8401d83a94ba64fcc381d95Cameron Zwarich // See llvm::isInTailCallPosition(). 6144bae588c75fbd6d1b8401d83a94ba64fcc381d95Cameron Zwarich const Function *F = BB->getParent(); 6154bae588c75fbd6d1b8401d83a94ba64fcc381d95Cameron Zwarich unsigned CallerRetAttr = F->getAttributes().getRetAttributes(); 6164bae588c75fbd6d1b8401d83a94ba64fcc381d95Cameron Zwarich if ((CallerRetAttr & Attribute::ZExt) || (CallerRetAttr & Attribute::SExt)) 6174bae588c75fbd6d1b8401d83a94ba64fcc381d95Cameron Zwarich return false; 618485fafc8406db8552ba5e3ff871a6ee32694ad90Evan Cheng 6196e8ffc1c4d73e6c91aca9ac28ef5859ead26e2b6Cameron Zwarich // Make sure there are no instructions between the PHI and return, or that the 6206e8ffc1c4d73e6c91aca9ac28ef5859ead26e2b6Cameron Zwarich // return is the first instruction in the block. 6216e8ffc1c4d73e6c91aca9ac28ef5859ead26e2b6Cameron Zwarich if (PN) { 6226e8ffc1c4d73e6c91aca9ac28ef5859ead26e2b6Cameron Zwarich BasicBlock::iterator BI = BB->begin(); 6236e8ffc1c4d73e6c91aca9ac28ef5859ead26e2b6Cameron Zwarich do { ++BI; } while (isa<DbgInfoIntrinsic>(BI)); 6246e8ffc1c4d73e6c91aca9ac28ef5859ead26e2b6Cameron Zwarich if (&*BI != RI) 6256e8ffc1c4d73e6c91aca9ac28ef5859ead26e2b6Cameron Zwarich return false; 6266e8ffc1c4d73e6c91aca9ac28ef5859ead26e2b6Cameron Zwarich } else { 627903548420016325db6d22328687f78cd4180facbCameron Zwarich BasicBlock::iterator BI = BB->begin(); 628903548420016325db6d22328687f78cd4180facbCameron Zwarich while (isa<DbgInfoIntrinsic>(BI)) ++BI; 629903548420016325db6d22328687f78cd4180facbCameron Zwarich if (&*BI != RI) 6306e8ffc1c4d73e6c91aca9ac28ef5859ead26e2b6Cameron Zwarich return false; 6316e8ffc1c4d73e6c91aca9ac28ef5859ead26e2b6Cameron Zwarich } 632485fafc8406db8552ba5e3ff871a6ee32694ad90Evan Cheng 6334bae588c75fbd6d1b8401d83a94ba64fcc381d95Cameron Zwarich /// Only dup the ReturnInst if the CallInst is likely to be emitted as a tail 6344bae588c75fbd6d1b8401d83a94ba64fcc381d95Cameron Zwarich /// call. 6354bae588c75fbd6d1b8401d83a94ba64fcc381d95Cameron Zwarich SmallVector<CallInst*, 4> TailCalls; 6366e8ffc1c4d73e6c91aca9ac28ef5859ead26e2b6Cameron Zwarich if (PN) { 6376e8ffc1c4d73e6c91aca9ac28ef5859ead26e2b6Cameron Zwarich for (unsigned I = 0, E = PN->getNumIncomingValues(); I != E; ++I) { 6386e8ffc1c4d73e6c91aca9ac28ef5859ead26e2b6Cameron Zwarich CallInst *CI = dyn_cast<CallInst>(PN->getIncomingValue(I)); 6396e8ffc1c4d73e6c91aca9ac28ef5859ead26e2b6Cameron Zwarich // Make sure the phi value is indeed produced by the tail call. 6406e8ffc1c4d73e6c91aca9ac28ef5859ead26e2b6Cameron Zwarich if (CI && CI->hasOneUse() && CI->getParent() == PN->getIncomingBlock(I) && 6416e8ffc1c4d73e6c91aca9ac28ef5859ead26e2b6Cameron Zwarich TLI->mayBeEmittedAsTailCall(CI)) 6426e8ffc1c4d73e6c91aca9ac28ef5859ead26e2b6Cameron Zwarich TailCalls.push_back(CI); 6436e8ffc1c4d73e6c91aca9ac28ef5859ead26e2b6Cameron Zwarich } 6446e8ffc1c4d73e6c91aca9ac28ef5859ead26e2b6Cameron Zwarich } else { 6456e8ffc1c4d73e6c91aca9ac28ef5859ead26e2b6Cameron Zwarich SmallPtrSet<BasicBlock*, 4> VisitedBBs; 6466e8ffc1c4d73e6c91aca9ac28ef5859ead26e2b6Cameron Zwarich for (pred_iterator PI = pred_begin(BB), PE = pred_end(BB); PI != PE; ++PI) { 6476e8ffc1c4d73e6c91aca9ac28ef5859ead26e2b6Cameron Zwarich if (!VisitedBBs.insert(*PI)) 6486e8ffc1c4d73e6c91aca9ac28ef5859ead26e2b6Cameron Zwarich continue; 6496e8ffc1c4d73e6c91aca9ac28ef5859ead26e2b6Cameron Zwarich 6506e8ffc1c4d73e6c91aca9ac28ef5859ead26e2b6Cameron Zwarich BasicBlock::InstListType &InstList = (*PI)->getInstList(); 6516e8ffc1c4d73e6c91aca9ac28ef5859ead26e2b6Cameron Zwarich BasicBlock::InstListType::reverse_iterator RI = InstList.rbegin(); 6526e8ffc1c4d73e6c91aca9ac28ef5859ead26e2b6Cameron Zwarich BasicBlock::InstListType::reverse_iterator RE = InstList.rend(); 653903548420016325db6d22328687f78cd4180facbCameron Zwarich do { ++RI; } while (RI != RE && isa<DbgInfoIntrinsic>(&*RI)); 654903548420016325db6d22328687f78cd4180facbCameron Zwarich if (RI == RE) 6556e8ffc1c4d73e6c91aca9ac28ef5859ead26e2b6Cameron Zwarich continue; 656903548420016325db6d22328687f78cd4180facbCameron Zwarich 6576e8ffc1c4d73e6c91aca9ac28ef5859ead26e2b6Cameron Zwarich CallInst *CI = dyn_cast<CallInst>(&*RI); 658dc31cfeb74c46fe564a350ffd20880e61d04f286Cameron Zwarich if (CI && CI->use_empty() && TLI->mayBeEmittedAsTailCall(CI)) 6596e8ffc1c4d73e6c91aca9ac28ef5859ead26e2b6Cameron Zwarich TailCalls.push_back(CI); 6606e8ffc1c4d73e6c91aca9ac28ef5859ead26e2b6Cameron Zwarich } 6614bae588c75fbd6d1b8401d83a94ba64fcc381d95Cameron Zwarich } 662485fafc8406db8552ba5e3ff871a6ee32694ad90Evan Cheng 6634bae588c75fbd6d1b8401d83a94ba64fcc381d95Cameron Zwarich bool Changed = false; 6644bae588c75fbd6d1b8401d83a94ba64fcc381d95Cameron Zwarich for (unsigned i = 0, e = TailCalls.size(); i != e; ++i) { 6654bae588c75fbd6d1b8401d83a94ba64fcc381d95Cameron Zwarich CallInst *CI = TailCalls[i]; 6664bae588c75fbd6d1b8401d83a94ba64fcc381d95Cameron Zwarich CallSite CS(CI); 6674bae588c75fbd6d1b8401d83a94ba64fcc381d95Cameron Zwarich 6684bae588c75fbd6d1b8401d83a94ba64fcc381d95Cameron Zwarich // Conservatively require the attributes of the call to match those of the 6694bae588c75fbd6d1b8401d83a94ba64fcc381d95Cameron Zwarich // return. Ignore noalias because it doesn't affect the call sequence. 6704bae588c75fbd6d1b8401d83a94ba64fcc381d95Cameron Zwarich unsigned CalleeRetAttr = CS.getAttributes().getRetAttributes(); 6714bae588c75fbd6d1b8401d83a94ba64fcc381d95Cameron Zwarich if ((CalleeRetAttr ^ CallerRetAttr) & ~Attribute::NoAlias) 6724bae588c75fbd6d1b8401d83a94ba64fcc381d95Cameron Zwarich continue; 673485fafc8406db8552ba5e3ff871a6ee32694ad90Evan Cheng 6744bae588c75fbd6d1b8401d83a94ba64fcc381d95Cameron Zwarich // Make sure the call instruction is followed by an unconditional branch to 6754bae588c75fbd6d1b8401d83a94ba64fcc381d95Cameron Zwarich // the return block. 6764bae588c75fbd6d1b8401d83a94ba64fcc381d95Cameron Zwarich BasicBlock *CallBB = CI->getParent(); 6774bae588c75fbd6d1b8401d83a94ba64fcc381d95Cameron Zwarich BranchInst *BI = dyn_cast<BranchInst>(CallBB->getTerminator()); 6784bae588c75fbd6d1b8401d83a94ba64fcc381d95Cameron Zwarich if (!BI || !BI->isUnconditional() || BI->getSuccessor(0) != BB) 6794bae588c75fbd6d1b8401d83a94ba64fcc381d95Cameron Zwarich continue; 6804bae588c75fbd6d1b8401d83a94ba64fcc381d95Cameron Zwarich 6814bae588c75fbd6d1b8401d83a94ba64fcc381d95Cameron Zwarich // Duplicate the return into CallBB. 6824bae588c75fbd6d1b8401d83a94ba64fcc381d95Cameron Zwarich (void)FoldReturnIntoUncondBranch(RI, BB, CallBB); 68352e37df8c05eb73e40421f0703c0d89fe854ffeaDevang Patel ModifiedDT = Changed = true; 6844bae588c75fbd6d1b8401d83a94ba64fcc381d95Cameron Zwarich ++NumRetsDup; 685485fafc8406db8552ba5e3ff871a6ee32694ad90Evan Cheng } 686485fafc8406db8552ba5e3ff871a6ee32694ad90Evan Cheng 6874bae588c75fbd6d1b8401d83a94ba64fcc381d95Cameron Zwarich // If we eliminated all predecessors of the block, delete the block now. 6884bae588c75fbd6d1b8401d83a94ba64fcc381d95Cameron Zwarich if (Changed && pred_begin(BB) == pred_end(BB)) 6894bae588c75fbd6d1b8401d83a94ba64fcc381d95Cameron Zwarich BB->eraseFromParent(); 6904bae588c75fbd6d1b8401d83a94ba64fcc381d95Cameron Zwarich 6914bae588c75fbd6d1b8401d83a94ba64fcc381d95Cameron Zwarich return Changed; 692485fafc8406db8552ba5e3ff871a6ee32694ad90Evan Cheng} 693485fafc8406db8552ba5e3ff871a6ee32694ad90Evan Cheng 69488a5c832ac71eb31d2b1bc143817af9248f4c549Chris Lattner//===----------------------------------------------------------------------===// 69588a5c832ac71eb31d2b1bc143817af9248f4c549Chris Lattner// Memory Optimization 69688a5c832ac71eb31d2b1bc143817af9248f4c549Chris Lattner//===----------------------------------------------------------------------===// 69788a5c832ac71eb31d2b1bc143817af9248f4c549Chris Lattner 698dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner/// IsNonLocalValue - Return true if the specified values are defined in a 699dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner/// different basic block than BB. 700dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattnerstatic bool IsNonLocalValue(Value *V, BasicBlock *BB) { 701dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner if (Instruction *I = dyn_cast<Instruction>(V)) 702dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner return I->getParent() != BB; 703dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner return false; 704dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner} 705dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner 7064a8ee23a8181f668dc294b417f67e1675ad391abBob Wilson/// OptimizeMemoryInst - Load and Store Instructions often have 707dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner/// addressing modes that can do significant amounts of computation. As such, 708dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner/// instruction selection will try to get the load or store to do as much 709dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner/// computation as possible for the program. The problem is that isel can only 710dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner/// see within a single block. As such, we sink as much legal addressing mode 711dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner/// stuff into the block as possible. 71288a5c832ac71eb31d2b1bc143817af9248f4c549Chris Lattner/// 71388a5c832ac71eb31d2b1bc143817af9248f4c549Chris Lattner/// This method is used to optimize both load/store and inline asms with memory 71488a5c832ac71eb31d2b1bc143817af9248f4c549Chris Lattner/// operands. 715896617b776e7b015346160645b19be776cbe3805Chris Lattnerbool CodeGenPrepare::OptimizeMemoryInst(Instruction *MemoryInst, Value *Addr, 716db125cfaf57cc83e7dd7453de2d509bc8efd0e5eChris Lattner Type *AccessTy) { 71735bf4d6d8018160557a92b86181acbcef76f86ebOwen Anderson Value *Repl = Addr; 71835bf4d6d8018160557a92b86181acbcef76f86ebOwen Anderson 719d2f4174fcc69a3328076734fa3256b31e5b7f734Owen Anderson // Try to collapse single-value PHI nodes. This is necessary to undo 720d2f4174fcc69a3328076734fa3256b31e5b7f734Owen Anderson // unprofitable PRE transformations. 7217cb4fa20b5534decf527a6bfcc74bd79ea11cbb1Cameron Zwarich SmallVector<Value*, 8> worklist; 7227cb4fa20b5534decf527a6bfcc74bd79ea11cbb1Cameron Zwarich SmallPtrSet<Value*, 16> Visited; 72335bf4d6d8018160557a92b86181acbcef76f86ebOwen Anderson worklist.push_back(Addr); 72435bf4d6d8018160557a92b86181acbcef76f86ebOwen Anderson 72535bf4d6d8018160557a92b86181acbcef76f86ebOwen Anderson // Use a worklist to iteratively look through PHI nodes, and ensure that 72635bf4d6d8018160557a92b86181acbcef76f86ebOwen Anderson // the addressing mode obtained from the non-PHI roots of the graph 72735bf4d6d8018160557a92b86181acbcef76f86ebOwen Anderson // are equivalent. 72835bf4d6d8018160557a92b86181acbcef76f86ebOwen Anderson Value *Consensus = 0; 7294c078f0d6df6136cbbcf581c254869051d455fdcCameron Zwarich unsigned NumUsesConsensus = 0; 7307c8d351d997655eb457bac5f810c219a9089594cCameron Zwarich bool IsNumUsesConsensusValid = false; 73135bf4d6d8018160557a92b86181acbcef76f86ebOwen Anderson SmallVector<Instruction*, 16> AddrModeInsts; 73235bf4d6d8018160557a92b86181acbcef76f86ebOwen Anderson ExtAddrMode AddrMode; 73335bf4d6d8018160557a92b86181acbcef76f86ebOwen Anderson while (!worklist.empty()) { 73435bf4d6d8018160557a92b86181acbcef76f86ebOwen Anderson Value *V = worklist.back(); 73535bf4d6d8018160557a92b86181acbcef76f86ebOwen Anderson worklist.pop_back(); 73635bf4d6d8018160557a92b86181acbcef76f86ebOwen Anderson 73735bf4d6d8018160557a92b86181acbcef76f86ebOwen Anderson // Break use-def graph loops. 73835bf4d6d8018160557a92b86181acbcef76f86ebOwen Anderson if (Visited.count(V)) { 73935bf4d6d8018160557a92b86181acbcef76f86ebOwen Anderson Consensus = 0; 74035bf4d6d8018160557a92b86181acbcef76f86ebOwen Anderson break; 74135bf4d6d8018160557a92b86181acbcef76f86ebOwen Anderson } 74235bf4d6d8018160557a92b86181acbcef76f86ebOwen Anderson 74335bf4d6d8018160557a92b86181acbcef76f86ebOwen Anderson Visited.insert(V); 74435bf4d6d8018160557a92b86181acbcef76f86ebOwen Anderson 74535bf4d6d8018160557a92b86181acbcef76f86ebOwen Anderson // For a PHI node, push all of its incoming values. 74635bf4d6d8018160557a92b86181acbcef76f86ebOwen Anderson if (PHINode *P = dyn_cast<PHINode>(V)) { 74735bf4d6d8018160557a92b86181acbcef76f86ebOwen Anderson for (unsigned i = 0, e = P->getNumIncomingValues(); i != e; ++i) 74835bf4d6d8018160557a92b86181acbcef76f86ebOwen Anderson worklist.push_back(P->getIncomingValue(i)); 74935bf4d6d8018160557a92b86181acbcef76f86ebOwen Anderson continue; 75035bf4d6d8018160557a92b86181acbcef76f86ebOwen Anderson } 75135bf4d6d8018160557a92b86181acbcef76f86ebOwen Anderson 75235bf4d6d8018160557a92b86181acbcef76f86ebOwen Anderson // For non-PHIs, determine the addressing mode being computed. 75335bf4d6d8018160557a92b86181acbcef76f86ebOwen Anderson SmallVector<Instruction*, 16> NewAddrModeInsts; 75435bf4d6d8018160557a92b86181acbcef76f86ebOwen Anderson ExtAddrMode NewAddrMode = 75535bf4d6d8018160557a92b86181acbcef76f86ebOwen Anderson AddressingModeMatcher::Match(V, AccessTy,MemoryInst, 75635bf4d6d8018160557a92b86181acbcef76f86ebOwen Anderson NewAddrModeInsts, *TLI); 7577c8d351d997655eb457bac5f810c219a9089594cCameron Zwarich 7587c8d351d997655eb457bac5f810c219a9089594cCameron Zwarich // This check is broken into two cases with very similar code to avoid using 7597c8d351d997655eb457bac5f810c219a9089594cCameron Zwarich // getNumUses() as much as possible. Some values have a lot of uses, so 7607c8d351d997655eb457bac5f810c219a9089594cCameron Zwarich // calling getNumUses() unconditionally caused a significant compile-time 7617c8d351d997655eb457bac5f810c219a9089594cCameron Zwarich // regression. 7627c8d351d997655eb457bac5f810c219a9089594cCameron Zwarich if (!Consensus) { 7637c8d351d997655eb457bac5f810c219a9089594cCameron Zwarich Consensus = V; 7647c8d351d997655eb457bac5f810c219a9089594cCameron Zwarich AddrMode = NewAddrMode; 7657c8d351d997655eb457bac5f810c219a9089594cCameron Zwarich AddrModeInsts = NewAddrModeInsts; 7667c8d351d997655eb457bac5f810c219a9089594cCameron Zwarich continue; 7677c8d351d997655eb457bac5f810c219a9089594cCameron Zwarich } else if (NewAddrMode == AddrMode) { 7687c8d351d997655eb457bac5f810c219a9089594cCameron Zwarich if (!IsNumUsesConsensusValid) { 7697c8d351d997655eb457bac5f810c219a9089594cCameron Zwarich NumUsesConsensus = Consensus->getNumUses(); 7707c8d351d997655eb457bac5f810c219a9089594cCameron Zwarich IsNumUsesConsensusValid = true; 7717c8d351d997655eb457bac5f810c219a9089594cCameron Zwarich } 7727c8d351d997655eb457bac5f810c219a9089594cCameron Zwarich 7737c8d351d997655eb457bac5f810c219a9089594cCameron Zwarich // Ensure that the obtained addressing mode is equivalent to that obtained 7747c8d351d997655eb457bac5f810c219a9089594cCameron Zwarich // for all other roots of the PHI traversal. Also, when choosing one 7757c8d351d997655eb457bac5f810c219a9089594cCameron Zwarich // such root as representative, select the one with the most uses in order 7767c8d351d997655eb457bac5f810c219a9089594cCameron Zwarich // to keep the cost modeling heuristics in AddressingModeMatcher 7777c8d351d997655eb457bac5f810c219a9089594cCameron Zwarich // applicable. 7784c078f0d6df6136cbbcf581c254869051d455fdcCameron Zwarich unsigned NumUses = V->getNumUses(); 7794c078f0d6df6136cbbcf581c254869051d455fdcCameron Zwarich if (NumUses > NumUsesConsensus) { 78035bf4d6d8018160557a92b86181acbcef76f86ebOwen Anderson Consensus = V; 7814c078f0d6df6136cbbcf581c254869051d455fdcCameron Zwarich NumUsesConsensus = NumUses; 78235bf4d6d8018160557a92b86181acbcef76f86ebOwen Anderson AddrModeInsts = NewAddrModeInsts; 783d2f4174fcc69a3328076734fa3256b31e5b7f734Owen Anderson } 78435bf4d6d8018160557a92b86181acbcef76f86ebOwen Anderson continue; 785d2f4174fcc69a3328076734fa3256b31e5b7f734Owen Anderson } 786d2f4174fcc69a3328076734fa3256b31e5b7f734Owen Anderson 78735bf4d6d8018160557a92b86181acbcef76f86ebOwen Anderson Consensus = 0; 78835bf4d6d8018160557a92b86181acbcef76f86ebOwen Anderson break; 789d2f4174fcc69a3328076734fa3256b31e5b7f734Owen Anderson } 790d2f4174fcc69a3328076734fa3256b31e5b7f734Owen Anderson 79135bf4d6d8018160557a92b86181acbcef76f86ebOwen Anderson // If the addressing mode couldn't be determined, or if multiple different 79235bf4d6d8018160557a92b86181acbcef76f86ebOwen Anderson // ones were determined, bail out now. 79335bf4d6d8018160557a92b86181acbcef76f86ebOwen Anderson if (!Consensus) return false; 79435bf4d6d8018160557a92b86181acbcef76f86ebOwen Anderson 795dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner // Check to see if any of the instructions supersumed by this addr mode are 796dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner // non-local to I's BB. 797dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner bool AnyNonLocal = false; 798dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner for (unsigned i = 0, e = AddrModeInsts.size(); i != e; ++i) { 799896617b776e7b015346160645b19be776cbe3805Chris Lattner if (IsNonLocalValue(AddrModeInsts[i], MemoryInst->getParent())) { 800dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner AnyNonLocal = true; 801dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner break; 802dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner } 803dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner } 804692bf6b85e0eaed549cd47d67289ab7b28e32651Eric Christopher 805dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner // If all the instructions matched are already in this BB, don't do anything. 806dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner if (!AnyNonLocal) { 80768d67fdf203ff2d5b0eeb925befd0866bce3aceeDavid Greene DEBUG(dbgs() << "CGP: Found local addrmode: " << AddrMode << "\n"); 808dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner return false; 809dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner } 810692bf6b85e0eaed549cd47d67289ab7b28e32651Eric Christopher 811dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner // Insert this computation right after this user. Since our caller is 812dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner // scanning from the top of the BB to the bottom, reuse of the expr are 813dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner // guaranteed to happen later. 8142048c379dd9e080c3e1bb0c93636da9564d8772cDevang Patel IRBuilder<> Builder(MemoryInst); 815692bf6b85e0eaed549cd47d67289ab7b28e32651Eric Christopher 816dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner // Now that we determined the addressing expression we want to use and know 817dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner // that we have to sink it into this block. Check to see if we have already 818dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner // done this for some other load/store instr in this block. If so, reuse the 819dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner // computation. 820dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner Value *&SunkAddr = SunkAddrs[Addr]; 821dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner if (SunkAddr) { 82268d67fdf203ff2d5b0eeb925befd0866bce3aceeDavid Greene DEBUG(dbgs() << "CGP: Reusing nonlocal addrmode: " << AddrMode << " for " 8236c1980b3357207c4d756255bc5e32323eac278dcDan Gohman << *MemoryInst); 824dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner if (SunkAddr->getType() != Addr->getType()) 8252048c379dd9e080c3e1bb0c93636da9564d8772cDevang Patel SunkAddr = Builder.CreateBitCast(SunkAddr, Addr->getType(), "tmp"); 826dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner } else { 82768d67fdf203ff2d5b0eeb925befd0866bce3aceeDavid Greene DEBUG(dbgs() << "CGP: SINKING nonlocal addrmode: " << AddrMode << " for " 8286c1980b3357207c4d756255bc5e32323eac278dcDan Gohman << *MemoryInst); 829db125cfaf57cc83e7dd7453de2d509bc8efd0e5eChris Lattner Type *IntPtrTy = 8301d0be15f89cb5056e20e2d24faa8d6afb1573bcaOwen Anderson TLI->getTargetData()->getIntPtrType(AccessTy->getContext()); 831692bf6b85e0eaed549cd47d67289ab7b28e32651Eric Christopher 832dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner Value *Result = 0; 833d8d0b6a42c09f1c5b00a4e7029b08074a3da5acdDan Gohman 834d8d0b6a42c09f1c5b00a4e7029b08074a3da5acdDan Gohman // Start with the base register. Do this first so that subsequent address 835d8d0b6a42c09f1c5b00a4e7029b08074a3da5acdDan Gohman // matching finds it last, which will prevent it from trying to match it 836d8d0b6a42c09f1c5b00a4e7029b08074a3da5acdDan Gohman // as the scaled value in case it happens to be a mul. That would be 837d8d0b6a42c09f1c5b00a4e7029b08074a3da5acdDan Gohman // problematic if we've sunk a different mul for the scale, because then 838d8d0b6a42c09f1c5b00a4e7029b08074a3da5acdDan Gohman // we'd end up sinking both muls. 839d8d0b6a42c09f1c5b00a4e7029b08074a3da5acdDan Gohman if (AddrMode.BaseReg) { 840d8d0b6a42c09f1c5b00a4e7029b08074a3da5acdDan Gohman Value *V = AddrMode.BaseReg; 8411df9859c40492511b8aa4321eb76496005d3b75bDuncan Sands if (V->getType()->isPointerTy()) 8422048c379dd9e080c3e1bb0c93636da9564d8772cDevang Patel V = Builder.CreatePtrToInt(V, IntPtrTy, "sunkaddr"); 843d8d0b6a42c09f1c5b00a4e7029b08074a3da5acdDan Gohman if (V->getType() != IntPtrTy) 8442048c379dd9e080c3e1bb0c93636da9564d8772cDevang Patel V = Builder.CreateIntCast(V, IntPtrTy, /*isSigned=*/true, "sunkaddr"); 845d8d0b6a42c09f1c5b00a4e7029b08074a3da5acdDan Gohman Result = V; 846d8d0b6a42c09f1c5b00a4e7029b08074a3da5acdDan Gohman } 847d8d0b6a42c09f1c5b00a4e7029b08074a3da5acdDan Gohman 848d8d0b6a42c09f1c5b00a4e7029b08074a3da5acdDan Gohman // Add the scale value. 849dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner if (AddrMode.Scale) { 850dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner Value *V = AddrMode.ScaledReg; 851dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner if (V->getType() == IntPtrTy) { 852dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner // done. 8531df9859c40492511b8aa4321eb76496005d3b75bDuncan Sands } else if (V->getType()->isPointerTy()) { 8542048c379dd9e080c3e1bb0c93636da9564d8772cDevang Patel V = Builder.CreatePtrToInt(V, IntPtrTy, "sunkaddr"); 855dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner } else if (cast<IntegerType>(IntPtrTy)->getBitWidth() < 856dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner cast<IntegerType>(V->getType())->getBitWidth()) { 8572048c379dd9e080c3e1bb0c93636da9564d8772cDevang Patel V = Builder.CreateTrunc(V, IntPtrTy, "sunkaddr"); 858dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner } else { 8592048c379dd9e080c3e1bb0c93636da9564d8772cDevang Patel V = Builder.CreateSExt(V, IntPtrTy, "sunkaddr"); 860dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner } 861dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner if (AddrMode.Scale != 1) 8622048c379dd9e080c3e1bb0c93636da9564d8772cDevang Patel V = Builder.CreateMul(V, ConstantInt::get(IntPtrTy, AddrMode.Scale), 8632048c379dd9e080c3e1bb0c93636da9564d8772cDevang Patel "sunkaddr"); 864dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner if (Result) 8652048c379dd9e080c3e1bb0c93636da9564d8772cDevang Patel Result = Builder.CreateAdd(Result, V, "sunkaddr"); 866dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner else 867dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner Result = V; 868dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner } 869692bf6b85e0eaed549cd47d67289ab7b28e32651Eric Christopher 870dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner // Add in the BaseGV if present. 871dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner if (AddrMode.BaseGV) { 8722048c379dd9e080c3e1bb0c93636da9564d8772cDevang Patel Value *V = Builder.CreatePtrToInt(AddrMode.BaseGV, IntPtrTy, "sunkaddr"); 873dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner if (Result) 8742048c379dd9e080c3e1bb0c93636da9564d8772cDevang Patel Result = Builder.CreateAdd(Result, V, "sunkaddr"); 875dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner else 876dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner Result = V; 877dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner } 878692bf6b85e0eaed549cd47d67289ab7b28e32651Eric Christopher 879dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner // Add in the Base Offset if present. 880dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner if (AddrMode.BaseOffs) { 881eed707b1e6097aac2bb6b3d47271f6300ace7f2eOwen Anderson Value *V = ConstantInt::get(IntPtrTy, AddrMode.BaseOffs); 882dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner if (Result) 8832048c379dd9e080c3e1bb0c93636da9564d8772cDevang Patel Result = Builder.CreateAdd(Result, V, "sunkaddr"); 884dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner else 885dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner Result = V; 886dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner } 887dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner 888dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner if (Result == 0) 889a7235ea7245028a0723e8ab7fd011386b3900777Owen Anderson SunkAddr = Constant::getNullValue(Addr->getType()); 890dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner else 8912048c379dd9e080c3e1bb0c93636da9564d8772cDevang Patel SunkAddr = Builder.CreateIntToPtr(Result, Addr->getType(), "sunkaddr"); 892dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner } 893692bf6b85e0eaed549cd47d67289ab7b28e32651Eric Christopher 894d2f4174fcc69a3328076734fa3256b31e5b7f734Owen Anderson MemoryInst->replaceUsesOfWith(Repl, SunkAddr); 895692bf6b85e0eaed549cd47d67289ab7b28e32651Eric Christopher 8960403b473dd99b5c7db1fa7048288be6cb42e7abdChris Lattner // If we have no uses, recursively delete the value and all dead instructions 8970403b473dd99b5c7db1fa7048288be6cb42e7abdChris Lattner // using it. 898d2f4174fcc69a3328076734fa3256b31e5b7f734Owen Anderson if (Repl->use_empty()) { 8990403b473dd99b5c7db1fa7048288be6cb42e7abdChris Lattner // This can cause recursive deletion, which can invalidate our iterator. 9000403b473dd99b5c7db1fa7048288be6cb42e7abdChris Lattner // Use a WeakVH to hold onto it in case this happens. 9010403b473dd99b5c7db1fa7048288be6cb42e7abdChris Lattner WeakVH IterHandle(CurInstIterator); 9020403b473dd99b5c7db1fa7048288be6cb42e7abdChris Lattner BasicBlock *BB = CurInstIterator->getParent(); 9030403b473dd99b5c7db1fa7048288be6cb42e7abdChris Lattner 904d2f4174fcc69a3328076734fa3256b31e5b7f734Owen Anderson RecursivelyDeleteTriviallyDeadInstructions(Repl); 9050403b473dd99b5c7db1fa7048288be6cb42e7abdChris Lattner 9060403b473dd99b5c7db1fa7048288be6cb42e7abdChris Lattner if (IterHandle != CurInstIterator) { 9070403b473dd99b5c7db1fa7048288be6cb42e7abdChris Lattner // If the iterator instruction was recursively deleted, start over at the 9080403b473dd99b5c7db1fa7048288be6cb42e7abdChris Lattner // start of the block. 9090403b473dd99b5c7db1fa7048288be6cb42e7abdChris Lattner CurInstIterator = BB->begin(); 9100403b473dd99b5c7db1fa7048288be6cb42e7abdChris Lattner SunkAddrs.clear(); 9110403b473dd99b5c7db1fa7048288be6cb42e7abdChris Lattner } else { 9120403b473dd99b5c7db1fa7048288be6cb42e7abdChris Lattner // This address is now available for reassignment, so erase the table 9130403b473dd99b5c7db1fa7048288be6cb42e7abdChris Lattner // entry; we don't want to match some completely different instruction. 9140403b473dd99b5c7db1fa7048288be6cb42e7abdChris Lattner SunkAddrs[Addr] = 0; 9150403b473dd99b5c7db1fa7048288be6cb42e7abdChris Lattner } 916536d31b5b391ee76eae33f4756f6442bf10b2d72Dale Johannesen } 91731ff1333e0651192212cee6e090df2ff57d19b53Cameron Zwarich ++NumMemoryInsts; 918dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner return true; 919dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner} 920dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner 9219bf12b5583104c810cfadcdce91edf9efad79973Evan Cheng/// OptimizeInlineAsmInst - If there are any memory operands, use 92288a5c832ac71eb31d2b1bc143817af9248f4c549Chris Lattner/// OptimizeMemoryInst to sink their address computing into the block when 9239bf12b5583104c810cfadcdce91edf9efad79973Evan Cheng/// possible / profitable. 9247579609bfe0d915b6c2d8dc094a132d793ec8855Chris Lattnerbool CodeGenPrepare::OptimizeInlineAsmInst(CallInst *CS) { 9259bf12b5583104c810cfadcdce91edf9efad79973Evan Cheng bool MadeChange = false; 9269bf12b5583104c810cfadcdce91edf9efad79973Evan Cheng 9277579609bfe0d915b6c2d8dc094a132d793ec8855Chris Lattner TargetLowering::AsmOperandInfoVector 9287579609bfe0d915b6c2d8dc094a132d793ec8855Chris Lattner TargetConstraints = TLI->ParseConstraints(CS); 929677c6ecd0804c247eb727a830b50cd6537a6c12cDale Johannesen unsigned ArgNo = 0; 930eac6e1d0c748afc3d1496be0753ffbe5f5a4279bJohn Thompson for (unsigned i = 0, e = TargetConstraints.size(); i != e; ++i) { 931eac6e1d0c748afc3d1496be0753ffbe5f5a4279bJohn Thompson TargetLowering::AsmOperandInfo &OpInfo = TargetConstraints[i]; 932eac6e1d0c748afc3d1496be0753ffbe5f5a4279bJohn Thompson 9339bf12b5583104c810cfadcdce91edf9efad79973Evan Cheng // Compute the constraint code and ConstraintType to use. 9341784d160e4efa75782884d451d0788b9457e67dcDale Johannesen TLI->ComputeConstraintToUse(OpInfo, SDValue()); 9359bf12b5583104c810cfadcdce91edf9efad79973Evan Cheng 9369ec8095485c994522c9a50e16fc029de94c20476Eli Friedman if (OpInfo.ConstraintType == TargetLowering::C_Memory && 9379ec8095485c994522c9a50e16fc029de94c20476Eli Friedman OpInfo.isIndirect) { 9387579609bfe0d915b6c2d8dc094a132d793ec8855Chris Lattner Value *OpVal = CS->getArgOperand(ArgNo++); 9391a8943a1f872a47b821fe7075f07b42403fa1a3fChris Lattner MadeChange |= OptimizeMemoryInst(CS, OpVal, OpVal->getType()); 940677c6ecd0804c247eb727a830b50cd6537a6c12cDale Johannesen } else if (OpInfo.Type == InlineAsm::isInput) 941677c6ecd0804c247eb727a830b50cd6537a6c12cDale Johannesen ArgNo++; 9429bf12b5583104c810cfadcdce91edf9efad79973Evan Cheng } 9439bf12b5583104c810cfadcdce91edf9efad79973Evan Cheng 9449bf12b5583104c810cfadcdce91edf9efad79973Evan Cheng return MadeChange; 9459bf12b5583104c810cfadcdce91edf9efad79973Evan Cheng} 9469bf12b5583104c810cfadcdce91edf9efad79973Evan Cheng 947b00f236b03ea57520f94823780896ebdbc5d8bdcDan Gohman/// MoveExtToFormExtLoad - Move a zext or sext fed by a load into the same 948b00f236b03ea57520f94823780896ebdbc5d8bdcDan Gohman/// basic block as the load, unless conditions are unfavorable. This allows 949b00f236b03ea57520f94823780896ebdbc5d8bdcDan Gohman/// SelectionDAG to fold the extend into the load. 950b00f236b03ea57520f94823780896ebdbc5d8bdcDan Gohman/// 951b00f236b03ea57520f94823780896ebdbc5d8bdcDan Gohmanbool CodeGenPrepare::MoveExtToFormExtLoad(Instruction *I) { 952b00f236b03ea57520f94823780896ebdbc5d8bdcDan Gohman // Look for a load being extended. 953b00f236b03ea57520f94823780896ebdbc5d8bdcDan Gohman LoadInst *LI = dyn_cast<LoadInst>(I->getOperand(0)); 954b00f236b03ea57520f94823780896ebdbc5d8bdcDan Gohman if (!LI) return false; 955b00f236b03ea57520f94823780896ebdbc5d8bdcDan Gohman 956b00f236b03ea57520f94823780896ebdbc5d8bdcDan Gohman // If they're already in the same block, there's nothing to do. 957b00f236b03ea57520f94823780896ebdbc5d8bdcDan Gohman if (LI->getParent() == I->getParent()) 958b00f236b03ea57520f94823780896ebdbc5d8bdcDan Gohman return false; 959b00f236b03ea57520f94823780896ebdbc5d8bdcDan Gohman 960b00f236b03ea57520f94823780896ebdbc5d8bdcDan Gohman // If the load has other users and the truncate is not free, this probably 961b00f236b03ea57520f94823780896ebdbc5d8bdcDan Gohman // isn't worthwhile. 962b00f236b03ea57520f94823780896ebdbc5d8bdcDan Gohman if (!LI->hasOneUse() && 963ec57a1acec7803fff2faa54c6ea8fec2be01aeb9Bob Wilson TLI && (TLI->isTypeLegal(TLI->getValueType(LI->getType())) || 964ec57a1acec7803fff2faa54c6ea8fec2be01aeb9Bob Wilson !TLI->isTypeLegal(TLI->getValueType(I->getType()))) && 96571dc4d96ed39fadcdccf8c578d49a1afdae0c6baBob Wilson !TLI->isTruncateFree(I->getType(), LI->getType())) 966b00f236b03ea57520f94823780896ebdbc5d8bdcDan Gohman return false; 967b00f236b03ea57520f94823780896ebdbc5d8bdcDan Gohman 968b00f236b03ea57520f94823780896ebdbc5d8bdcDan Gohman // Check whether the target supports casts folded into loads. 969b00f236b03ea57520f94823780896ebdbc5d8bdcDan Gohman unsigned LType; 970b00f236b03ea57520f94823780896ebdbc5d8bdcDan Gohman if (isa<ZExtInst>(I)) 971b00f236b03ea57520f94823780896ebdbc5d8bdcDan Gohman LType = ISD::ZEXTLOAD; 972b00f236b03ea57520f94823780896ebdbc5d8bdcDan Gohman else { 973b00f236b03ea57520f94823780896ebdbc5d8bdcDan Gohman assert(isa<SExtInst>(I) && "Unexpected ext type!"); 974b00f236b03ea57520f94823780896ebdbc5d8bdcDan Gohman LType = ISD::SEXTLOAD; 975b00f236b03ea57520f94823780896ebdbc5d8bdcDan Gohman } 976b00f236b03ea57520f94823780896ebdbc5d8bdcDan Gohman if (TLI && !TLI->isLoadExtLegal(LType, TLI->getValueType(LI->getType()))) 977b00f236b03ea57520f94823780896ebdbc5d8bdcDan Gohman return false; 978b00f236b03ea57520f94823780896ebdbc5d8bdcDan Gohman 979b00f236b03ea57520f94823780896ebdbc5d8bdcDan Gohman // Move the extend into the same block as the load, so that SelectionDAG 980b00f236b03ea57520f94823780896ebdbc5d8bdcDan Gohman // can fold it. 981b00f236b03ea57520f94823780896ebdbc5d8bdcDan Gohman I->removeFromParent(); 982b00f236b03ea57520f94823780896ebdbc5d8bdcDan Gohman I->insertAfter(LI); 98331ff1333e0651192212cee6e090df2ff57d19b53Cameron Zwarich ++NumExtsMoved; 984b00f236b03ea57520f94823780896ebdbc5d8bdcDan Gohman return true; 985b00f236b03ea57520f94823780896ebdbc5d8bdcDan Gohman} 986b00f236b03ea57520f94823780896ebdbc5d8bdcDan Gohman 987bdcb726fcad1e3fddc70847a2b91d4d4f9396938Evan Chengbool CodeGenPrepare::OptimizeExtUses(Instruction *I) { 988bdcb726fcad1e3fddc70847a2b91d4d4f9396938Evan Cheng BasicBlock *DefBB = I->getParent(); 989bdcb726fcad1e3fddc70847a2b91d4d4f9396938Evan Cheng 9909120f5c35b756e0b9d7747616e97df8f30edfcc8Bob Wilson // If the result of a {s|z}ext and its source are both live out, rewrite all 991bdcb726fcad1e3fddc70847a2b91d4d4f9396938Evan Cheng // other uses of the source with result of extension. 992bdcb726fcad1e3fddc70847a2b91d4d4f9396938Evan Cheng Value *Src = I->getOperand(0); 993bdcb726fcad1e3fddc70847a2b91d4d4f9396938Evan Cheng if (Src->hasOneUse()) 994bdcb726fcad1e3fddc70847a2b91d4d4f9396938Evan Cheng return false; 995bdcb726fcad1e3fddc70847a2b91d4d4f9396938Evan Cheng 996696e5c047bd06bf6b7b5471b3f4dec319b43628bEvan Cheng // Only do this xform if truncating is free. 99753bdbd756581a9a1d6d381059f103c5f3c687bb6Gabor Greif if (TLI && !TLI->isTruncateFree(I->getType(), Src->getType())) 998f9785f92b630e69262c395b2fc0893451169d68bEvan Cheng return false; 999f9785f92b630e69262c395b2fc0893451169d68bEvan Cheng 1000772de516b6851e679d3da9e5171712b9c3122019Evan Cheng // Only safe to perform the optimization if the source is also defined in 1001765dff258545f019502023045b471443ff9ef6c4Evan Cheng // this block. 1002765dff258545f019502023045b471443ff9ef6c4Evan Cheng if (!isa<Instruction>(Src) || DefBB != cast<Instruction>(Src)->getParent()) 1003772de516b6851e679d3da9e5171712b9c3122019Evan Cheng return false; 1004772de516b6851e679d3da9e5171712b9c3122019Evan Cheng 1005bdcb726fcad1e3fddc70847a2b91d4d4f9396938Evan Cheng bool DefIsLiveOut = false; 1006692bf6b85e0eaed549cd47d67289ab7b28e32651Eric Christopher for (Value::use_iterator UI = I->use_begin(), E = I->use_end(); 1007bdcb726fcad1e3fddc70847a2b91d4d4f9396938Evan Cheng UI != E; ++UI) { 1008bdcb726fcad1e3fddc70847a2b91d4d4f9396938Evan Cheng Instruction *User = cast<Instruction>(*UI); 1009bdcb726fcad1e3fddc70847a2b91d4d4f9396938Evan Cheng 1010bdcb726fcad1e3fddc70847a2b91d4d4f9396938Evan Cheng // Figure out which BB this ext is used in. 1011bdcb726fcad1e3fddc70847a2b91d4d4f9396938Evan Cheng BasicBlock *UserBB = User->getParent(); 1012bdcb726fcad1e3fddc70847a2b91d4d4f9396938Evan Cheng if (UserBB == DefBB) continue; 1013bdcb726fcad1e3fddc70847a2b91d4d4f9396938Evan Cheng DefIsLiveOut = true; 1014bdcb726fcad1e3fddc70847a2b91d4d4f9396938Evan Cheng break; 1015bdcb726fcad1e3fddc70847a2b91d4d4f9396938Evan Cheng } 1016bdcb726fcad1e3fddc70847a2b91d4d4f9396938Evan Cheng if (!DefIsLiveOut) 1017bdcb726fcad1e3fddc70847a2b91d4d4f9396938Evan Cheng return false; 1018bdcb726fcad1e3fddc70847a2b91d4d4f9396938Evan Cheng 1019765dff258545f019502023045b471443ff9ef6c4Evan Cheng // Make sure non of the uses are PHI nodes. 1020692bf6b85e0eaed549cd47d67289ab7b28e32651Eric Christopher for (Value::use_iterator UI = Src->use_begin(), E = Src->use_end(); 1021765dff258545f019502023045b471443ff9ef6c4Evan Cheng UI != E; ++UI) { 1022765dff258545f019502023045b471443ff9ef6c4Evan Cheng Instruction *User = cast<Instruction>(*UI); 1023f9785f92b630e69262c395b2fc0893451169d68bEvan Cheng BasicBlock *UserBB = User->getParent(); 1024f9785f92b630e69262c395b2fc0893451169d68bEvan Cheng if (UserBB == DefBB) continue; 1025f9785f92b630e69262c395b2fc0893451169d68bEvan Cheng // Be conservative. We don't want this xform to end up introducing 1026f9785f92b630e69262c395b2fc0893451169d68bEvan Cheng // reloads just before load / store instructions. 1027f9785f92b630e69262c395b2fc0893451169d68bEvan Cheng if (isa<PHINode>(User) || isa<LoadInst>(User) || isa<StoreInst>(User)) 1028765dff258545f019502023045b471443ff9ef6c4Evan Cheng return false; 1029765dff258545f019502023045b471443ff9ef6c4Evan Cheng } 1030765dff258545f019502023045b471443ff9ef6c4Evan Cheng 1031bdcb726fcad1e3fddc70847a2b91d4d4f9396938Evan Cheng // InsertedTruncs - Only insert one trunc in each block once. 1032bdcb726fcad1e3fddc70847a2b91d4d4f9396938Evan Cheng DenseMap<BasicBlock*, Instruction*> InsertedTruncs; 1033bdcb726fcad1e3fddc70847a2b91d4d4f9396938Evan Cheng 1034bdcb726fcad1e3fddc70847a2b91d4d4f9396938Evan Cheng bool MadeChange = false; 1035692bf6b85e0eaed549cd47d67289ab7b28e32651Eric Christopher for (Value::use_iterator UI = Src->use_begin(), E = Src->use_end(); 1036bdcb726fcad1e3fddc70847a2b91d4d4f9396938Evan Cheng UI != E; ++UI) { 1037bdcb726fcad1e3fddc70847a2b91d4d4f9396938Evan Cheng Use &TheUse = UI.getUse(); 1038bdcb726fcad1e3fddc70847a2b91d4d4f9396938Evan Cheng Instruction *User = cast<Instruction>(*UI); 1039bdcb726fcad1e3fddc70847a2b91d4d4f9396938Evan Cheng 1040bdcb726fcad1e3fddc70847a2b91d4d4f9396938Evan Cheng // Figure out which BB this ext is used in. 1041bdcb726fcad1e3fddc70847a2b91d4d4f9396938Evan Cheng BasicBlock *UserBB = User->getParent(); 1042bdcb726fcad1e3fddc70847a2b91d4d4f9396938Evan Cheng if (UserBB == DefBB) continue; 1043bdcb726fcad1e3fddc70847a2b91d4d4f9396938Evan Cheng 1044bdcb726fcad1e3fddc70847a2b91d4d4f9396938Evan Cheng // Both src and def are live in this block. Rewrite the use. 1045bdcb726fcad1e3fddc70847a2b91d4d4f9396938Evan Cheng Instruction *&InsertedTrunc = InsertedTruncs[UserBB]; 1046bdcb726fcad1e3fddc70847a2b91d4d4f9396938Evan Cheng 1047bdcb726fcad1e3fddc70847a2b91d4d4f9396938Evan Cheng if (!InsertedTrunc) { 10485b6f42f57e730c2d968c313a27fa505a3c3e5efaBill Wendling BasicBlock::iterator InsertPt = UserBB->getFirstInsertionPt(); 1049bdcb726fcad1e3fddc70847a2b91d4d4f9396938Evan Cheng InsertedTrunc = new TruncInst(I, Src->getType(), "", InsertPt); 1050bdcb726fcad1e3fddc70847a2b91d4d4f9396938Evan Cheng } 1051bdcb726fcad1e3fddc70847a2b91d4d4f9396938Evan Cheng 1052bdcb726fcad1e3fddc70847a2b91d4d4f9396938Evan Cheng // Replace a use of the {s|z}ext source with a use of the result. 1053bdcb726fcad1e3fddc70847a2b91d4d4f9396938Evan Cheng TheUse = InsertedTrunc; 105431ff1333e0651192212cee6e090df2ff57d19b53Cameron Zwarich ++NumExtUses; 1055bdcb726fcad1e3fddc70847a2b91d4d4f9396938Evan Cheng MadeChange = true; 1056bdcb726fcad1e3fddc70847a2b91d4d4f9396938Evan Cheng } 1057bdcb726fcad1e3fddc70847a2b91d4d4f9396938Evan Cheng 1058bdcb726fcad1e3fddc70847a2b91d4d4f9396938Evan Cheng return MadeChange; 1059bdcb726fcad1e3fddc70847a2b91d4d4f9396938Evan Cheng} 1060bdcb726fcad1e3fddc70847a2b91d4d4f9396938Evan Cheng 1061c061101e03ef6d2ca550f8fe71594a5e1c02e348Cameron Zwarichbool CodeGenPrepare::OptimizeInst(Instruction *I) { 1062c061101e03ef6d2ca550f8fe71594a5e1c02e348Cameron Zwarich if (PHINode *P = dyn_cast<PHINode>(I)) { 1063c061101e03ef6d2ca550f8fe71594a5e1c02e348Cameron Zwarich // It is possible for very late stage optimizations (such as SimplifyCFG) 1064c061101e03ef6d2ca550f8fe71594a5e1c02e348Cameron Zwarich // to introduce PHI nodes too late to be cleaned up. If we detect such a 1065c061101e03ef6d2ca550f8fe71594a5e1c02e348Cameron Zwarich // trivial PHI, go ahead and zap it here. 1066c061101e03ef6d2ca550f8fe71594a5e1c02e348Cameron Zwarich if (Value *V = SimplifyInstruction(P)) { 1067c061101e03ef6d2ca550f8fe71594a5e1c02e348Cameron Zwarich P->replaceAllUsesWith(V); 1068c061101e03ef6d2ca550f8fe71594a5e1c02e348Cameron Zwarich P->eraseFromParent(); 1069c061101e03ef6d2ca550f8fe71594a5e1c02e348Cameron Zwarich ++NumPHIsElim; 10701a8943a1f872a47b821fe7075f07b42403fa1a3fChris Lattner return true; 1071c061101e03ef6d2ca550f8fe71594a5e1c02e348Cameron Zwarich } 10721a8943a1f872a47b821fe7075f07b42403fa1a3fChris Lattner return false; 10731a8943a1f872a47b821fe7075f07b42403fa1a3fChris Lattner } 10741a8943a1f872a47b821fe7075f07b42403fa1a3fChris Lattner 10751a8943a1f872a47b821fe7075f07b42403fa1a3fChris Lattner if (CastInst *CI = dyn_cast<CastInst>(I)) { 1076c061101e03ef6d2ca550f8fe71594a5e1c02e348Cameron Zwarich // If the source of the cast is a constant, then this should have 1077c061101e03ef6d2ca550f8fe71594a5e1c02e348Cameron Zwarich // already been constant folded. The only reason NOT to constant fold 1078c061101e03ef6d2ca550f8fe71594a5e1c02e348Cameron Zwarich // it is if something (e.g. LSR) was careful to place the constant 1079c061101e03ef6d2ca550f8fe71594a5e1c02e348Cameron Zwarich // evaluation in a block other than then one that uses it (e.g. to hoist 1080c061101e03ef6d2ca550f8fe71594a5e1c02e348Cameron Zwarich // the address of globals out of a loop). If this is the case, we don't 1081c061101e03ef6d2ca550f8fe71594a5e1c02e348Cameron Zwarich // want to forward-subst the cast. 1082c061101e03ef6d2ca550f8fe71594a5e1c02e348Cameron Zwarich if (isa<Constant>(CI->getOperand(0))) 1083c061101e03ef6d2ca550f8fe71594a5e1c02e348Cameron Zwarich return false; 1084c061101e03ef6d2ca550f8fe71594a5e1c02e348Cameron Zwarich 10851a8943a1f872a47b821fe7075f07b42403fa1a3fChris Lattner if (TLI && OptimizeNoopCopyExpression(CI, *TLI)) 10861a8943a1f872a47b821fe7075f07b42403fa1a3fChris Lattner return true; 1087c061101e03ef6d2ca550f8fe71594a5e1c02e348Cameron Zwarich 10881a8943a1f872a47b821fe7075f07b42403fa1a3fChris Lattner if (isa<ZExtInst>(I) || isa<SExtInst>(I)) { 10891a8943a1f872a47b821fe7075f07b42403fa1a3fChris Lattner bool MadeChange = MoveExtToFormExtLoad(I); 10901a8943a1f872a47b821fe7075f07b42403fa1a3fChris Lattner return MadeChange | OptimizeExtUses(I); 1091c061101e03ef6d2ca550f8fe71594a5e1c02e348Cameron Zwarich } 10921a8943a1f872a47b821fe7075f07b42403fa1a3fChris Lattner return false; 10931a8943a1f872a47b821fe7075f07b42403fa1a3fChris Lattner } 10941a8943a1f872a47b821fe7075f07b42403fa1a3fChris Lattner 10951a8943a1f872a47b821fe7075f07b42403fa1a3fChris Lattner if (CmpInst *CI = dyn_cast<CmpInst>(I)) 10961a8943a1f872a47b821fe7075f07b42403fa1a3fChris Lattner return OptimizeCmpExpression(CI); 10971a8943a1f872a47b821fe7075f07b42403fa1a3fChris Lattner 10981a8943a1f872a47b821fe7075f07b42403fa1a3fChris Lattner if (LoadInst *LI = dyn_cast<LoadInst>(I)) { 1099c061101e03ef6d2ca550f8fe71594a5e1c02e348Cameron Zwarich if (TLI) 11001a8943a1f872a47b821fe7075f07b42403fa1a3fChris Lattner return OptimizeMemoryInst(I, I->getOperand(0), LI->getType()); 11011a8943a1f872a47b821fe7075f07b42403fa1a3fChris Lattner return false; 11021a8943a1f872a47b821fe7075f07b42403fa1a3fChris Lattner } 11031a8943a1f872a47b821fe7075f07b42403fa1a3fChris Lattner 11041a8943a1f872a47b821fe7075f07b42403fa1a3fChris Lattner if (StoreInst *SI = dyn_cast<StoreInst>(I)) { 1105c061101e03ef6d2ca550f8fe71594a5e1c02e348Cameron Zwarich if (TLI) 11061a8943a1f872a47b821fe7075f07b42403fa1a3fChris Lattner return OptimizeMemoryInst(I, SI->getOperand(1), 11071a8943a1f872a47b821fe7075f07b42403fa1a3fChris Lattner SI->getOperand(0)->getType()); 11081a8943a1f872a47b821fe7075f07b42403fa1a3fChris Lattner return false; 11091a8943a1f872a47b821fe7075f07b42403fa1a3fChris Lattner } 11101a8943a1f872a47b821fe7075f07b42403fa1a3fChris Lattner 11111a8943a1f872a47b821fe7075f07b42403fa1a3fChris Lattner if (GetElementPtrInst *GEPI = dyn_cast<GetElementPtrInst>(I)) { 1112865ae1a9e77920e07c4a6a992736109c2cd4fe02Cameron Zwarich if (GEPI->hasAllZeroIndices()) { 1113865ae1a9e77920e07c4a6a992736109c2cd4fe02Cameron Zwarich /// The GEP operand must be a pointer, so must its result -> BitCast 1114865ae1a9e77920e07c4a6a992736109c2cd4fe02Cameron Zwarich Instruction *NC = new BitCastInst(GEPI->getOperand(0), GEPI->getType(), 1115865ae1a9e77920e07c4a6a992736109c2cd4fe02Cameron Zwarich GEPI->getName(), GEPI); 1116865ae1a9e77920e07c4a6a992736109c2cd4fe02Cameron Zwarich GEPI->replaceAllUsesWith(NC); 1117865ae1a9e77920e07c4a6a992736109c2cd4fe02Cameron Zwarich GEPI->eraseFromParent(); 1118865ae1a9e77920e07c4a6a992736109c2cd4fe02Cameron Zwarich ++NumGEPsElim; 1119865ae1a9e77920e07c4a6a992736109c2cd4fe02Cameron Zwarich OptimizeInst(NC); 11201a8943a1f872a47b821fe7075f07b42403fa1a3fChris Lattner return true; 1121865ae1a9e77920e07c4a6a992736109c2cd4fe02Cameron Zwarich } 11221a8943a1f872a47b821fe7075f07b42403fa1a3fChris Lattner return false; 1123c061101e03ef6d2ca550f8fe71594a5e1c02e348Cameron Zwarich } 11241a8943a1f872a47b821fe7075f07b42403fa1a3fChris Lattner 11251a8943a1f872a47b821fe7075f07b42403fa1a3fChris Lattner if (CallInst *CI = dyn_cast<CallInst>(I)) 11261a8943a1f872a47b821fe7075f07b42403fa1a3fChris Lattner return OptimizeCallInst(CI); 1127c061101e03ef6d2ca550f8fe71594a5e1c02e348Cameron Zwarich 1128485fafc8406db8552ba5e3ff871a6ee32694ad90Evan Cheng if (ReturnInst *RI = dyn_cast<ReturnInst>(I)) 1129485fafc8406db8552ba5e3ff871a6ee32694ad90Evan Cheng return DupRetToEnableTailCallOpts(RI); 1130485fafc8406db8552ba5e3ff871a6ee32694ad90Evan Cheng 11311a8943a1f872a47b821fe7075f07b42403fa1a3fChris Lattner return false; 1132c061101e03ef6d2ca550f8fe71594a5e1c02e348Cameron Zwarich} 1133c061101e03ef6d2ca550f8fe71594a5e1c02e348Cameron Zwarich 1134dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner// In this pass we look for GEP and cast instructions that are used 1135dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner// across basic blocks and rewrite them to improve basic-block-at-a-time 1136dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner// selection. 1137dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattnerbool CodeGenPrepare::OptimizeBlock(BasicBlock &BB) { 11388c3527e7a475dd3369a485a4f610d56f7005b7b5Cameron Zwarich SunkAddrs.clear(); 113956e3793acf8099eafa36154d2b6c900d46b5965eCameron Zwarich bool MadeChange = false; 1140692bf6b85e0eaed549cd47d67289ab7b28e32651Eric Christopher 11417579609bfe0d915b6c2d8dc094a132d793ec8855Chris Lattner CurInstIterator = BB.begin(); 114294e8e0cfbe13cdbdf7addc6e36df863cab92e4c9Chris Lattner for (BasicBlock::iterator E = BB.end(); CurInstIterator != E; ) 114394e8e0cfbe13cdbdf7addc6e36df863cab92e4c9Chris Lattner MadeChange |= OptimizeInst(CurInstIterator++); 1144692bf6b85e0eaed549cd47d67289ab7b28e32651Eric Christopher 1145dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner return MadeChange; 1146dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner} 1147f56ea610ed63db0b8a8a9aca95222aa78ce293eeDevang Patel 1148f56ea610ed63db0b8a8a9aca95222aa78ce293eeDevang Patel// llvm.dbg.value is far away from the value then iSel may not be able 1149f56ea610ed63db0b8a8a9aca95222aa78ce293eeDevang Patel// handle it properly. iSel will drop llvm.dbg.value if it can not 1150f56ea610ed63db0b8a8a9aca95222aa78ce293eeDevang Patel// find a node corresponding to the value. 1151f56ea610ed63db0b8a8a9aca95222aa78ce293eeDevang Patelbool CodeGenPrepare::PlaceDbgValues(Function &F) { 1152f56ea610ed63db0b8a8a9aca95222aa78ce293eeDevang Patel bool MadeChange = false; 1153f56ea610ed63db0b8a8a9aca95222aa78ce293eeDevang Patel for (Function::iterator I = F.begin(), E = F.end(); I != E; ++I) { 1154f56ea610ed63db0b8a8a9aca95222aa78ce293eeDevang Patel Instruction *PrevNonDbgInst = NULL; 1155f56ea610ed63db0b8a8a9aca95222aa78ce293eeDevang Patel for (BasicBlock::iterator BI = I->begin(), BE = I->end(); BI != BE;) { 1156f56ea610ed63db0b8a8a9aca95222aa78ce293eeDevang Patel Instruction *Insn = BI; ++BI; 1157f56ea610ed63db0b8a8a9aca95222aa78ce293eeDevang Patel DbgValueInst *DVI = dyn_cast<DbgValueInst>(Insn); 1158f56ea610ed63db0b8a8a9aca95222aa78ce293eeDevang Patel if (!DVI) { 1159f56ea610ed63db0b8a8a9aca95222aa78ce293eeDevang Patel PrevNonDbgInst = Insn; 1160f56ea610ed63db0b8a8a9aca95222aa78ce293eeDevang Patel continue; 1161f56ea610ed63db0b8a8a9aca95222aa78ce293eeDevang Patel } 1162f56ea610ed63db0b8a8a9aca95222aa78ce293eeDevang Patel 1163f56ea610ed63db0b8a8a9aca95222aa78ce293eeDevang Patel Instruction *VI = dyn_cast_or_null<Instruction>(DVI->getValue()); 1164f56ea610ed63db0b8a8a9aca95222aa78ce293eeDevang Patel if (VI && VI != PrevNonDbgInst && !VI->isTerminator()) { 1165f56ea610ed63db0b8a8a9aca95222aa78ce293eeDevang Patel DEBUG(dbgs() << "Moving Debug Value before :\n" << *DVI << ' ' << *VI); 1166f56ea610ed63db0b8a8a9aca95222aa78ce293eeDevang Patel DVI->removeFromParent(); 1167f56ea610ed63db0b8a8a9aca95222aa78ce293eeDevang Patel if (isa<PHINode>(VI)) 1168f56ea610ed63db0b8a8a9aca95222aa78ce293eeDevang Patel DVI->insertBefore(VI->getParent()->getFirstInsertionPt()); 1169f56ea610ed63db0b8a8a9aca95222aa78ce293eeDevang Patel else 1170f56ea610ed63db0b8a8a9aca95222aa78ce293eeDevang Patel DVI->insertAfter(VI); 1171f56ea610ed63db0b8a8a9aca95222aa78ce293eeDevang Patel MadeChange = true; 1172f56ea610ed63db0b8a8a9aca95222aa78ce293eeDevang Patel ++NumDbgValueMoved; 1173f56ea610ed63db0b8a8a9aca95222aa78ce293eeDevang Patel } 1174f56ea610ed63db0b8a8a9aca95222aa78ce293eeDevang Patel } 1175f56ea610ed63db0b8a8a9aca95222aa78ce293eeDevang Patel } 1176f56ea610ed63db0b8a8a9aca95222aa78ce293eeDevang Patel return MadeChange; 1177f56ea610ed63db0b8a8a9aca95222aa78ce293eeDevang Patel} 1178