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/InitializePasses.h"
  31 #include "llvm/Pass.h"
  32 #include "llvm/Support/Debug.h"
  33 #include "llvm/Transforms/Scalar.h"
  34 #include "llvm/Transforms/Utils/Local.h"
  35 #include <optional>
  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> UnsimplifiedUsers;
  59   replaceAndRecursivelySimplify(II, NewValue, nullptr, nullptr, nullptr,
  60                                 &UnsimplifiedUsers);
  61   // UnsimplifiedUsers can contain PHI nodes that may be removed when
  62   // replacing the branch instructions, so use a value handle worklist
  63   // to handle those possibly removed instructions.
  64   SmallVector<WeakVH, 8> Worklist(UnsimplifiedUsers.begin(),
  65                                   UnsimplifiedUsers.end());
  66
  67   for (auto &VH : Worklist) {
  68     BranchInst *BI = dyn_cast_or_null<BranchInst>(VH);
  69     if (!BI)
  70       continue;
  71     if (BI->isUnconditional())
  72       continue;
  73
  74     BasicBlock *Target, *Other;
  75     if (match(BI->getOperand(0), m_Zero())) {
  76       Target = BI->getSuccessor(1);
  77       Other = BI->getSuccessor(0);
  78     } else if (match(BI->getOperand(0), m_One())) {
  79       Target = BI->getSuccessor(0);
  80       Other = BI->getSuccessor(1);
  81     } else {
  82       Target = nullptr;
  83       Other = nullptr;
  84     }
  85     if (Target && Target != Other) {
  86       BasicBlock *Source = BI->getParent();
  87       Other->removePredecessor(Source);
  88       BI->eraseFromParent();
  89       BranchInst::Create(Target, Source);
  90       if (DTU)
  91         DTU->applyUpdates({{DominatorTree::Delete, Source, Other}});
  92       if (pred_empty(Other))
  93         HasDeadBlocks = true;
  94     }
  95   }
  96   return HasDeadBlocks;
  97 }
  98
  99 static bool lowerConstantIntrinsics(Function &F, const TargetLibraryInfo &TLI,
 100                                     DominatorTree *DT) {
 101   std::optional<DomTreeUpdater> DTU;
 102   if (DT)
 103     DTU.emplace(DT, DomTreeUpdater::UpdateStrategy::Lazy);
 104
 105   bool HasDeadBlocks = false;
 106   const auto &DL = F.getParent()->getDataLayout();
 107   SmallVector<WeakTrackingVH, 8> Worklist;
 108
 109   ReversePostOrderTraversal<Function *> RPOT(&F);
 110   for (BasicBlock *BB : RPOT) {
 111     for (Instruction &I: *BB) {
 112       IntrinsicInst *II = dyn_cast<IntrinsicInst>(&I);
 113       if (!II)
 114         continue;
 115       switch (II->getIntrinsicID()) {
 116       default:
 117         break;
 118       case Intrinsic::is_constant:
 119       case Intrinsic::objectsize:
 120         Worklist.push_back(WeakTrackingVH(&I));
 121         break;
 122       }
 123     }
 124   }
 125   for (WeakTrackingVH &VH: Worklist) {
 126     // Items on the worklist can be mutated by earlier recursive replaces.
 127     // This can remove the intrinsic as dead (VH == null), but also replace
 128     // the intrinsic in place.
 129     if (!VH)
 130       continue;
 131     IntrinsicInst *II = dyn_cast<IntrinsicInst>(&*VH);
 132     if (!II)
 133       continue;
 134     Value *NewValue;
 135     switch (II->getIntrinsicID()) {
 136     default:
 137       continue;
 138     case Intrinsic::is_constant:
 139       NewValue = lowerIsConstantIntrinsic(II);
 140       LLVM_DEBUG(dbgs() << "Folding " << *II << " to " << *NewValue << "\n");
 141       IsConstantIntrinsicsHandled++;
 142       break;
 143     case Intrinsic::objectsize:
 144       NewValue = lowerObjectSizeCall(II, DL, &TLI, true);
 145       LLVM_DEBUG(dbgs() << "Folding " << *II << " to " << *NewValue << "\n");
 146       ObjectSizeIntrinsicsHandled++;
 147       break;
 148     }
 149     HasDeadBlocks |= replaceConditionalBranchesOnConstant(
 150         II, NewValue, DTU ? &*DTU : nullptr);
 151   }
 152   if (HasDeadBlocks)
 153     removeUnreachableBlocks(F, DTU ? &*DTU : nullptr);
 154   return !Worklist.empty();
 155 }
 156
 157 PreservedAnalyses
 158 LowerConstantIntrinsicsPass::run(Function &F, FunctionAnalysisManager &AM) {
 159   if (lowerConstantIntrinsics(F, AM.getResult<TargetLibraryAnalysis>(F),
 160                               AM.getCachedResult<DominatorTreeAnalysis>(F))) {
 161     PreservedAnalyses PA;
 162     PA.preserve<DominatorTreeAnalysis>();
 163     return PA;
 164   }
 165
 166   return PreservedAnalyses::all();
 167 }
 168
 169 namespace {
 170 /// Legacy pass for lowering is.constant intrinsics out of the IR.
 171 ///
 172 /// When this pass is run over a function it converts is.constant intrinsics
 173 /// into 'true' or 'false'. This complements the normal constant folding
 174 /// to 'true' as part of Instruction Simplify passes.
 175 class LowerConstantIntrinsics : public FunctionPass {
 176 public:
 177   static char ID;
 178   LowerConstantIntrinsics() : FunctionPass(ID) {
 179     initializeLowerConstantIntrinsicsPass(*PassRegistry::getPassRegistry());
 180   }
 181
 182   bool runOnFunction(Function &F) override {
 183     const TargetLibraryInfo &TLI =
 184         getAnalysis<TargetLibraryInfoWrapperPass>().getTLI(F);
 185     DominatorTree *DT = nullptr;
 186     if (auto *DTWP = getAnalysisIfAvailable<DominatorTreeWrapperPass>())
 187       DT = &DTWP->getDomTree();
 188     return lowerConstantIntrinsics(F, TLI, DT);
 189   }
 190
 191   void getAnalysisUsage(AnalysisUsage &AU) const override {
 192     AU.addRequired<TargetLibraryInfoWrapperPass>();
 193     AU.addPreserved<GlobalsAAWrapperPass>();
 194     AU.addPreserved<DominatorTreeWrapperPass>();
 195   }
 196 };
 197 } // namespace
 198
 199 char LowerConstantIntrinsics::ID = 0;
 200 INITIALIZE_PASS_BEGIN(LowerConstantIntrinsics, "lower-constant-intrinsics",
 201                       "Lower constant intrinsics", false, false)
 202 INITIALIZE_PASS_DEPENDENCY(TargetLibraryInfoWrapperPass)
 203 INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass)
 204 INITIALIZE_PASS_END(LowerConstantIntrinsics, "lower-constant-intrinsics",
 205                     "Lower constant intrinsics", false, false)
 206
 207 FunctionPass *llvm::createLowerConstantIntrinsicsPass() {
 208   return new LowerConstantIntrinsics();
 209 }