1894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman//===- CodeGenPrepare.cpp - Prepare a function for code generation --------===// 2894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman// 3894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman// The LLVM Compiler Infrastructure 4894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman// 5894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman// This file is distributed under the University of Illinois Open Source 6894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman// License. See LICENSE.TXT for details. 7894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman// 8894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman//===----------------------------------------------------------------------===// 9894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman// 10894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman// This pass munges the code in the input function to better prepare it for 11894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman// SelectionDAG-based code generation. This works around limitations in it's 12894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman// basic-block-at-a-time approach. It should eventually be removed. 13894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman// 14894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman//===----------------------------------------------------------------------===// 15894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 16894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman#define DEBUG_TYPE "codegenprepare" 17894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman#include "llvm/Transforms/Scalar.h" 18894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman#include "llvm/Constants.h" 19894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman#include "llvm/DerivedTypes.h" 20894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman#include "llvm/Function.h" 21894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman#include "llvm/InlineAsm.h" 22894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman#include "llvm/Instructions.h" 23894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman#include "llvm/IntrinsicInst.h" 24894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman#include "llvm/Pass.h" 2519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman#include "llvm/Analysis/Dominators.h" 2619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman#include "llvm/Analysis/InstructionSimplify.h" 27894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman#include "llvm/Analysis/ProfileInfo.h" 28894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman#include "llvm/Target/TargetData.h" 29894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman#include "llvm/Target/TargetLowering.h" 30894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman#include "llvm/Transforms/Utils/AddrModeMatcher.h" 31894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman#include "llvm/Transforms/Utils/BasicBlockUtils.h" 32894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman#include "llvm/Transforms/Utils/Local.h" 33894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman#include "llvm/Transforms/Utils/BuildLibCalls.h" 34894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman#include "llvm/ADT/DenseMap.h" 35894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman#include "llvm/ADT/SmallSet.h" 3619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman#include "llvm/ADT/Statistic.h" 37894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman#include "llvm/Assembly/Writer.h" 38894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman#include "llvm/Support/CallSite.h" 3919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman#include "llvm/Support/CommandLine.h" 40894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman#include "llvm/Support/Debug.h" 41894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman#include "llvm/Support/GetElementPtrTypeIterator.h" 42894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman#include "llvm/Support/PatternMatch.h" 43894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman#include "llvm/Support/raw_ostream.h" 44894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman#include "llvm/Support/IRBuilder.h" 4519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman#include "llvm/Support/ValueHandle.h" 46894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Baumanusing namespace llvm; 47894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Baumanusing namespace llvm::PatternMatch; 48894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 4919bac1e08be200c31efd26f0f5fd144c9b3eefd3John BaumanSTATISTIC(NumBlocksElim, "Number of blocks eliminated"); 5019bac1e08be200c31efd26f0f5fd144c9b3eefd3John BaumanSTATISTIC(NumPHIsElim, "Number of trivial PHIs eliminated"); 5119bac1e08be200c31efd26f0f5fd144c9b3eefd3John BaumanSTATISTIC(NumGEPsElim, "Number of GEPs converted to casts"); 5219bac1e08be200c31efd26f0f5fd144c9b3eefd3John BaumanSTATISTIC(NumCmpUses, "Number of uses of Cmp expressions replaced with uses of " 5319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman "sunken Cmps"); 5419bac1e08be200c31efd26f0f5fd144c9b3eefd3John BaumanSTATISTIC(NumCastUses, "Number of uses of Cast expressions replaced with uses " 5519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman "of sunken Casts"); 5619bac1e08be200c31efd26f0f5fd144c9b3eefd3John BaumanSTATISTIC(NumMemoryInsts, "Number of memory instructions whose address " 5719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman "computations were sunk"); 5819bac1e08be200c31efd26f0f5fd144c9b3eefd3John BaumanSTATISTIC(NumExtsMoved, "Number of [s|z]ext instructions combined with loads"); 5919bac1e08be200c31efd26f0f5fd144c9b3eefd3John BaumanSTATISTIC(NumExtUses, "Number of uses of [s|z]ext instructions optimized"); 6019bac1e08be200c31efd26f0f5fd144c9b3eefd3John BaumanSTATISTIC(NumRetsDup, "Number of return instructions duplicated"); 6119bac1e08be200c31efd26f0f5fd144c9b3eefd3John BaumanSTATISTIC(NumDbgValueMoved, "Number of debug value instructions moved"); 6219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 6319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Baumanstatic cl::opt<bool> DisableBranchOpts( 6419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman "disable-cgp-branch-opts", cl::Hidden, cl::init(false), 6519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman cl::desc("Disable branch optimizations in CodeGenPrepare")); 6619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 67894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Baumannamespace { 68894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman class CodeGenPrepare : public FunctionPass { 69894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman /// TLI - Keep a pointer of a TargetLowering to consult for determining 70894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman /// transformation profitability. 71894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman const TargetLowering *TLI; 7219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman DominatorTree *DT; 73894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman ProfileInfo *PFI; 7419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 7519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman /// CurInstIterator - As we scan instructions optimizing them, this is the 7619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman /// next instruction to optimize. Xforms that can invalidate this should 7719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman /// update it. 7819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman BasicBlock::iterator CurInstIterator; 7919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 8019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman /// Keeps track of non-local addresses that have been sunk into a block. 8119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman /// This allows us to avoid inserting duplicate code for blocks with 8219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman /// multiple load/stores of the same address. 8319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman DenseMap<Value*, Value*> SunkAddrs; 8419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 8519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman /// ModifiedDT - If CFG is modified in anyway, dominator tree may need to 8619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman /// be updated. 8719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman bool ModifiedDT; 88894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 89894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman public: 90894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman static char ID; // Pass identification, replacement for typeid 91894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman explicit CodeGenPrepare(const TargetLowering *tli = 0) 9219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman : FunctionPass(ID), TLI(tli) { 9319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman initializeCodeGenPreparePass(*PassRegistry::getPassRegistry()); 9419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman } 95894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman bool runOnFunction(Function &F); 96894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 97894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman virtual void getAnalysisUsage(AnalysisUsage &AU) const { 9819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman AU.addPreserved<DominatorTree>(); 99894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman AU.addPreserved<ProfileInfo>(); 100894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 101894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 102894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman private: 103894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman bool EliminateMostlyEmptyBlocks(Function &F); 104894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman bool CanMergeBlocks(const BasicBlock *BB, const BasicBlock *DestBB) const; 105894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman void EliminateMostlyEmptyBlock(BasicBlock *BB); 106894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman bool OptimizeBlock(BasicBlock &BB); 10719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman bool OptimizeInst(Instruction *I); 10819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman bool OptimizeMemoryInst(Instruction *I, Value *Addr, Type *AccessTy); 10919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman bool OptimizeInlineAsmInst(CallInst *CS); 110894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman bool OptimizeCallInst(CallInst *CI); 111894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman bool MoveExtToFormExtLoad(Instruction *I); 112894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman bool OptimizeExtUses(Instruction *I); 11319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman bool DupRetToEnableTailCallOpts(ReturnInst *RI); 11419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman bool PlaceDbgValues(Function &F); 115894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman }; 116894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman} 117894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 118894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Baumanchar CodeGenPrepare::ID = 0; 119894018228b0e0bdbd7aa7e8f47d4a9458789ca82John BaumanINITIALIZE_PASS(CodeGenPrepare, "codegenprepare", 12019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman "Optimize for code generation", false, false) 121894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 122894018228b0e0bdbd7aa7e8f47d4a9458789ca82John BaumanFunctionPass *llvm::createCodeGenPreparePass(const TargetLowering *TLI) { 123894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman return new CodeGenPrepare(TLI); 124894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman} 125894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 126894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Baumanbool CodeGenPrepare::runOnFunction(Function &F) { 127894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman bool EverMadeChange = false; 128894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 12919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman ModifiedDT = false; 13019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman DT = getAnalysisIfAvailable<DominatorTree>(); 131894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman PFI = getAnalysisIfAvailable<ProfileInfo>(); 13219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 133894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // First pass, eliminate blocks that contain only PHI nodes and an 134894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // unconditional branch. 135894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman EverMadeChange |= EliminateMostlyEmptyBlocks(F); 136894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 13719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // llvm.dbg.value is far away from the value then iSel may not be able 13819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // handle it properly. iSel will drop llvm.dbg.value if it can not 13919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // find a node corresponding to the value. 14019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman EverMadeChange |= PlaceDbgValues(F); 141894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 142894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman bool MadeChange = true; 143894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman while (MadeChange) { 144894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman MadeChange = false; 14519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman for (Function::iterator I = F.begin(), E = F.end(); I != E; ) { 14619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman BasicBlock *BB = I++; 147894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman MadeChange |= OptimizeBlock(*BB); 14819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman } 14919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman EverMadeChange |= MadeChange; 15019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman } 15119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 15219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman SunkAddrs.clear(); 15319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 15419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (!DisableBranchOpts) { 15519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman MadeChange = false; 15619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman for (Function::iterator BB = F.begin(), E = F.end(); BB != E; ++BB) 15719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman MadeChange |= ConstantFoldTerminator(BB, true); 15819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 15919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (MadeChange) 16019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman ModifiedDT = true; 161894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman EverMadeChange |= MadeChange; 162894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 16319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 16419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (ModifiedDT && DT) 16519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman DT->DT->recalculate(F); 16619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 167894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman return EverMadeChange; 168894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman} 169894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 170894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman/// EliminateMostlyEmptyBlocks - eliminate blocks that contain only PHI nodes, 171894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman/// debug info directives, and an unconditional branch. Passes before isel 172894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman/// (e.g. LSR/loopsimplify) often split edges in ways that are non-optimal for 173894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman/// isel. Start by eliminating these blocks so we can split them the way we 174894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman/// want them. 175894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Baumanbool CodeGenPrepare::EliminateMostlyEmptyBlocks(Function &F) { 176894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman bool MadeChange = false; 177894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // Note that this intentionally skips the entry block. 178894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman for (Function::iterator I = ++F.begin(), E = F.end(); I != E; ) { 179894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman BasicBlock *BB = I++; 180894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 181894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // If this block doesn't end with an uncond branch, ignore it. 182894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman BranchInst *BI = dyn_cast<BranchInst>(BB->getTerminator()); 183894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (!BI || !BI->isUnconditional()) 184894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman continue; 185894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 186894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // If the instruction before the branch (skipping debug info) isn't a phi 187894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // node, then other stuff is happening here. 188894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman BasicBlock::iterator BBI = BI; 189894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (BBI != BB->begin()) { 190894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman --BBI; 19119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman while (isa<DbgInfoIntrinsic>(BBI)) { 192894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (BBI == BB->begin()) 193894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman break; 194894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman --BBI; 195894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 19619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (!isa<DbgInfoIntrinsic>(BBI) && !isa<PHINode>(BBI)) 197894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman continue; 198894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 199894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 200894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // Do not break infinite loops. 201894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman BasicBlock *DestBB = BI->getSuccessor(0); 202894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (DestBB == BB) 203894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman continue; 204894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 205894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (!CanMergeBlocks(BB, DestBB)) 206894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman continue; 207894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 208894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman EliminateMostlyEmptyBlock(BB); 209894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman MadeChange = true; 210894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 211894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman return MadeChange; 212894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman} 213894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 214894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman/// CanMergeBlocks - Return true if we can merge BB into DestBB if there is a 215894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman/// single uncond branch between them, and BB contains no other non-phi 216894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman/// instructions. 217894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Baumanbool CodeGenPrepare::CanMergeBlocks(const BasicBlock *BB, 218894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman const BasicBlock *DestBB) const { 219894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // We only want to eliminate blocks whose phi nodes are used by phi nodes in 220894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // the successor. If there are more complex condition (e.g. preheaders), 221894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // don't mess around with them. 222894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman BasicBlock::const_iterator BBI = BB->begin(); 223894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman while (const PHINode *PN = dyn_cast<PHINode>(BBI++)) { 224894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman for (Value::const_use_iterator UI = PN->use_begin(), E = PN->use_end(); 225894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman UI != E; ++UI) { 226894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman const Instruction *User = cast<Instruction>(*UI); 227894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (User->getParent() != DestBB || !isa<PHINode>(User)) 228894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman return false; 229894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // If User is inside DestBB block and it is a PHINode then check 230894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // incoming value. If incoming value is not from BB then this is 231894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // a complex condition (e.g. preheaders) we want to avoid here. 232894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (User->getParent() == DestBB) { 233894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (const PHINode *UPN = dyn_cast<PHINode>(User)) 234894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman for (unsigned I = 0, E = UPN->getNumIncomingValues(); I != E; ++I) { 235894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman Instruction *Insn = dyn_cast<Instruction>(UPN->getIncomingValue(I)); 236894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (Insn && Insn->getParent() == BB && 237894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman Insn->getParent() != UPN->getIncomingBlock(I)) 238894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman return false; 239894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 240894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 241894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 242894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 243894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 244894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // If BB and DestBB contain any common predecessors, then the phi nodes in BB 245894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // and DestBB may have conflicting incoming values for the block. If so, we 246894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // can't merge the block. 247894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman const PHINode *DestBBPN = dyn_cast<PHINode>(DestBB->begin()); 248894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (!DestBBPN) return true; // no conflict. 249894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 250894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // Collect the preds of BB. 251894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman SmallPtrSet<const BasicBlock*, 16> BBPreds; 252894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (const PHINode *BBPN = dyn_cast<PHINode>(BB->begin())) { 253894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // It is faster to get preds from a PHI than with pred_iterator. 254894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman for (unsigned i = 0, e = BBPN->getNumIncomingValues(); i != e; ++i) 255894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman BBPreds.insert(BBPN->getIncomingBlock(i)); 256894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } else { 257894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman BBPreds.insert(pred_begin(BB), pred_end(BB)); 258894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 259894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 260894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // Walk the preds of DestBB. 261894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman for (unsigned i = 0, e = DestBBPN->getNumIncomingValues(); i != e; ++i) { 262894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman BasicBlock *Pred = DestBBPN->getIncomingBlock(i); 263894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (BBPreds.count(Pred)) { // Common predecessor? 264894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman BBI = DestBB->begin(); 265894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman while (const PHINode *PN = dyn_cast<PHINode>(BBI++)) { 266894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman const Value *V1 = PN->getIncomingValueForBlock(Pred); 267894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman const Value *V2 = PN->getIncomingValueForBlock(BB); 268894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 269894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // If V2 is a phi node in BB, look up what the mapped value will be. 270894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (const PHINode *V2PN = dyn_cast<PHINode>(V2)) 271894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (V2PN->getParent() == BB) 272894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman V2 = V2PN->getIncomingValueForBlock(Pred); 273894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 274894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // If there is a conflict, bail out. 275894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (V1 != V2) return false; 276894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 277894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 278894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 279894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 280894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman return true; 281894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman} 282894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 283894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 284894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman/// EliminateMostlyEmptyBlock - Eliminate a basic block that have only phi's and 285894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman/// an unconditional branch in it. 286894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Baumanvoid CodeGenPrepare::EliminateMostlyEmptyBlock(BasicBlock *BB) { 287894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman BranchInst *BI = cast<BranchInst>(BB->getTerminator()); 288894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman BasicBlock *DestBB = BI->getSuccessor(0); 289894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 290894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman DEBUG(dbgs() << "MERGING MOSTLY EMPTY BLOCKS - BEFORE:\n" << *BB << *DestBB); 291894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 292894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // If the destination block has a single pred, then this is a trivial edge, 293894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // just collapse it. 294894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (BasicBlock *SinglePred = DestBB->getSinglePredecessor()) { 295894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (SinglePred != DestBB) { 296894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // Remember if SinglePred was the entry block of the function. If so, we 297894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // will need to move BB back to the entry position. 298894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman bool isEntry = SinglePred == &SinglePred->getParent()->getEntryBlock(); 299894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman MergeBasicBlockIntoOnlyPred(DestBB, this); 300894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 301894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (isEntry && BB != &BB->getParent()->getEntryBlock()) 302894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman BB->moveBefore(&BB->getParent()->getEntryBlock()); 303894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 304894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman DEBUG(dbgs() << "AFTER:\n" << *DestBB << "\n\n\n"); 305894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman return; 306894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 307894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 308894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 309894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // Otherwise, we have multiple predecessors of BB. Update the PHIs in DestBB 310894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // to handle the new incoming edges it is about to have. 311894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman PHINode *PN; 312894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman for (BasicBlock::iterator BBI = DestBB->begin(); 313894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman (PN = dyn_cast<PHINode>(BBI)); ++BBI) { 314894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // Remove the incoming value for BB, and remember it. 315894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman Value *InVal = PN->removeIncomingValue(BB, false); 316894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 317894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // Two options: either the InVal is a phi node defined in BB or it is some 318894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // value that dominates BB. 319894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman PHINode *InValPhi = dyn_cast<PHINode>(InVal); 320894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (InValPhi && InValPhi->getParent() == BB) { 321894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // Add all of the input values of the input PHI as inputs of this phi. 322894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman for (unsigned i = 0, e = InValPhi->getNumIncomingValues(); i != e; ++i) 323894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman PN->addIncoming(InValPhi->getIncomingValue(i), 324894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman InValPhi->getIncomingBlock(i)); 325894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } else { 326894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // Otherwise, add one instance of the dominating value for each edge that 327894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // we will be adding. 328894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (PHINode *BBPN = dyn_cast<PHINode>(BB->begin())) { 329894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman for (unsigned i = 0, e = BBPN->getNumIncomingValues(); i != e; ++i) 330894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman PN->addIncoming(InVal, BBPN->getIncomingBlock(i)); 331894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } else { 332894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman for (pred_iterator PI = pred_begin(BB), E = pred_end(BB); PI != E; ++PI) 333894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman PN->addIncoming(InVal, *PI); 334894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 335894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 336894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 337894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 338894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // The PHIs are now updated, change everything that refers to BB to use 339894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // DestBB and remove BB. 340894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman BB->replaceAllUsesWith(DestBB); 34119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (DT && !ModifiedDT) { 34219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman BasicBlock *BBIDom = DT->getNode(BB)->getIDom()->getBlock(); 34319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman BasicBlock *DestBBIDom = DT->getNode(DestBB)->getIDom()->getBlock(); 34419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman BasicBlock *NewIDom = DT->findNearestCommonDominator(BBIDom, DestBBIDom); 34519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman DT->changeImmediateDominator(DestBB, NewIDom); 34619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman DT->eraseNode(BB); 34719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman } 348894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (PFI) { 349894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman PFI->replaceAllUses(BB, DestBB); 350894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman PFI->removeEdge(ProfileInfo::getEdge(BB, DestBB)); 351894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 352894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman BB->eraseFromParent(); 35319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman ++NumBlocksElim; 354894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 355894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman DEBUG(dbgs() << "AFTER:\n" << *DestBB << "\n\n\n"); 356894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman} 357894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 358894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman/// OptimizeNoopCopyExpression - If the specified cast instruction is a noop 359894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman/// copy (e.g. it's casting from one pointer type to another, i32->i8 on PPC), 360894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman/// sink it into user blocks to reduce the number of virtual 361894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman/// registers that must be created and coalesced. 362894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman/// 363894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman/// Return true if any changes are made. 364894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman/// 365894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Baumanstatic bool OptimizeNoopCopyExpression(CastInst *CI, const TargetLowering &TLI){ 366894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // If this is a noop copy, 367894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman EVT SrcVT = TLI.getValueType(CI->getOperand(0)->getType()); 368894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman EVT DstVT = TLI.getValueType(CI->getType()); 369894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 370894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // This is an fp<->int conversion? 371894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (SrcVT.isInteger() != DstVT.isInteger()) 372894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman return false; 373894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 374894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // If this is an extension, it will be a zero or sign extension, which 375894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // isn't a noop. 376894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (SrcVT.bitsLT(DstVT)) return false; 377894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 378894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // If these values will be promoted, find out what they will be promoted 379894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // to. This helps us consider truncates on PPC as noop copies when they 380894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // are. 38119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (TLI.getTypeAction(CI->getContext(), SrcVT) == 38219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman TargetLowering::TypePromoteInteger) 383894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman SrcVT = TLI.getTypeToTransformTo(CI->getContext(), SrcVT); 38419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (TLI.getTypeAction(CI->getContext(), DstVT) == 38519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman TargetLowering::TypePromoteInteger) 386894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman DstVT = TLI.getTypeToTransformTo(CI->getContext(), DstVT); 387894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 388894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // If, after promotion, these are the same types, this is a noop copy. 389894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (SrcVT != DstVT) 390894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman return false; 391894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 392894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman BasicBlock *DefBB = CI->getParent(); 393894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 394894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman /// InsertedCasts - Only insert a cast in each block once. 395894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman DenseMap<BasicBlock*, CastInst*> InsertedCasts; 396894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 397894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman bool MadeChange = false; 398894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman for (Value::use_iterator UI = CI->use_begin(), E = CI->use_end(); 399894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman UI != E; ) { 400894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman Use &TheUse = UI.getUse(); 401894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman Instruction *User = cast<Instruction>(*UI); 402894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 403894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // Figure out which BB this cast is used in. For PHI's this is the 404894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // appropriate predecessor block. 405894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman BasicBlock *UserBB = User->getParent(); 406894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (PHINode *PN = dyn_cast<PHINode>(User)) { 407894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman UserBB = PN->getIncomingBlock(UI); 408894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 409894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 410894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // Preincrement use iterator so we don't invalidate it. 411894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman ++UI; 412894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 413894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // If this user is in the same block as the cast, don't change the cast. 414894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (UserBB == DefBB) continue; 415894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 416894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // If we have already inserted a cast into this block, use it. 417894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman CastInst *&InsertedCast = InsertedCasts[UserBB]; 418894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 419894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (!InsertedCast) { 42019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman BasicBlock::iterator InsertPt = UserBB->getFirstInsertionPt(); 421894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman InsertedCast = 42219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman CastInst::Create(CI->getOpcode(), CI->getOperand(0), CI->getType(), "", 423894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman InsertPt); 424894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman MadeChange = true; 425894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 426894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 427894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // Replace a use of the cast with a use of the new cast. 428894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman TheUse = InsertedCast; 42919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman ++NumCastUses; 430894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 431894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 432894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // If we removed all uses, nuke the cast. 433894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (CI->use_empty()) { 434894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman CI->eraseFromParent(); 435894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman MadeChange = true; 436894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 437894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 438894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman return MadeChange; 439894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman} 440894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 441894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman/// OptimizeCmpExpression - sink the given CmpInst into user blocks to reduce 442894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman/// the number of virtual registers that must be created and coalesced. This is 443894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman/// a clear win except on targets with multiple condition code registers 444894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman/// (PowerPC), where it might lose; some adjustment may be wanted there. 445894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman/// 446894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman/// Return true if any changes are made. 447894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Baumanstatic bool OptimizeCmpExpression(CmpInst *CI) { 448894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman BasicBlock *DefBB = CI->getParent(); 449894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 450894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman /// InsertedCmp - Only insert a cmp in each block once. 451894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman DenseMap<BasicBlock*, CmpInst*> InsertedCmps; 452894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 453894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman bool MadeChange = false; 454894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman for (Value::use_iterator UI = CI->use_begin(), E = CI->use_end(); 455894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman UI != E; ) { 456894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman Use &TheUse = UI.getUse(); 457894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman Instruction *User = cast<Instruction>(*UI); 458894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 459894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // Preincrement use iterator so we don't invalidate it. 460894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman ++UI; 461894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 462894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // Don't bother for PHI nodes. 463894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (isa<PHINode>(User)) 464894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman continue; 465894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 466894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // Figure out which BB this cmp is used in. 467894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman BasicBlock *UserBB = User->getParent(); 468894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 469894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // If this user is in the same block as the cmp, don't change the cmp. 470894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (UserBB == DefBB) continue; 471894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 472894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // If we have already inserted a cmp into this block, use it. 473894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman CmpInst *&InsertedCmp = InsertedCmps[UserBB]; 474894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 475894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (!InsertedCmp) { 47619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman BasicBlock::iterator InsertPt = UserBB->getFirstInsertionPt(); 477894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman InsertedCmp = 478894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman CmpInst::Create(CI->getOpcode(), 479894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman CI->getPredicate(), CI->getOperand(0), 48019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman CI->getOperand(1), "", InsertPt); 481894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman MadeChange = true; 482894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 483894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 484894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // Replace a use of the cmp with a use of the new cmp. 485894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman TheUse = InsertedCmp; 48619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman ++NumCmpUses; 487894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 488894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 489894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // If we removed all uses, nuke the cmp. 490894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (CI->use_empty()) 491894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman CI->eraseFromParent(); 492894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 493894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman return MadeChange; 494894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman} 495894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 49619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Baumannamespace { 49719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Baumanclass CodeGenPrepareFortifiedLibCalls : public SimplifyFortifiedLibCalls { 49819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Baumanprotected: 49919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman void replaceCall(Value *With) { 50019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman CI->replaceAllUsesWith(With); 50119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman CI->eraseFromParent(); 50219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman } 50319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman bool isFoldable(unsigned SizeCIOp, unsigned, bool) const { 50419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (ConstantInt *SizeCI = 50519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman dyn_cast<ConstantInt>(CI->getArgOperand(SizeCIOp))) 50619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman return SizeCI->isAllOnesValue(); 50719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman return false; 50819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman } 50919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman}; 51019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman} // end anonymous namespace 51119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 512894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Baumanbool CodeGenPrepare::OptimizeCallInst(CallInst *CI) { 51319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman BasicBlock *BB = CI->getParent(); 51419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 51519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // Lower inline assembly if we can. 51619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // If we found an inline asm expession, and if the target knows how to 51719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // lower it to normal LLVM code, do so now. 51819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (TLI && isa<InlineAsm>(CI->getCalledValue())) { 51919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (TLI->ExpandInlineAsm(CI)) { 52019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // Avoid invalidating the iterator. 52119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman CurInstIterator = BB->begin(); 52219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // Avoid processing instructions out of order, which could cause 52319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // reuse before a value is defined. 52419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman SunkAddrs.clear(); 52519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman return true; 52619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman } 52719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // Sink address computing for memory operands into the block. 52819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (OptimizeInlineAsmInst(CI)) 52919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman return true; 53019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman } 53119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 532894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // Lower all uses of llvm.objectsize.* 533894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman IntrinsicInst *II = dyn_cast<IntrinsicInst>(CI); 534894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (II && II->getIntrinsicID() == Intrinsic::objectsize) { 535894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman bool Min = (cast<ConstantInt>(II->getArgOperand(1))->getZExtValue() == 1); 53619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman Type *ReturnTy = CI->getType(); 537894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman Constant *RetVal = ConstantInt::get(ReturnTy, Min ? 0 : -1ULL); 53819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 53919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // Substituting this can cause recursive simplifications, which can 54019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // invalidate our iterator. Use a WeakVH to hold onto it in case this 54119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // happens. 54219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman WeakVH IterHandle(CurInstIterator); 54319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 54419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman ReplaceAndSimplifyAllUses(CI, RetVal, TLI ? TLI->getTargetData() : 0, 54519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman ModifiedDT ? 0 : DT); 54619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 54719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // If the iterator instruction was recursively deleted, start over at the 54819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // start of the block. 54919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (IterHandle != CurInstIterator) { 55019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman CurInstIterator = BB->begin(); 55119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman SunkAddrs.clear(); 55219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman } 553894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman return true; 554894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 55519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 55619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // From here on out we're working with named functions. 55719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (CI->getCalledFunction() == 0) return false; 55819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 55919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // We'll need TargetData from here on out. 56019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman const TargetData *TD = TLI ? TLI->getTargetData() : 0; 56119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (!TD) return false; 562894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 56319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // Lower all default uses of _chk calls. This is very similar 56419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // to what InstCombineCalls does, but here we are only lowering calls 56519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // that have the default "don't know" as the objectsize. Anything else 56619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // should be left alone. 56719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman CodeGenPrepareFortifiedLibCalls Simplifier; 56819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman return Simplifier.fold(CI, TD); 569894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman} 57019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 57119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman/// DupRetToEnableTailCallOpts - Look for opportunities to duplicate return 57219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman/// instructions to the predecessor to enable tail call optimizations. The 57319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman/// case it is currently looking for is: 57419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman/// bb0: 57519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman/// %tmp0 = tail call i32 @f0() 57619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman/// br label %return 57719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman/// bb1: 57819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman/// %tmp1 = tail call i32 @f1() 57919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman/// br label %return 58019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman/// bb2: 58119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman/// %tmp2 = tail call i32 @f2() 58219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman/// br label %return 58319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman/// return: 58419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman/// %retval = phi i32 [ %tmp0, %bb0 ], [ %tmp1, %bb1 ], [ %tmp2, %bb2 ] 58519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman/// ret i32 %retval 58619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman/// 58719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman/// => 58819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman/// 58919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman/// bb0: 59019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman/// %tmp0 = tail call i32 @f0() 59119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman/// ret i32 %tmp0 59219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman/// bb1: 59319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman/// %tmp1 = tail call i32 @f1() 59419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman/// ret i32 %tmp1 59519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman/// bb2: 59619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman/// %tmp2 = tail call i32 @f2() 59719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman/// ret i32 %tmp2 59819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman/// 59919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Baumanbool CodeGenPrepare::DupRetToEnableTailCallOpts(ReturnInst *RI) { 60019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (!TLI) 60119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman return false; 60219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 60319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman Value *V = RI->getReturnValue(); 60419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman PHINode *PN = V ? dyn_cast<PHINode>(V) : NULL; 60519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (V && !PN) 60619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman return false; 60719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 60819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman BasicBlock *BB = RI->getParent(); 60919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (PN && PN->getParent() != BB) 61019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman return false; 61119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 61219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // It's not safe to eliminate the sign / zero extension of the return value. 61319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // See llvm::isInTailCallPosition(). 61419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman const Function *F = BB->getParent(); 61519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman unsigned CallerRetAttr = F->getAttributes().getRetAttributes(); 61619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if ((CallerRetAttr & Attribute::ZExt) || (CallerRetAttr & Attribute::SExt)) 61719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman return false; 61819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 61919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // Make sure there are no instructions between the PHI and return, or that the 62019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // return is the first instruction in the block. 62119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (PN) { 62219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman BasicBlock::iterator BI = BB->begin(); 62319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman do { ++BI; } while (isa<DbgInfoIntrinsic>(BI)); 62419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (&*BI != RI) 62519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman return false; 62619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman } else { 62719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman BasicBlock::iterator BI = BB->begin(); 62819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman while (isa<DbgInfoIntrinsic>(BI)) ++BI; 62919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (&*BI != RI) 63019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman return false; 63119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman } 63219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 63319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman /// Only dup the ReturnInst if the CallInst is likely to be emitted as a tail 63419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman /// call. 63519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman SmallVector<CallInst*, 4> TailCalls; 63619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (PN) { 63719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman for (unsigned I = 0, E = PN->getNumIncomingValues(); I != E; ++I) { 63819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman CallInst *CI = dyn_cast<CallInst>(PN->getIncomingValue(I)); 63919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // Make sure the phi value is indeed produced by the tail call. 64019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (CI && CI->hasOneUse() && CI->getParent() == PN->getIncomingBlock(I) && 64119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman TLI->mayBeEmittedAsTailCall(CI)) 64219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman TailCalls.push_back(CI); 64319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman } 64419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman } else { 64519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman SmallPtrSet<BasicBlock*, 4> VisitedBBs; 64619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman for (pred_iterator PI = pred_begin(BB), PE = pred_end(BB); PI != PE; ++PI) { 64719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (!VisitedBBs.insert(*PI)) 64819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman continue; 64919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 65019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman BasicBlock::InstListType &InstList = (*PI)->getInstList(); 65119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman BasicBlock::InstListType::reverse_iterator RI = InstList.rbegin(); 65219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman BasicBlock::InstListType::reverse_iterator RE = InstList.rend(); 65319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman do { ++RI; } while (RI != RE && isa<DbgInfoIntrinsic>(&*RI)); 65419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (RI == RE) 65519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman continue; 65619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 65719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman CallInst *CI = dyn_cast<CallInst>(&*RI); 65819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (CI && CI->use_empty() && TLI->mayBeEmittedAsTailCall(CI)) 65919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman TailCalls.push_back(CI); 66019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman } 66119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman } 66219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 66319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman bool Changed = false; 66419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman for (unsigned i = 0, e = TailCalls.size(); i != e; ++i) { 66519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman CallInst *CI = TailCalls[i]; 66619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman CallSite CS(CI); 66719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 66819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // Conservatively require the attributes of the call to match those of the 66919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // return. Ignore noalias because it doesn't affect the call sequence. 67019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman unsigned CalleeRetAttr = CS.getAttributes().getRetAttributes(); 67119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if ((CalleeRetAttr ^ CallerRetAttr) & ~Attribute::NoAlias) 67219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman continue; 67319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 67419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // Make sure the call instruction is followed by an unconditional branch to 67519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // the return block. 67619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman BasicBlock *CallBB = CI->getParent(); 67719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman BranchInst *BI = dyn_cast<BranchInst>(CallBB->getTerminator()); 67819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (!BI || !BI->isUnconditional() || BI->getSuccessor(0) != BB) 67919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman continue; 68019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 68119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // Duplicate the return into CallBB. 68219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman (void)FoldReturnIntoUncondBranch(RI, BB, CallBB); 68319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman ModifiedDT = Changed = true; 68419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman ++NumRetsDup; 68519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman } 68619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 68719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // If we eliminated all predecessors of the block, delete the block now. 68819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (Changed && pred_begin(BB) == pred_end(BB)) 68919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman BB->eraseFromParent(); 69019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 69119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman return Changed; 69219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman} 69319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 694894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman//===----------------------------------------------------------------------===// 695894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman// Memory Optimization 696894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman//===----------------------------------------------------------------------===// 697894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 698894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman/// IsNonLocalValue - Return true if the specified values are defined in a 699894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman/// different basic block than BB. 700894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Baumanstatic bool IsNonLocalValue(Value *V, BasicBlock *BB) { 701894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (Instruction *I = dyn_cast<Instruction>(V)) 702894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman return I->getParent() != BB; 703894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman return false; 704894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman} 705894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 706894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman/// OptimizeMemoryInst - Load and Store Instructions often have 707894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman/// addressing modes that can do significant amounts of computation. As such, 708894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman/// instruction selection will try to get the load or store to do as much 709894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman/// computation as possible for the program. The problem is that isel can only 710894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman/// see within a single block. As such, we sink as much legal addressing mode 711894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman/// stuff into the block as possible. 712894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman/// 713894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman/// This method is used to optimize both load/store and inline asms with memory 714894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman/// operands. 715894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Baumanbool CodeGenPrepare::OptimizeMemoryInst(Instruction *MemoryInst, Value *Addr, 71619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman Type *AccessTy) { 71719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman Value *Repl = Addr; 71819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 71919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // Try to collapse single-value PHI nodes. This is necessary to undo 72019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // unprofitable PRE transformations. 72119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman SmallVector<Value*, 8> worklist; 72219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman SmallPtrSet<Value*, 16> Visited; 72319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman worklist.push_back(Addr); 72419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 72519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // Use a worklist to iteratively look through PHI nodes, and ensure that 72619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // the addressing mode obtained from the non-PHI roots of the graph 72719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // are equivalent. 72819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman Value *Consensus = 0; 72919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman unsigned NumUsesConsensus = 0; 73019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman bool IsNumUsesConsensusValid = false; 731894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman SmallVector<Instruction*, 16> AddrModeInsts; 73219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman ExtAddrMode AddrMode; 73319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman while (!worklist.empty()) { 73419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman Value *V = worklist.back(); 73519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman worklist.pop_back(); 73619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 73719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // Break use-def graph loops. 73819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (!Visited.insert(V)) { 73919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman Consensus = 0; 74019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman break; 74119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman } 74219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 74319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // For a PHI node, push all of its incoming values. 74419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (PHINode *P = dyn_cast<PHINode>(V)) { 74519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman for (unsigned i = 0, e = P->getNumIncomingValues(); i != e; ++i) 74619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman worklist.push_back(P->getIncomingValue(i)); 74719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman continue; 74819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman } 74919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 75019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // For non-PHIs, determine the addressing mode being computed. 75119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman SmallVector<Instruction*, 16> NewAddrModeInsts; 75219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman ExtAddrMode NewAddrMode = 75319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman AddressingModeMatcher::Match(V, AccessTy, MemoryInst, 75419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman NewAddrModeInsts, *TLI); 75519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 75619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // This check is broken into two cases with very similar code to avoid using 75719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // getNumUses() as much as possible. Some values have a lot of uses, so 75819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // calling getNumUses() unconditionally caused a significant compile-time 75919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // regression. 76019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (!Consensus) { 76119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman Consensus = V; 76219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman AddrMode = NewAddrMode; 76319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman AddrModeInsts = NewAddrModeInsts; 76419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman continue; 76519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman } else if (NewAddrMode == AddrMode) { 76619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (!IsNumUsesConsensusValid) { 76719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman NumUsesConsensus = Consensus->getNumUses(); 76819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman IsNumUsesConsensusValid = true; 76919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman } 770894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 77119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // Ensure that the obtained addressing mode is equivalent to that obtained 77219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // for all other roots of the PHI traversal. Also, when choosing one 77319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // such root as representative, select the one with the most uses in order 77419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // to keep the cost modeling heuristics in AddressingModeMatcher 77519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // applicable. 77619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman unsigned NumUses = V->getNumUses(); 77719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (NumUses > NumUsesConsensus) { 77819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman Consensus = V; 77919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman NumUsesConsensus = NumUses; 78019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman AddrModeInsts = NewAddrModeInsts; 78119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman } 78219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman continue; 78319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman } 78419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 78519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman Consensus = 0; 78619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman break; 78719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman } 78819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 78919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // If the addressing mode couldn't be determined, or if multiple different 79019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // ones were determined, bail out now. 79119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (!Consensus) return false; 79219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 793894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // Check to see if any of the instructions supersumed by this addr mode are 794894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // non-local to I's BB. 795894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman bool AnyNonLocal = false; 796894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman for (unsigned i = 0, e = AddrModeInsts.size(); i != e; ++i) { 797894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (IsNonLocalValue(AddrModeInsts[i], MemoryInst->getParent())) { 798894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman AnyNonLocal = true; 799894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman break; 800894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 801894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 802894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 803894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // If all the instructions matched are already in this BB, don't do anything. 804894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (!AnyNonLocal) { 805894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman DEBUG(dbgs() << "CGP: Found local addrmode: " << AddrMode << "\n"); 806894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman return false; 807894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 808894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 809894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // Insert this computation right after this user. Since our caller is 810894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // scanning from the top of the BB to the bottom, reuse of the expr are 811894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // guaranteed to happen later. 81219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman IRBuilder<> Builder(MemoryInst); 813894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 814894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // Now that we determined the addressing expression we want to use and know 815894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // that we have to sink it into this block. Check to see if we have already 816894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // done this for some other load/store instr in this block. If so, reuse the 817894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // computation. 818894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman Value *&SunkAddr = SunkAddrs[Addr]; 819894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (SunkAddr) { 820894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman DEBUG(dbgs() << "CGP: Reusing nonlocal addrmode: " << AddrMode << " for " 821894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman << *MemoryInst); 822894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (SunkAddr->getType() != Addr->getType()) 82319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman SunkAddr = Builder.CreateBitCast(SunkAddr, Addr->getType()); 824894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } else { 825894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman DEBUG(dbgs() << "CGP: SINKING nonlocal addrmode: " << AddrMode << " for " 826894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman << *MemoryInst); 82719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman Type *IntPtrTy = 828894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman TLI->getTargetData()->getIntPtrType(AccessTy->getContext()); 829894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 830894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman Value *Result = 0; 831894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 832894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // Start with the base register. Do this first so that subsequent address 833894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // matching finds it last, which will prevent it from trying to match it 834894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // as the scaled value in case it happens to be a mul. That would be 835894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // problematic if we've sunk a different mul for the scale, because then 836894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // we'd end up sinking both muls. 837894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (AddrMode.BaseReg) { 838894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman Value *V = AddrMode.BaseReg; 839894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (V->getType()->isPointerTy()) 84019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman V = Builder.CreatePtrToInt(V, IntPtrTy, "sunkaddr"); 841894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (V->getType() != IntPtrTy) 84219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman V = Builder.CreateIntCast(V, IntPtrTy, /*isSigned=*/true, "sunkaddr"); 843894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman Result = V; 844894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 845894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 846894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // Add the scale value. 847894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (AddrMode.Scale) { 848894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman Value *V = AddrMode.ScaledReg; 849894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (V->getType() == IntPtrTy) { 850894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // done. 851894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } else if (V->getType()->isPointerTy()) { 85219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman V = Builder.CreatePtrToInt(V, IntPtrTy, "sunkaddr"); 853894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } else if (cast<IntegerType>(IntPtrTy)->getBitWidth() < 854894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman cast<IntegerType>(V->getType())->getBitWidth()) { 85519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman V = Builder.CreateTrunc(V, IntPtrTy, "sunkaddr"); 856894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } else { 85719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman V = Builder.CreateSExt(V, IntPtrTy, "sunkaddr"); 858894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 859894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (AddrMode.Scale != 1) 86019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman V = Builder.CreateMul(V, ConstantInt::get(IntPtrTy, AddrMode.Scale), 86119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman "sunkaddr"); 862894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (Result) 86319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman Result = Builder.CreateAdd(Result, V, "sunkaddr"); 864894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman else 865894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman Result = V; 866894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 867894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 868894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // Add in the BaseGV if present. 869894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (AddrMode.BaseGV) { 87019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman Value *V = Builder.CreatePtrToInt(AddrMode.BaseGV, IntPtrTy, "sunkaddr"); 871894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (Result) 87219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman Result = Builder.CreateAdd(Result, V, "sunkaddr"); 873894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman else 874894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman Result = V; 875894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 876894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 877894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // Add in the Base Offset if present. 878894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (AddrMode.BaseOffs) { 879894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman Value *V = ConstantInt::get(IntPtrTy, AddrMode.BaseOffs); 880894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (Result) 88119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman Result = Builder.CreateAdd(Result, V, "sunkaddr"); 882894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman else 883894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman Result = V; 884894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 885894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 886894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (Result == 0) 887894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman SunkAddr = Constant::getNullValue(Addr->getType()); 888894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman else 88919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman SunkAddr = Builder.CreateIntToPtr(Result, Addr->getType(), "sunkaddr"); 890894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 891894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 89219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman MemoryInst->replaceUsesOfWith(Repl, SunkAddr); 89319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 89419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // If we have no uses, recursively delete the value and all dead instructions 89519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // using it. 89619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (Repl->use_empty()) { 89719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // This can cause recursive deletion, which can invalidate our iterator. 89819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // Use a WeakVH to hold onto it in case this happens. 89919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman WeakVH IterHandle(CurInstIterator); 90019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman BasicBlock *BB = CurInstIterator->getParent(); 90119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 90219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman RecursivelyDeleteTriviallyDeadInstructions(Repl); 903894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 90419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (IterHandle != CurInstIterator) { 90519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // If the iterator instruction was recursively deleted, start over at the 90619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // start of the block. 90719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman CurInstIterator = BB->begin(); 90819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman SunkAddrs.clear(); 90919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman } else { 91019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // This address is now available for reassignment, so erase the table 91119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // entry; we don't want to match some completely different instruction. 91219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman SunkAddrs[Addr] = 0; 91319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman } 914894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 91519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman ++NumMemoryInsts; 916894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman return true; 917894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman} 918894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 919894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman/// OptimizeInlineAsmInst - If there are any memory operands, use 920894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman/// OptimizeMemoryInst to sink their address computing into the block when 921894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman/// possible / profitable. 92219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Baumanbool CodeGenPrepare::OptimizeInlineAsmInst(CallInst *CS) { 923894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman bool MadeChange = false; 924894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 92519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman TargetLowering::AsmOperandInfoVector 92619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman TargetConstraints = TLI->ParseConstraints(CS); 92719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman unsigned ArgNo = 0; 92819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman for (unsigned i = 0, e = TargetConstraints.size(); i != e; ++i) { 92919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman TargetLowering::AsmOperandInfo &OpInfo = TargetConstraints[i]; 93019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 931894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // Compute the constraint code and ConstraintType to use. 932894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman TLI->ComputeConstraintToUse(OpInfo, SDValue()); 933894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 934894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (OpInfo.ConstraintType == TargetLowering::C_Memory && 935894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman OpInfo.isIndirect) { 93619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman Value *OpVal = CS->getArgOperand(ArgNo++); 93719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman MadeChange |= OptimizeMemoryInst(CS, OpVal, OpVal->getType()); 93819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman } else if (OpInfo.Type == InlineAsm::isInput) 93919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman ArgNo++; 940894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 941894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 942894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman return MadeChange; 943894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman} 944894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 945894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman/// MoveExtToFormExtLoad - Move a zext or sext fed by a load into the same 946894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman/// basic block as the load, unless conditions are unfavorable. This allows 947894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman/// SelectionDAG to fold the extend into the load. 948894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman/// 949894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Baumanbool CodeGenPrepare::MoveExtToFormExtLoad(Instruction *I) { 950894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // Look for a load being extended. 951894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman LoadInst *LI = dyn_cast<LoadInst>(I->getOperand(0)); 952894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (!LI) return false; 953894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 954894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // If they're already in the same block, there's nothing to do. 955894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (LI->getParent() == I->getParent()) 956894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman return false; 957894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 958894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // If the load has other users and the truncate is not free, this probably 959894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // isn't worthwhile. 960894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (!LI->hasOneUse() && 96119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman TLI && (TLI->isTypeLegal(TLI->getValueType(LI->getType())) || 96219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman !TLI->isTypeLegal(TLI->getValueType(I->getType()))) && 96319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman !TLI->isTruncateFree(I->getType(), LI->getType())) 964894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman return false; 965894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 966894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // Check whether the target supports casts folded into loads. 967894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman unsigned LType; 968894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (isa<ZExtInst>(I)) 969894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman LType = ISD::ZEXTLOAD; 970894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman else { 971894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman assert(isa<SExtInst>(I) && "Unexpected ext type!"); 972894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman LType = ISD::SEXTLOAD; 973894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 974894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (TLI && !TLI->isLoadExtLegal(LType, TLI->getValueType(LI->getType()))) 975894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman return false; 976894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 977894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // Move the extend into the same block as the load, so that SelectionDAG 978894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // can fold it. 979894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman I->removeFromParent(); 980894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman I->insertAfter(LI); 98119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman ++NumExtsMoved; 982894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman return true; 983894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman} 984894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 985894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Baumanbool CodeGenPrepare::OptimizeExtUses(Instruction *I) { 986894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman BasicBlock *DefBB = I->getParent(); 987894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 98819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // If the result of a {s|z}ext and its source are both live out, rewrite all 989894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // other uses of the source with result of extension. 990894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman Value *Src = I->getOperand(0); 991894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (Src->hasOneUse()) 992894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman return false; 993894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 994894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // Only do this xform if truncating is free. 995894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (TLI && !TLI->isTruncateFree(I->getType(), Src->getType())) 996894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman return false; 997894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 998894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // Only safe to perform the optimization if the source is also defined in 999894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // this block. 1000894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (!isa<Instruction>(Src) || DefBB != cast<Instruction>(Src)->getParent()) 1001894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman return false; 1002894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 1003894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman bool DefIsLiveOut = false; 1004894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman for (Value::use_iterator UI = I->use_begin(), E = I->use_end(); 1005894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman UI != E; ++UI) { 1006894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman Instruction *User = cast<Instruction>(*UI); 1007894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 1008894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // Figure out which BB this ext is used in. 1009894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman BasicBlock *UserBB = User->getParent(); 1010894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (UserBB == DefBB) continue; 1011894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman DefIsLiveOut = true; 1012894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman break; 1013894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 1014894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (!DefIsLiveOut) 1015894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman return false; 1016894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 1017894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // Make sure non of the uses are PHI nodes. 1018894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman for (Value::use_iterator UI = Src->use_begin(), E = Src->use_end(); 1019894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman UI != E; ++UI) { 1020894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman Instruction *User = cast<Instruction>(*UI); 1021894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman BasicBlock *UserBB = User->getParent(); 1022894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (UserBB == DefBB) continue; 1023894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // Be conservative. We don't want this xform to end up introducing 1024894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // reloads just before load / store instructions. 1025894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (isa<PHINode>(User) || isa<LoadInst>(User) || isa<StoreInst>(User)) 1026894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman return false; 1027894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 1028894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 1029894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // InsertedTruncs - Only insert one trunc in each block once. 1030894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman DenseMap<BasicBlock*, Instruction*> InsertedTruncs; 1031894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 1032894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman bool MadeChange = false; 1033894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman for (Value::use_iterator UI = Src->use_begin(), E = Src->use_end(); 1034894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman UI != E; ++UI) { 1035894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman Use &TheUse = UI.getUse(); 1036894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman Instruction *User = cast<Instruction>(*UI); 1037894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 1038894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // Figure out which BB this ext is used in. 1039894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman BasicBlock *UserBB = User->getParent(); 1040894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (UserBB == DefBB) continue; 1041894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 1042894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // Both src and def are live in this block. Rewrite the use. 1043894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman Instruction *&InsertedTrunc = InsertedTruncs[UserBB]; 1044894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 1045894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (!InsertedTrunc) { 104619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman BasicBlock::iterator InsertPt = UserBB->getFirstInsertionPt(); 104719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman InsertedTrunc = new TruncInst(I, Src->getType(), "", InsertPt); 1048894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 1049894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 1050894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // Replace a use of the {s|z}ext source with a use of the result. 1051894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman TheUse = InsertedTrunc; 105219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman ++NumExtUses; 1053894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman MadeChange = true; 1054894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 1055894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 1056894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman return MadeChange; 1057894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman} 1058894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 105919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Baumanbool CodeGenPrepare::OptimizeInst(Instruction *I) { 106019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (PHINode *P = dyn_cast<PHINode>(I)) { 106119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // It is possible for very late stage optimizations (such as SimplifyCFG) 106219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // to introduce PHI nodes too late to be cleaned up. If we detect such a 106319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // trivial PHI, go ahead and zap it here. 106419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (Value *V = SimplifyInstruction(P)) { 106519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman P->replaceAllUsesWith(V); 106619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman P->eraseFromParent(); 106719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman ++NumPHIsElim; 106819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman return true; 106919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman } 107019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman return false; 107119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman } 107219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 107319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (CastInst *CI = dyn_cast<CastInst>(I)) { 107419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // If the source of the cast is a constant, then this should have 107519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // already been constant folded. The only reason NOT to constant fold 107619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // it is if something (e.g. LSR) was careful to place the constant 107719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // evaluation in a block other than then one that uses it (e.g. to hoist 107819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // the address of globals out of a loop). If this is the case, we don't 107919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // want to forward-subst the cast. 108019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (isa<Constant>(CI->getOperand(0))) 108119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman return false; 108219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 108319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (TLI && OptimizeNoopCopyExpression(CI, *TLI)) 108419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman return true; 108519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 108619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (isa<ZExtInst>(I) || isa<SExtInst>(I)) { 108719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman bool MadeChange = MoveExtToFormExtLoad(I); 108819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman return MadeChange | OptimizeExtUses(I); 108919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman } 109019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman return false; 109119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman } 109219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 109319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (CmpInst *CI = dyn_cast<CmpInst>(I)) 109419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman return OptimizeCmpExpression(CI); 109519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 109619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (LoadInst *LI = dyn_cast<LoadInst>(I)) { 109719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (TLI) 109819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman return OptimizeMemoryInst(I, I->getOperand(0), LI->getType()); 109919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman return false; 110019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman } 110119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 110219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (StoreInst *SI = dyn_cast<StoreInst>(I)) { 110319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (TLI) 110419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman return OptimizeMemoryInst(I, SI->getOperand(1), 110519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman SI->getOperand(0)->getType()); 110619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman return false; 110719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman } 110819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 110919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (GetElementPtrInst *GEPI = dyn_cast<GetElementPtrInst>(I)) { 111019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (GEPI->hasAllZeroIndices()) { 111119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman /// The GEP operand must be a pointer, so must its result -> BitCast 111219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman Instruction *NC = new BitCastInst(GEPI->getOperand(0), GEPI->getType(), 111319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman GEPI->getName(), GEPI); 111419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman GEPI->replaceAllUsesWith(NC); 111519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman GEPI->eraseFromParent(); 111619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman ++NumGEPsElim; 111719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman OptimizeInst(NC); 111819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman return true; 111919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman } 112019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman return false; 112119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman } 112219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 112319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (CallInst *CI = dyn_cast<CallInst>(I)) 112419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman return OptimizeCallInst(CI); 112519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 112619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (ReturnInst *RI = dyn_cast<ReturnInst>(I)) 112719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman return DupRetToEnableTailCallOpts(RI); 112819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 112919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman return false; 113019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman} 113119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 1132894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman// In this pass we look for GEP and cast instructions that are used 1133894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman// across basic blocks and rewrite them to improve basic-block-at-a-time 1134894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman// selection. 1135894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Baumanbool CodeGenPrepare::OptimizeBlock(BasicBlock &BB) { 113619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman SunkAddrs.clear(); 1137894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman bool MadeChange = false; 1138894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 113919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman CurInstIterator = BB.begin(); 114019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman for (BasicBlock::iterator E = BB.end(); CurInstIterator != E; ) 114119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman MadeChange |= OptimizeInst(CurInstIterator++); 1142894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 114319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman return MadeChange; 114419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman} 1145894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 114619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman// llvm.dbg.value is far away from the value then iSel may not be able 114719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman// handle it properly. iSel will drop llvm.dbg.value if it can not 114819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman// find a node corresponding to the value. 114919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Baumanbool CodeGenPrepare::PlaceDbgValues(Function &F) { 115019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman bool MadeChange = false; 115119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman for (Function::iterator I = F.begin(), E = F.end(); I != E; ++I) { 115219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman Instruction *PrevNonDbgInst = NULL; 115319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman for (BasicBlock::iterator BI = I->begin(), BE = I->end(); BI != BE;) { 115419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman Instruction *Insn = BI; ++BI; 115519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman DbgValueInst *DVI = dyn_cast<DbgValueInst>(Insn); 115619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (!DVI) { 115719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman PrevNonDbgInst = Insn; 1158894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman continue; 1159894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 1160894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 116119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman Instruction *VI = dyn_cast_or_null<Instruction>(DVI->getValue()); 116219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (VI && VI != PrevNonDbgInst && !VI->isTerminator()) { 116319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman DEBUG(dbgs() << "Moving Debug Value before :\n" << *DVI << ' ' << *VI); 116419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman DVI->removeFromParent(); 116519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (isa<PHINode>(VI)) 116619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman DVI->insertBefore(VI->getParent()->getFirstInsertionPt()); 116719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman else 116819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman DVI->insertAfter(VI); 1169894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman MadeChange = true; 117019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman ++NumDbgValueMoved; 1171894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 1172894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 1173894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 1174894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman return MadeChange; 1175894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman} 1176