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" 29618c1dbd293d15ee19f61b1156ab8086ad28311aChad Rosier#include "llvm/Target/TargetLibraryInfo.h" 30dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner#include "llvm/Target/TargetLowering.h" 31a1fd5b386dd8eb4c86bfd2b9659c219a1c4f56dbEvan Cheng#include "llvm/Transforms/Utils/AddrModeMatcher.h" 32dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner#include "llvm/Transforms/Utils/BasicBlockUtils.h" 33dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner#include "llvm/Transforms/Utils/Local.h" 34040056fd11693ffc41ce9b777281c71705d0dc1fEric Christopher#include "llvm/Transforms/Utils/BuildLibCalls.h" 35dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner#include "llvm/ADT/DenseMap.h" 36dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner#include "llvm/ADT/SmallSet.h" 377eb589d3f9294dbfe4d5205045bd8119a9666532Jakob Stoklund Olesen#include "llvm/ADT/Statistic.h" 3803ce042d70c423a41edca0714112a0e06b16493bDan Gohman#include "llvm/Assembly/Writer.h" 399bf12b5583104c810cfadcdce91edf9efad79973Evan Cheng#include "llvm/Support/CallSite.h" 40e1bcb440dc0ca3c41fda1c0c581abfc4f38ca170Evan Cheng#include "llvm/Support/CommandLine.h" 41bdcb726fcad1e3fddc70847a2b91d4d4f9396938Evan Cheng#include "llvm/Support/Debug.h" 42dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner#include "llvm/Support/GetElementPtrTypeIterator.h" 43088a1e84ea985a22efcf907d7789064fee3a97b9Chris Lattner#include "llvm/Support/PatternMatch.h" 446c1980b3357207c4d756255bc5e32323eac278dcDan Gohman#include "llvm/Support/raw_ostream.h" 45040056fd11693ffc41ce9b777281c71705d0dc1fEric Christopher#include "llvm/Support/IRBuilder.h" 4694e8e0cfbe13cdbdf7addc6e36df863cab92e4c9Chris Lattner#include "llvm/Support/ValueHandle.h" 47dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattnerusing namespace llvm; 48088a1e84ea985a22efcf907d7789064fee3a97b9Chris Lattnerusing namespace llvm::PatternMatch; 49dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner 5031ff1333e0651192212cee6e090df2ff57d19b53Cameron ZwarichSTATISTIC(NumBlocksElim, "Number of blocks eliminated"); 51485fafc8406db8552ba5e3ff871a6ee32694ad90Evan ChengSTATISTIC(NumPHIsElim, "Number of trivial PHIs eliminated"); 52485fafc8406db8552ba5e3ff871a6ee32694ad90Evan ChengSTATISTIC(NumGEPsElim, "Number of GEPs converted to casts"); 5331ff1333e0651192212cee6e090df2ff57d19b53Cameron ZwarichSTATISTIC(NumCmpUses, "Number of uses of Cmp expressions replaced with uses of " 5431ff1333e0651192212cee6e090df2ff57d19b53Cameron Zwarich "sunken Cmps"); 5531ff1333e0651192212cee6e090df2ff57d19b53Cameron ZwarichSTATISTIC(NumCastUses, "Number of uses of Cast expressions replaced with uses " 5631ff1333e0651192212cee6e090df2ff57d19b53Cameron Zwarich "of sunken Casts"); 5731ff1333e0651192212cee6e090df2ff57d19b53Cameron ZwarichSTATISTIC(NumMemoryInsts, "Number of memory instructions whose address " 5831ff1333e0651192212cee6e090df2ff57d19b53Cameron Zwarich "computations were sunk"); 59485fafc8406db8552ba5e3ff871a6ee32694ad90Evan ChengSTATISTIC(NumExtsMoved, "Number of [s|z]ext instructions combined with loads"); 60485fafc8406db8552ba5e3ff871a6ee32694ad90Evan ChengSTATISTIC(NumExtUses, "Number of uses of [s|z]ext instructions optimized"); 61485fafc8406db8552ba5e3ff871a6ee32694ad90Evan ChengSTATISTIC(NumRetsDup, "Number of return instructions duplicated"); 62f56ea610ed63db0b8a8a9aca95222aa78ce293eeDevang PatelSTATISTIC(NumDbgValueMoved, "Number of debug value instructions moved"); 637eb589d3f9294dbfe4d5205045bd8119a9666532Jakob Stoklund Olesen 64899eaa35696bb0a9a625acd70a14876834af6cc5Cameron Zwarichstatic cl::opt<bool> DisableBranchOpts( 65899eaa35696bb0a9a625acd70a14876834af6cc5Cameron Zwarich "disable-cgp-branch-opts", cl::Hidden, cl::init(false), 66899eaa35696bb0a9a625acd70a14876834af6cc5Cameron Zwarich cl::desc("Disable branch optimizations in CodeGenPrepare")); 67899eaa35696bb0a9a625acd70a14876834af6cc5Cameron Zwarich 68e3e394d982a2bd2bc37edb1f8c3492d0382e37a9Bill Wendling// FIXME: Remove this abomination once all of the tests pass without it! 69e3e394d982a2bd2bc37edb1f8c3492d0382e37a9Bill Wendlingstatic cl::opt<bool> DisableDeleteDeadBlocks( 70e3e394d982a2bd2bc37edb1f8c3492d0382e37a9Bill Wendling "disable-cgp-delete-dead-blocks", cl::Hidden, cl::init(false), 71e3e394d982a2bd2bc37edb1f8c3492d0382e37a9Bill Wendling cl::desc("Disable deleting dead blocks in CodeGenPrepare")); 72e3e394d982a2bd2bc37edb1f8c3492d0382e37a9Bill Wendling 73692bf6b85e0eaed549cd47d67289ab7b28e32651Eric Christophernamespace { 743e8b6631e67e01e4960a7ba4668a50c596607473Chris Lattner class CodeGenPrepare : public FunctionPass { 75dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner /// TLI - Keep a pointer of a TargetLowering to consult for determining 76dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner /// transformation profitability. 77dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner const TargetLowering *TLI; 78618c1dbd293d15ee19f61b1156ab8086ad28311aChad Rosier const TargetLibraryInfo *TLInfo; 7980f6a507d4e11ba066ad0e53e12ad25ad8cf07baCameron Zwarich DominatorTree *DT; 8004149f7ffd033773adfe85e4acf3f560e29bd47dEvan Cheng ProfileInfo *PFI; 817579609bfe0d915b6c2d8dc094a132d793ec8855Chris Lattner 827579609bfe0d915b6c2d8dc094a132d793ec8855Chris Lattner /// CurInstIterator - As we scan instructions optimizing them, this is the 837579609bfe0d915b6c2d8dc094a132d793ec8855Chris Lattner /// next instruction to optimize. Xforms that can invalidate this should 847579609bfe0d915b6c2d8dc094a132d793ec8855Chris Lattner /// update it. 857579609bfe0d915b6c2d8dc094a132d793ec8855Chris Lattner BasicBlock::iterator CurInstIterator; 86ab63152871f4144050d0a58d592a95e089fe40d4Evan Cheng 87485fafc8406db8552ba5e3ff871a6ee32694ad90Evan Cheng /// Keeps track of non-local addresses that have been sunk into a block. 88485fafc8406db8552ba5e3ff871a6ee32694ad90Evan Cheng /// This allows us to avoid inserting duplicate code for blocks with 89485fafc8406db8552ba5e3ff871a6ee32694ad90Evan Cheng /// multiple load/stores of the same address. 908c3527e7a475dd3369a485a4f610d56f7005b7b5Cameron Zwarich DenseMap<Value*, Value*> SunkAddrs; 918c3527e7a475dd3369a485a4f610d56f7005b7b5Cameron Zwarich 9252e37df8c05eb73e40421f0703c0d89fe854ffeaDevang Patel /// ModifiedDT - If CFG is modified in anyway, dominator tree may need to 93485fafc8406db8552ba5e3ff871a6ee32694ad90Evan Cheng /// be updated. 9452e37df8c05eb73e40421f0703c0d89fe854ffeaDevang Patel bool ModifiedDT; 95485fafc8406db8552ba5e3ff871a6ee32694ad90Evan Cheng 96dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner public: 97ecd94c804a563f2a86572dcf1d2e81f397e19daaNick Lewycky static char ID; // Pass identification, replacement for typeid 98c2bbfc18e9adbbdcf5b3375d8d25e2452f7df7f1Dan Gohman explicit CodeGenPrepare(const TargetLowering *tli = 0) 99081c34b725980f995be9080eaec24cd3dfaaf065Owen Anderson : FunctionPass(ID), TLI(tli) { 100081c34b725980f995be9080eaec24cd3dfaaf065Owen Anderson initializeCodeGenPreparePass(*PassRegistry::getPassRegistry()); 101081c34b725980f995be9080eaec24cd3dfaaf065Owen Anderson } 102dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner bool runOnFunction(Function &F); 103692bf6b85e0eaed549cd47d67289ab7b28e32651Eric Christopher 104ad80981a106c9d0ec83351e63ee3ac75ed646bf4Andreas Neustifter virtual void getAnalysisUsage(AnalysisUsage &AU) const { 10580f6a507d4e11ba066ad0e53e12ad25ad8cf07baCameron Zwarich AU.addPreserved<DominatorTree>(); 106ad80981a106c9d0ec83351e63ee3ac75ed646bf4Andreas Neustifter AU.addPreserved<ProfileInfo>(); 107618c1dbd293d15ee19f61b1156ab8086ad28311aChad Rosier AU.addRequired<TargetLibraryInfo>(); 108ad80981a106c9d0ec83351e63ee3ac75ed646bf4Andreas Neustifter } 109ad80981a106c9d0ec83351e63ee3ac75ed646bf4Andreas Neustifter 110dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner private: 111d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner bool EliminateMostlyEmptyBlocks(Function &F); 112d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner bool CanMergeBlocks(const BasicBlock *BB, const BasicBlock *DestBB) const; 113d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner void EliminateMostlyEmptyBlock(BasicBlock *BB); 114dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner bool OptimizeBlock(BasicBlock &BB); 115c061101e03ef6d2ca550f8fe71594a5e1c02e348Cameron Zwarich bool OptimizeInst(Instruction *I); 116db125cfaf57cc83e7dd7453de2d509bc8efd0e5eChris Lattner bool OptimizeMemoryInst(Instruction *I, Value *Addr, Type *AccessTy); 1177579609bfe0d915b6c2d8dc094a132d793ec8855Chris Lattner bool OptimizeInlineAsmInst(CallInst *CS); 118040056fd11693ffc41ce9b777281c71705d0dc1fEric Christopher bool OptimizeCallInst(CallInst *CI); 119b00f236b03ea57520f94823780896ebdbc5d8bdcDan Gohman bool MoveExtToFormExtLoad(Instruction *I); 120bdcb726fcad1e3fddc70847a2b91d4d4f9396938Evan Cheng bool OptimizeExtUses(Instruction *I); 121485fafc8406db8552ba5e3ff871a6ee32694ad90Evan Cheng bool DupRetToEnableTailCallOpts(ReturnInst *RI); 122f56ea610ed63db0b8a8a9aca95222aa78ce293eeDevang Patel bool PlaceDbgValues(Function &F); 123dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner }; 124dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner} 125794fd75c67a2cdc128d67342c6d88a504d186896Devang Patel 1261997473cf72957d0e70322e2fe6fe2ab141c58a6Devang Patelchar CodeGenPrepare::ID = 0; 127618c1dbd293d15ee19f61b1156ab8086ad28311aChad RosierINITIALIZE_PASS_BEGIN(CodeGenPrepare, "codegenprepare", 128618c1dbd293d15ee19f61b1156ab8086ad28311aChad Rosier "Optimize for code generation", false, false) 129618c1dbd293d15ee19f61b1156ab8086ad28311aChad RosierINITIALIZE_PASS_DEPENDENCY(TargetLibraryInfo) 130618c1dbd293d15ee19f61b1156ab8086ad28311aChad RosierINITIALIZE_PASS_END(CodeGenPrepare, "codegenprepare", 131ce665bd2e2b581ab0858d1afe359192bac96b868Owen Anderson "Optimize for code generation", false, false) 132dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner 133dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris LattnerFunctionPass *llvm::createCodeGenPreparePass(const TargetLowering *TLI) { 134dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner return new CodeGenPrepare(TLI); 135dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner} 136dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner 137dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattnerbool CodeGenPrepare::runOnFunction(Function &F) { 138dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner bool EverMadeChange = false; 139692bf6b85e0eaed549cd47d67289ab7b28e32651Eric Christopher 14052e37df8c05eb73e40421f0703c0d89fe854ffeaDevang Patel ModifiedDT = false; 141618c1dbd293d15ee19f61b1156ab8086ad28311aChad Rosier TLInfo = &getAnalysis<TargetLibraryInfo>(); 14280f6a507d4e11ba066ad0e53e12ad25ad8cf07baCameron Zwarich DT = getAnalysisIfAvailable<DominatorTree>(); 14304149f7ffd033773adfe85e4acf3f560e29bd47dEvan Cheng PFI = getAnalysisIfAvailable<ProfileInfo>(); 144485fafc8406db8552ba5e3ff871a6ee32694ad90Evan Cheng 145d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner // First pass, eliminate blocks that contain only PHI nodes and an 146d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner // unconditional branch. 147d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner EverMadeChange |= EliminateMostlyEmptyBlocks(F); 148692bf6b85e0eaed549cd47d67289ab7b28e32651Eric Christopher 149f56ea610ed63db0b8a8a9aca95222aa78ce293eeDevang Patel // llvm.dbg.value is far away from the value then iSel may not be able 150f56ea610ed63db0b8a8a9aca95222aa78ce293eeDevang Patel // handle it properly. iSel will drop llvm.dbg.value if it can not 151f56ea610ed63db0b8a8a9aca95222aa78ce293eeDevang Patel // find a node corresponding to the value. 152f56ea610ed63db0b8a8a9aca95222aa78ce293eeDevang Patel EverMadeChange |= PlaceDbgValues(F); 153f56ea610ed63db0b8a8a9aca95222aa78ce293eeDevang Patel 154d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner bool MadeChange = true; 155dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner while (MadeChange) { 156dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner MadeChange = false; 157485fafc8406db8552ba5e3ff871a6ee32694ad90Evan Cheng for (Function::iterator I = F.begin(), E = F.end(); I != E; ) { 158485fafc8406db8552ba5e3ff871a6ee32694ad90Evan Cheng BasicBlock *BB = I++; 159dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner MadeChange |= OptimizeBlock(*BB); 160485fafc8406db8552ba5e3ff871a6ee32694ad90Evan Cheng } 161dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner EverMadeChange |= MadeChange; 162dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner } 1638c3527e7a475dd3369a485a4f610d56f7005b7b5Cameron Zwarich 1648c3527e7a475dd3369a485a4f610d56f7005b7b5Cameron Zwarich SunkAddrs.clear(); 1658c3527e7a475dd3369a485a4f610d56f7005b7b5Cameron Zwarich 166899eaa35696bb0a9a625acd70a14876834af6cc5Cameron Zwarich if (!DisableBranchOpts) { 167899eaa35696bb0a9a625acd70a14876834af6cc5Cameron Zwarich MadeChange = false; 168e3e394d982a2bd2bc37edb1f8c3492d0382e37a9Bill Wendling SmallPtrSet<BasicBlock*, 8> WorkList; 169e3e394d982a2bd2bc37edb1f8c3492d0382e37a9Bill Wendling for (Function::iterator BB = F.begin(), E = F.end(); BB != E; ++BB) { 170e3e394d982a2bd2bc37edb1f8c3492d0382e37a9Bill Wendling SmallVector<BasicBlock*, 2> Successors(succ_begin(BB), succ_end(BB)); 1715649ba70fb39f2fda4791d255ae8bb373071874fFrits van Bommel MadeChange |= ConstantFoldTerminator(BB, true); 172e3e394d982a2bd2bc37edb1f8c3492d0382e37a9Bill Wendling if (!MadeChange) continue; 173e3e394d982a2bd2bc37edb1f8c3492d0382e37a9Bill Wendling 174e3e394d982a2bd2bc37edb1f8c3492d0382e37a9Bill Wendling for (SmallVectorImpl<BasicBlock*>::iterator 175e3e394d982a2bd2bc37edb1f8c3492d0382e37a9Bill Wendling II = Successors.begin(), IE = Successors.end(); II != IE; ++II) 176e3e394d982a2bd2bc37edb1f8c3492d0382e37a9Bill Wendling if (pred_begin(*II) == pred_end(*II)) 177e3e394d982a2bd2bc37edb1f8c3492d0382e37a9Bill Wendling WorkList.insert(*II); 178e3e394d982a2bd2bc37edb1f8c3492d0382e37a9Bill Wendling } 179e3e394d982a2bd2bc37edb1f8c3492d0382e37a9Bill Wendling 180e3e394d982a2bd2bc37edb1f8c3492d0382e37a9Bill Wendling if (!DisableDeleteDeadBlocks) 181e3e394d982a2bd2bc37edb1f8c3492d0382e37a9Bill Wendling for (SmallPtrSet<BasicBlock*, 8>::iterator 182e3e394d982a2bd2bc37edb1f8c3492d0382e37a9Bill Wendling I = WorkList.begin(), E = WorkList.end(); I != E; ++I) 183e3e394d982a2bd2bc37edb1f8c3492d0382e37a9Bill Wendling DeleteDeadBlock(*I); 184899eaa35696bb0a9a625acd70a14876834af6cc5Cameron Zwarich 185485fafc8406db8552ba5e3ff871a6ee32694ad90Evan Cheng if (MadeChange) 18652e37df8c05eb73e40421f0703c0d89fe854ffeaDevang Patel ModifiedDT = true; 187899eaa35696bb0a9a625acd70a14876834af6cc5Cameron Zwarich EverMadeChange |= MadeChange; 188899eaa35696bb0a9a625acd70a14876834af6cc5Cameron Zwarich } 189899eaa35696bb0a9a625acd70a14876834af6cc5Cameron Zwarich 19052e37df8c05eb73e40421f0703c0d89fe854ffeaDevang Patel if (ModifiedDT && DT) 191485fafc8406db8552ba5e3ff871a6ee32694ad90Evan Cheng DT->DT->recalculate(F); 192485fafc8406db8552ba5e3ff871a6ee32694ad90Evan Cheng 193dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner return EverMadeChange; 194dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner} 195dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner 1962d69724938e67ec248e0ba42f86287923b3a5171Dale Johannesen/// EliminateMostlyEmptyBlocks - eliminate blocks that contain only PHI nodes, 1972d69724938e67ec248e0ba42f86287923b3a5171Dale Johannesen/// debug info directives, and an unconditional branch. Passes before isel 1982d69724938e67ec248e0ba42f86287923b3a5171Dale Johannesen/// (e.g. LSR/loopsimplify) often split edges in ways that are non-optimal for 1992d69724938e67ec248e0ba42f86287923b3a5171Dale Johannesen/// isel. Start by eliminating these blocks so we can split them the way we 2002d69724938e67ec248e0ba42f86287923b3a5171Dale Johannesen/// want them. 201d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattnerbool CodeGenPrepare::EliminateMostlyEmptyBlocks(Function &F) { 202d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner bool MadeChange = false; 203d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner // Note that this intentionally skips the entry block. 204d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner for (Function::iterator I = ++F.begin(), E = F.end(); I != E; ) { 205d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner BasicBlock *BB = I++; 206d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner 207d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner // If this block doesn't end with an uncond branch, ignore it. 208d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner BranchInst *BI = dyn_cast<BranchInst>(BB->getTerminator()); 209d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner if (!BI || !BI->isUnconditional()) 210d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner continue; 211692bf6b85e0eaed549cd47d67289ab7b28e32651Eric Christopher 2122d69724938e67ec248e0ba42f86287923b3a5171Dale Johannesen // If the instruction before the branch (skipping debug info) isn't a phi 2132d69724938e67ec248e0ba42f86287923b3a5171Dale Johannesen // node, then other stuff is happening here. 214d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner BasicBlock::iterator BBI = BI; 215d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner if (BBI != BB->begin()) { 216d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner --BBI; 2172d69724938e67ec248e0ba42f86287923b3a5171Dale Johannesen while (isa<DbgInfoIntrinsic>(BBI)) { 2182d69724938e67ec248e0ba42f86287923b3a5171Dale Johannesen if (BBI == BB->begin()) 2192d69724938e67ec248e0ba42f86287923b3a5171Dale Johannesen break; 2202d69724938e67ec248e0ba42f86287923b3a5171Dale Johannesen --BBI; 2212d69724938e67ec248e0ba42f86287923b3a5171Dale Johannesen } 2222d69724938e67ec248e0ba42f86287923b3a5171Dale Johannesen if (!isa<DbgInfoIntrinsic>(BBI) && !isa<PHINode>(BBI)) 2232d69724938e67ec248e0ba42f86287923b3a5171Dale Johannesen continue; 224d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner } 225692bf6b85e0eaed549cd47d67289ab7b28e32651Eric Christopher 226d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner // Do not break infinite loops. 227d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner BasicBlock *DestBB = BI->getSuccessor(0); 228d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner if (DestBB == BB) 229d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner continue; 230692bf6b85e0eaed549cd47d67289ab7b28e32651Eric Christopher 231d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner if (!CanMergeBlocks(BB, DestBB)) 232d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner continue; 233692bf6b85e0eaed549cd47d67289ab7b28e32651Eric Christopher 234d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner EliminateMostlyEmptyBlock(BB); 235d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner MadeChange = true; 236d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner } 237d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner return MadeChange; 238d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner} 239d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner 240d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner/// CanMergeBlocks - Return true if we can merge BB into DestBB if there is a 241d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner/// single uncond branch between them, and BB contains no other non-phi 242d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner/// instructions. 243d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattnerbool CodeGenPrepare::CanMergeBlocks(const BasicBlock *BB, 244d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner const BasicBlock *DestBB) const { 245d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner // We only want to eliminate blocks whose phi nodes are used by phi nodes in 246d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner // the successor. If there are more complex condition (e.g. preheaders), 247d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner // don't mess around with them. 248d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner BasicBlock::const_iterator BBI = BB->begin(); 249d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner while (const PHINode *PN = dyn_cast<PHINode>(BBI++)) { 25060ad781c61815ca5b8dc2a45a102e1c8af65992fGabor Greif for (Value::const_use_iterator UI = PN->use_begin(), E = PN->use_end(); 251d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner UI != E; ++UI) { 252d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner const Instruction *User = cast<Instruction>(*UI); 253d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner if (User->getParent() != DestBB || !isa<PHINode>(User)) 254d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner return false; 255692bf6b85e0eaed549cd47d67289ab7b28e32651Eric Christopher // If User is inside DestBB block and it is a PHINode then check 256692bf6b85e0eaed549cd47d67289ab7b28e32651Eric Christopher // incoming value. If incoming value is not from BB then this is 25775abc1ed0618048c3cf6c5b71c9868c10d6c1478Devang Patel // a complex condition (e.g. preheaders) we want to avoid here. 25875abc1ed0618048c3cf6c5b71c9868c10d6c1478Devang Patel if (User->getParent() == DestBB) { 25975abc1ed0618048c3cf6c5b71c9868c10d6c1478Devang Patel if (const PHINode *UPN = dyn_cast<PHINode>(User)) 26075abc1ed0618048c3cf6c5b71c9868c10d6c1478Devang Patel for (unsigned I = 0, E = UPN->getNumIncomingValues(); I != E; ++I) { 26175abc1ed0618048c3cf6c5b71c9868c10d6c1478Devang Patel Instruction *Insn = dyn_cast<Instruction>(UPN->getIncomingValue(I)); 26275abc1ed0618048c3cf6c5b71c9868c10d6c1478Devang Patel if (Insn && Insn->getParent() == BB && 26375abc1ed0618048c3cf6c5b71c9868c10d6c1478Devang Patel Insn->getParent() != UPN->getIncomingBlock(I)) 26475abc1ed0618048c3cf6c5b71c9868c10d6c1478Devang Patel return false; 26575abc1ed0618048c3cf6c5b71c9868c10d6c1478Devang Patel } 26675abc1ed0618048c3cf6c5b71c9868c10d6c1478Devang Patel } 267d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner } 268d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner } 269692bf6b85e0eaed549cd47d67289ab7b28e32651Eric Christopher 270d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner // If BB and DestBB contain any common predecessors, then the phi nodes in BB 271d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner // and DestBB may have conflicting incoming values for the block. If so, we 272d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner // can't merge the block. 273d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner const PHINode *DestBBPN = dyn_cast<PHINode>(DestBB->begin()); 274d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner if (!DestBBPN) return true; // no conflict. 275692bf6b85e0eaed549cd47d67289ab7b28e32651Eric Christopher 276d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner // Collect the preds of BB. 277f67f73a519eac94b6c1f98dbce7d251a3a4aea07Chris Lattner SmallPtrSet<const BasicBlock*, 16> BBPreds; 278d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner if (const PHINode *BBPN = dyn_cast<PHINode>(BB->begin())) { 279d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner // It is faster to get preds from a PHI than with pred_iterator. 280d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner for (unsigned i = 0, e = BBPN->getNumIncomingValues(); i != e; ++i) 281d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner BBPreds.insert(BBPN->getIncomingBlock(i)); 282d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner } else { 283d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner BBPreds.insert(pred_begin(BB), pred_end(BB)); 284d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner } 285692bf6b85e0eaed549cd47d67289ab7b28e32651Eric Christopher 286d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner // Walk the preds of DestBB. 287d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner for (unsigned i = 0, e = DestBBPN->getNumIncomingValues(); i != e; ++i) { 288d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner BasicBlock *Pred = DestBBPN->getIncomingBlock(i); 289d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner if (BBPreds.count(Pred)) { // Common predecessor? 290d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner BBI = DestBB->begin(); 291d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner while (const PHINode *PN = dyn_cast<PHINode>(BBI++)) { 292d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner const Value *V1 = PN->getIncomingValueForBlock(Pred); 293d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner const Value *V2 = PN->getIncomingValueForBlock(BB); 294692bf6b85e0eaed549cd47d67289ab7b28e32651Eric Christopher 295d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner // If V2 is a phi node in BB, look up what the mapped value will be. 296d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner if (const PHINode *V2PN = dyn_cast<PHINode>(V2)) 297d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner if (V2PN->getParent() == BB) 298d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner V2 = V2PN->getIncomingValueForBlock(Pred); 299692bf6b85e0eaed549cd47d67289ab7b28e32651Eric Christopher 300d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner // If there is a conflict, bail out. 301d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner if (V1 != V2) return false; 302d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner } 303d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner } 304d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner } 305d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner 306d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner return true; 307d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner} 308d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner 309d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner 310d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner/// EliminateMostlyEmptyBlock - Eliminate a basic block that have only phi's and 311d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner/// an unconditional branch in it. 312d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattnervoid CodeGenPrepare::EliminateMostlyEmptyBlock(BasicBlock *BB) { 313d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner BranchInst *BI = cast<BranchInst>(BB->getTerminator()); 314d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner BasicBlock *DestBB = BI->getSuccessor(0); 315692bf6b85e0eaed549cd47d67289ab7b28e32651Eric Christopher 31668d67fdf203ff2d5b0eeb925befd0866bce3aceeDavid Greene DEBUG(dbgs() << "MERGING MOSTLY EMPTY BLOCKS - BEFORE:\n" << *BB << *DestBB); 317692bf6b85e0eaed549cd47d67289ab7b28e32651Eric Christopher 318d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner // If the destination block has a single pred, then this is a trivial edge, 319d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner // just collapse it. 3209918fb5631974f2201a640384b7ebe672c749e43Chris Lattner if (BasicBlock *SinglePred = DestBB->getSinglePredecessor()) { 321f5102a0f088e7c96f7028bf7ca1c24975c314fffChris Lattner if (SinglePred != DestBB) { 322f5102a0f088e7c96f7028bf7ca1c24975c314fffChris Lattner // Remember if SinglePred was the entry block of the function. If so, we 323f5102a0f088e7c96f7028bf7ca1c24975c314fffChris Lattner // will need to move BB back to the entry position. 324f5102a0f088e7c96f7028bf7ca1c24975c314fffChris Lattner bool isEntry = SinglePred == &SinglePred->getParent()->getEntryBlock(); 325ad80981a106c9d0ec83351e63ee3ac75ed646bf4Andreas Neustifter MergeBasicBlockIntoOnlyPred(DestBB, this); 326f5102a0f088e7c96f7028bf7ca1c24975c314fffChris Lattner 327f5102a0f088e7c96f7028bf7ca1c24975c314fffChris Lattner if (isEntry && BB != &BB->getParent()->getEntryBlock()) 328f5102a0f088e7c96f7028bf7ca1c24975c314fffChris Lattner BB->moveBefore(&BB->getParent()->getEntryBlock()); 329f5102a0f088e7c96f7028bf7ca1c24975c314fffChris Lattner 33068d67fdf203ff2d5b0eeb925befd0866bce3aceeDavid Greene DEBUG(dbgs() << "AFTER:\n" << *DestBB << "\n\n\n"); 331f5102a0f088e7c96f7028bf7ca1c24975c314fffChris Lattner return; 332f5102a0f088e7c96f7028bf7ca1c24975c314fffChris Lattner } 333d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner } 334692bf6b85e0eaed549cd47d67289ab7b28e32651Eric Christopher 335d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner // Otherwise, we have multiple predecessors of BB. Update the PHIs in DestBB 336d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner // to handle the new incoming edges it is about to have. 337d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner PHINode *PN; 338d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner for (BasicBlock::iterator BBI = DestBB->begin(); 339d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner (PN = dyn_cast<PHINode>(BBI)); ++BBI) { 340d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner // Remove the incoming value for BB, and remember it. 341d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner Value *InVal = PN->removeIncomingValue(BB, false); 342692bf6b85e0eaed549cd47d67289ab7b28e32651Eric Christopher 343d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner // Two options: either the InVal is a phi node defined in BB or it is some 344d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner // value that dominates BB. 345d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner PHINode *InValPhi = dyn_cast<PHINode>(InVal); 346d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner if (InValPhi && InValPhi->getParent() == BB) { 347d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner // Add all of the input values of the input PHI as inputs of this phi. 348d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner for (unsigned i = 0, e = InValPhi->getNumIncomingValues(); i != e; ++i) 349d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner PN->addIncoming(InValPhi->getIncomingValue(i), 350d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner InValPhi->getIncomingBlock(i)); 351d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner } else { 352d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner // Otherwise, add one instance of the dominating value for each edge that 353d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner // we will be adding. 354d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner if (PHINode *BBPN = dyn_cast<PHINode>(BB->begin())) { 355d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner for (unsigned i = 0, e = BBPN->getNumIncomingValues(); i != e; ++i) 356d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner PN->addIncoming(InVal, BBPN->getIncomingBlock(i)); 357d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner } else { 358d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner for (pred_iterator PI = pred_begin(BB), E = pred_end(BB); PI != E; ++PI) 359d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner PN->addIncoming(InVal, *PI); 360d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner } 361d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner } 362d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner } 363692bf6b85e0eaed549cd47d67289ab7b28e32651Eric Christopher 364d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner // The PHIs are now updated, change everything that refers to BB to use 365d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner // DestBB and remove BB. 366d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner BB->replaceAllUsesWith(DestBB); 36752e37df8c05eb73e40421f0703c0d89fe854ffeaDevang Patel if (DT && !ModifiedDT) { 36880f6a507d4e11ba066ad0e53e12ad25ad8cf07baCameron Zwarich BasicBlock *BBIDom = DT->getNode(BB)->getIDom()->getBlock(); 36980f6a507d4e11ba066ad0e53e12ad25ad8cf07baCameron Zwarich BasicBlock *DestBBIDom = DT->getNode(DestBB)->getIDom()->getBlock(); 37080f6a507d4e11ba066ad0e53e12ad25ad8cf07baCameron Zwarich BasicBlock *NewIDom = DT->findNearestCommonDominator(BBIDom, DestBBIDom); 37180f6a507d4e11ba066ad0e53e12ad25ad8cf07baCameron Zwarich DT->changeImmediateDominator(DestBB, NewIDom); 37280f6a507d4e11ba066ad0e53e12ad25ad8cf07baCameron Zwarich DT->eraseNode(BB); 37380f6a507d4e11ba066ad0e53e12ad25ad8cf07baCameron Zwarich } 37404149f7ffd033773adfe85e4acf3f560e29bd47dEvan Cheng if (PFI) { 37504149f7ffd033773adfe85e4acf3f560e29bd47dEvan Cheng PFI->replaceAllUses(BB, DestBB); 37604149f7ffd033773adfe85e4acf3f560e29bd47dEvan Cheng PFI->removeEdge(ProfileInfo::getEdge(BB, DestBB)); 377ad80981a106c9d0ec83351e63ee3ac75ed646bf4Andreas Neustifter } 378d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner BB->eraseFromParent(); 37931ff1333e0651192212cee6e090df2ff57d19b53Cameron Zwarich ++NumBlocksElim; 380692bf6b85e0eaed549cd47d67289ab7b28e32651Eric Christopher 38168d67fdf203ff2d5b0eeb925befd0866bce3aceeDavid Greene DEBUG(dbgs() << "AFTER:\n" << *DestBB << "\n\n\n"); 382d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner} 383d9c3a0d7cce72ac802516483c4a325b3b31bbc0eChris Lattner 384dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner/// OptimizeNoopCopyExpression - If the specified cast instruction is a noop 385a119de86a064414622562cfe32953de7f9b0ee40Dan Gohman/// copy (e.g. it's casting from one pointer type to another, i32->i8 on PPC), 386a119de86a064414622562cfe32953de7f9b0ee40Dan Gohman/// sink it into user blocks to reduce the number of virtual 387ce0b23721e434789f9600c0fd13f0ca17444264fDale Johannesen/// registers that must be created and coalesced. 388dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner/// 389dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner/// Return true if any changes are made. 39085fa13c02d383bb87dd9b8b9081a4d34a3e9c52cChris Lattner/// 391dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattnerstatic bool OptimizeNoopCopyExpression(CastInst *CI, const TargetLowering &TLI){ 392692bf6b85e0eaed549cd47d67289ab7b28e32651Eric Christopher // If this is a noop copy, 393e50ed30282bb5b4a9ed952580523f2dda16215acOwen Anderson EVT SrcVT = TLI.getValueType(CI->getOperand(0)->getType()); 394e50ed30282bb5b4a9ed952580523f2dda16215acOwen Anderson EVT DstVT = TLI.getValueType(CI->getType()); 395692bf6b85e0eaed549cd47d67289ab7b28e32651Eric Christopher 396dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner // This is an fp<->int conversion? 39783ec4b6711980242ef3c55a4fa36b2d7a39c1bfbDuncan Sands if (SrcVT.isInteger() != DstVT.isInteger()) 398dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner return false; 3998e4eb09b1e3571965f49edcdfb56b1375b1b7551Duncan Sands 400dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner // If this is an extension, it will be a zero or sign extension, which 401dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner // isn't a noop. 4028e4eb09b1e3571965f49edcdfb56b1375b1b7551Duncan Sands if (SrcVT.bitsLT(DstVT)) return false; 403692bf6b85e0eaed549cd47d67289ab7b28e32651Eric Christopher 404dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner // If these values will be promoted, find out what they will be promoted 405dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner // to. This helps us consider truncates on PPC as noop copies when they 406dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner // are. 4070ccc12ae8bab69d4ec8e265fff1865db9553137fNadav Rotem if (TLI.getTypeAction(CI->getContext(), SrcVT) == 4080ccc12ae8bab69d4ec8e265fff1865db9553137fNadav Rotem TargetLowering::TypePromoteInteger) 40923b9b19b1a5a00faa9fce0788155c7dbfd00bfb1Owen Anderson SrcVT = TLI.getTypeToTransformTo(CI->getContext(), SrcVT); 4100ccc12ae8bab69d4ec8e265fff1865db9553137fNadav Rotem if (TLI.getTypeAction(CI->getContext(), DstVT) == 4110ccc12ae8bab69d4ec8e265fff1865db9553137fNadav Rotem TargetLowering::TypePromoteInteger) 41223b9b19b1a5a00faa9fce0788155c7dbfd00bfb1Owen Anderson DstVT = TLI.getTypeToTransformTo(CI->getContext(), DstVT); 413692bf6b85e0eaed549cd47d67289ab7b28e32651Eric Christopher 414dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner // If, after promotion, these are the same types, this is a noop copy. 415dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner if (SrcVT != DstVT) 416dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner return false; 417692bf6b85e0eaed549cd47d67289ab7b28e32651Eric Christopher 418dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner BasicBlock *DefBB = CI->getParent(); 419692bf6b85e0eaed549cd47d67289ab7b28e32651Eric Christopher 420dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner /// InsertedCasts - Only insert a cast in each block once. 421ce0b23721e434789f9600c0fd13f0ca17444264fDale Johannesen DenseMap<BasicBlock*, CastInst*> InsertedCasts; 422692bf6b85e0eaed549cd47d67289ab7b28e32651Eric Christopher 423dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner bool MadeChange = false; 424692bf6b85e0eaed549cd47d67289ab7b28e32651Eric Christopher for (Value::use_iterator UI = CI->use_begin(), E = CI->use_end(); 425dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner UI != E; ) { 426dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner Use &TheUse = UI.getUse(); 427dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner Instruction *User = cast<Instruction>(*UI); 428692bf6b85e0eaed549cd47d67289ab7b28e32651Eric Christopher 429dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner // Figure out which BB this cast is used in. For PHI's this is the 430dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner // appropriate predecessor block. 431dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner BasicBlock *UserBB = User->getParent(); 432dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner if (PHINode *PN = dyn_cast<PHINode>(User)) { 433a36791da41cf4f635e50077b290676b873836bdaGabor Greif UserBB = PN->getIncomingBlock(UI); 434dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner } 435692bf6b85e0eaed549cd47d67289ab7b28e32651Eric Christopher 436dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner // Preincrement use iterator so we don't invalidate it. 437dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner ++UI; 438692bf6b85e0eaed549cd47d67289ab7b28e32651Eric Christopher 439dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner // If this user is in the same block as the cast, don't change the cast. 440dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner if (UserBB == DefBB) continue; 441692bf6b85e0eaed549cd47d67289ab7b28e32651Eric Christopher 442dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner // If we have already inserted a cast into this block, use it. 443dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner CastInst *&InsertedCast = InsertedCasts[UserBB]; 444dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner 445dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner if (!InsertedCast) { 4465b6f42f57e730c2d968c313a27fa505a3c3e5efaBill Wendling BasicBlock::iterator InsertPt = UserBB->getFirstInsertionPt(); 447692bf6b85e0eaed549cd47d67289ab7b28e32651Eric Christopher InsertedCast = 448692bf6b85e0eaed549cd47d67289ab7b28e32651Eric Christopher CastInst::Create(CI->getOpcode(), CI->getOperand(0), CI->getType(), "", 449dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner InsertPt); 450dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner MadeChange = true; 451dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner } 452692bf6b85e0eaed549cd47d67289ab7b28e32651Eric Christopher 453ce0b23721e434789f9600c0fd13f0ca17444264fDale Johannesen // Replace a use of the cast with a use of the new cast. 454dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner TheUse = InsertedCast; 45531ff1333e0651192212cee6e090df2ff57d19b53Cameron Zwarich ++NumCastUses; 456dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner } 457692bf6b85e0eaed549cd47d67289ab7b28e32651Eric Christopher 458dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner // If we removed all uses, nuke the cast. 459e003813e9613f41ff2c6a10cb1d3ae3a5b8eab1fDuncan Sands if (CI->use_empty()) { 460dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner CI->eraseFromParent(); 461e003813e9613f41ff2c6a10cb1d3ae3a5b8eab1fDuncan Sands MadeChange = true; 462e003813e9613f41ff2c6a10cb1d3ae3a5b8eab1fDuncan Sands } 463692bf6b85e0eaed549cd47d67289ab7b28e32651Eric Christopher 464dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner return MadeChange; 465dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner} 466dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner 467692bf6b85e0eaed549cd47d67289ab7b28e32651Eric Christopher/// OptimizeCmpExpression - sink the given CmpInst into user blocks to reduce 468ce0b23721e434789f9600c0fd13f0ca17444264fDale Johannesen/// the number of virtual registers that must be created and coalesced. This is 469684b22df79c51114a12289e10a4063d5f02259a9Chris Lattner/// a clear win except on targets with multiple condition code registers 470684b22df79c51114a12289e10a4063d5f02259a9Chris Lattner/// (PowerPC), where it might lose; some adjustment may be wanted there. 471ce0b23721e434789f9600c0fd13f0ca17444264fDale Johannesen/// 472ce0b23721e434789f9600c0fd13f0ca17444264fDale Johannesen/// Return true if any changes are made. 47385fa13c02d383bb87dd9b8b9081a4d34a3e9c52cChris Lattnerstatic bool OptimizeCmpExpression(CmpInst *CI) { 474ce0b23721e434789f9600c0fd13f0ca17444264fDale Johannesen BasicBlock *DefBB = CI->getParent(); 475692bf6b85e0eaed549cd47d67289ab7b28e32651Eric Christopher 476ce0b23721e434789f9600c0fd13f0ca17444264fDale Johannesen /// InsertedCmp - Only insert a cmp in each block once. 477ce0b23721e434789f9600c0fd13f0ca17444264fDale Johannesen DenseMap<BasicBlock*, CmpInst*> InsertedCmps; 478692bf6b85e0eaed549cd47d67289ab7b28e32651Eric Christopher 479ce0b23721e434789f9600c0fd13f0ca17444264fDale Johannesen bool MadeChange = false; 480692bf6b85e0eaed549cd47d67289ab7b28e32651Eric Christopher for (Value::use_iterator UI = CI->use_begin(), E = CI->use_end(); 481ce0b23721e434789f9600c0fd13f0ca17444264fDale Johannesen UI != E; ) { 482ce0b23721e434789f9600c0fd13f0ca17444264fDale Johannesen Use &TheUse = UI.getUse(); 483ce0b23721e434789f9600c0fd13f0ca17444264fDale Johannesen Instruction *User = cast<Instruction>(*UI); 484692bf6b85e0eaed549cd47d67289ab7b28e32651Eric Christopher 485ce0b23721e434789f9600c0fd13f0ca17444264fDale Johannesen // Preincrement use iterator so we don't invalidate it. 486ce0b23721e434789f9600c0fd13f0ca17444264fDale Johannesen ++UI; 487692bf6b85e0eaed549cd47d67289ab7b28e32651Eric Christopher 488ce0b23721e434789f9600c0fd13f0ca17444264fDale Johannesen // Don't bother for PHI nodes. 489ce0b23721e434789f9600c0fd13f0ca17444264fDale Johannesen if (isa<PHINode>(User)) 490ce0b23721e434789f9600c0fd13f0ca17444264fDale Johannesen continue; 491ce0b23721e434789f9600c0fd13f0ca17444264fDale Johannesen 492ce0b23721e434789f9600c0fd13f0ca17444264fDale Johannesen // Figure out which BB this cmp is used in. 493ce0b23721e434789f9600c0fd13f0ca17444264fDale Johannesen BasicBlock *UserBB = User->getParent(); 494692bf6b85e0eaed549cd47d67289ab7b28e32651Eric Christopher 495ce0b23721e434789f9600c0fd13f0ca17444264fDale Johannesen // If this user is in the same block as the cmp, don't change the cmp. 496ce0b23721e434789f9600c0fd13f0ca17444264fDale Johannesen if (UserBB == DefBB) continue; 497692bf6b85e0eaed549cd47d67289ab7b28e32651Eric Christopher 498ce0b23721e434789f9600c0fd13f0ca17444264fDale Johannesen // If we have already inserted a cmp into this block, use it. 499ce0b23721e434789f9600c0fd13f0ca17444264fDale Johannesen CmpInst *&InsertedCmp = InsertedCmps[UserBB]; 500ce0b23721e434789f9600c0fd13f0ca17444264fDale Johannesen 501ce0b23721e434789f9600c0fd13f0ca17444264fDale Johannesen if (!InsertedCmp) { 5025b6f42f57e730c2d968c313a27fa505a3c3e5efaBill Wendling BasicBlock::iterator InsertPt = UserBB->getFirstInsertionPt(); 503692bf6b85e0eaed549cd47d67289ab7b28e32651Eric Christopher InsertedCmp = 5041c8a23c440b1665ba422778cdc74a0c59ecaf39eDan Gohman CmpInst::Create(CI->getOpcode(), 505333c40096561218bc3597cf153c0a3895274414cOwen Anderson CI->getPredicate(), CI->getOperand(0), 506ce0b23721e434789f9600c0fd13f0ca17444264fDale Johannesen CI->getOperand(1), "", InsertPt); 507ce0b23721e434789f9600c0fd13f0ca17444264fDale Johannesen MadeChange = true; 508ce0b23721e434789f9600c0fd13f0ca17444264fDale Johannesen } 509692bf6b85e0eaed549cd47d67289ab7b28e32651Eric Christopher 510ce0b23721e434789f9600c0fd13f0ca17444264fDale Johannesen // Replace a use of the cmp with a use of the new cmp. 511ce0b23721e434789f9600c0fd13f0ca17444264fDale Johannesen TheUse = InsertedCmp; 51231ff1333e0651192212cee6e090df2ff57d19b53Cameron Zwarich ++NumCmpUses; 513ce0b23721e434789f9600c0fd13f0ca17444264fDale Johannesen } 514692bf6b85e0eaed549cd47d67289ab7b28e32651Eric Christopher 515ce0b23721e434789f9600c0fd13f0ca17444264fDale Johannesen // If we removed all uses, nuke the cmp. 516ce0b23721e434789f9600c0fd13f0ca17444264fDale Johannesen if (CI->use_empty()) 517ce0b23721e434789f9600c0fd13f0ca17444264fDale Johannesen CI->eraseFromParent(); 518692bf6b85e0eaed549cd47d67289ab7b28e32651Eric Christopher 519ce0b23721e434789f9600c0fd13f0ca17444264fDale Johannesen return MadeChange; 520ce0b23721e434789f9600c0fd13f0ca17444264fDale Johannesen} 521ce0b23721e434789f9600c0fd13f0ca17444264fDale Johannesen 5220b6cb507385c8bd10b6a51b5e45a9b99d8d94798Benjamin Kramernamespace { 5230b6cb507385c8bd10b6a51b5e45a9b99d8d94798Benjamin Kramerclass CodeGenPrepareFortifiedLibCalls : public SimplifyFortifiedLibCalls { 5240b6cb507385c8bd10b6a51b5e45a9b99d8d94798Benjamin Kramerprotected: 5250b6cb507385c8bd10b6a51b5e45a9b99d8d94798Benjamin Kramer void replaceCall(Value *With) { 5260b6cb507385c8bd10b6a51b5e45a9b99d8d94798Benjamin Kramer CI->replaceAllUsesWith(With); 5270b6cb507385c8bd10b6a51b5e45a9b99d8d94798Benjamin Kramer CI->eraseFromParent(); 5280b6cb507385c8bd10b6a51b5e45a9b99d8d94798Benjamin Kramer } 5290b6cb507385c8bd10b6a51b5e45a9b99d8d94798Benjamin Kramer bool isFoldable(unsigned SizeCIOp, unsigned, bool) const { 530a6aac4c5bc22bb10c7adb11eee3f82c703af7002Gabor Greif if (ConstantInt *SizeCI = 531a6aac4c5bc22bb10c7adb11eee3f82c703af7002Gabor Greif dyn_cast<ConstantInt>(CI->getArgOperand(SizeCIOp))) 532a6aac4c5bc22bb10c7adb11eee3f82c703af7002Gabor Greif return SizeCI->isAllOnesValue(); 5330b6cb507385c8bd10b6a51b5e45a9b99d8d94798Benjamin Kramer return false; 5340b6cb507385c8bd10b6a51b5e45a9b99d8d94798Benjamin Kramer } 5350b6cb507385c8bd10b6a51b5e45a9b99d8d94798Benjamin Kramer}; 5360b6cb507385c8bd10b6a51b5e45a9b99d8d94798Benjamin Kramer} // end anonymous namespace 5370b6cb507385c8bd10b6a51b5e45a9b99d8d94798Benjamin Kramer 538040056fd11693ffc41ce9b777281c71705d0dc1fEric Christopherbool CodeGenPrepare::OptimizeCallInst(CallInst *CI) { 5397579609bfe0d915b6c2d8dc094a132d793ec8855Chris Lattner BasicBlock *BB = CI->getParent(); 5407579609bfe0d915b6c2d8dc094a132d793ec8855Chris Lattner 5417579609bfe0d915b6c2d8dc094a132d793ec8855Chris Lattner // Lower inline assembly if we can. 5427579609bfe0d915b6c2d8dc094a132d793ec8855Chris Lattner // If we found an inline asm expession, and if the target knows how to 5437579609bfe0d915b6c2d8dc094a132d793ec8855Chris Lattner // lower it to normal LLVM code, do so now. 5447579609bfe0d915b6c2d8dc094a132d793ec8855Chris Lattner if (TLI && isa<InlineAsm>(CI->getCalledValue())) { 5457579609bfe0d915b6c2d8dc094a132d793ec8855Chris Lattner if (TLI->ExpandInlineAsm(CI)) { 5467579609bfe0d915b6c2d8dc094a132d793ec8855Chris Lattner // Avoid invalidating the iterator. 5477579609bfe0d915b6c2d8dc094a132d793ec8855Chris Lattner CurInstIterator = BB->begin(); 5487579609bfe0d915b6c2d8dc094a132d793ec8855Chris Lattner // Avoid processing instructions out of order, which could cause 5497579609bfe0d915b6c2d8dc094a132d793ec8855Chris Lattner // reuse before a value is defined. 5507579609bfe0d915b6c2d8dc094a132d793ec8855Chris Lattner SunkAddrs.clear(); 5517579609bfe0d915b6c2d8dc094a132d793ec8855Chris Lattner return true; 5527579609bfe0d915b6c2d8dc094a132d793ec8855Chris Lattner } 5537579609bfe0d915b6c2d8dc094a132d793ec8855Chris Lattner // Sink address computing for memory operands into the block. 5547579609bfe0d915b6c2d8dc094a132d793ec8855Chris Lattner if (OptimizeInlineAsmInst(CI)) 5557579609bfe0d915b6c2d8dc094a132d793ec8855Chris Lattner return true; 5567579609bfe0d915b6c2d8dc094a132d793ec8855Chris Lattner } 5577579609bfe0d915b6c2d8dc094a132d793ec8855Chris Lattner 558040056fd11693ffc41ce9b777281c71705d0dc1fEric Christopher // Lower all uses of llvm.objectsize.* 559040056fd11693ffc41ce9b777281c71705d0dc1fEric Christopher IntrinsicInst *II = dyn_cast<IntrinsicInst>(CI); 560040056fd11693ffc41ce9b777281c71705d0dc1fEric Christopher if (II && II->getIntrinsicID() == Intrinsic::objectsize) { 561de9f5452d3ae894bb7fdd455cec5af50e2560aa5Gabor Greif bool Min = (cast<ConstantInt>(II->getArgOperand(1))->getZExtValue() == 1); 562db125cfaf57cc83e7dd7453de2d509bc8efd0e5eChris Lattner Type *ReturnTy = CI->getType(); 563040056fd11693ffc41ce9b777281c71705d0dc1fEric Christopher Constant *RetVal = ConstantInt::get(ReturnTy, Min ? 0 : -1ULL); 56494e8e0cfbe13cdbdf7addc6e36df863cab92e4c9Chris Lattner 56594e8e0cfbe13cdbdf7addc6e36df863cab92e4c9Chris Lattner // Substituting this can cause recursive simplifications, which can 56694e8e0cfbe13cdbdf7addc6e36df863cab92e4c9Chris Lattner // invalidate our iterator. Use a WeakVH to hold onto it in case this 56794e8e0cfbe13cdbdf7addc6e36df863cab92e4c9Chris Lattner // happens. 56894e8e0cfbe13cdbdf7addc6e36df863cab92e4c9Chris Lattner WeakVH IterHandle(CurInstIterator); 56994e8e0cfbe13cdbdf7addc6e36df863cab92e4c9Chris Lattner 5706b980541df5846ad335c377c8803b517968daee2Chandler Carruth replaceAndRecursivelySimplify(CI, RetVal, TLI ? TLI->getTargetData() : 0, 5716b980541df5846ad335c377c8803b517968daee2Chandler Carruth TLInfo, ModifiedDT ? 0 : DT); 57294e8e0cfbe13cdbdf7addc6e36df863cab92e4c9Chris Lattner 57394e8e0cfbe13cdbdf7addc6e36df863cab92e4c9Chris Lattner // If the iterator instruction was recursively deleted, start over at the 57494e8e0cfbe13cdbdf7addc6e36df863cab92e4c9Chris Lattner // start of the block. 575435b4d2eba723e9513453f20885244ad1d16e0d4Chris Lattner if (IterHandle != CurInstIterator) { 57694e8e0cfbe13cdbdf7addc6e36df863cab92e4c9Chris Lattner CurInstIterator = BB->begin(); 577435b4d2eba723e9513453f20885244ad1d16e0d4Chris Lattner SunkAddrs.clear(); 578435b4d2eba723e9513453f20885244ad1d16e0d4Chris Lattner } 579040056fd11693ffc41ce9b777281c71705d0dc1fEric Christopher return true; 580040056fd11693ffc41ce9b777281c71705d0dc1fEric Christopher } 581040056fd11693ffc41ce9b777281c71705d0dc1fEric Christopher 582f210b68b41704cb602feffa4ebb334220abda407Pete Cooper if (II && TLI) { 583f210b68b41704cb602feffa4ebb334220abda407Pete Cooper SmallVector<Value*, 2> PtrOps; 584f210b68b41704cb602feffa4ebb334220abda407Pete Cooper Type *AccessTy; 585f210b68b41704cb602feffa4ebb334220abda407Pete Cooper if (TLI->GetAddrModeArguments(II, PtrOps, AccessTy)) 586f210b68b41704cb602feffa4ebb334220abda407Pete Cooper while (!PtrOps.empty()) 587f210b68b41704cb602feffa4ebb334220abda407Pete Cooper if (OptimizeMemoryInst(II, PtrOps.pop_back_val(), AccessTy)) 588f210b68b41704cb602feffa4ebb334220abda407Pete Cooper return true; 589f210b68b41704cb602feffa4ebb334220abda407Pete Cooper } 590f210b68b41704cb602feffa4ebb334220abda407Pete Cooper 591040056fd11693ffc41ce9b777281c71705d0dc1fEric Christopher // From here on out we're working with named functions. 592040056fd11693ffc41ce9b777281c71705d0dc1fEric Christopher if (CI->getCalledFunction() == 0) return false; 59397de92c08d675e5ee5be2e1ebec64cbff86c17f4Devang Patel 594040056fd11693ffc41ce9b777281c71705d0dc1fEric Christopher // We'll need TargetData from here on out. 595040056fd11693ffc41ce9b777281c71705d0dc1fEric Christopher const TargetData *TD = TLI ? TLI->getTargetData() : 0; 596040056fd11693ffc41ce9b777281c71705d0dc1fEric Christopher if (!TD) return false; 597040056fd11693ffc41ce9b777281c71705d0dc1fEric Christopher 5980b6cb507385c8bd10b6a51b5e45a9b99d8d94798Benjamin Kramer // Lower all default uses of _chk calls. This is very similar 5990b6cb507385c8bd10b6a51b5e45a9b99d8d94798Benjamin Kramer // to what InstCombineCalls does, but here we are only lowering calls 600040056fd11693ffc41ce9b777281c71705d0dc1fEric Christopher // that have the default "don't know" as the objectsize. Anything else 601040056fd11693ffc41ce9b777281c71705d0dc1fEric Christopher // should be left alone. 6020b6cb507385c8bd10b6a51b5e45a9b99d8d94798Benjamin Kramer CodeGenPrepareFortifiedLibCalls Simplifier; 6030b6cb507385c8bd10b6a51b5e45a9b99d8d94798Benjamin Kramer return Simplifier.fold(CI, TD); 604040056fd11693ffc41ce9b777281c71705d0dc1fEric Christopher} 60594e8e0cfbe13cdbdf7addc6e36df863cab92e4c9Chris Lattner 606485fafc8406db8552ba5e3ff871a6ee32694ad90Evan Cheng/// DupRetToEnableTailCallOpts - Look for opportunities to duplicate return 607485fafc8406db8552ba5e3ff871a6ee32694ad90Evan Cheng/// instructions to the predecessor to enable tail call optimizations. The 608485fafc8406db8552ba5e3ff871a6ee32694ad90Evan Cheng/// case it is currently looking for is: 609485fafc8406db8552ba5e3ff871a6ee32694ad90Evan Cheng/// bb0: 610485fafc8406db8552ba5e3ff871a6ee32694ad90Evan Cheng/// %tmp0 = tail call i32 @f0() 611485fafc8406db8552ba5e3ff871a6ee32694ad90Evan Cheng/// br label %return 612485fafc8406db8552ba5e3ff871a6ee32694ad90Evan Cheng/// bb1: 613485fafc8406db8552ba5e3ff871a6ee32694ad90Evan Cheng/// %tmp1 = tail call i32 @f1() 614485fafc8406db8552ba5e3ff871a6ee32694ad90Evan Cheng/// br label %return 615485fafc8406db8552ba5e3ff871a6ee32694ad90Evan Cheng/// bb2: 616485fafc8406db8552ba5e3ff871a6ee32694ad90Evan Cheng/// %tmp2 = tail call i32 @f2() 617485fafc8406db8552ba5e3ff871a6ee32694ad90Evan Cheng/// br label %return 618485fafc8406db8552ba5e3ff871a6ee32694ad90Evan Cheng/// return: 619485fafc8406db8552ba5e3ff871a6ee32694ad90Evan Cheng/// %retval = phi i32 [ %tmp0, %bb0 ], [ %tmp1, %bb1 ], [ %tmp2, %bb2 ] 620485fafc8406db8552ba5e3ff871a6ee32694ad90Evan Cheng/// ret i32 %retval 621485fafc8406db8552ba5e3ff871a6ee32694ad90Evan Cheng/// 622485fafc8406db8552ba5e3ff871a6ee32694ad90Evan Cheng/// => 623485fafc8406db8552ba5e3ff871a6ee32694ad90Evan Cheng/// 624485fafc8406db8552ba5e3ff871a6ee32694ad90Evan Cheng/// bb0: 625485fafc8406db8552ba5e3ff871a6ee32694ad90Evan Cheng/// %tmp0 = tail call i32 @f0() 626485fafc8406db8552ba5e3ff871a6ee32694ad90Evan Cheng/// ret i32 %tmp0 627485fafc8406db8552ba5e3ff871a6ee32694ad90Evan Cheng/// bb1: 628485fafc8406db8552ba5e3ff871a6ee32694ad90Evan Cheng/// %tmp1 = tail call i32 @f1() 629485fafc8406db8552ba5e3ff871a6ee32694ad90Evan Cheng/// ret i32 %tmp1 630485fafc8406db8552ba5e3ff871a6ee32694ad90Evan Cheng/// bb2: 631485fafc8406db8552ba5e3ff871a6ee32694ad90Evan Cheng/// %tmp2 = tail call i32 @f2() 632485fafc8406db8552ba5e3ff871a6ee32694ad90Evan Cheng/// ret i32 %tmp2 633485fafc8406db8552ba5e3ff871a6ee32694ad90Evan Cheng/// 634485fafc8406db8552ba5e3ff871a6ee32694ad90Evan Chengbool CodeGenPrepare::DupRetToEnableTailCallOpts(ReturnInst *RI) { 635661a390b830fcdea13ed9daeaf4e6dbd1adcdca6Cameron Zwarich if (!TLI) 636661a390b830fcdea13ed9daeaf4e6dbd1adcdca6Cameron Zwarich return false; 637661a390b830fcdea13ed9daeaf4e6dbd1adcdca6Cameron Zwarich 638485fafc8406db8552ba5e3ff871a6ee32694ad90Evan Cheng Value *V = RI->getReturnValue(); 6396e8ffc1c4d73e6c91aca9ac28ef5859ead26e2b6Cameron Zwarich PHINode *PN = V ? dyn_cast<PHINode>(V) : NULL; 6406e8ffc1c4d73e6c91aca9ac28ef5859ead26e2b6Cameron Zwarich if (V && !PN) 6414bae588c75fbd6d1b8401d83a94ba64fcc381d95Cameron Zwarich return false; 642485fafc8406db8552ba5e3ff871a6ee32694ad90Evan Cheng 6434bae588c75fbd6d1b8401d83a94ba64fcc381d95Cameron Zwarich BasicBlock *BB = RI->getParent(); 6446e8ffc1c4d73e6c91aca9ac28ef5859ead26e2b6Cameron Zwarich if (PN && PN->getParent() != BB) 6454bae588c75fbd6d1b8401d83a94ba64fcc381d95Cameron Zwarich return false; 646485fafc8406db8552ba5e3ff871a6ee32694ad90Evan Cheng 6474bae588c75fbd6d1b8401d83a94ba64fcc381d95Cameron Zwarich // It's not safe to eliminate the sign / zero extension of the return value. 6484bae588c75fbd6d1b8401d83a94ba64fcc381d95Cameron Zwarich // See llvm::isInTailCallPosition(). 6494bae588c75fbd6d1b8401d83a94ba64fcc381d95Cameron Zwarich const Function *F = BB->getParent(); 650164b86b4399559e45fab7846f1e3e09119cab4e2Kostya Serebryany Attributes CallerRetAttr = F->getAttributes().getRetAttributes(); 6514bae588c75fbd6d1b8401d83a94ba64fcc381d95Cameron Zwarich if ((CallerRetAttr & Attribute::ZExt) || (CallerRetAttr & Attribute::SExt)) 6524bae588c75fbd6d1b8401d83a94ba64fcc381d95Cameron Zwarich return false; 653485fafc8406db8552ba5e3ff871a6ee32694ad90Evan Cheng 6546e8ffc1c4d73e6c91aca9ac28ef5859ead26e2b6Cameron Zwarich // Make sure there are no instructions between the PHI and return, or that the 6556e8ffc1c4d73e6c91aca9ac28ef5859ead26e2b6Cameron Zwarich // return is the first instruction in the block. 6566e8ffc1c4d73e6c91aca9ac28ef5859ead26e2b6Cameron Zwarich if (PN) { 6576e8ffc1c4d73e6c91aca9ac28ef5859ead26e2b6Cameron Zwarich BasicBlock::iterator BI = BB->begin(); 6586e8ffc1c4d73e6c91aca9ac28ef5859ead26e2b6Cameron Zwarich do { ++BI; } while (isa<DbgInfoIntrinsic>(BI)); 6596e8ffc1c4d73e6c91aca9ac28ef5859ead26e2b6Cameron Zwarich if (&*BI != RI) 6606e8ffc1c4d73e6c91aca9ac28ef5859ead26e2b6Cameron Zwarich return false; 6616e8ffc1c4d73e6c91aca9ac28ef5859ead26e2b6Cameron Zwarich } else { 662903548420016325db6d22328687f78cd4180facbCameron Zwarich BasicBlock::iterator BI = BB->begin(); 663903548420016325db6d22328687f78cd4180facbCameron Zwarich while (isa<DbgInfoIntrinsic>(BI)) ++BI; 664903548420016325db6d22328687f78cd4180facbCameron Zwarich if (&*BI != RI) 6656e8ffc1c4d73e6c91aca9ac28ef5859ead26e2b6Cameron Zwarich return false; 6666e8ffc1c4d73e6c91aca9ac28ef5859ead26e2b6Cameron Zwarich } 667485fafc8406db8552ba5e3ff871a6ee32694ad90Evan Cheng 6684bae588c75fbd6d1b8401d83a94ba64fcc381d95Cameron Zwarich /// Only dup the ReturnInst if the CallInst is likely to be emitted as a tail 6694bae588c75fbd6d1b8401d83a94ba64fcc381d95Cameron Zwarich /// call. 6704bae588c75fbd6d1b8401d83a94ba64fcc381d95Cameron Zwarich SmallVector<CallInst*, 4> TailCalls; 6716e8ffc1c4d73e6c91aca9ac28ef5859ead26e2b6Cameron Zwarich if (PN) { 6726e8ffc1c4d73e6c91aca9ac28ef5859ead26e2b6Cameron Zwarich for (unsigned I = 0, E = PN->getNumIncomingValues(); I != E; ++I) { 6736e8ffc1c4d73e6c91aca9ac28ef5859ead26e2b6Cameron Zwarich CallInst *CI = dyn_cast<CallInst>(PN->getIncomingValue(I)); 6746e8ffc1c4d73e6c91aca9ac28ef5859ead26e2b6Cameron Zwarich // Make sure the phi value is indeed produced by the tail call. 6756e8ffc1c4d73e6c91aca9ac28ef5859ead26e2b6Cameron Zwarich if (CI && CI->hasOneUse() && CI->getParent() == PN->getIncomingBlock(I) && 6766e8ffc1c4d73e6c91aca9ac28ef5859ead26e2b6Cameron Zwarich TLI->mayBeEmittedAsTailCall(CI)) 6776e8ffc1c4d73e6c91aca9ac28ef5859ead26e2b6Cameron Zwarich TailCalls.push_back(CI); 6786e8ffc1c4d73e6c91aca9ac28ef5859ead26e2b6Cameron Zwarich } 6796e8ffc1c4d73e6c91aca9ac28ef5859ead26e2b6Cameron Zwarich } else { 6806e8ffc1c4d73e6c91aca9ac28ef5859ead26e2b6Cameron Zwarich SmallPtrSet<BasicBlock*, 4> VisitedBBs; 6816e8ffc1c4d73e6c91aca9ac28ef5859ead26e2b6Cameron Zwarich for (pred_iterator PI = pred_begin(BB), PE = pred_end(BB); PI != PE; ++PI) { 6826e8ffc1c4d73e6c91aca9ac28ef5859ead26e2b6Cameron Zwarich if (!VisitedBBs.insert(*PI)) 6836e8ffc1c4d73e6c91aca9ac28ef5859ead26e2b6Cameron Zwarich continue; 6846e8ffc1c4d73e6c91aca9ac28ef5859ead26e2b6Cameron Zwarich 6856e8ffc1c4d73e6c91aca9ac28ef5859ead26e2b6Cameron Zwarich BasicBlock::InstListType &InstList = (*PI)->getInstList(); 6866e8ffc1c4d73e6c91aca9ac28ef5859ead26e2b6Cameron Zwarich BasicBlock::InstListType::reverse_iterator RI = InstList.rbegin(); 6876e8ffc1c4d73e6c91aca9ac28ef5859ead26e2b6Cameron Zwarich BasicBlock::InstListType::reverse_iterator RE = InstList.rend(); 688903548420016325db6d22328687f78cd4180facbCameron Zwarich do { ++RI; } while (RI != RE && isa<DbgInfoIntrinsic>(&*RI)); 689903548420016325db6d22328687f78cd4180facbCameron Zwarich if (RI == RE) 6906e8ffc1c4d73e6c91aca9ac28ef5859ead26e2b6Cameron Zwarich continue; 691903548420016325db6d22328687f78cd4180facbCameron Zwarich 6926e8ffc1c4d73e6c91aca9ac28ef5859ead26e2b6Cameron Zwarich CallInst *CI = dyn_cast<CallInst>(&*RI); 693dc31cfeb74c46fe564a350ffd20880e61d04f286Cameron Zwarich if (CI && CI->use_empty() && TLI->mayBeEmittedAsTailCall(CI)) 6946e8ffc1c4d73e6c91aca9ac28ef5859ead26e2b6Cameron Zwarich TailCalls.push_back(CI); 6956e8ffc1c4d73e6c91aca9ac28ef5859ead26e2b6Cameron Zwarich } 6964bae588c75fbd6d1b8401d83a94ba64fcc381d95Cameron Zwarich } 697485fafc8406db8552ba5e3ff871a6ee32694ad90Evan Cheng 6984bae588c75fbd6d1b8401d83a94ba64fcc381d95Cameron Zwarich bool Changed = false; 6994bae588c75fbd6d1b8401d83a94ba64fcc381d95Cameron Zwarich for (unsigned i = 0, e = TailCalls.size(); i != e; ++i) { 7004bae588c75fbd6d1b8401d83a94ba64fcc381d95Cameron Zwarich CallInst *CI = TailCalls[i]; 7014bae588c75fbd6d1b8401d83a94ba64fcc381d95Cameron Zwarich CallSite CS(CI); 7024bae588c75fbd6d1b8401d83a94ba64fcc381d95Cameron Zwarich 7034bae588c75fbd6d1b8401d83a94ba64fcc381d95Cameron Zwarich // Conservatively require the attributes of the call to match those of the 7044bae588c75fbd6d1b8401d83a94ba64fcc381d95Cameron Zwarich // return. Ignore noalias because it doesn't affect the call sequence. 705164b86b4399559e45fab7846f1e3e09119cab4e2Kostya Serebryany Attributes CalleeRetAttr = CS.getAttributes().getRetAttributes(); 7064bae588c75fbd6d1b8401d83a94ba64fcc381d95Cameron Zwarich if ((CalleeRetAttr ^ CallerRetAttr) & ~Attribute::NoAlias) 7074bae588c75fbd6d1b8401d83a94ba64fcc381d95Cameron Zwarich continue; 708485fafc8406db8552ba5e3ff871a6ee32694ad90Evan Cheng 7094bae588c75fbd6d1b8401d83a94ba64fcc381d95Cameron Zwarich // Make sure the call instruction is followed by an unconditional branch to 7104bae588c75fbd6d1b8401d83a94ba64fcc381d95Cameron Zwarich // the return block. 7114bae588c75fbd6d1b8401d83a94ba64fcc381d95Cameron Zwarich BasicBlock *CallBB = CI->getParent(); 7124bae588c75fbd6d1b8401d83a94ba64fcc381d95Cameron Zwarich BranchInst *BI = dyn_cast<BranchInst>(CallBB->getTerminator()); 7134bae588c75fbd6d1b8401d83a94ba64fcc381d95Cameron Zwarich if (!BI || !BI->isUnconditional() || BI->getSuccessor(0) != BB) 7144bae588c75fbd6d1b8401d83a94ba64fcc381d95Cameron Zwarich continue; 7154bae588c75fbd6d1b8401d83a94ba64fcc381d95Cameron Zwarich 7164bae588c75fbd6d1b8401d83a94ba64fcc381d95Cameron Zwarich // Duplicate the return into CallBB. 7174bae588c75fbd6d1b8401d83a94ba64fcc381d95Cameron Zwarich (void)FoldReturnIntoUncondBranch(RI, BB, CallBB); 71852e37df8c05eb73e40421f0703c0d89fe854ffeaDevang Patel ModifiedDT = Changed = true; 7194bae588c75fbd6d1b8401d83a94ba64fcc381d95Cameron Zwarich ++NumRetsDup; 720485fafc8406db8552ba5e3ff871a6ee32694ad90Evan Cheng } 721485fafc8406db8552ba5e3ff871a6ee32694ad90Evan Cheng 7224bae588c75fbd6d1b8401d83a94ba64fcc381d95Cameron Zwarich // If we eliminated all predecessors of the block, delete the block now. 7234bae588c75fbd6d1b8401d83a94ba64fcc381d95Cameron Zwarich if (Changed && pred_begin(BB) == pred_end(BB)) 7244bae588c75fbd6d1b8401d83a94ba64fcc381d95Cameron Zwarich BB->eraseFromParent(); 7254bae588c75fbd6d1b8401d83a94ba64fcc381d95Cameron Zwarich 7264bae588c75fbd6d1b8401d83a94ba64fcc381d95Cameron Zwarich return Changed; 727485fafc8406db8552ba5e3ff871a6ee32694ad90Evan Cheng} 728485fafc8406db8552ba5e3ff871a6ee32694ad90Evan Cheng 72988a5c832ac71eb31d2b1bc143817af9248f4c549Chris Lattner//===----------------------------------------------------------------------===// 73088a5c832ac71eb31d2b1bc143817af9248f4c549Chris Lattner// Memory Optimization 73188a5c832ac71eb31d2b1bc143817af9248f4c549Chris Lattner//===----------------------------------------------------------------------===// 73288a5c832ac71eb31d2b1bc143817af9248f4c549Chris Lattner 733dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner/// IsNonLocalValue - Return true if the specified values are defined in a 734dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner/// different basic block than BB. 735dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattnerstatic bool IsNonLocalValue(Value *V, BasicBlock *BB) { 736dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner if (Instruction *I = dyn_cast<Instruction>(V)) 737dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner return I->getParent() != BB; 738dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner return false; 739dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner} 740dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner 7414a8ee23a8181f668dc294b417f67e1675ad391abBob Wilson/// OptimizeMemoryInst - Load and Store Instructions often have 742dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner/// addressing modes that can do significant amounts of computation. As such, 743dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner/// instruction selection will try to get the load or store to do as much 744dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner/// computation as possible for the program. The problem is that isel can only 745dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner/// see within a single block. As such, we sink as much legal addressing mode 746dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner/// stuff into the block as possible. 74788a5c832ac71eb31d2b1bc143817af9248f4c549Chris Lattner/// 74888a5c832ac71eb31d2b1bc143817af9248f4c549Chris Lattner/// This method is used to optimize both load/store and inline asms with memory 74988a5c832ac71eb31d2b1bc143817af9248f4c549Chris Lattner/// operands. 750896617b776e7b015346160645b19be776cbe3805Chris Lattnerbool CodeGenPrepare::OptimizeMemoryInst(Instruction *MemoryInst, Value *Addr, 751db125cfaf57cc83e7dd7453de2d509bc8efd0e5eChris Lattner Type *AccessTy) { 75235bf4d6d8018160557a92b86181acbcef76f86ebOwen Anderson Value *Repl = Addr; 75335bf4d6d8018160557a92b86181acbcef76f86ebOwen Anderson 754d2f4174fcc69a3328076734fa3256b31e5b7f734Owen Anderson // Try to collapse single-value PHI nodes. This is necessary to undo 755d2f4174fcc69a3328076734fa3256b31e5b7f734Owen Anderson // unprofitable PRE transformations. 7567cb4fa20b5534decf527a6bfcc74bd79ea11cbb1Cameron Zwarich SmallVector<Value*, 8> worklist; 7577cb4fa20b5534decf527a6bfcc74bd79ea11cbb1Cameron Zwarich SmallPtrSet<Value*, 16> Visited; 75835bf4d6d8018160557a92b86181acbcef76f86ebOwen Anderson worklist.push_back(Addr); 75935bf4d6d8018160557a92b86181acbcef76f86ebOwen Anderson 76035bf4d6d8018160557a92b86181acbcef76f86ebOwen Anderson // Use a worklist to iteratively look through PHI nodes, and ensure that 76135bf4d6d8018160557a92b86181acbcef76f86ebOwen Anderson // the addressing mode obtained from the non-PHI roots of the graph 76235bf4d6d8018160557a92b86181acbcef76f86ebOwen Anderson // are equivalent. 76335bf4d6d8018160557a92b86181acbcef76f86ebOwen Anderson Value *Consensus = 0; 7644c078f0d6df6136cbbcf581c254869051d455fdcCameron Zwarich unsigned NumUsesConsensus = 0; 7657c8d351d997655eb457bac5f810c219a9089594cCameron Zwarich bool IsNumUsesConsensusValid = false; 76635bf4d6d8018160557a92b86181acbcef76f86ebOwen Anderson SmallVector<Instruction*, 16> AddrModeInsts; 76735bf4d6d8018160557a92b86181acbcef76f86ebOwen Anderson ExtAddrMode AddrMode; 76835bf4d6d8018160557a92b86181acbcef76f86ebOwen Anderson while (!worklist.empty()) { 76935bf4d6d8018160557a92b86181acbcef76f86ebOwen Anderson Value *V = worklist.back(); 77035bf4d6d8018160557a92b86181acbcef76f86ebOwen Anderson worklist.pop_back(); 77135bf4d6d8018160557a92b86181acbcef76f86ebOwen Anderson 77235bf4d6d8018160557a92b86181acbcef76f86ebOwen Anderson // Break use-def graph loops. 77348105286cbbe046d82d1a7e36a07d656d8ba2fafNick Lewycky if (!Visited.insert(V)) { 77435bf4d6d8018160557a92b86181acbcef76f86ebOwen Anderson Consensus = 0; 77535bf4d6d8018160557a92b86181acbcef76f86ebOwen Anderson break; 77635bf4d6d8018160557a92b86181acbcef76f86ebOwen Anderson } 77735bf4d6d8018160557a92b86181acbcef76f86ebOwen Anderson 77835bf4d6d8018160557a92b86181acbcef76f86ebOwen Anderson // For a PHI node, push all of its incoming values. 77935bf4d6d8018160557a92b86181acbcef76f86ebOwen Anderson if (PHINode *P = dyn_cast<PHINode>(V)) { 78035bf4d6d8018160557a92b86181acbcef76f86ebOwen Anderson for (unsigned i = 0, e = P->getNumIncomingValues(); i != e; ++i) 78135bf4d6d8018160557a92b86181acbcef76f86ebOwen Anderson worklist.push_back(P->getIncomingValue(i)); 78235bf4d6d8018160557a92b86181acbcef76f86ebOwen Anderson continue; 78335bf4d6d8018160557a92b86181acbcef76f86ebOwen Anderson } 78435bf4d6d8018160557a92b86181acbcef76f86ebOwen Anderson 78535bf4d6d8018160557a92b86181acbcef76f86ebOwen Anderson // For non-PHIs, determine the addressing mode being computed. 78635bf4d6d8018160557a92b86181acbcef76f86ebOwen Anderson SmallVector<Instruction*, 16> NewAddrModeInsts; 78735bf4d6d8018160557a92b86181acbcef76f86ebOwen Anderson ExtAddrMode NewAddrMode = 78848105286cbbe046d82d1a7e36a07d656d8ba2fafNick Lewycky AddressingModeMatcher::Match(V, AccessTy, MemoryInst, 78935bf4d6d8018160557a92b86181acbcef76f86ebOwen Anderson NewAddrModeInsts, *TLI); 7907c8d351d997655eb457bac5f810c219a9089594cCameron Zwarich 7917c8d351d997655eb457bac5f810c219a9089594cCameron Zwarich // This check is broken into two cases with very similar code to avoid using 7927c8d351d997655eb457bac5f810c219a9089594cCameron Zwarich // getNumUses() as much as possible. Some values have a lot of uses, so 7937c8d351d997655eb457bac5f810c219a9089594cCameron Zwarich // calling getNumUses() unconditionally caused a significant compile-time 7947c8d351d997655eb457bac5f810c219a9089594cCameron Zwarich // regression. 7957c8d351d997655eb457bac5f810c219a9089594cCameron Zwarich if (!Consensus) { 7967c8d351d997655eb457bac5f810c219a9089594cCameron Zwarich Consensus = V; 7977c8d351d997655eb457bac5f810c219a9089594cCameron Zwarich AddrMode = NewAddrMode; 7987c8d351d997655eb457bac5f810c219a9089594cCameron Zwarich AddrModeInsts = NewAddrModeInsts; 7997c8d351d997655eb457bac5f810c219a9089594cCameron Zwarich continue; 8007c8d351d997655eb457bac5f810c219a9089594cCameron Zwarich } else if (NewAddrMode == AddrMode) { 8017c8d351d997655eb457bac5f810c219a9089594cCameron Zwarich if (!IsNumUsesConsensusValid) { 8027c8d351d997655eb457bac5f810c219a9089594cCameron Zwarich NumUsesConsensus = Consensus->getNumUses(); 8037c8d351d997655eb457bac5f810c219a9089594cCameron Zwarich IsNumUsesConsensusValid = true; 8047c8d351d997655eb457bac5f810c219a9089594cCameron Zwarich } 8057c8d351d997655eb457bac5f810c219a9089594cCameron Zwarich 8067c8d351d997655eb457bac5f810c219a9089594cCameron Zwarich // Ensure that the obtained addressing mode is equivalent to that obtained 8077c8d351d997655eb457bac5f810c219a9089594cCameron Zwarich // for all other roots of the PHI traversal. Also, when choosing one 8087c8d351d997655eb457bac5f810c219a9089594cCameron Zwarich // such root as representative, select the one with the most uses in order 8097c8d351d997655eb457bac5f810c219a9089594cCameron Zwarich // to keep the cost modeling heuristics in AddressingModeMatcher 8107c8d351d997655eb457bac5f810c219a9089594cCameron Zwarich // applicable. 8114c078f0d6df6136cbbcf581c254869051d455fdcCameron Zwarich unsigned NumUses = V->getNumUses(); 8124c078f0d6df6136cbbcf581c254869051d455fdcCameron Zwarich if (NumUses > NumUsesConsensus) { 81335bf4d6d8018160557a92b86181acbcef76f86ebOwen Anderson Consensus = V; 8144c078f0d6df6136cbbcf581c254869051d455fdcCameron Zwarich NumUsesConsensus = NumUses; 81535bf4d6d8018160557a92b86181acbcef76f86ebOwen Anderson AddrModeInsts = NewAddrModeInsts; 816d2f4174fcc69a3328076734fa3256b31e5b7f734Owen Anderson } 81735bf4d6d8018160557a92b86181acbcef76f86ebOwen Anderson continue; 818d2f4174fcc69a3328076734fa3256b31e5b7f734Owen Anderson } 819d2f4174fcc69a3328076734fa3256b31e5b7f734Owen Anderson 82035bf4d6d8018160557a92b86181acbcef76f86ebOwen Anderson Consensus = 0; 82135bf4d6d8018160557a92b86181acbcef76f86ebOwen Anderson break; 822d2f4174fcc69a3328076734fa3256b31e5b7f734Owen Anderson } 823d2f4174fcc69a3328076734fa3256b31e5b7f734Owen Anderson 82435bf4d6d8018160557a92b86181acbcef76f86ebOwen Anderson // If the addressing mode couldn't be determined, or if multiple different 82535bf4d6d8018160557a92b86181acbcef76f86ebOwen Anderson // ones were determined, bail out now. 82635bf4d6d8018160557a92b86181acbcef76f86ebOwen Anderson if (!Consensus) return false; 82735bf4d6d8018160557a92b86181acbcef76f86ebOwen Anderson 828dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner // Check to see if any of the instructions supersumed by this addr mode are 829dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner // non-local to I's BB. 830dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner bool AnyNonLocal = false; 831dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner for (unsigned i = 0, e = AddrModeInsts.size(); i != e; ++i) { 832896617b776e7b015346160645b19be776cbe3805Chris Lattner if (IsNonLocalValue(AddrModeInsts[i], MemoryInst->getParent())) { 833dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner AnyNonLocal = true; 834dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner break; 835dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner } 836dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner } 837692bf6b85e0eaed549cd47d67289ab7b28e32651Eric Christopher 838dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner // If all the instructions matched are already in this BB, don't do anything. 839dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner if (!AnyNonLocal) { 84068d67fdf203ff2d5b0eeb925befd0866bce3aceeDavid Greene DEBUG(dbgs() << "CGP: Found local addrmode: " << AddrMode << "\n"); 841dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner return false; 842dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner } 843692bf6b85e0eaed549cd47d67289ab7b28e32651Eric Christopher 844dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner // Insert this computation right after this user. Since our caller is 845dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner // scanning from the top of the BB to the bottom, reuse of the expr are 846dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner // guaranteed to happen later. 8472048c379dd9e080c3e1bb0c93636da9564d8772cDevang Patel IRBuilder<> Builder(MemoryInst); 848692bf6b85e0eaed549cd47d67289ab7b28e32651Eric Christopher 849dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner // Now that we determined the addressing expression we want to use and know 850dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner // that we have to sink it into this block. Check to see if we have already 851dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner // done this for some other load/store instr in this block. If so, reuse the 852dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner // computation. 853dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner Value *&SunkAddr = SunkAddrs[Addr]; 854dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner if (SunkAddr) { 85568d67fdf203ff2d5b0eeb925befd0866bce3aceeDavid Greene DEBUG(dbgs() << "CGP: Reusing nonlocal addrmode: " << AddrMode << " for " 8566c1980b3357207c4d756255bc5e32323eac278dcDan Gohman << *MemoryInst); 857dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner if (SunkAddr->getType() != Addr->getType()) 858a9390a4d5f5d568059a80970d22194b165d097a7Benjamin Kramer SunkAddr = Builder.CreateBitCast(SunkAddr, Addr->getType()); 859dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner } else { 86068d67fdf203ff2d5b0eeb925befd0866bce3aceeDavid Greene DEBUG(dbgs() << "CGP: SINKING nonlocal addrmode: " << AddrMode << " for " 8616c1980b3357207c4d756255bc5e32323eac278dcDan Gohman << *MemoryInst); 862db125cfaf57cc83e7dd7453de2d509bc8efd0e5eChris Lattner Type *IntPtrTy = 8631d0be15f89cb5056e20e2d24faa8d6afb1573bcaOwen Anderson TLI->getTargetData()->getIntPtrType(AccessTy->getContext()); 864692bf6b85e0eaed549cd47d67289ab7b28e32651Eric Christopher 865dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner Value *Result = 0; 866d8d0b6a42c09f1c5b00a4e7029b08074a3da5acdDan Gohman 867d8d0b6a42c09f1c5b00a4e7029b08074a3da5acdDan Gohman // Start with the base register. Do this first so that subsequent address 868d8d0b6a42c09f1c5b00a4e7029b08074a3da5acdDan Gohman // matching finds it last, which will prevent it from trying to match it 869d8d0b6a42c09f1c5b00a4e7029b08074a3da5acdDan Gohman // as the scaled value in case it happens to be a mul. That would be 870d8d0b6a42c09f1c5b00a4e7029b08074a3da5acdDan Gohman // problematic if we've sunk a different mul for the scale, because then 871d8d0b6a42c09f1c5b00a4e7029b08074a3da5acdDan Gohman // we'd end up sinking both muls. 872d8d0b6a42c09f1c5b00a4e7029b08074a3da5acdDan Gohman if (AddrMode.BaseReg) { 873d8d0b6a42c09f1c5b00a4e7029b08074a3da5acdDan Gohman Value *V = AddrMode.BaseReg; 8741df9859c40492511b8aa4321eb76496005d3b75bDuncan Sands if (V->getType()->isPointerTy()) 8752048c379dd9e080c3e1bb0c93636da9564d8772cDevang Patel V = Builder.CreatePtrToInt(V, IntPtrTy, "sunkaddr"); 876d8d0b6a42c09f1c5b00a4e7029b08074a3da5acdDan Gohman if (V->getType() != IntPtrTy) 8772048c379dd9e080c3e1bb0c93636da9564d8772cDevang Patel V = Builder.CreateIntCast(V, IntPtrTy, /*isSigned=*/true, "sunkaddr"); 878d8d0b6a42c09f1c5b00a4e7029b08074a3da5acdDan Gohman Result = V; 879d8d0b6a42c09f1c5b00a4e7029b08074a3da5acdDan Gohman } 880d8d0b6a42c09f1c5b00a4e7029b08074a3da5acdDan Gohman 881d8d0b6a42c09f1c5b00a4e7029b08074a3da5acdDan Gohman // Add the scale value. 882dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner if (AddrMode.Scale) { 883dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner Value *V = AddrMode.ScaledReg; 884dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner if (V->getType() == IntPtrTy) { 885dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner // done. 8861df9859c40492511b8aa4321eb76496005d3b75bDuncan Sands } else if (V->getType()->isPointerTy()) { 8872048c379dd9e080c3e1bb0c93636da9564d8772cDevang Patel V = Builder.CreatePtrToInt(V, IntPtrTy, "sunkaddr"); 888dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner } else if (cast<IntegerType>(IntPtrTy)->getBitWidth() < 889dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner cast<IntegerType>(V->getType())->getBitWidth()) { 8902048c379dd9e080c3e1bb0c93636da9564d8772cDevang Patel V = Builder.CreateTrunc(V, IntPtrTy, "sunkaddr"); 891dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner } else { 8922048c379dd9e080c3e1bb0c93636da9564d8772cDevang Patel V = Builder.CreateSExt(V, IntPtrTy, "sunkaddr"); 893dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner } 894dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner if (AddrMode.Scale != 1) 8952048c379dd9e080c3e1bb0c93636da9564d8772cDevang Patel V = Builder.CreateMul(V, ConstantInt::get(IntPtrTy, AddrMode.Scale), 8962048c379dd9e080c3e1bb0c93636da9564d8772cDevang Patel "sunkaddr"); 897dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner if (Result) 8982048c379dd9e080c3e1bb0c93636da9564d8772cDevang Patel Result = Builder.CreateAdd(Result, V, "sunkaddr"); 899dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner else 900dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner Result = V; 901dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner } 902692bf6b85e0eaed549cd47d67289ab7b28e32651Eric Christopher 903dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner // Add in the BaseGV if present. 904dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner if (AddrMode.BaseGV) { 9052048c379dd9e080c3e1bb0c93636da9564d8772cDevang Patel Value *V = Builder.CreatePtrToInt(AddrMode.BaseGV, IntPtrTy, "sunkaddr"); 906dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner if (Result) 9072048c379dd9e080c3e1bb0c93636da9564d8772cDevang Patel Result = Builder.CreateAdd(Result, V, "sunkaddr"); 908dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner else 909dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner Result = V; 910dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner } 911692bf6b85e0eaed549cd47d67289ab7b28e32651Eric Christopher 912dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner // Add in the Base Offset if present. 913dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner if (AddrMode.BaseOffs) { 914eed707b1e6097aac2bb6b3d47271f6300ace7f2eOwen Anderson Value *V = ConstantInt::get(IntPtrTy, AddrMode.BaseOffs); 915dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner if (Result) 9162048c379dd9e080c3e1bb0c93636da9564d8772cDevang Patel Result = Builder.CreateAdd(Result, V, "sunkaddr"); 917dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner else 918dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner Result = V; 919dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner } 920dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner 921dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner if (Result == 0) 922a7235ea7245028a0723e8ab7fd011386b3900777Owen Anderson SunkAddr = Constant::getNullValue(Addr->getType()); 923dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner else 9242048c379dd9e080c3e1bb0c93636da9564d8772cDevang Patel SunkAddr = Builder.CreateIntToPtr(Result, Addr->getType(), "sunkaddr"); 925dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner } 926692bf6b85e0eaed549cd47d67289ab7b28e32651Eric Christopher 927d2f4174fcc69a3328076734fa3256b31e5b7f734Owen Anderson MemoryInst->replaceUsesOfWith(Repl, SunkAddr); 928692bf6b85e0eaed549cd47d67289ab7b28e32651Eric Christopher 9290403b473dd99b5c7db1fa7048288be6cb42e7abdChris Lattner // If we have no uses, recursively delete the value and all dead instructions 9300403b473dd99b5c7db1fa7048288be6cb42e7abdChris Lattner // using it. 931d2f4174fcc69a3328076734fa3256b31e5b7f734Owen Anderson if (Repl->use_empty()) { 9320403b473dd99b5c7db1fa7048288be6cb42e7abdChris Lattner // This can cause recursive deletion, which can invalidate our iterator. 9330403b473dd99b5c7db1fa7048288be6cb42e7abdChris Lattner // Use a WeakVH to hold onto it in case this happens. 9340403b473dd99b5c7db1fa7048288be6cb42e7abdChris Lattner WeakVH IterHandle(CurInstIterator); 9350403b473dd99b5c7db1fa7048288be6cb42e7abdChris Lattner BasicBlock *BB = CurInstIterator->getParent(); 9360403b473dd99b5c7db1fa7048288be6cb42e7abdChris Lattner 937d2f4174fcc69a3328076734fa3256b31e5b7f734Owen Anderson RecursivelyDeleteTriviallyDeadInstructions(Repl); 9380403b473dd99b5c7db1fa7048288be6cb42e7abdChris Lattner 9390403b473dd99b5c7db1fa7048288be6cb42e7abdChris Lattner if (IterHandle != CurInstIterator) { 9400403b473dd99b5c7db1fa7048288be6cb42e7abdChris Lattner // If the iterator instruction was recursively deleted, start over at the 9410403b473dd99b5c7db1fa7048288be6cb42e7abdChris Lattner // start of the block. 9420403b473dd99b5c7db1fa7048288be6cb42e7abdChris Lattner CurInstIterator = BB->begin(); 9430403b473dd99b5c7db1fa7048288be6cb42e7abdChris Lattner SunkAddrs.clear(); 9440403b473dd99b5c7db1fa7048288be6cb42e7abdChris Lattner } else { 9450403b473dd99b5c7db1fa7048288be6cb42e7abdChris Lattner // This address is now available for reassignment, so erase the table 9460403b473dd99b5c7db1fa7048288be6cb42e7abdChris Lattner // entry; we don't want to match some completely different instruction. 9470403b473dd99b5c7db1fa7048288be6cb42e7abdChris Lattner SunkAddrs[Addr] = 0; 9480403b473dd99b5c7db1fa7048288be6cb42e7abdChris Lattner } 949536d31b5b391ee76eae33f4756f6442bf10b2d72Dale Johannesen } 95031ff1333e0651192212cee6e090df2ff57d19b53Cameron Zwarich ++NumMemoryInsts; 951dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner return true; 952dd77df3cbc2301c14f56c9d2cfd412a032c27241Chris Lattner} 953dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner 9549bf12b5583104c810cfadcdce91edf9efad79973Evan Cheng/// OptimizeInlineAsmInst - If there are any memory operands, use 95588a5c832ac71eb31d2b1bc143817af9248f4c549Chris Lattner/// OptimizeMemoryInst to sink their address computing into the block when 9569bf12b5583104c810cfadcdce91edf9efad79973Evan Cheng/// possible / profitable. 9577579609bfe0d915b6c2d8dc094a132d793ec8855Chris Lattnerbool CodeGenPrepare::OptimizeInlineAsmInst(CallInst *CS) { 9589bf12b5583104c810cfadcdce91edf9efad79973Evan Cheng bool MadeChange = false; 9599bf12b5583104c810cfadcdce91edf9efad79973Evan Cheng 9607579609bfe0d915b6c2d8dc094a132d793ec8855Chris Lattner TargetLowering::AsmOperandInfoVector 9617579609bfe0d915b6c2d8dc094a132d793ec8855Chris Lattner TargetConstraints = TLI->ParseConstraints(CS); 962677c6ecd0804c247eb727a830b50cd6537a6c12cDale Johannesen unsigned ArgNo = 0; 963eac6e1d0c748afc3d1496be0753ffbe5f5a4279bJohn Thompson for (unsigned i = 0, e = TargetConstraints.size(); i != e; ++i) { 964eac6e1d0c748afc3d1496be0753ffbe5f5a4279bJohn Thompson TargetLowering::AsmOperandInfo &OpInfo = TargetConstraints[i]; 965eac6e1d0c748afc3d1496be0753ffbe5f5a4279bJohn Thompson 9669bf12b5583104c810cfadcdce91edf9efad79973Evan Cheng // Compute the constraint code and ConstraintType to use. 9671784d160e4efa75782884d451d0788b9457e67dcDale Johannesen TLI->ComputeConstraintToUse(OpInfo, SDValue()); 9689bf12b5583104c810cfadcdce91edf9efad79973Evan Cheng 9699ec8095485c994522c9a50e16fc029de94c20476Eli Friedman if (OpInfo.ConstraintType == TargetLowering::C_Memory && 9709ec8095485c994522c9a50e16fc029de94c20476Eli Friedman OpInfo.isIndirect) { 9717579609bfe0d915b6c2d8dc094a132d793ec8855Chris Lattner Value *OpVal = CS->getArgOperand(ArgNo++); 9721a8943a1f872a47b821fe7075f07b42403fa1a3fChris Lattner MadeChange |= OptimizeMemoryInst(CS, OpVal, OpVal->getType()); 973677c6ecd0804c247eb727a830b50cd6537a6c12cDale Johannesen } else if (OpInfo.Type == InlineAsm::isInput) 974677c6ecd0804c247eb727a830b50cd6537a6c12cDale Johannesen ArgNo++; 9759bf12b5583104c810cfadcdce91edf9efad79973Evan Cheng } 9769bf12b5583104c810cfadcdce91edf9efad79973Evan Cheng 9779bf12b5583104c810cfadcdce91edf9efad79973Evan Cheng return MadeChange; 9789bf12b5583104c810cfadcdce91edf9efad79973Evan Cheng} 9799bf12b5583104c810cfadcdce91edf9efad79973Evan Cheng 980b00f236b03ea57520f94823780896ebdbc5d8bdcDan Gohman/// MoveExtToFormExtLoad - Move a zext or sext fed by a load into the same 981b00f236b03ea57520f94823780896ebdbc5d8bdcDan Gohman/// basic block as the load, unless conditions are unfavorable. This allows 982b00f236b03ea57520f94823780896ebdbc5d8bdcDan Gohman/// SelectionDAG to fold the extend into the load. 983b00f236b03ea57520f94823780896ebdbc5d8bdcDan Gohman/// 984b00f236b03ea57520f94823780896ebdbc5d8bdcDan Gohmanbool CodeGenPrepare::MoveExtToFormExtLoad(Instruction *I) { 985b00f236b03ea57520f94823780896ebdbc5d8bdcDan Gohman // Look for a load being extended. 986b00f236b03ea57520f94823780896ebdbc5d8bdcDan Gohman LoadInst *LI = dyn_cast<LoadInst>(I->getOperand(0)); 987b00f236b03ea57520f94823780896ebdbc5d8bdcDan Gohman if (!LI) return false; 988b00f236b03ea57520f94823780896ebdbc5d8bdcDan Gohman 989b00f236b03ea57520f94823780896ebdbc5d8bdcDan Gohman // If they're already in the same block, there's nothing to do. 990b00f236b03ea57520f94823780896ebdbc5d8bdcDan Gohman if (LI->getParent() == I->getParent()) 991b00f236b03ea57520f94823780896ebdbc5d8bdcDan Gohman return false; 992b00f236b03ea57520f94823780896ebdbc5d8bdcDan Gohman 993b00f236b03ea57520f94823780896ebdbc5d8bdcDan Gohman // If the load has other users and the truncate is not free, this probably 994b00f236b03ea57520f94823780896ebdbc5d8bdcDan Gohman // isn't worthwhile. 995b00f236b03ea57520f94823780896ebdbc5d8bdcDan Gohman if (!LI->hasOneUse() && 996ec57a1acec7803fff2faa54c6ea8fec2be01aeb9Bob Wilson TLI && (TLI->isTypeLegal(TLI->getValueType(LI->getType())) || 997ec57a1acec7803fff2faa54c6ea8fec2be01aeb9Bob Wilson !TLI->isTypeLegal(TLI->getValueType(I->getType()))) && 99871dc4d96ed39fadcdccf8c578d49a1afdae0c6baBob Wilson !TLI->isTruncateFree(I->getType(), LI->getType())) 999b00f236b03ea57520f94823780896ebdbc5d8bdcDan Gohman return false; 1000b00f236b03ea57520f94823780896ebdbc5d8bdcDan Gohman 1001b00f236b03ea57520f94823780896ebdbc5d8bdcDan Gohman // Check whether the target supports casts folded into loads. 1002b00f236b03ea57520f94823780896ebdbc5d8bdcDan Gohman unsigned LType; 1003b00f236b03ea57520f94823780896ebdbc5d8bdcDan Gohman if (isa<ZExtInst>(I)) 1004b00f236b03ea57520f94823780896ebdbc5d8bdcDan Gohman LType = ISD::ZEXTLOAD; 1005b00f236b03ea57520f94823780896ebdbc5d8bdcDan Gohman else { 1006b00f236b03ea57520f94823780896ebdbc5d8bdcDan Gohman assert(isa<SExtInst>(I) && "Unexpected ext type!"); 1007b00f236b03ea57520f94823780896ebdbc5d8bdcDan Gohman LType = ISD::SEXTLOAD; 1008b00f236b03ea57520f94823780896ebdbc5d8bdcDan Gohman } 1009b00f236b03ea57520f94823780896ebdbc5d8bdcDan Gohman if (TLI && !TLI->isLoadExtLegal(LType, TLI->getValueType(LI->getType()))) 1010b00f236b03ea57520f94823780896ebdbc5d8bdcDan Gohman return false; 1011b00f236b03ea57520f94823780896ebdbc5d8bdcDan Gohman 1012b00f236b03ea57520f94823780896ebdbc5d8bdcDan Gohman // Move the extend into the same block as the load, so that SelectionDAG 1013b00f236b03ea57520f94823780896ebdbc5d8bdcDan Gohman // can fold it. 1014b00f236b03ea57520f94823780896ebdbc5d8bdcDan Gohman I->removeFromParent(); 1015b00f236b03ea57520f94823780896ebdbc5d8bdcDan Gohman I->insertAfter(LI); 101631ff1333e0651192212cee6e090df2ff57d19b53Cameron Zwarich ++NumExtsMoved; 1017b00f236b03ea57520f94823780896ebdbc5d8bdcDan Gohman return true; 1018b00f236b03ea57520f94823780896ebdbc5d8bdcDan Gohman} 1019b00f236b03ea57520f94823780896ebdbc5d8bdcDan Gohman 1020bdcb726fcad1e3fddc70847a2b91d4d4f9396938Evan Chengbool CodeGenPrepare::OptimizeExtUses(Instruction *I) { 1021bdcb726fcad1e3fddc70847a2b91d4d4f9396938Evan Cheng BasicBlock *DefBB = I->getParent(); 1022bdcb726fcad1e3fddc70847a2b91d4d4f9396938Evan Cheng 10239120f5c35b756e0b9d7747616e97df8f30edfcc8Bob Wilson // If the result of a {s|z}ext and its source are both live out, rewrite all 1024bdcb726fcad1e3fddc70847a2b91d4d4f9396938Evan Cheng // other uses of the source with result of extension. 1025bdcb726fcad1e3fddc70847a2b91d4d4f9396938Evan Cheng Value *Src = I->getOperand(0); 1026bdcb726fcad1e3fddc70847a2b91d4d4f9396938Evan Cheng if (Src->hasOneUse()) 1027bdcb726fcad1e3fddc70847a2b91d4d4f9396938Evan Cheng return false; 1028bdcb726fcad1e3fddc70847a2b91d4d4f9396938Evan Cheng 1029696e5c047bd06bf6b7b5471b3f4dec319b43628bEvan Cheng // Only do this xform if truncating is free. 103053bdbd756581a9a1d6d381059f103c5f3c687bb6Gabor Greif if (TLI && !TLI->isTruncateFree(I->getType(), Src->getType())) 1031f9785f92b630e69262c395b2fc0893451169d68bEvan Cheng return false; 1032f9785f92b630e69262c395b2fc0893451169d68bEvan Cheng 1033772de516b6851e679d3da9e5171712b9c3122019Evan Cheng // Only safe to perform the optimization if the source is also defined in 1034765dff258545f019502023045b471443ff9ef6c4Evan Cheng // this block. 1035765dff258545f019502023045b471443ff9ef6c4Evan Cheng if (!isa<Instruction>(Src) || DefBB != cast<Instruction>(Src)->getParent()) 1036772de516b6851e679d3da9e5171712b9c3122019Evan Cheng return false; 1037772de516b6851e679d3da9e5171712b9c3122019Evan Cheng 1038bdcb726fcad1e3fddc70847a2b91d4d4f9396938Evan Cheng bool DefIsLiveOut = false; 1039692bf6b85e0eaed549cd47d67289ab7b28e32651Eric Christopher for (Value::use_iterator UI = I->use_begin(), E = I->use_end(); 1040bdcb726fcad1e3fddc70847a2b91d4d4f9396938Evan Cheng UI != E; ++UI) { 1041bdcb726fcad1e3fddc70847a2b91d4d4f9396938Evan Cheng Instruction *User = cast<Instruction>(*UI); 1042bdcb726fcad1e3fddc70847a2b91d4d4f9396938Evan Cheng 1043bdcb726fcad1e3fddc70847a2b91d4d4f9396938Evan Cheng // Figure out which BB this ext is used in. 1044bdcb726fcad1e3fddc70847a2b91d4d4f9396938Evan Cheng BasicBlock *UserBB = User->getParent(); 1045bdcb726fcad1e3fddc70847a2b91d4d4f9396938Evan Cheng if (UserBB == DefBB) continue; 1046bdcb726fcad1e3fddc70847a2b91d4d4f9396938Evan Cheng DefIsLiveOut = true; 1047bdcb726fcad1e3fddc70847a2b91d4d4f9396938Evan Cheng break; 1048bdcb726fcad1e3fddc70847a2b91d4d4f9396938Evan Cheng } 1049bdcb726fcad1e3fddc70847a2b91d4d4f9396938Evan Cheng if (!DefIsLiveOut) 1050bdcb726fcad1e3fddc70847a2b91d4d4f9396938Evan Cheng return false; 1051bdcb726fcad1e3fddc70847a2b91d4d4f9396938Evan Cheng 1052765dff258545f019502023045b471443ff9ef6c4Evan Cheng // Make sure non of the uses are PHI nodes. 1053692bf6b85e0eaed549cd47d67289ab7b28e32651Eric Christopher for (Value::use_iterator UI = Src->use_begin(), E = Src->use_end(); 1054765dff258545f019502023045b471443ff9ef6c4Evan Cheng UI != E; ++UI) { 1055765dff258545f019502023045b471443ff9ef6c4Evan Cheng Instruction *User = cast<Instruction>(*UI); 1056f9785f92b630e69262c395b2fc0893451169d68bEvan Cheng BasicBlock *UserBB = User->getParent(); 1057f9785f92b630e69262c395b2fc0893451169d68bEvan Cheng if (UserBB == DefBB) continue; 1058f9785f92b630e69262c395b2fc0893451169d68bEvan Cheng // Be conservative. We don't want this xform to end up introducing 1059f9785f92b630e69262c395b2fc0893451169d68bEvan Cheng // reloads just before load / store instructions. 1060f9785f92b630e69262c395b2fc0893451169d68bEvan Cheng if (isa<PHINode>(User) || isa<LoadInst>(User) || isa<StoreInst>(User)) 1061765dff258545f019502023045b471443ff9ef6c4Evan Cheng return false; 1062765dff258545f019502023045b471443ff9ef6c4Evan Cheng } 1063765dff258545f019502023045b471443ff9ef6c4Evan Cheng 1064bdcb726fcad1e3fddc70847a2b91d4d4f9396938Evan Cheng // InsertedTruncs - Only insert one trunc in each block once. 1065bdcb726fcad1e3fddc70847a2b91d4d4f9396938Evan Cheng DenseMap<BasicBlock*, Instruction*> InsertedTruncs; 1066bdcb726fcad1e3fddc70847a2b91d4d4f9396938Evan Cheng 1067bdcb726fcad1e3fddc70847a2b91d4d4f9396938Evan Cheng bool MadeChange = false; 1068692bf6b85e0eaed549cd47d67289ab7b28e32651Eric Christopher for (Value::use_iterator UI = Src->use_begin(), E = Src->use_end(); 1069bdcb726fcad1e3fddc70847a2b91d4d4f9396938Evan Cheng UI != E; ++UI) { 1070bdcb726fcad1e3fddc70847a2b91d4d4f9396938Evan Cheng Use &TheUse = UI.getUse(); 1071bdcb726fcad1e3fddc70847a2b91d4d4f9396938Evan Cheng Instruction *User = cast<Instruction>(*UI); 1072bdcb726fcad1e3fddc70847a2b91d4d4f9396938Evan Cheng 1073bdcb726fcad1e3fddc70847a2b91d4d4f9396938Evan Cheng // Figure out which BB this ext is used in. 1074bdcb726fcad1e3fddc70847a2b91d4d4f9396938Evan Cheng BasicBlock *UserBB = User->getParent(); 1075bdcb726fcad1e3fddc70847a2b91d4d4f9396938Evan Cheng if (UserBB == DefBB) continue; 1076bdcb726fcad1e3fddc70847a2b91d4d4f9396938Evan Cheng 1077bdcb726fcad1e3fddc70847a2b91d4d4f9396938Evan Cheng // Both src and def are live in this block. Rewrite the use. 1078bdcb726fcad1e3fddc70847a2b91d4d4f9396938Evan Cheng Instruction *&InsertedTrunc = InsertedTruncs[UserBB]; 1079bdcb726fcad1e3fddc70847a2b91d4d4f9396938Evan Cheng 1080bdcb726fcad1e3fddc70847a2b91d4d4f9396938Evan Cheng if (!InsertedTrunc) { 10815b6f42f57e730c2d968c313a27fa505a3c3e5efaBill Wendling BasicBlock::iterator InsertPt = UserBB->getFirstInsertionPt(); 1082bdcb726fcad1e3fddc70847a2b91d4d4f9396938Evan Cheng InsertedTrunc = new TruncInst(I, Src->getType(), "", InsertPt); 1083bdcb726fcad1e3fddc70847a2b91d4d4f9396938Evan Cheng } 1084bdcb726fcad1e3fddc70847a2b91d4d4f9396938Evan Cheng 1085bdcb726fcad1e3fddc70847a2b91d4d4f9396938Evan Cheng // Replace a use of the {s|z}ext source with a use of the result. 1086bdcb726fcad1e3fddc70847a2b91d4d4f9396938Evan Cheng TheUse = InsertedTrunc; 108731ff1333e0651192212cee6e090df2ff57d19b53Cameron Zwarich ++NumExtUses; 1088bdcb726fcad1e3fddc70847a2b91d4d4f9396938Evan Cheng MadeChange = true; 1089bdcb726fcad1e3fddc70847a2b91d4d4f9396938Evan Cheng } 1090bdcb726fcad1e3fddc70847a2b91d4d4f9396938Evan Cheng 1091bdcb726fcad1e3fddc70847a2b91d4d4f9396938Evan Cheng return MadeChange; 1092bdcb726fcad1e3fddc70847a2b91d4d4f9396938Evan Cheng} 1093bdcb726fcad1e3fddc70847a2b91d4d4f9396938Evan Cheng 1094c061101e03ef6d2ca550f8fe71594a5e1c02e348Cameron Zwarichbool CodeGenPrepare::OptimizeInst(Instruction *I) { 1095c061101e03ef6d2ca550f8fe71594a5e1c02e348Cameron Zwarich if (PHINode *P = dyn_cast<PHINode>(I)) { 1096c061101e03ef6d2ca550f8fe71594a5e1c02e348Cameron Zwarich // It is possible for very late stage optimizations (such as SimplifyCFG) 1097c061101e03ef6d2ca550f8fe71594a5e1c02e348Cameron Zwarich // to introduce PHI nodes too late to be cleaned up. If we detect such a 1098c061101e03ef6d2ca550f8fe71594a5e1c02e348Cameron Zwarich // trivial PHI, go ahead and zap it here. 1099c061101e03ef6d2ca550f8fe71594a5e1c02e348Cameron Zwarich if (Value *V = SimplifyInstruction(P)) { 1100c061101e03ef6d2ca550f8fe71594a5e1c02e348Cameron Zwarich P->replaceAllUsesWith(V); 1101c061101e03ef6d2ca550f8fe71594a5e1c02e348Cameron Zwarich P->eraseFromParent(); 1102c061101e03ef6d2ca550f8fe71594a5e1c02e348Cameron Zwarich ++NumPHIsElim; 11031a8943a1f872a47b821fe7075f07b42403fa1a3fChris Lattner return true; 1104c061101e03ef6d2ca550f8fe71594a5e1c02e348Cameron Zwarich } 11051a8943a1f872a47b821fe7075f07b42403fa1a3fChris Lattner return false; 11061a8943a1f872a47b821fe7075f07b42403fa1a3fChris Lattner } 11071a8943a1f872a47b821fe7075f07b42403fa1a3fChris Lattner 11081a8943a1f872a47b821fe7075f07b42403fa1a3fChris Lattner if (CastInst *CI = dyn_cast<CastInst>(I)) { 1109c061101e03ef6d2ca550f8fe71594a5e1c02e348Cameron Zwarich // If the source of the cast is a constant, then this should have 1110c061101e03ef6d2ca550f8fe71594a5e1c02e348Cameron Zwarich // already been constant folded. The only reason NOT to constant fold 1111c061101e03ef6d2ca550f8fe71594a5e1c02e348Cameron Zwarich // it is if something (e.g. LSR) was careful to place the constant 1112c061101e03ef6d2ca550f8fe71594a5e1c02e348Cameron Zwarich // evaluation in a block other than then one that uses it (e.g. to hoist 1113c061101e03ef6d2ca550f8fe71594a5e1c02e348Cameron Zwarich // the address of globals out of a loop). If this is the case, we don't 1114c061101e03ef6d2ca550f8fe71594a5e1c02e348Cameron Zwarich // want to forward-subst the cast. 1115c061101e03ef6d2ca550f8fe71594a5e1c02e348Cameron Zwarich if (isa<Constant>(CI->getOperand(0))) 1116c061101e03ef6d2ca550f8fe71594a5e1c02e348Cameron Zwarich return false; 1117c061101e03ef6d2ca550f8fe71594a5e1c02e348Cameron Zwarich 11181a8943a1f872a47b821fe7075f07b42403fa1a3fChris Lattner if (TLI && OptimizeNoopCopyExpression(CI, *TLI)) 11191a8943a1f872a47b821fe7075f07b42403fa1a3fChris Lattner return true; 1120c061101e03ef6d2ca550f8fe71594a5e1c02e348Cameron Zwarich 11211a8943a1f872a47b821fe7075f07b42403fa1a3fChris Lattner if (isa<ZExtInst>(I) || isa<SExtInst>(I)) { 11221a8943a1f872a47b821fe7075f07b42403fa1a3fChris Lattner bool MadeChange = MoveExtToFormExtLoad(I); 11231a8943a1f872a47b821fe7075f07b42403fa1a3fChris Lattner return MadeChange | OptimizeExtUses(I); 1124c061101e03ef6d2ca550f8fe71594a5e1c02e348Cameron Zwarich } 11251a8943a1f872a47b821fe7075f07b42403fa1a3fChris Lattner return false; 11261a8943a1f872a47b821fe7075f07b42403fa1a3fChris Lattner } 11271a8943a1f872a47b821fe7075f07b42403fa1a3fChris Lattner 11281a8943a1f872a47b821fe7075f07b42403fa1a3fChris Lattner if (CmpInst *CI = dyn_cast<CmpInst>(I)) 11291a8943a1f872a47b821fe7075f07b42403fa1a3fChris Lattner return OptimizeCmpExpression(CI); 11301a8943a1f872a47b821fe7075f07b42403fa1a3fChris Lattner 11311a8943a1f872a47b821fe7075f07b42403fa1a3fChris Lattner if (LoadInst *LI = dyn_cast<LoadInst>(I)) { 1132c061101e03ef6d2ca550f8fe71594a5e1c02e348Cameron Zwarich if (TLI) 11331a8943a1f872a47b821fe7075f07b42403fa1a3fChris Lattner return OptimizeMemoryInst(I, I->getOperand(0), LI->getType()); 11341a8943a1f872a47b821fe7075f07b42403fa1a3fChris Lattner return false; 11351a8943a1f872a47b821fe7075f07b42403fa1a3fChris Lattner } 11361a8943a1f872a47b821fe7075f07b42403fa1a3fChris Lattner 11371a8943a1f872a47b821fe7075f07b42403fa1a3fChris Lattner if (StoreInst *SI = dyn_cast<StoreInst>(I)) { 1138c061101e03ef6d2ca550f8fe71594a5e1c02e348Cameron Zwarich if (TLI) 11391a8943a1f872a47b821fe7075f07b42403fa1a3fChris Lattner return OptimizeMemoryInst(I, SI->getOperand(1), 11401a8943a1f872a47b821fe7075f07b42403fa1a3fChris Lattner SI->getOperand(0)->getType()); 11411a8943a1f872a47b821fe7075f07b42403fa1a3fChris Lattner return false; 11421a8943a1f872a47b821fe7075f07b42403fa1a3fChris Lattner } 11431a8943a1f872a47b821fe7075f07b42403fa1a3fChris Lattner 11441a8943a1f872a47b821fe7075f07b42403fa1a3fChris Lattner if (GetElementPtrInst *GEPI = dyn_cast<GetElementPtrInst>(I)) { 1145865ae1a9e77920e07c4a6a992736109c2cd4fe02Cameron Zwarich if (GEPI->hasAllZeroIndices()) { 1146865ae1a9e77920e07c4a6a992736109c2cd4fe02Cameron Zwarich /// The GEP operand must be a pointer, so must its result -> BitCast 1147865ae1a9e77920e07c4a6a992736109c2cd4fe02Cameron Zwarich Instruction *NC = new BitCastInst(GEPI->getOperand(0), GEPI->getType(), 1148865ae1a9e77920e07c4a6a992736109c2cd4fe02Cameron Zwarich GEPI->getName(), GEPI); 1149865ae1a9e77920e07c4a6a992736109c2cd4fe02Cameron Zwarich GEPI->replaceAllUsesWith(NC); 1150865ae1a9e77920e07c4a6a992736109c2cd4fe02Cameron Zwarich GEPI->eraseFromParent(); 1151865ae1a9e77920e07c4a6a992736109c2cd4fe02Cameron Zwarich ++NumGEPsElim; 1152865ae1a9e77920e07c4a6a992736109c2cd4fe02Cameron Zwarich OptimizeInst(NC); 11531a8943a1f872a47b821fe7075f07b42403fa1a3fChris Lattner return true; 1154865ae1a9e77920e07c4a6a992736109c2cd4fe02Cameron Zwarich } 11551a8943a1f872a47b821fe7075f07b42403fa1a3fChris Lattner return false; 1156c061101e03ef6d2ca550f8fe71594a5e1c02e348Cameron Zwarich } 11571a8943a1f872a47b821fe7075f07b42403fa1a3fChris Lattner 11581a8943a1f872a47b821fe7075f07b42403fa1a3fChris Lattner if (CallInst *CI = dyn_cast<CallInst>(I)) 11591a8943a1f872a47b821fe7075f07b42403fa1a3fChris Lattner return OptimizeCallInst(CI); 1160c061101e03ef6d2ca550f8fe71594a5e1c02e348Cameron Zwarich 1161485fafc8406db8552ba5e3ff871a6ee32694ad90Evan Cheng if (ReturnInst *RI = dyn_cast<ReturnInst>(I)) 1162485fafc8406db8552ba5e3ff871a6ee32694ad90Evan Cheng return DupRetToEnableTailCallOpts(RI); 1163485fafc8406db8552ba5e3ff871a6ee32694ad90Evan Cheng 11641a8943a1f872a47b821fe7075f07b42403fa1a3fChris Lattner return false; 1165c061101e03ef6d2ca550f8fe71594a5e1c02e348Cameron Zwarich} 1166c061101e03ef6d2ca550f8fe71594a5e1c02e348Cameron Zwarich 1167dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner// In this pass we look for GEP and cast instructions that are used 1168dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner// across basic blocks and rewrite them to improve basic-block-at-a-time 1169dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner// selection. 1170dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattnerbool CodeGenPrepare::OptimizeBlock(BasicBlock &BB) { 11718c3527e7a475dd3369a485a4f610d56f7005b7b5Cameron Zwarich SunkAddrs.clear(); 117256e3793acf8099eafa36154d2b6c900d46b5965eCameron Zwarich bool MadeChange = false; 1173692bf6b85e0eaed549cd47d67289ab7b28e32651Eric Christopher 11747579609bfe0d915b6c2d8dc094a132d793ec8855Chris Lattner CurInstIterator = BB.begin(); 117594e8e0cfbe13cdbdf7addc6e36df863cab92e4c9Chris Lattner for (BasicBlock::iterator E = BB.end(); CurInstIterator != E; ) 117694e8e0cfbe13cdbdf7addc6e36df863cab92e4c9Chris Lattner MadeChange |= OptimizeInst(CurInstIterator++); 1177692bf6b85e0eaed549cd47d67289ab7b28e32651Eric Christopher 1178dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner return MadeChange; 1179dbe0deca339585dfbaed5951ef0ca2c6a0df173cChris Lattner} 1180f56ea610ed63db0b8a8a9aca95222aa78ce293eeDevang Patel 1181f56ea610ed63db0b8a8a9aca95222aa78ce293eeDevang Patel// llvm.dbg.value is far away from the value then iSel may not be able 1182f56ea610ed63db0b8a8a9aca95222aa78ce293eeDevang Patel// handle it properly. iSel will drop llvm.dbg.value if it can not 1183f56ea610ed63db0b8a8a9aca95222aa78ce293eeDevang Patel// find a node corresponding to the value. 1184f56ea610ed63db0b8a8a9aca95222aa78ce293eeDevang Patelbool CodeGenPrepare::PlaceDbgValues(Function &F) { 1185f56ea610ed63db0b8a8a9aca95222aa78ce293eeDevang Patel bool MadeChange = false; 1186f56ea610ed63db0b8a8a9aca95222aa78ce293eeDevang Patel for (Function::iterator I = F.begin(), E = F.end(); I != E; ++I) { 1187f56ea610ed63db0b8a8a9aca95222aa78ce293eeDevang Patel Instruction *PrevNonDbgInst = NULL; 1188f56ea610ed63db0b8a8a9aca95222aa78ce293eeDevang Patel for (BasicBlock::iterator BI = I->begin(), BE = I->end(); BI != BE;) { 1189f56ea610ed63db0b8a8a9aca95222aa78ce293eeDevang Patel Instruction *Insn = BI; ++BI; 1190f56ea610ed63db0b8a8a9aca95222aa78ce293eeDevang Patel DbgValueInst *DVI = dyn_cast<DbgValueInst>(Insn); 1191f56ea610ed63db0b8a8a9aca95222aa78ce293eeDevang Patel if (!DVI) { 1192f56ea610ed63db0b8a8a9aca95222aa78ce293eeDevang Patel PrevNonDbgInst = Insn; 1193f56ea610ed63db0b8a8a9aca95222aa78ce293eeDevang Patel continue; 1194f56ea610ed63db0b8a8a9aca95222aa78ce293eeDevang Patel } 1195f56ea610ed63db0b8a8a9aca95222aa78ce293eeDevang Patel 1196f56ea610ed63db0b8a8a9aca95222aa78ce293eeDevang Patel Instruction *VI = dyn_cast_or_null<Instruction>(DVI->getValue()); 1197f56ea610ed63db0b8a8a9aca95222aa78ce293eeDevang Patel if (VI && VI != PrevNonDbgInst && !VI->isTerminator()) { 1198f56ea610ed63db0b8a8a9aca95222aa78ce293eeDevang Patel DEBUG(dbgs() << "Moving Debug Value before :\n" << *DVI << ' ' << *VI); 1199f56ea610ed63db0b8a8a9aca95222aa78ce293eeDevang Patel DVI->removeFromParent(); 1200f56ea610ed63db0b8a8a9aca95222aa78ce293eeDevang Patel if (isa<PHINode>(VI)) 1201f56ea610ed63db0b8a8a9aca95222aa78ce293eeDevang Patel DVI->insertBefore(VI->getParent()->getFirstInsertionPt()); 1202f56ea610ed63db0b8a8a9aca95222aa78ce293eeDevang Patel else 1203f56ea610ed63db0b8a8a9aca95222aa78ce293eeDevang Patel DVI->insertAfter(VI); 1204f56ea610ed63db0b8a8a9aca95222aa78ce293eeDevang Patel MadeChange = true; 1205f56ea610ed63db0b8a8a9aca95222aa78ce293eeDevang Patel ++NumDbgValueMoved; 1206f56ea610ed63db0b8a8a9aca95222aa78ce293eeDevang Patel } 1207f56ea610ed63db0b8a8a9aca95222aa78ce293eeDevang Patel } 1208f56ea610ed63db0b8a8a9aca95222aa78ce293eeDevang Patel } 1209f56ea610ed63db0b8a8a9aca95222aa78ce293eeDevang Patel return MadeChange; 1210f56ea610ed63db0b8a8a9aca95222aa78ce293eeDevang Patel} 1211