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