llvm/lib/Transforms/Scalar/LowerConstantIntrinsics.cpp

   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/PatternMatch.h"
  30 #include "llvm/Pass.h"
  31 #include "llvm/Support/Debug.h"
  32 #include "llvm/Transforms/Scalar.h"
  33 #include "llvm/Transforms/Utils/Local.h"
  34 #include <optional>
  35
  36 using namespace llvm;
  37 using namespace llvm::PatternMatch;
  38
  39 #define DEBUG_TYPE "lower-is-constant-intrinsic"
  40
  41 STATISTIC(IsConstantIntrinsicsHandled,
  42           "Number of 'is.constant' intrinsic calls handled");
  43 STATISTIC(ObjectSizeIntrinsicsHandled,
  44           "Number of 'objectsize' intrinsic calls handled");
  45
  46 static Value *lowerIsConstantIntrinsic(IntrinsicInst *II) {
  47   if (auto *C = dyn_cast<Constant>(II->getOperand(0)))
  48     if (C->isManifestConstant())
  49       return ConstantInt::getTrue(II->getType());
  50   return ConstantInt::getFalse(II->getType());
  51 }
  52
  53 static bool replaceConditionalBranchesOnConstant(Instruction *II,
  54                                                  Value *NewValue,
  55                                                  DomTreeUpdater *DTU) {
  56   bool HasDeadBlocks = false;
  57   SmallSetVector<Instruction *, 8> UnsimplifiedUsers;
  58   replaceAndRecursivelySimplify(II, NewValue, nullptr, nullptr, nullptr,
  59                                 &UnsimplifiedUsers);
  60   // UnsimplifiedUsers can contain PHI nodes that may be removed when
  61   // replacing the branch instructions, so use a value handle worklist
  62   // to handle those possibly removed instructions.
  63   SmallVector<WeakVH, 8> Worklist(UnsimplifiedUsers.begin(),
  64                                   UnsimplifiedUsers.end());
  65
  66   for (auto &VH : Worklist) {
  67     BranchInst *BI = dyn_cast_or_null<BranchInst>(VH);
  68     if (!BI)
  69       continue;
  70     if (BI->isUnconditional())
  71       continue;
  72
  73     BasicBlock *Target, *Other;
  74     if (match(BI->getOperand(0), m_Zero())) {
  75       Target = BI->getSuccessor(1);
  76       Other = BI->getSuccessor(0);
  77     } else if (match(BI->getOperand(0), m_One())) {
  78       Target = BI->getSuccessor(0);
  79       Other = BI->getSuccessor(1);
  80     } else {
  81       Target = nullptr;
  82       Other = nullptr;
  83     }
  84     if (Target && Target != Other) {
  85       BasicBlock *Source = BI->getParent();
  86       Other->removePredecessor(Source);
  87
  88       Instruction *NewBI = BranchInst::Create(Target, Source);
  89       NewBI->setDebugLoc(BI->getDebugLoc());
  90       BI->eraseFromParent();
  91
  92       if (DTU)
  93         DTU->applyUpdates({{DominatorTree::Delete, Source, Other}});
  94       if (pred_empty(Other))
  95         HasDeadBlocks = true;
  96     }
  97   }
  98   return HasDeadBlocks;
  99 }
 100
 101 bool llvm::lowerConstantIntrinsics(Function &F, const TargetLibraryInfo &TLI,
 102                                    DominatorTree *DT) {
 103   std::optional<DomTreeUpdater> DTU;
 104   if (DT)
 105     DTU.emplace(DT, DomTreeUpdater::UpdateStrategy::Lazy);
 106
 107   bool HasDeadBlocks = false;
 108   const auto &DL = F.getDataLayout();
 109   SmallVector<WeakTrackingVH, 8> Worklist;
 110
 111   ReversePostOrderTraversal<Function *> RPOT(&F);
 112   for (BasicBlock *BB : RPOT) {
 113     for (Instruction &I: *BB) {
 114       IntrinsicInst *II = dyn_cast<IntrinsicInst>(&I);
 115       if (!II)
 116         continue;
 117       switch (II->getIntrinsicID()) {
 118       default:
 119         break;
 120       case Intrinsic::is_constant:
 121       case Intrinsic::objectsize:
 122         Worklist.push_back(WeakTrackingVH(&I));
 123         break;
 124       }
 125     }
 126   }
 127   for (WeakTrackingVH &VH: Worklist) {
 128     // Items on the worklist can be mutated by earlier recursive replaces.
 129     // This can remove the intrinsic as dead (VH == null), but also replace
 130     // the intrinsic in place.
 131     if (!VH)
 132       continue;
 133     IntrinsicInst *II = dyn_cast<IntrinsicInst>(&*VH);
 134     if (!II)
 135       continue;
 136     Value *NewValue;
 137     switch (II->getIntrinsicID()) {
 138     default:
 139       continue;
 140     case Intrinsic::is_constant:
 141       NewValue = lowerIsConstantIntrinsic(II);
 142       LLVM_DEBUG(dbgs() << "Folding " << *II << " to " << *NewValue << "\n");
 143       IsConstantIntrinsicsHandled++;
 144       break;
 145     case Intrinsic::objectsize:
 146       NewValue = lowerObjectSizeCall(II, DL, &TLI, true);
 147       LLVM_DEBUG(dbgs() << "Folding " << *II << " to " << *NewValue << "\n");
 148       ObjectSizeIntrinsicsHandled++;
 149       break;
 150     }
 151     HasDeadBlocks |= replaceConditionalBranchesOnConstant(
 152         II, NewValue, DTU ? &*DTU : nullptr);
 153   }
 154   if (HasDeadBlocks)
 155     removeUnreachableBlocks(F, DTU ? &*DTU : nullptr);
 156   return !Worklist.empty();
 157 }
 158
 159 PreservedAnalyses
 160 LowerConstantIntrinsicsPass::run(Function &F, FunctionAnalysisManager &AM) {
 161   if (lowerConstantIntrinsics(F, AM.getResult<TargetLibraryAnalysis>(F),
 162                               AM.getCachedResult<DominatorTreeAnalysis>(F))) {
 163     PreservedAnalyses PA;
 164     PA.preserve<DominatorTreeAnalysis>();
 165     return PA;
 166   }
 167
 168   return PreservedAnalyses::all();
 169 }