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/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       BI->eraseFromParent();
88       BranchInst::Create(Target, Source);
89       if (DTU)
90         DTU->applyUpdates({{DominatorTree::Delete, Source, Other}});
91       if (pred_empty(Other))
92         HasDeadBlocks = true;
93     }
94   }
95   return HasDeadBlocks;
96 }
97 
98 static bool lowerConstantIntrinsics(Function &F, const TargetLibraryInfo &TLI,
99                                     DominatorTree *DT) {
100   std::optional<DomTreeUpdater> DTU;
101   if (DT)
102     DTU.emplace(DT, DomTreeUpdater::UpdateStrategy::Lazy);
103 
104   bool HasDeadBlocks = false;
105   const auto &DL = F.getParent()->getDataLayout();
106   SmallVector<WeakTrackingVH, 8> Worklist;
107 
108   ReversePostOrderTraversal<Function *> RPOT(&F);
109   for (BasicBlock *BB : RPOT) {
110     for (Instruction &I: *BB) {
111       IntrinsicInst *II = dyn_cast<IntrinsicInst>(&I);
112       if (!II)
113         continue;
114       switch (II->getIntrinsicID()) {
115       default:
116         break;
117       case Intrinsic::is_constant:
118       case Intrinsic::objectsize:
119         Worklist.push_back(WeakTrackingVH(&I));
120         break;
121       }
122     }
123   }
124   for (WeakTrackingVH &VH: Worklist) {
125     // Items on the worklist can be mutated by earlier recursive replaces.
126     // This can remove the intrinsic as dead (VH == null), but also replace
127     // the intrinsic in place.
128     if (!VH)
129       continue;
130     IntrinsicInst *II = dyn_cast<IntrinsicInst>(&*VH);
131     if (!II)
132       continue;
133     Value *NewValue;
134     switch (II->getIntrinsicID()) {
135     default:
136       continue;
137     case Intrinsic::is_constant:
138       NewValue = lowerIsConstantIntrinsic(II);
139       IsConstantIntrinsicsHandled++;
140       break;
141     case Intrinsic::objectsize:
142       NewValue = lowerObjectSizeCall(II, DL, &TLI, true);
143       ObjectSizeIntrinsicsHandled++;
144       break;
145     }
146     HasDeadBlocks |= replaceConditionalBranchesOnConstant(
147         II, NewValue, DTU ? &*DTU : nullptr);
148   }
149   if (HasDeadBlocks)
150     removeUnreachableBlocks(F, DTU ? &*DTU : nullptr);
151   return !Worklist.empty();
152 }
153 
154 PreservedAnalyses
155 LowerConstantIntrinsicsPass::run(Function &F, FunctionAnalysisManager &AM) {
156   if (lowerConstantIntrinsics(F, AM.getResult<TargetLibraryAnalysis>(F),
157                               AM.getCachedResult<DominatorTreeAnalysis>(F))) {
158     PreservedAnalyses PA;
159     PA.preserve<DominatorTreeAnalysis>();
160     return PA;
161   }
162 
163   return PreservedAnalyses::all();
164 }
165 
166 namespace {
167 /// Legacy pass for lowering is.constant intrinsics out of the IR.
168 ///
169 /// When this pass is run over a function it converts is.constant intrinsics
170 /// into 'true' or 'false'. This complements the normal constant folding
171 /// to 'true' as part of Instruction Simplify passes.
172 class LowerConstantIntrinsics : public FunctionPass {
173 public:
174   static char ID;
175   LowerConstantIntrinsics() : FunctionPass(ID) {
176     initializeLowerConstantIntrinsicsPass(*PassRegistry::getPassRegistry());
177   }
178 
179   bool runOnFunction(Function &F) override {
180     const TargetLibraryInfo &TLI =
181         getAnalysis<TargetLibraryInfoWrapperPass>().getTLI(F);
182     DominatorTree *DT = nullptr;
183     if (auto *DTWP = getAnalysisIfAvailable<DominatorTreeWrapperPass>())
184       DT = &DTWP->getDomTree();
185     return lowerConstantIntrinsics(F, TLI, DT);
186   }
187 
188   void getAnalysisUsage(AnalysisUsage &AU) const override {
189     AU.addRequired<TargetLibraryInfoWrapperPass>();
190     AU.addPreserved<GlobalsAAWrapperPass>();
191     AU.addPreserved<DominatorTreeWrapperPass>();
192   }
193 };
194 } // namespace
195 
196 char LowerConstantIntrinsics::ID = 0;
197 INITIALIZE_PASS_BEGIN(LowerConstantIntrinsics, "lower-constant-intrinsics",
198                       "Lower constant intrinsics", false, false)
199 INITIALIZE_PASS_DEPENDENCY(TargetLibraryInfoWrapperPass)
200 INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass)
201 INITIALIZE_PASS_END(LowerConstantIntrinsics, "lower-constant-intrinsics",
202                     "Lower constant intrinsics", false, false)
203 
204 FunctionPass *llvm::createLowerConstantIntrinsicsPass() {
205   return new LowerConstantIntrinsics();
206 }
207