Home | History | Annotate | Line # | Download | only in Scalar 
      1 //===- LowerConstantIntrinsics.cpp - Lower constant intrinsic calls -------===//
      2 //
      3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
      4 // See https://llvm.org/LICENSE.txt for license information.
      5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
      6 //
      7 //===----------------------------------------------------------------------===//
      8 //
      9 // This pass lowers all remaining 'objectsize' 'is.constant' intrinsic calls
     10 // and provides constant propagation and basic CFG cleanup on the result.
     11 //
     12 //===----------------------------------------------------------------------===//
     13 
     14 #include "llvm/Transforms/Scalar/LowerConstantIntrinsics.h"
     15 #include "llvm/ADT/PostOrderIterator.h"
     16 #include "llvm/ADT/SetVector.h"
     17 #include "llvm/ADT/Statistic.h"
     18 #include "llvm/Analysis/DomTreeUpdater.h"
     19 #include "llvm/Analysis/GlobalsModRef.h"
     20 #include "llvm/Analysis/InstructionSimplify.h"
     21 #include "llvm/Analysis/MemoryBuiltins.h"
     22 #include "llvm/Analysis/TargetLibraryInfo.h"
     23 #include "llvm/IR/BasicBlock.h"
     24 #include "llvm/IR/Constants.h"
     25 #include "llvm/IR/Dominators.h"
     26 #include "llvm/IR/Function.h"
     27 #include "llvm/IR/Instructions.h"
     28 #include "llvm/IR/IntrinsicInst.h"
     29 #include "llvm/IR/Intrinsics.h"
     30 #include "llvm/IR/PatternMatch.h"
     31 #include "llvm/InitializePasses.h"
     32 #include "llvm/Pass.h"
     33 #include "llvm/Support/Debug.h"
     34 #include "llvm/Transforms/Scalar.h"
     35 #include "llvm/Transforms/Utils/Local.h"
     36 
     37 using namespace llvm;
     38 using namespace llvm::PatternMatch;
     39 
     40 #define DEBUG_TYPE "lower-is-constant-intrinsic"
     41 
     42 STATISTIC(IsConstantIntrinsicsHandled,
     43           "Number of 'is.constant' intrinsic calls handled");
     44 STATISTIC(ObjectSizeIntrinsicsHandled,
     45           "Number of 'objectsize' intrinsic calls handled");
     46 
     47 static Value *lowerIsConstantIntrinsic(IntrinsicInst *II) {
     48   if (auto *C = dyn_cast<Constant>(II->getOperand(0)))
     49     if (C->isManifestConstant())
     50       return ConstantInt::getTrue(II->getType());
     51   return ConstantInt::getFalse(II->getType());
     52 }
     53 
     54 static bool replaceConditionalBranchesOnConstant(Instruction *II,
     55                                                  Value *NewValue,
     56                                                  DomTreeUpdater *DTU) {
     57   bool HasDeadBlocks = false;
     58   SmallSetVector<Instruction *, 8> Worklist;
     59   replaceAndRecursivelySimplify(II, NewValue, nullptr, nullptr, nullptr,
     60                                 &Worklist);
     61   for (auto I : Worklist) {
     62     BranchInst *BI = dyn_cast<BranchInst>(I);
     63     if (!BI)
     64       continue;
     65     if (BI->isUnconditional())
     66       continue;
     67 
     68     BasicBlock *Target, *Other;
     69     if (match(BI->getOperand(0), m_Zero())) {
     70       Target = BI->getSuccessor(1);
     71       Other = BI->getSuccessor(0);
     72     } else if (match(BI->getOperand(0), m_One())) {
     73       Target = BI->getSuccessor(0);
     74       Other = BI->getSuccessor(1);
     75     } else {
     76       Target = nullptr;
     77       Other = nullptr;
     78     }
     79     if (Target && Target != Other) {
     80       BasicBlock *Source = BI->getParent();
     81       Other->removePredecessor(Source);
     82       BI->eraseFromParent();
     83       BranchInst::Create(Target, Source);
     84       if (DTU)
     85         DTU->applyUpdates({{DominatorTree::Delete, Source, Other}});
     86       if (pred_empty(Other))
     87         HasDeadBlocks = true;
     88     }
     89   }
     90   return HasDeadBlocks;
     91 }
     92 
     93 static bool lowerConstantIntrinsics(Function &F, const TargetLibraryInfo *TLI,
     94                                     DominatorTree *DT) {
     95   Optional<DomTreeUpdater> DTU;
     96   if (DT)
     97     DTU.emplace(DT, DomTreeUpdater::UpdateStrategy::Lazy);
     98 
     99   bool HasDeadBlocks = false;
    100   const auto &DL = F.getParent()->getDataLayout();
    101   SmallVector<WeakTrackingVH, 8> Worklist;
    102 
    103   ReversePostOrderTraversal<Function *> RPOT(&F);
    104   for (BasicBlock *BB : RPOT) {
    105     for (Instruction &I: *BB) {
    106       IntrinsicInst *II = dyn_cast<IntrinsicInst>(&I);
    107       if (!II)
    108         continue;
    109       switch (II->getIntrinsicID()) {
    110       default:
    111         break;
    112       case Intrinsic::is_constant:
    113       case Intrinsic::objectsize:
    114         Worklist.push_back(WeakTrackingVH(&I));
    115         break;
    116       }
    117     }
    118   }
    119   for (WeakTrackingVH &VH: Worklist) {
    120     // Items on the worklist can be mutated by earlier recursive replaces.
    121     // This can remove the intrinsic as dead (VH == null), but also replace
    122     // the intrinsic in place.
    123     if (!VH)
    124       continue;
    125     IntrinsicInst *II = dyn_cast<IntrinsicInst>(&*VH);
    126     if (!II)
    127       continue;
    128     Value *NewValue;
    129     switch (II->getIntrinsicID()) {
    130     default:
    131       continue;
    132     case Intrinsic::is_constant:
    133       NewValue = lowerIsConstantIntrinsic(II);
    134       IsConstantIntrinsicsHandled++;
    135       break;
    136     case Intrinsic::objectsize:
    137       NewValue = lowerObjectSizeCall(II, DL, TLI, true);
    138       ObjectSizeIntrinsicsHandled++;
    139       break;
    140     }
    141     HasDeadBlocks |= replaceConditionalBranchesOnConstant(
    142         II, NewValue, DTU.hasValue() ? DTU.getPointer() : nullptr);
    143   }
    144   if (HasDeadBlocks)
    145     removeUnreachableBlocks(F, DTU.hasValue() ? DTU.getPointer() : nullptr);
    146   return !Worklist.empty();
    147 }
    148 
    149 PreservedAnalyses
    150 LowerConstantIntrinsicsPass::run(Function &F, FunctionAnalysisManager &AM) {
    151   if (lowerConstantIntrinsics(F, AM.getCachedResult<TargetLibraryAnalysis>(F),
    152                               AM.getCachedResult<DominatorTreeAnalysis>(F))) {
    153     PreservedAnalyses PA;
    154     PA.preserve<DominatorTreeAnalysis>();
    155     return PA;
    156   }
    157 
    158   return PreservedAnalyses::all();
    159 }
    160 
    161 namespace {
    162 /// Legacy pass for lowering is.constant intrinsics out of the IR.
    163 ///
    164 /// When this pass is run over a function it converts is.constant intrinsics
    165 /// into 'true' or 'false'. This complements the normal constant folding
    166 /// to 'true' as part of Instruction Simplify passes.
    167 class LowerConstantIntrinsics : public FunctionPass {
    168 public:
    169   static char ID;
    170   LowerConstantIntrinsics() : FunctionPass(ID) {
    171     initializeLowerConstantIntrinsicsPass(*PassRegistry::getPassRegistry());
    172   }
    173 
    174   bool runOnFunction(Function &F) override {
    175     auto *TLIP = getAnalysisIfAvailable<TargetLibraryInfoWrapperPass>();
    176     const TargetLibraryInfo *TLI = TLIP ? &TLIP->getTLI(F) : nullptr;
    177     DominatorTree *DT = nullptr;
    178     if (auto *DTWP = getAnalysisIfAvailable<DominatorTreeWrapperPass>())
    179       DT = &DTWP->getDomTree();
    180     return lowerConstantIntrinsics(F, TLI, DT);
    181   }
    182 
    183   void getAnalysisUsage(AnalysisUsage &AU) const override {
    184     AU.addPreserved<GlobalsAAWrapperPass>();
    185     AU.addPreserved<DominatorTreeWrapperPass>();
    186   }
    187 };
    188 } // namespace
    189 
    190 char LowerConstantIntrinsics::ID = 0;
    191 INITIALIZE_PASS_BEGIN(LowerConstantIntrinsics, "lower-constant-intrinsics",
    192                       "Lower constant intrinsics", false, false)
    193 INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass)
    194 INITIALIZE_PASS_END(LowerConstantIntrinsics, "lower-constant-intrinsics",
    195                     "Lower constant intrinsics", false, false)
    196 
    197 FunctionPass *llvm::createLowerConstantIntrinsicsPass() {
    198   return new LowerConstantIntrinsics();
    199 }
    200