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 }
210