LCOV - code coverage report
Current view: top level - include/llvm/Transforms/Utils - Local.h (source / functions) Hit Total Coverage
Test: llvm-toolchain.info Lines: 36 36 100.0 %
Date: 2017-09-14 15:23:50 Functions: 2 2 100.0 %
Legend: Lines: hit not hit

          Line data    Source code
       1             : //===-- Local.h - Functions to perform local transformations ----*- C++ -*-===//
       2             : //
       3             : //                     The LLVM Compiler Infrastructure
       4             : //
       5             : // This file is distributed under the University of Illinois Open Source
       6             : // License. See LICENSE.TXT for details.
       7             : //
       8             : //===----------------------------------------------------------------------===//
       9             : //
      10             : // This family of functions perform various local transformations to the
      11             : // program.
      12             : //
      13             : //===----------------------------------------------------------------------===//
      14             : 
      15             : #ifndef LLVM_TRANSFORMS_UTILS_LOCAL_H
      16             : #define LLVM_TRANSFORMS_UTILS_LOCAL_H
      17             : 
      18             : #include "llvm/ADT/SmallPtrSet.h"
      19             : #include "llvm/Analysis/AliasAnalysis.h"
      20             : #include "llvm/IR/DataLayout.h"
      21             : #include "llvm/IR/Dominators.h"
      22             : #include "llvm/IR/GetElementPtrTypeIterator.h"
      23             : #include "llvm/IR/IRBuilder.h"
      24             : #include "llvm/IR/Operator.h"
      25             : 
      26             : namespace llvm {
      27             : 
      28             : class User;
      29             : class BasicBlock;
      30             : class Function;
      31             : class BranchInst;
      32             : class Instruction;
      33             : class CallInst;
      34             : class DbgDeclareInst;
      35             : class DbgValueInst;
      36             : class StoreInst;
      37             : class LoadInst;
      38             : class Value;
      39             : class PHINode;
      40             : class AllocaInst;
      41             : class AssumptionCache;
      42             : class ConstantExpr;
      43             : class DataLayout;
      44             : class TargetLibraryInfo;
      45             : class TargetTransformInfo;
      46             : class DIBuilder;
      47             : class DominatorTree;
      48             : class LazyValueInfo;
      49             : 
      50             : template<typename T> class SmallVectorImpl;
      51             : 
      52             : //===----------------------------------------------------------------------===//
      53             : //  Local constant propagation.
      54             : //
      55             : 
      56             : /// If a terminator instruction is predicated on a constant value, convert it
      57             : /// into an unconditional branch to the constant destination.
      58             : /// This is a nontrivial operation because the successors of this basic block
      59             : /// must have their PHI nodes updated.
      60             : /// Also calls RecursivelyDeleteTriviallyDeadInstructions() on any branch/switch
      61             : /// conditions and indirectbr addresses this might make dead if
      62             : /// DeleteDeadConditions is true.
      63             : bool ConstantFoldTerminator(BasicBlock *BB, bool DeleteDeadConditions = false,
      64             :                             const TargetLibraryInfo *TLI = nullptr);
      65             : 
      66             : //===----------------------------------------------------------------------===//
      67             : //  Local dead code elimination.
      68             : //
      69             : 
      70             : /// Return true if the result produced by the instruction is not used, and the
      71             : /// instruction has no side effects.
      72             : bool isInstructionTriviallyDead(Instruction *I,
      73             :                                 const TargetLibraryInfo *TLI = nullptr);
      74             : 
      75             : /// Return true if the result produced by the instruction would have no side
      76             : /// effects if it was not used. This is equivalent to checking whether
      77             : /// isInstructionTriviallyDead would be true if the use count was 0.
      78             : bool wouldInstructionBeTriviallyDead(Instruction *I,
      79             :                                      const TargetLibraryInfo *TLI = nullptr);
      80             : 
      81             : /// If the specified value is a trivially dead instruction, delete it.
      82             : /// If that makes any of its operands trivially dead, delete them too,
      83             : /// recursively. Return true if any instructions were deleted.
      84             : bool RecursivelyDeleteTriviallyDeadInstructions(Value *V,
      85             :                                         const TargetLibraryInfo *TLI = nullptr);
      86             : 
      87             : /// If the specified value is an effectively dead PHI node, due to being a
      88             : /// def-use chain of single-use nodes that either forms a cycle or is terminated
      89             : /// by a trivially dead instruction, delete it. If that makes any of its
      90             : /// operands trivially dead, delete them too, recursively. Return true if a
      91             : /// change was made.
      92             : bool RecursivelyDeleteDeadPHINode(PHINode *PN,
      93             :                                   const TargetLibraryInfo *TLI = nullptr);
      94             : 
      95             : /// Scan the specified basic block and try to simplify any instructions in it
      96             : /// and recursively delete dead instructions.
      97             : ///
      98             : /// This returns true if it changed the code, note that it can delete
      99             : /// instructions in other blocks as well in this block.
     100             : bool SimplifyInstructionsInBlock(BasicBlock *BB,
     101             :                                  const TargetLibraryInfo *TLI = nullptr);
     102             : 
     103             : //===----------------------------------------------------------------------===//
     104             : //  Control Flow Graph Restructuring.
     105             : //
     106             : 
     107             : /// Like BasicBlock::removePredecessor, this method is called when we're about
     108             : /// to delete Pred as a predecessor of BB. If BB contains any PHI nodes, this
     109             : /// drops the entries in the PHI nodes for Pred.
     110             : ///
     111             : /// Unlike the removePredecessor method, this attempts to simplify uses of PHI
     112             : /// nodes that collapse into identity values.  For example, if we have:
     113             : ///   x = phi(1, 0, 0, 0)
     114             : ///   y = and x, z
     115             : ///
     116             : /// .. and delete the predecessor corresponding to the '1', this will attempt to
     117             : /// recursively fold the 'and' to 0.
     118             : void RemovePredecessorAndSimplify(BasicBlock *BB, BasicBlock *Pred);
     119             : 
     120             : /// BB is a block with one predecessor and its predecessor is known to have one
     121             : /// successor (BB!). Eliminate the edge between them, moving the instructions in
     122             : /// the predecessor into BB. This deletes the predecessor block.
     123             : void MergeBasicBlockIntoOnlyPred(BasicBlock *BB, DominatorTree *DT = nullptr);
     124             : 
     125             : /// BB is known to contain an unconditional branch, and contains no instructions
     126             : /// other than PHI nodes, potential debug intrinsics and the branch. If
     127             : /// possible, eliminate BB by rewriting all the predecessors to branch to the
     128             : /// successor block and return true. If we can't transform, return false.
     129             : bool TryToSimplifyUncondBranchFromEmptyBlock(BasicBlock *BB);
     130             : 
     131             : /// Check for and eliminate duplicate PHI nodes in this block. This doesn't try
     132             : /// to be clever about PHI nodes which differ only in the order of the incoming
     133             : /// values, but instcombine orders them so it usually won't matter.
     134             : bool EliminateDuplicatePHINodes(BasicBlock *BB);
     135             : 
     136             : /// This function is used to do simplification of a CFG.  For
     137             : /// example, it adjusts branches to branches to eliminate the extra hop, it
     138             : /// eliminates unreachable basic blocks, and does other "peephole" optimization
     139             : /// of the CFG.  It returns true if a modification was made, possibly deleting
     140             : /// the basic block that was pointed to. LoopHeaders is an optional input
     141             : /// parameter, providing the set of loop header that SimplifyCFG should not
     142             : /// eliminate.
     143             : bool SimplifyCFG(BasicBlock *BB, const TargetTransformInfo &TTI,
     144             :                  unsigned BonusInstThreshold, AssumptionCache *AC = nullptr,
     145             :                  SmallPtrSetImpl<BasicBlock *> *LoopHeaders = nullptr,
     146             :                  bool LateSimplifyCFG = false);
     147             : 
     148             : /// This function is used to flatten a CFG. For example, it uses parallel-and
     149             : /// and parallel-or mode to collapse if-conditions and merge if-regions with
     150             : /// identical statements.
     151             : bool FlattenCFG(BasicBlock *BB, AliasAnalysis *AA = nullptr);
     152             : 
     153             : /// If this basic block is ONLY a setcc and a branch, and if a predecessor
     154             : /// branches to us and one of our successors, fold the setcc into the
     155             : /// predecessor and use logical operations to pick the right destination.
     156             : bool FoldBranchToCommonDest(BranchInst *BI, unsigned BonusInstThreshold = 1);
     157             : 
     158             : /// This function takes a virtual register computed by an Instruction and
     159             : /// replaces it with a slot in the stack frame, allocated via alloca.
     160             : /// This allows the CFG to be changed around without fear of invalidating the
     161             : /// SSA information for the value. It returns the pointer to the alloca inserted
     162             : /// to create a stack slot for X.
     163             : AllocaInst *DemoteRegToStack(Instruction &X,
     164             :                              bool VolatileLoads = false,
     165             :                              Instruction *AllocaPoint = nullptr);
     166             : 
     167             : /// This function takes a virtual register computed by a phi node and replaces
     168             : /// it with a slot in the stack frame, allocated via alloca. The phi node is
     169             : /// deleted and it returns the pointer to the alloca inserted.
     170             : AllocaInst *DemotePHIToStack(PHINode *P, Instruction *AllocaPoint = nullptr);
     171             : 
     172             : /// Try to ensure that the alignment of \p V is at least \p PrefAlign bytes. If
     173             : /// the owning object can be modified and has an alignment less than \p
     174             : /// PrefAlign, it will be increased and \p PrefAlign returned. If the alignment
     175             : /// cannot be increased, the known alignment of the value is returned.
     176             : ///
     177             : /// It is not always possible to modify the alignment of the underlying object,
     178             : /// so if alignment is important, a more reliable approach is to simply align
     179             : /// all global variables and allocation instructions to their preferred
     180             : /// alignment from the beginning.
     181             : unsigned getOrEnforceKnownAlignment(Value *V, unsigned PrefAlign,
     182             :                                     const DataLayout &DL,
     183             :                                     const Instruction *CxtI = nullptr,
     184             :                                     AssumptionCache *AC = nullptr,
     185             :                                     const DominatorTree *DT = nullptr);
     186             : 
     187             : /// Try to infer an alignment for the specified pointer.
     188             : static inline unsigned getKnownAlignment(Value *V, const DataLayout &DL,
     189             :                                          const Instruction *CxtI = nullptr,
     190             :                                          AssumptionCache *AC = nullptr,
     191             :                                          const DominatorTree *DT = nullptr) {
     192      165254 :   return getOrEnforceKnownAlignment(V, 0, DL, CxtI, AC, DT);
     193             : }
     194             : 
     195             : /// Given a getelementptr instruction/constantexpr, emit the code necessary to
     196             : /// compute the offset from the base pointer (without adding in the base
     197             : /// pointer). Return the result as a signed integer of intptr size.
     198             : /// When NoAssumptions is true, no assumptions about index computation not
     199             : /// overflowing is made.
     200             : template <typename IRBuilderTy>
     201          98 : Value *EmitGEPOffset(IRBuilderTy *Builder, const DataLayout &DL, User *GEP,
     202             :                      bool NoAssumptions = false) {
     203          98 :   GEPOperator *GEPOp = cast<GEPOperator>(GEP);
     204          98 :   Type *IntPtrTy = DL.getIntPtrType(GEP->getType());
     205          98 :   Value *Result = Constant::getNullValue(IntPtrTy);
     206             : 
     207             :   // If the GEP is inbounds, we know that none of the addressing operations will
     208             :   // overflow in an unsigned sense.
     209          98 :   bool isInBounds = GEPOp->isInBounds() && !NoAssumptions;
     210             : 
     211             :   // Build a mask for high order bits.
     212         196 :   unsigned IntPtrWidth = IntPtrTy->getScalarType()->getIntegerBitWidth();
     213          98 :   uint64_t PtrSizeMask = ~0ULL >> (64 - IntPtrWidth);
     214             : 
     215          98 :   gep_type_iterator GTI = gep_type_begin(GEP);
     216         319 :   for (User::op_iterator i = GEP->op_begin() + 1, e = GEP->op_end(); i != e;
     217             :        ++i, ++GTI) {
     218         123 :     Value *Op = *i;
     219         123 :     uint64_t Size = DL.getTypeAllocSize(GTI.getIndexedType()) & PtrSizeMask;
     220          38 :     if (Constant *OpC = dyn_cast<Constant>(Op)) {
     221          38 :       if (OpC->isZeroValue())
     222          22 :         continue;
     223             : 
     224             :       // Handle a struct index, which adds its field offset to the pointer.
     225           2 :       if (StructType *STy = GTI.getStructTypeOrNull()) {
     226           4 :         if (OpC->getType()->isVectorTy())
     227           2 :           OpC = OpC->getSplatValue();
     228             : 
     229           4 :         uint64_t OpValue = cast<ConstantInt>(OpC)->getZExtValue();
     230           4 :         Size = DL.getStructLayout(STy)->getElementOffset(OpValue);
     231             : 
     232           2 :         if (Size)
     233           2 :           Result = Builder->CreateAdd(Result, ConstantInt::get(IntPtrTy, Size),
     234           6 :                                       GEP->getName()+".offs");
     235           2 :         continue;
     236             :       }
     237             : 
     238          14 :       Constant *Scale = ConstantInt::get(IntPtrTy, Size);
     239          14 :       Constant *OC = ConstantExpr::getIntegerCast(OpC, IntPtrTy, true /*SExt*/);
     240          14 :       Scale = ConstantExpr::getMul(OC, Scale, isInBounds/*NUW*/);
     241             :       // Emit an add instruction.
     242          28 :       Result = Builder->CreateAdd(Result, Scale, GEP->getName()+".offs");
     243          14 :       continue;
     244             :     }
     245             :     // Convert to correct type.
     246          85 :     if (Op->getType() != IntPtrTy)
     247           2 :       Op = Builder->CreateIntCast(Op, IntPtrTy, true, Op->getName()+".c");
     248          85 :     if (Size != 1) {
     249             :       // We'll let instcombine(mul) convert this to a shl if possible.
     250          58 :       Op = Builder->CreateMul(Op, ConstantInt::get(IntPtrTy, Size),
     251          87 :                               GEP->getName()+".idx", isInBounds /*NUW*/);
     252             :     }
     253             : 
     254             :     // Emit an add instruction.
     255         170 :     Result = Builder->CreateAdd(Op, Result, GEP->getName()+".offs");
     256             :   }
     257          98 :   return Result;
     258             : }
     259             : 
     260             : ///===---------------------------------------------------------------------===//
     261             : ///  Dbg Intrinsic utilities
     262             : ///
     263             : 
     264             : /// Inserts a llvm.dbg.value intrinsic before a store to an alloca'd value
     265             : /// that has an associated llvm.dbg.decl intrinsic.
     266             : void ConvertDebugDeclareToDebugValue(DbgDeclareInst *DDI,
     267             :                                      StoreInst *SI, DIBuilder &Builder);
     268             : 
     269             : /// Inserts a llvm.dbg.value intrinsic before a load of an alloca'd value
     270             : /// that has an associated llvm.dbg.decl intrinsic.
     271             : void ConvertDebugDeclareToDebugValue(DbgDeclareInst *DDI,
     272             :                                      LoadInst *LI, DIBuilder &Builder);
     273             : 
     274             : /// Inserts a llvm.dbg.value intrinsic after a phi of an alloca'd value
     275             : /// that has an associated llvm.dbg.decl intrinsic.
     276             : void ConvertDebugDeclareToDebugValue(DbgDeclareInst *DDI,
     277             :                                      PHINode *LI, DIBuilder &Builder);
     278             : 
     279             : /// Lowers llvm.dbg.declare intrinsics into appropriate set of
     280             : /// llvm.dbg.value intrinsics.
     281             : bool LowerDbgDeclare(Function &F);
     282             : 
     283             : /// Finds the llvm.dbg.declare intrinsic corresponding to an alloca, if any.
     284             : DbgDeclareInst *FindAllocaDbgDeclare(Value *V);
     285             : 
     286             : /// Finds the llvm.dbg.value intrinsics describing a value.
     287             : void findDbgValues(SmallVectorImpl<DbgValueInst *> &DbgValues, Value *V);
     288             : 
     289             : /// Replaces llvm.dbg.declare instruction when the address it describes
     290             : /// is replaced with a new value. If Deref is true, an additional DW_OP_deref is
     291             : /// prepended to the expression. If Offset is non-zero, a constant displacement
     292             : /// is added to the expression (after the optional Deref). Offset can be
     293             : /// negative.
     294             : bool replaceDbgDeclare(Value *Address, Value *NewAddress,
     295             :                        Instruction *InsertBefore, DIBuilder &Builder,
     296             :                        bool Deref, int Offset);
     297             : 
     298             : /// Replaces llvm.dbg.declare instruction when the alloca it describes
     299             : /// is replaced with a new value. If Deref is true, an additional DW_OP_deref is
     300             : /// prepended to the expression. If Offset is non-zero, a constant displacement
     301             : /// is added to the expression (after the optional Deref). Offset can be
     302             : /// negative. New llvm.dbg.declare is inserted immediately before AI.
     303             : bool replaceDbgDeclareForAlloca(AllocaInst *AI, Value *NewAllocaAddress,
     304             :                                 DIBuilder &Builder, bool Deref, int Offset = 0);
     305             : 
     306             : /// Replaces multiple llvm.dbg.value instructions when the alloca it describes
     307             : /// is replaced with a new value. If Offset is non-zero, a constant displacement
     308             : /// is added to the expression (after the mandatory Deref). Offset can be
     309             : /// negative. New llvm.dbg.value instructions are inserted at the locations of
     310             : /// the instructions they replace.
     311             : void replaceDbgValueForAlloca(AllocaInst *AI, Value *NewAllocaAddress,
     312             :                               DIBuilder &Builder, int Offset = 0);
     313             : 
     314             : /// Assuming the instruction \p I is going to be deleted, attempt to salvage any
     315             : /// dbg.value intrinsics referring to \p I by rewriting its effect into a
     316             : /// DIExpression.
     317             : void salvageDebugInfo(Instruction &I);
     318             : 
     319             : /// Remove all instructions from a basic block other than it's terminator
     320             : /// and any present EH pad instructions.
     321             : unsigned removeAllNonTerminatorAndEHPadInstructions(BasicBlock *BB);
     322             : 
     323             : /// Insert an unreachable instruction before the specified
     324             : /// instruction, making it and the rest of the code in the block dead.
     325             : unsigned changeToUnreachable(Instruction *I, bool UseLLVMTrap,
     326             :                              bool PreserveLCSSA = false);
     327             : 
     328             : /// Convert the CallInst to InvokeInst with the specified unwind edge basic
     329             : /// block.  This also splits the basic block where CI is located, because
     330             : /// InvokeInst is a terminator instruction.  Returns the newly split basic
     331             : /// block.
     332             : BasicBlock *changeToInvokeAndSplitBasicBlock(CallInst *CI,
     333             :                                              BasicBlock *UnwindEdge);
     334             : 
     335             : /// Replace 'BB's terminator with one that does not have an unwind successor
     336             : /// block. Rewrites `invoke` to `call`, etc. Updates any PHIs in unwind
     337             : /// successor.
     338             : ///
     339             : /// \param BB  Block whose terminator will be replaced.  Its terminator must
     340             : ///            have an unwind successor.
     341             : void removeUnwindEdge(BasicBlock *BB);
     342             : 
     343             : /// Remove all blocks that can not be reached from the function's entry.
     344             : ///
     345             : /// Returns true if any basic block was removed.
     346             : bool removeUnreachableBlocks(Function &F, LazyValueInfo *LVI = nullptr);
     347             : 
     348             : /// Combine the metadata of two instructions so that K can replace J
     349             : ///
     350             : /// Metadata not listed as known via KnownIDs is removed
     351             : void combineMetadata(Instruction *K, const Instruction *J, ArrayRef<unsigned> KnownIDs);
     352             : 
     353             : /// Combine the metadata of two instructions so that K can replace J. This
     354             : /// specifically handles the case of CSE-like transformations.
     355             : ///
     356             : /// Unknown metadata is removed.
     357             : void combineMetadataForCSE(Instruction *K, const Instruction *J);
     358             : 
     359             : // Replace each use of 'From' with 'To', if that use does not belong to basic
     360             : // block where 'From' is defined. Returns the number of replacements made.
     361             : unsigned replaceNonLocalUsesWith(Instruction *From, Value *To);
     362             : 
     363             : /// Replace each use of 'From' with 'To' if that use is dominated by
     364             : /// the given edge.  Returns the number of replacements made.
     365             : unsigned replaceDominatedUsesWith(Value *From, Value *To, DominatorTree &DT,
     366             :                                   const BasicBlockEdge &Edge);
     367             : /// Replace each use of 'From' with 'To' if that use is dominated by
     368             : /// the end of the given BasicBlock. Returns the number of replacements made.
     369             : unsigned replaceDominatedUsesWith(Value *From, Value *To, DominatorTree &DT,
     370             :                                   const BasicBlock *BB);
     371             : 
     372             : 
     373             : /// Return true if the CallSite CS calls a gc leaf function.
     374             : ///
     375             : /// A leaf function is a function that does not safepoint the thread during its
     376             : /// execution.  During a call or invoke to such a function, the callers stack
     377             : /// does not have to be made parseable.
     378             : ///
     379             : /// Most passes can and should ignore this information, and it is only used
     380             : /// during lowering by the GC infrastructure.
     381             : bool callsGCLeafFunction(ImmutableCallSite CS, const TargetLibraryInfo &TLI);
     382             : 
     383             : /// Copy a nonnull metadata node to a new load instruction.
     384             : ///
     385             : /// This handles mapping it to range metadata if the new load is an integer
     386             : /// load instead of a pointer load.
     387             : void copyNonnullMetadata(const LoadInst &OldLI, MDNode *N, LoadInst &NewLI);
     388             : 
     389             : /// Copy a range metadata node to a new load instruction.
     390             : ///
     391             : /// This handles mapping it to nonnull metadata if the new load is a pointer
     392             : /// load instead of an integer load and the range doesn't cover null.
     393             : void copyRangeMetadata(const DataLayout &DL, const LoadInst &OldLI, MDNode *N,
     394             :                        LoadInst &NewLI);
     395             : 
     396             : //===----------------------------------------------------------------------===//
     397             : //  Intrinsic pattern matching
     398             : //
     399             : 
     400             : /// Try and match a bswap or bitreverse idiom.
     401             : ///
     402             : /// If an idiom is matched, an intrinsic call is inserted before \c I. Any added
     403             : /// instructions are returned in \c InsertedInsts. They will all have been added
     404             : /// to a basic block.
     405             : ///
     406             : /// A bitreverse idiom normally requires around 2*BW nodes to be searched (where
     407             : /// BW is the bitwidth of the integer type). A bswap idiom requires anywhere up
     408             : /// to BW / 4 nodes to be searched, so is significantly faster.
     409             : ///
     410             : /// This function returns true on a successful match or false otherwise.
     411             : bool recognizeBSwapOrBitReverseIdiom(
     412             :     Instruction *I, bool MatchBSwaps, bool MatchBitReversals,
     413             :     SmallVectorImpl<Instruction *> &InsertedInsts);
     414             : 
     415             : //===----------------------------------------------------------------------===//
     416             : //  Sanitizer utilities
     417             : //
     418             : 
     419             : /// Given a CallInst, check if it calls a string function known to CodeGen,
     420             : /// and mark it with NoBuiltin if so.  To be used by sanitizers that intend
     421             : /// to intercept string functions and want to avoid converting them to target
     422             : /// specific instructions.
     423             : void maybeMarkSanitizerLibraryCallNoBuiltin(CallInst *CI,
     424             :                                             const TargetLibraryInfo *TLI);
     425             : 
     426             : //===----------------------------------------------------------------------===//
     427             : //  Transform predicates
     428             : //
     429             : 
     430             : /// Given an instruction, is it legal to set operand OpIdx to a non-constant
     431             : /// value?
     432             : bool canReplaceOperandWithVariable(const Instruction *I, unsigned OpIdx);
     433             : 
     434             : } // End llvm namespace
     435             : 
     436             : #endif

Generated by: LCOV version 1.13