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
36using namespace llvm;
37using namespace llvm::PatternMatch;
38
39#define DEBUG_TYPE "lower-is-constant-intrinsic"
40
41STATISTIC(IsConstantIntrinsicsHandled,
42 "Number of 'is.constant' intrinsic calls handled");
43STATISTIC(ObjectSizeIntrinsicsHandled,
44 "Number of 'objectsize' intrinsic calls handled");
45
46static Value *lowerIsConstantIntrinsic(IntrinsicInst *II) {
47 if (auto *C = dyn_cast<Constant>(Val: II->getOperand(i_nocapture: 0)))
48 if (C->isManifestConstant())
49 return ConstantInt::getTrue(Ty: II->getType());
50 return ConstantInt::getFalse(Ty: II->getType());
51}
52
53static bool replaceConditionalBranchesOnConstant(Instruction *II,
54 Value *NewValue,
55 DomTreeUpdater *DTU) {
56 bool HasDeadBlocks = false;
57 SmallSetVector<Instruction *, 8> UnsimplifiedUsers;
58 replaceAndRecursivelySimplify(I: II, SimpleV: NewValue, TLI: nullptr, DT: nullptr, AC: nullptr,
59 UnsimplifiedUsers: &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>(Val&: VH);
68 if (!BI)
69 continue;
70 if (BI->isUnconditional())
71 continue;
72
73 BasicBlock *Target, *Other;
74 if (match(V: BI->getOperand(i_nocapture: 0), P: m_Zero())) {
75 Target = BI->getSuccessor(i: 1);
76 Other = BI->getSuccessor(i: 0);
77 } else if (match(V: BI->getOperand(i_nocapture: 0), P: m_One())) {
78 Target = BI->getSuccessor(i: 0);
79 Other = BI->getSuccessor(i: 1);
80 } else {
81 Target = nullptr;
82 Other = nullptr;
83 }
84 if (Target && Target != Other) {
85 BasicBlock *Source = BI->getParent();
86 Other->removePredecessor(Pred: Source);
87
88 Instruction *NewBI = BranchInst::Create(IfTrue: Target, InsertBefore: Source);
89 NewBI->setDebugLoc(BI->getDebugLoc());
90 BI->eraseFromParent();
91
92 if (DTU)
93 DTU->applyUpdates(Updates: {{DominatorTree::Delete, Source, Other}});
94 if (pred_empty(BB: Other))
95 HasDeadBlocks = true;
96 }
97 }
98 return HasDeadBlocks;
99}
100
101bool llvm::lowerConstantIntrinsics(Function &F, const TargetLibraryInfo &TLI,
102 DominatorTree *DT) {
103 std::optional<DomTreeUpdater> DTU;
104 if (DT)
105 DTU.emplace(args&: DT, args: 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>(Val: &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(Elt: 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>(Val: &*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(ObjectSize: II, DL, TLI: &TLI, MustSucceed: true);
147 LLVM_DEBUG(dbgs() << "Folding " << *II << " to " << *NewValue << "\n");
148 ObjectSizeIntrinsicsHandled++;
149 break;
150 }
151 HasDeadBlocks |= replaceConditionalBranchesOnConstant(
152 II, NewValue, DTU: DTU ? &*DTU : nullptr);
153 }
154 if (HasDeadBlocks)
155 removeUnreachableBlocks(F, DTU: DTU ? &*DTU : nullptr);
156 return !Worklist.empty();
157}
158
159PreservedAnalyses
160LowerConstantIntrinsicsPass::run(Function &F, FunctionAnalysisManager &AM) {
161 if (lowerConstantIntrinsics(F, TLI: AM.getResult<TargetLibraryAnalysis>(IR&: F),
162 DT: AM.getCachedResult<DominatorTreeAnalysis>(IR&: F))) {
163 PreservedAnalyses PA;
164 PA.preserve<DominatorTreeAnalysis>();
165 return PA;
166 }
167
168 return PreservedAnalyses::all();
169}
170