1 //===- CorrelatedValuePropagation.cpp - Propagate CFG-derived info --------===//
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 file implements the Correlated Value Propagation pass.
10 //
11 //===----------------------------------------------------------------------===//
12
13 #include "llvm/Transforms/Scalar/CorrelatedValuePropagation.h"
14 #include "llvm/ADT/DepthFirstIterator.h"
15 #include "llvm/ADT/Optional.h"
16 #include "llvm/ADT/SmallVector.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/LazyValueInfo.h"
22 #include "llvm/IR/Attributes.h"
23 #include "llvm/IR/BasicBlock.h"
24 #include "llvm/IR/CFG.h"
25 #include "llvm/IR/Constant.h"
26 #include "llvm/IR/ConstantRange.h"
27 #include "llvm/IR/Constants.h"
28 #include "llvm/IR/DerivedTypes.h"
29 #include "llvm/IR/Function.h"
30 #include "llvm/IR/IRBuilder.h"
31 #include "llvm/IR/InstrTypes.h"
32 #include "llvm/IR/Instruction.h"
33 #include "llvm/IR/Instructions.h"
34 #include "llvm/IR/IntrinsicInst.h"
35 #include "llvm/IR/Operator.h"
36 #include "llvm/IR/PassManager.h"
37 #include "llvm/IR/Type.h"
38 #include "llvm/IR/Value.h"
39 #include "llvm/InitializePasses.h"
40 #include "llvm/Pass.h"
41 #include "llvm/Support/Casting.h"
42 #include "llvm/Support/CommandLine.h"
43 #include "llvm/Support/Debug.h"
44 #include "llvm/Support/raw_ostream.h"
45 #include "llvm/Transforms/Scalar.h"
46 #include "llvm/Transforms/Utils/Local.h"
47 #include <cassert>
48 #include <utility>
49
50 using namespace llvm;
51
52 #define DEBUG_TYPE "correlated-value-propagation"
53
54 STATISTIC(NumPhis, "Number of phis propagated");
55 STATISTIC(NumPhiCommon, "Number of phis deleted via common incoming value");
56 STATISTIC(NumSelects, "Number of selects propagated");
57 STATISTIC(NumMemAccess, "Number of memory access targets propagated");
58 STATISTIC(NumCmps, "Number of comparisons propagated");
59 STATISTIC(NumReturns, "Number of return values propagated");
60 STATISTIC(NumDeadCases, "Number of switch cases removed");
61 STATISTIC(NumSDivs, "Number of sdiv converted to udiv");
62 STATISTIC(NumUDivs, "Number of udivs whose width was decreased");
63 STATISTIC(NumAShrs, "Number of ashr converted to lshr");
64 STATISTIC(NumSRems, "Number of srem converted to urem");
65 STATISTIC(NumSExt, "Number of sext converted to zext");
66 STATISTIC(NumAnd, "Number of ands removed");
67 STATISTIC(NumNW, "Number of no-wrap deductions");
68 STATISTIC(NumNSW, "Number of no-signed-wrap deductions");
69 STATISTIC(NumNUW, "Number of no-unsigned-wrap deductions");
70 STATISTIC(NumAddNW, "Number of no-wrap deductions for add");
71 STATISTIC(NumAddNSW, "Number of no-signed-wrap deductions for add");
72 STATISTIC(NumAddNUW, "Number of no-unsigned-wrap deductions for add");
73 STATISTIC(NumSubNW, "Number of no-wrap deductions for sub");
74 STATISTIC(NumSubNSW, "Number of no-signed-wrap deductions for sub");
75 STATISTIC(NumSubNUW, "Number of no-unsigned-wrap deductions for sub");
76 STATISTIC(NumMulNW, "Number of no-wrap deductions for mul");
77 STATISTIC(NumMulNSW, "Number of no-signed-wrap deductions for mul");
78 STATISTIC(NumMulNUW, "Number of no-unsigned-wrap deductions for mul");
79 STATISTIC(NumShlNW, "Number of no-wrap deductions for shl");
80 STATISTIC(NumShlNSW, "Number of no-signed-wrap deductions for shl");
81 STATISTIC(NumShlNUW, "Number of no-unsigned-wrap deductions for shl");
82 STATISTIC(NumOverflows, "Number of overflow checks removed");
83 STATISTIC(NumSaturating,
84 "Number of saturating arithmetics converted to normal arithmetics");
85
86 static cl::opt<bool> DontAddNoWrapFlags("cvp-dont-add-nowrap-flags", cl::init(false));
87
88 namespace {
89
90 class CorrelatedValuePropagation : public FunctionPass {
91 public:
92 static char ID;
93
CorrelatedValuePropagation()94 CorrelatedValuePropagation(): FunctionPass(ID) {
95 initializeCorrelatedValuePropagationPass(*PassRegistry::getPassRegistry());
96 }
97
98 bool runOnFunction(Function &F) override;
99
getAnalysisUsage(AnalysisUsage & AU) const100 void getAnalysisUsage(AnalysisUsage &AU) const override {
101 AU.addRequired<DominatorTreeWrapperPass>();
102 AU.addRequired<LazyValueInfoWrapperPass>();
103 AU.addPreserved<GlobalsAAWrapperPass>();
104 AU.addPreserved<DominatorTreeWrapperPass>();
105 AU.addPreserved<LazyValueInfoWrapperPass>();
106 }
107 };
108
109 } // end anonymous namespace
110
111 char CorrelatedValuePropagation::ID = 0;
112
113 INITIALIZE_PASS_BEGIN(CorrelatedValuePropagation, "correlated-propagation",
114 "Value Propagation", false, false)
INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass)115 INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass)
116 INITIALIZE_PASS_DEPENDENCY(LazyValueInfoWrapperPass)
117 INITIALIZE_PASS_END(CorrelatedValuePropagation, "correlated-propagation",
118 "Value Propagation", false, false)
119
120 // Public interface to the Value Propagation pass
121 Pass *llvm::createCorrelatedValuePropagationPass() {
122 return new CorrelatedValuePropagation();
123 }
124
processSelect(SelectInst * S,LazyValueInfo * LVI)125 static bool processSelect(SelectInst *S, LazyValueInfo *LVI) {
126 if (S->getType()->isVectorTy()) return false;
127 if (isa<Constant>(S->getCondition())) return false;
128
129 Constant *C = LVI->getConstant(S->getCondition(), S->getParent(), S);
130 if (!C) return false;
131
132 ConstantInt *CI = dyn_cast<ConstantInt>(C);
133 if (!CI) return false;
134
135 Value *ReplaceWith = CI->isOne() ? S->getTrueValue() : S->getFalseValue();
136 S->replaceAllUsesWith(ReplaceWith);
137 S->eraseFromParent();
138
139 ++NumSelects;
140
141 return true;
142 }
143
144 /// Try to simplify a phi with constant incoming values that match the edge
145 /// values of a non-constant value on all other edges:
146 /// bb0:
147 /// %isnull = icmp eq i8* %x, null
148 /// br i1 %isnull, label %bb2, label %bb1
149 /// bb1:
150 /// br label %bb2
151 /// bb2:
152 /// %r = phi i8* [ %x, %bb1 ], [ null, %bb0 ]
153 /// -->
154 /// %r = %x
simplifyCommonValuePhi(PHINode * P,LazyValueInfo * LVI,DominatorTree * DT)155 static bool simplifyCommonValuePhi(PHINode *P, LazyValueInfo *LVI,
156 DominatorTree *DT) {
157 // Collect incoming constants and initialize possible common value.
158 SmallVector<std::pair<Constant *, unsigned>, 4> IncomingConstants;
159 Value *CommonValue = nullptr;
160 for (unsigned i = 0, e = P->getNumIncomingValues(); i != e; ++i) {
161 Value *Incoming = P->getIncomingValue(i);
162 if (auto *IncomingConstant = dyn_cast<Constant>(Incoming)) {
163 IncomingConstants.push_back(std::make_pair(IncomingConstant, i));
164 } else if (!CommonValue) {
165 // The potential common value is initialized to the first non-constant.
166 CommonValue = Incoming;
167 } else if (Incoming != CommonValue) {
168 // There can be only one non-constant common value.
169 return false;
170 }
171 }
172
173 if (!CommonValue || IncomingConstants.empty())
174 return false;
175
176 // The common value must be valid in all incoming blocks.
177 BasicBlock *ToBB = P->getParent();
178 if (auto *CommonInst = dyn_cast<Instruction>(CommonValue))
179 if (!DT->dominates(CommonInst, ToBB))
180 return false;
181
182 // We have a phi with exactly 1 variable incoming value and 1 or more constant
183 // incoming values. See if all constant incoming values can be mapped back to
184 // the same incoming variable value.
185 for (auto &IncomingConstant : IncomingConstants) {
186 Constant *C = IncomingConstant.first;
187 BasicBlock *IncomingBB = P->getIncomingBlock(IncomingConstant.second);
188 if (C != LVI->getConstantOnEdge(CommonValue, IncomingBB, ToBB, P))
189 return false;
190 }
191
192 // All constant incoming values map to the same variable along the incoming
193 // edges of the phi. The phi is unnecessary. However, we must drop all
194 // poison-generating flags to ensure that no poison is propagated to the phi
195 // location by performing this substitution.
196 // Warning: If the underlying analysis changes, this may not be enough to
197 // guarantee that poison is not propagated.
198 // TODO: We may be able to re-infer flags by re-analyzing the instruction.
199 if (auto *CommonInst = dyn_cast<Instruction>(CommonValue))
200 CommonInst->dropPoisonGeneratingFlags();
201 P->replaceAllUsesWith(CommonValue);
202 P->eraseFromParent();
203 ++NumPhiCommon;
204 return true;
205 }
206
processPHI(PHINode * P,LazyValueInfo * LVI,DominatorTree * DT,const SimplifyQuery & SQ)207 static bool processPHI(PHINode *P, LazyValueInfo *LVI, DominatorTree *DT,
208 const SimplifyQuery &SQ) {
209 bool Changed = false;
210
211 BasicBlock *BB = P->getParent();
212 for (unsigned i = 0, e = P->getNumIncomingValues(); i < e; ++i) {
213 Value *Incoming = P->getIncomingValue(i);
214 if (isa<Constant>(Incoming)) continue;
215
216 Value *V = LVI->getConstantOnEdge(Incoming, P->getIncomingBlock(i), BB, P);
217
218 // Look if the incoming value is a select with a scalar condition for which
219 // LVI can tells us the value. In that case replace the incoming value with
220 // the appropriate value of the select. This often allows us to remove the
221 // select later.
222 if (!V) {
223 SelectInst *SI = dyn_cast<SelectInst>(Incoming);
224 if (!SI) continue;
225
226 Value *Condition = SI->getCondition();
227 if (!Condition->getType()->isVectorTy()) {
228 if (Constant *C = LVI->getConstantOnEdge(
229 Condition, P->getIncomingBlock(i), BB, P)) {
230 if (C->isOneValue()) {
231 V = SI->getTrueValue();
232 } else if (C->isZeroValue()) {
233 V = SI->getFalseValue();
234 }
235 // Once LVI learns to handle vector types, we could also add support
236 // for vector type constants that are not all zeroes or all ones.
237 }
238 }
239
240 // Look if the select has a constant but LVI tells us that the incoming
241 // value can never be that constant. In that case replace the incoming
242 // value with the other value of the select. This often allows us to
243 // remove the select later.
244 if (!V) {
245 Constant *C = dyn_cast<Constant>(SI->getFalseValue());
246 if (!C) continue;
247
248 if (LVI->getPredicateOnEdge(ICmpInst::ICMP_EQ, SI, C,
249 P->getIncomingBlock(i), BB, P) !=
250 LazyValueInfo::False)
251 continue;
252 V = SI->getTrueValue();
253 }
254
255 LLVM_DEBUG(dbgs() << "CVP: Threading PHI over " << *SI << '\n');
256 }
257
258 P->setIncomingValue(i, V);
259 Changed = true;
260 }
261
262 if (Value *V = SimplifyInstruction(P, SQ)) {
263 P->replaceAllUsesWith(V);
264 P->eraseFromParent();
265 Changed = true;
266 }
267
268 if (!Changed)
269 Changed = simplifyCommonValuePhi(P, LVI, DT);
270
271 if (Changed)
272 ++NumPhis;
273
274 return Changed;
275 }
276
processMemAccess(Instruction * I,LazyValueInfo * LVI)277 static bool processMemAccess(Instruction *I, LazyValueInfo *LVI) {
278 Value *Pointer = nullptr;
279 if (LoadInst *L = dyn_cast<LoadInst>(I))
280 Pointer = L->getPointerOperand();
281 else
282 Pointer = cast<StoreInst>(I)->getPointerOperand();
283
284 if (isa<Constant>(Pointer)) return false;
285
286 Constant *C = LVI->getConstant(Pointer, I->getParent(), I);
287 if (!C) return false;
288
289 ++NumMemAccess;
290 I->replaceUsesOfWith(Pointer, C);
291 return true;
292 }
293
294 /// See if LazyValueInfo's ability to exploit edge conditions or range
295 /// information is sufficient to prove this comparison. Even for local
296 /// conditions, this can sometimes prove conditions instcombine can't by
297 /// exploiting range information.
processCmp(CmpInst * Cmp,LazyValueInfo * LVI)298 static bool processCmp(CmpInst *Cmp, LazyValueInfo *LVI) {
299 Value *Op0 = Cmp->getOperand(0);
300 auto *C = dyn_cast<Constant>(Cmp->getOperand(1));
301 if (!C)
302 return false;
303
304 // As a policy choice, we choose not to waste compile time on anything where
305 // the comparison is testing local values. While LVI can sometimes reason
306 // about such cases, it's not its primary purpose. We do make sure to do
307 // the block local query for uses from terminator instructions, but that's
308 // handled in the code for each terminator. As an exception, we allow phi
309 // nodes, for which LVI can thread the condition into predecessors.
310 auto *I = dyn_cast<Instruction>(Op0);
311 if (I && I->getParent() == Cmp->getParent() && !isa<PHINode>(I))
312 return false;
313
314 LazyValueInfo::Tristate Result =
315 LVI->getPredicateAt(Cmp->getPredicate(), Op0, C, Cmp);
316 if (Result == LazyValueInfo::Unknown)
317 return false;
318
319 ++NumCmps;
320 Constant *TorF = ConstantInt::get(Type::getInt1Ty(Cmp->getContext()), Result);
321 Cmp->replaceAllUsesWith(TorF);
322 Cmp->eraseFromParent();
323 return true;
324 }
325
326 /// Simplify a switch instruction by removing cases which can never fire. If the
327 /// uselessness of a case could be determined locally then constant propagation
328 /// would already have figured it out. Instead, walk the predecessors and
329 /// statically evaluate cases based on information available on that edge. Cases
330 /// that cannot fire no matter what the incoming edge can safely be removed. If
331 /// a case fires on every incoming edge then the entire switch can be removed
332 /// and replaced with a branch to the case destination.
processSwitch(SwitchInst * I,LazyValueInfo * LVI,DominatorTree * DT)333 static bool processSwitch(SwitchInst *I, LazyValueInfo *LVI,
334 DominatorTree *DT) {
335 DomTreeUpdater DTU(*DT, DomTreeUpdater::UpdateStrategy::Lazy);
336 Value *Cond = I->getCondition();
337 BasicBlock *BB = I->getParent();
338
339 // If the condition was defined in same block as the switch then LazyValueInfo
340 // currently won't say anything useful about it, though in theory it could.
341 if (isa<Instruction>(Cond) && cast<Instruction>(Cond)->getParent() == BB)
342 return false;
343
344 // If the switch is unreachable then trying to improve it is a waste of time.
345 pred_iterator PB = pred_begin(BB), PE = pred_end(BB);
346 if (PB == PE) return false;
347
348 // Analyse each switch case in turn.
349 bool Changed = false;
350 DenseMap<BasicBlock*, int> SuccessorsCount;
351 for (auto *Succ : successors(BB))
352 SuccessorsCount[Succ]++;
353
354 { // Scope for SwitchInstProfUpdateWrapper. It must not live during
355 // ConstantFoldTerminator() as the underlying SwitchInst can be changed.
356 SwitchInstProfUpdateWrapper SI(*I);
357
358 for (auto CI = SI->case_begin(), CE = SI->case_end(); CI != CE;) {
359 ConstantInt *Case = CI->getCaseValue();
360
361 // Check to see if the switch condition is equal to/not equal to the case
362 // value on every incoming edge, equal/not equal being the same each time.
363 LazyValueInfo::Tristate State = LazyValueInfo::Unknown;
364 for (pred_iterator PI = PB; PI != PE; ++PI) {
365 // Is the switch condition equal to the case value?
366 LazyValueInfo::Tristate Value = LVI->getPredicateOnEdge(CmpInst::ICMP_EQ,
367 Cond, Case, *PI,
368 BB, SI);
369 // Give up on this case if nothing is known.
370 if (Value == LazyValueInfo::Unknown) {
371 State = LazyValueInfo::Unknown;
372 break;
373 }
374
375 // If this was the first edge to be visited, record that all other edges
376 // need to give the same result.
377 if (PI == PB) {
378 State = Value;
379 continue;
380 }
381
382 // If this case is known to fire for some edges and known not to fire for
383 // others then there is nothing we can do - give up.
384 if (Value != State) {
385 State = LazyValueInfo::Unknown;
386 break;
387 }
388 }
389
390 if (State == LazyValueInfo::False) {
391 // This case never fires - remove it.
392 BasicBlock *Succ = CI->getCaseSuccessor();
393 Succ->removePredecessor(BB);
394 CI = SI.removeCase(CI);
395 CE = SI->case_end();
396
397 // The condition can be modified by removePredecessor's PHI simplification
398 // logic.
399 Cond = SI->getCondition();
400
401 ++NumDeadCases;
402 Changed = true;
403 if (--SuccessorsCount[Succ] == 0)
404 DTU.applyUpdatesPermissive({{DominatorTree::Delete, BB, Succ}});
405 continue;
406 }
407 if (State == LazyValueInfo::True) {
408 // This case always fires. Arrange for the switch to be turned into an
409 // unconditional branch by replacing the switch condition with the case
410 // value.
411 SI->setCondition(Case);
412 NumDeadCases += SI->getNumCases();
413 Changed = true;
414 break;
415 }
416
417 // Increment the case iterator since we didn't delete it.
418 ++CI;
419 }
420 }
421
422 if (Changed)
423 // If the switch has been simplified to the point where it can be replaced
424 // by a branch then do so now.
425 ConstantFoldTerminator(BB, /*DeleteDeadConditions = */ false,
426 /*TLI = */ nullptr, &DTU);
427 return Changed;
428 }
429
430 // See if we can prove that the given binary op intrinsic will not overflow.
willNotOverflow(BinaryOpIntrinsic * BO,LazyValueInfo * LVI)431 static bool willNotOverflow(BinaryOpIntrinsic *BO, LazyValueInfo *LVI) {
432 ConstantRange LRange = LVI->getConstantRange(
433 BO->getLHS(), BO->getParent(), BO);
434 ConstantRange RRange = LVI->getConstantRange(
435 BO->getRHS(), BO->getParent(), BO);
436 ConstantRange NWRegion = ConstantRange::makeGuaranteedNoWrapRegion(
437 BO->getBinaryOp(), RRange, BO->getNoWrapKind());
438 return NWRegion.contains(LRange);
439 }
440
setDeducedOverflowingFlags(Value * V,Instruction::BinaryOps Opcode,bool NewNSW,bool NewNUW)441 static void setDeducedOverflowingFlags(Value *V, Instruction::BinaryOps Opcode,
442 bool NewNSW, bool NewNUW) {
443 Statistic *OpcNW, *OpcNSW, *OpcNUW;
444 switch (Opcode) {
445 case Instruction::Add:
446 OpcNW = &NumAddNW;
447 OpcNSW = &NumAddNSW;
448 OpcNUW = &NumAddNUW;
449 break;
450 case Instruction::Sub:
451 OpcNW = &NumSubNW;
452 OpcNSW = &NumSubNSW;
453 OpcNUW = &NumSubNUW;
454 break;
455 case Instruction::Mul:
456 OpcNW = &NumMulNW;
457 OpcNSW = &NumMulNSW;
458 OpcNUW = &NumMulNUW;
459 break;
460 case Instruction::Shl:
461 OpcNW = &NumShlNW;
462 OpcNSW = &NumShlNSW;
463 OpcNUW = &NumShlNUW;
464 break;
465 default:
466 llvm_unreachable("Will not be called with other binops");
467 }
468
469 auto *Inst = dyn_cast<Instruction>(V);
470 if (NewNSW) {
471 ++NumNW;
472 ++*OpcNW;
473 ++NumNSW;
474 ++*OpcNSW;
475 if (Inst)
476 Inst->setHasNoSignedWrap();
477 }
478 if (NewNUW) {
479 ++NumNW;
480 ++*OpcNW;
481 ++NumNUW;
482 ++*OpcNUW;
483 if (Inst)
484 Inst->setHasNoUnsignedWrap();
485 }
486 }
487
488 static bool processBinOp(BinaryOperator *BinOp, LazyValueInfo *LVI);
489
490 // Rewrite this with.overflow intrinsic as non-overflowing.
processOverflowIntrinsic(WithOverflowInst * WO,LazyValueInfo * LVI)491 static void processOverflowIntrinsic(WithOverflowInst *WO, LazyValueInfo *LVI) {
492 IRBuilder<> B(WO);
493 Instruction::BinaryOps Opcode = WO->getBinaryOp();
494 bool NSW = WO->isSigned();
495 bool NUW = !WO->isSigned();
496
497 Value *NewOp =
498 B.CreateBinOp(Opcode, WO->getLHS(), WO->getRHS(), WO->getName());
499 setDeducedOverflowingFlags(NewOp, Opcode, NSW, NUW);
500
501 StructType *ST = cast<StructType>(WO->getType());
502 Constant *Struct = ConstantStruct::get(ST,
503 { UndefValue::get(ST->getElementType(0)),
504 ConstantInt::getFalse(ST->getElementType(1)) });
505 Value *NewI = B.CreateInsertValue(Struct, NewOp, 0);
506 WO->replaceAllUsesWith(NewI);
507 WO->eraseFromParent();
508 ++NumOverflows;
509
510 // See if we can infer the other no-wrap too.
511 if (auto *BO = dyn_cast<BinaryOperator>(NewOp))
512 processBinOp(BO, LVI);
513 }
514
processSaturatingInst(SaturatingInst * SI,LazyValueInfo * LVI)515 static void processSaturatingInst(SaturatingInst *SI, LazyValueInfo *LVI) {
516 Instruction::BinaryOps Opcode = SI->getBinaryOp();
517 bool NSW = SI->isSigned();
518 bool NUW = !SI->isSigned();
519 BinaryOperator *BinOp = BinaryOperator::Create(
520 Opcode, SI->getLHS(), SI->getRHS(), SI->getName(), SI);
521 BinOp->setDebugLoc(SI->getDebugLoc());
522 setDeducedOverflowingFlags(BinOp, Opcode, NSW, NUW);
523
524 SI->replaceAllUsesWith(BinOp);
525 SI->eraseFromParent();
526 ++NumSaturating;
527
528 // See if we can infer the other no-wrap too.
529 if (auto *BO = dyn_cast<BinaryOperator>(BinOp))
530 processBinOp(BO, LVI);
531 }
532
533 /// Infer nonnull attributes for the arguments at the specified callsite.
processCallSite(CallBase & CB,LazyValueInfo * LVI)534 static bool processCallSite(CallBase &CB, LazyValueInfo *LVI) {
535 SmallVector<unsigned, 4> ArgNos;
536 unsigned ArgNo = 0;
537
538 if (auto *WO = dyn_cast<WithOverflowInst>(&CB)) {
539 if (WO->getLHS()->getType()->isIntegerTy() && willNotOverflow(WO, LVI)) {
540 processOverflowIntrinsic(WO, LVI);
541 return true;
542 }
543 }
544
545 if (auto *SI = dyn_cast<SaturatingInst>(&CB)) {
546 if (SI->getType()->isIntegerTy() && willNotOverflow(SI, LVI)) {
547 processSaturatingInst(SI, LVI);
548 return true;
549 }
550 }
551
552 // Deopt bundle operands are intended to capture state with minimal
553 // perturbance of the code otherwise. If we can find a constant value for
554 // any such operand and remove a use of the original value, that's
555 // desireable since it may allow further optimization of that value (e.g. via
556 // single use rules in instcombine). Since deopt uses tend to,
557 // idiomatically, appear along rare conditional paths, it's reasonable likely
558 // we may have a conditional fact with which LVI can fold.
559 if (auto DeoptBundle = CB.getOperandBundle(LLVMContext::OB_deopt)) {
560 bool Progress = false;
561 for (const Use &ConstU : DeoptBundle->Inputs) {
562 Use &U = const_cast<Use&>(ConstU);
563 Value *V = U.get();
564 if (V->getType()->isVectorTy()) continue;
565 if (isa<Constant>(V)) continue;
566
567 Constant *C = LVI->getConstant(V, CB.getParent(), &CB);
568 if (!C) continue;
569 U.set(C);
570 Progress = true;
571 }
572 if (Progress)
573 return true;
574 }
575
576 for (Value *V : CB.args()) {
577 PointerType *Type = dyn_cast<PointerType>(V->getType());
578 // Try to mark pointer typed parameters as non-null. We skip the
579 // relatively expensive analysis for constants which are obviously either
580 // null or non-null to start with.
581 if (Type && !CB.paramHasAttr(ArgNo, Attribute::NonNull) &&
582 !isa<Constant>(V) &&
583 LVI->getPredicateAt(ICmpInst::ICMP_EQ, V,
584 ConstantPointerNull::get(Type),
585 &CB) == LazyValueInfo::False)
586 ArgNos.push_back(ArgNo);
587 ArgNo++;
588 }
589
590 assert(ArgNo == CB.arg_size() && "sanity check");
591
592 if (ArgNos.empty())
593 return false;
594
595 AttributeList AS = CB.getAttributes();
596 LLVMContext &Ctx = CB.getContext();
597 AS = AS.addParamAttribute(Ctx, ArgNos,
598 Attribute::get(Ctx, Attribute::NonNull));
599 CB.setAttributes(AS);
600
601 return true;
602 }
603
hasPositiveOperands(BinaryOperator * SDI,LazyValueInfo * LVI)604 static bool hasPositiveOperands(BinaryOperator *SDI, LazyValueInfo *LVI) {
605 Constant *Zero = ConstantInt::get(SDI->getType(), 0);
606 for (Value *O : SDI->operands()) {
607 auto Result = LVI->getPredicateAt(ICmpInst::ICMP_SGE, O, Zero, SDI);
608 if (Result != LazyValueInfo::True)
609 return false;
610 }
611 return true;
612 }
613
614 /// Try to shrink a udiv/urem's width down to the smallest power of two that's
615 /// sufficient to contain its operands.
processUDivOrURem(BinaryOperator * Instr,LazyValueInfo * LVI)616 static bool processUDivOrURem(BinaryOperator *Instr, LazyValueInfo *LVI) {
617 assert(Instr->getOpcode() == Instruction::UDiv ||
618 Instr->getOpcode() == Instruction::URem);
619 if (Instr->getType()->isVectorTy())
620 return false;
621
622 // Find the smallest power of two bitwidth that's sufficient to hold Instr's
623 // operands.
624 auto OrigWidth = Instr->getType()->getIntegerBitWidth();
625 ConstantRange OperandRange(OrigWidth, /*isFullSet=*/false);
626 for (Value *Operand : Instr->operands()) {
627 OperandRange = OperandRange.unionWith(
628 LVI->getConstantRange(Operand, Instr->getParent()));
629 }
630 // Don't shrink below 8 bits wide.
631 unsigned NewWidth = std::max<unsigned>(
632 PowerOf2Ceil(OperandRange.getUnsignedMax().getActiveBits()), 8);
633 // NewWidth might be greater than OrigWidth if OrigWidth is not a power of
634 // two.
635 if (NewWidth >= OrigWidth)
636 return false;
637
638 ++NumUDivs;
639 IRBuilder<> B{Instr};
640 auto *TruncTy = Type::getIntNTy(Instr->getContext(), NewWidth);
641 auto *LHS = B.CreateTruncOrBitCast(Instr->getOperand(0), TruncTy,
642 Instr->getName() + ".lhs.trunc");
643 auto *RHS = B.CreateTruncOrBitCast(Instr->getOperand(1), TruncTy,
644 Instr->getName() + ".rhs.trunc");
645 auto *BO = B.CreateBinOp(Instr->getOpcode(), LHS, RHS, Instr->getName());
646 auto *Zext = B.CreateZExt(BO, Instr->getType(), Instr->getName() + ".zext");
647 if (auto *BinOp = dyn_cast<BinaryOperator>(BO))
648 if (BinOp->getOpcode() == Instruction::UDiv)
649 BinOp->setIsExact(Instr->isExact());
650
651 Instr->replaceAllUsesWith(Zext);
652 Instr->eraseFromParent();
653 return true;
654 }
655
processSRem(BinaryOperator * SDI,LazyValueInfo * LVI)656 static bool processSRem(BinaryOperator *SDI, LazyValueInfo *LVI) {
657 if (SDI->getType()->isVectorTy() || !hasPositiveOperands(SDI, LVI))
658 return false;
659
660 ++NumSRems;
661 auto *BO = BinaryOperator::CreateURem(SDI->getOperand(0), SDI->getOperand(1),
662 SDI->getName(), SDI);
663 BO->setDebugLoc(SDI->getDebugLoc());
664 SDI->replaceAllUsesWith(BO);
665 SDI->eraseFromParent();
666
667 // Try to process our new urem.
668 processUDivOrURem(BO, LVI);
669
670 return true;
671 }
672
673 /// See if LazyValueInfo's ability to exploit edge conditions or range
674 /// information is sufficient to prove the both operands of this SDiv are
675 /// positive. If this is the case, replace the SDiv with a UDiv. Even for local
676 /// conditions, this can sometimes prove conditions instcombine can't by
677 /// exploiting range information.
processSDiv(BinaryOperator * SDI,LazyValueInfo * LVI)678 static bool processSDiv(BinaryOperator *SDI, LazyValueInfo *LVI) {
679 if (SDI->getType()->isVectorTy() || !hasPositiveOperands(SDI, LVI))
680 return false;
681
682 ++NumSDivs;
683 auto *BO = BinaryOperator::CreateUDiv(SDI->getOperand(0), SDI->getOperand(1),
684 SDI->getName(), SDI);
685 BO->setDebugLoc(SDI->getDebugLoc());
686 BO->setIsExact(SDI->isExact());
687 SDI->replaceAllUsesWith(BO);
688 SDI->eraseFromParent();
689
690 // Try to simplify our new udiv.
691 processUDivOrURem(BO, LVI);
692
693 return true;
694 }
695
processAShr(BinaryOperator * SDI,LazyValueInfo * LVI)696 static bool processAShr(BinaryOperator *SDI, LazyValueInfo *LVI) {
697 if (SDI->getType()->isVectorTy())
698 return false;
699
700 Constant *Zero = ConstantInt::get(SDI->getType(), 0);
701 if (LVI->getPredicateAt(ICmpInst::ICMP_SGE, SDI->getOperand(0), Zero, SDI) !=
702 LazyValueInfo::True)
703 return false;
704
705 ++NumAShrs;
706 auto *BO = BinaryOperator::CreateLShr(SDI->getOperand(0), SDI->getOperand(1),
707 SDI->getName(), SDI);
708 BO->setDebugLoc(SDI->getDebugLoc());
709 BO->setIsExact(SDI->isExact());
710 SDI->replaceAllUsesWith(BO);
711 SDI->eraseFromParent();
712
713 return true;
714 }
715
processSExt(SExtInst * SDI,LazyValueInfo * LVI)716 static bool processSExt(SExtInst *SDI, LazyValueInfo *LVI) {
717 if (SDI->getType()->isVectorTy())
718 return false;
719
720 Value *Base = SDI->getOperand(0);
721
722 Constant *Zero = ConstantInt::get(Base->getType(), 0);
723 if (LVI->getPredicateAt(ICmpInst::ICMP_SGE, Base, Zero, SDI) !=
724 LazyValueInfo::True)
725 return false;
726
727 ++NumSExt;
728 auto *ZExt =
729 CastInst::CreateZExtOrBitCast(Base, SDI->getType(), SDI->getName(), SDI);
730 ZExt->setDebugLoc(SDI->getDebugLoc());
731 SDI->replaceAllUsesWith(ZExt);
732 SDI->eraseFromParent();
733
734 return true;
735 }
736
processBinOp(BinaryOperator * BinOp,LazyValueInfo * LVI)737 static bool processBinOp(BinaryOperator *BinOp, LazyValueInfo *LVI) {
738 using OBO = OverflowingBinaryOperator;
739
740 if (DontAddNoWrapFlags)
741 return false;
742
743 if (BinOp->getType()->isVectorTy())
744 return false;
745
746 bool NSW = BinOp->hasNoSignedWrap();
747 bool NUW = BinOp->hasNoUnsignedWrap();
748 if (NSW && NUW)
749 return false;
750
751 BasicBlock *BB = BinOp->getParent();
752
753 Instruction::BinaryOps Opcode = BinOp->getOpcode();
754 Value *LHS = BinOp->getOperand(0);
755 Value *RHS = BinOp->getOperand(1);
756
757 ConstantRange LRange = LVI->getConstantRange(LHS, BB, BinOp);
758 ConstantRange RRange = LVI->getConstantRange(RHS, BB, BinOp);
759
760 bool Changed = false;
761 bool NewNUW = false, NewNSW = false;
762 if (!NUW) {
763 ConstantRange NUWRange = ConstantRange::makeGuaranteedNoWrapRegion(
764 Opcode, RRange, OBO::NoUnsignedWrap);
765 NewNUW = NUWRange.contains(LRange);
766 Changed |= NewNUW;
767 }
768 if (!NSW) {
769 ConstantRange NSWRange = ConstantRange::makeGuaranteedNoWrapRegion(
770 Opcode, RRange, OBO::NoSignedWrap);
771 NewNSW = NSWRange.contains(LRange);
772 Changed |= NewNSW;
773 }
774
775 setDeducedOverflowingFlags(BinOp, Opcode, NewNSW, NewNUW);
776
777 return Changed;
778 }
779
processAnd(BinaryOperator * BinOp,LazyValueInfo * LVI)780 static bool processAnd(BinaryOperator *BinOp, LazyValueInfo *LVI) {
781 if (BinOp->getType()->isVectorTy())
782 return false;
783
784 // Pattern match (and lhs, C) where C includes a superset of bits which might
785 // be set in lhs. This is a common truncation idiom created by instcombine.
786 BasicBlock *BB = BinOp->getParent();
787 Value *LHS = BinOp->getOperand(0);
788 ConstantInt *RHS = dyn_cast<ConstantInt>(BinOp->getOperand(1));
789 if (!RHS || !RHS->getValue().isMask())
790 return false;
791
792 // We can only replace the AND with LHS based on range info if the range does
793 // not include undef.
794 ConstantRange LRange =
795 LVI->getConstantRange(LHS, BB, BinOp, /*UndefAllowed=*/false);
796 if (!LRange.getUnsignedMax().ule(RHS->getValue()))
797 return false;
798
799 BinOp->replaceAllUsesWith(LHS);
800 BinOp->eraseFromParent();
801 NumAnd++;
802 return true;
803 }
804
805
getConstantAt(Value * V,Instruction * At,LazyValueInfo * LVI)806 static Constant *getConstantAt(Value *V, Instruction *At, LazyValueInfo *LVI) {
807 if (Constant *C = LVI->getConstant(V, At->getParent(), At))
808 return C;
809
810 // TODO: The following really should be sunk inside LVI's core algorithm, or
811 // at least the outer shims around such.
812 auto *C = dyn_cast<CmpInst>(V);
813 if (!C) return nullptr;
814
815 Value *Op0 = C->getOperand(0);
816 Constant *Op1 = dyn_cast<Constant>(C->getOperand(1));
817 if (!Op1) return nullptr;
818
819 LazyValueInfo::Tristate Result =
820 LVI->getPredicateAt(C->getPredicate(), Op0, Op1, At);
821 if (Result == LazyValueInfo::Unknown)
822 return nullptr;
823
824 return (Result == LazyValueInfo::True) ?
825 ConstantInt::getTrue(C->getContext()) :
826 ConstantInt::getFalse(C->getContext());
827 }
828
runImpl(Function & F,LazyValueInfo * LVI,DominatorTree * DT,const SimplifyQuery & SQ)829 static bool runImpl(Function &F, LazyValueInfo *LVI, DominatorTree *DT,
830 const SimplifyQuery &SQ) {
831 bool FnChanged = false;
832 // Visiting in a pre-order depth-first traversal causes us to simplify early
833 // blocks before querying later blocks (which require us to analyze early
834 // blocks). Eagerly simplifying shallow blocks means there is strictly less
835 // work to do for deep blocks. This also means we don't visit unreachable
836 // blocks.
837 for (BasicBlock *BB : depth_first(&F.getEntryBlock())) {
838 bool BBChanged = false;
839 for (BasicBlock::iterator BI = BB->begin(), BE = BB->end(); BI != BE;) {
840 Instruction *II = &*BI++;
841 switch (II->getOpcode()) {
842 case Instruction::Select:
843 BBChanged |= processSelect(cast<SelectInst>(II), LVI);
844 break;
845 case Instruction::PHI:
846 BBChanged |= processPHI(cast<PHINode>(II), LVI, DT, SQ);
847 break;
848 case Instruction::ICmp:
849 case Instruction::FCmp:
850 BBChanged |= processCmp(cast<CmpInst>(II), LVI);
851 break;
852 case Instruction::Load:
853 case Instruction::Store:
854 BBChanged |= processMemAccess(II, LVI);
855 break;
856 case Instruction::Call:
857 case Instruction::Invoke:
858 BBChanged |= processCallSite(cast<CallBase>(*II), LVI);
859 break;
860 case Instruction::SRem:
861 BBChanged |= processSRem(cast<BinaryOperator>(II), LVI);
862 break;
863 case Instruction::SDiv:
864 BBChanged |= processSDiv(cast<BinaryOperator>(II), LVI);
865 break;
866 case Instruction::UDiv:
867 case Instruction::URem:
868 BBChanged |= processUDivOrURem(cast<BinaryOperator>(II), LVI);
869 break;
870 case Instruction::AShr:
871 BBChanged |= processAShr(cast<BinaryOperator>(II), LVI);
872 break;
873 case Instruction::SExt:
874 BBChanged |= processSExt(cast<SExtInst>(II), LVI);
875 break;
876 case Instruction::Add:
877 case Instruction::Sub:
878 case Instruction::Mul:
879 case Instruction::Shl:
880 BBChanged |= processBinOp(cast<BinaryOperator>(II), LVI);
881 break;
882 case Instruction::And:
883 BBChanged |= processAnd(cast<BinaryOperator>(II), LVI);
884 break;
885 }
886 }
887
888 Instruction *Term = BB->getTerminator();
889 switch (Term->getOpcode()) {
890 case Instruction::Switch:
891 BBChanged |= processSwitch(cast<SwitchInst>(Term), LVI, DT);
892 break;
893 case Instruction::Ret: {
894 auto *RI = cast<ReturnInst>(Term);
895 // Try to determine the return value if we can. This is mainly here to
896 // simplify the writing of unit tests, but also helps to enable IPO by
897 // constant folding the return values of callees.
898 auto *RetVal = RI->getReturnValue();
899 if (!RetVal) break; // handle "ret void"
900 if (isa<Constant>(RetVal)) break; // nothing to do
901 if (auto *C = getConstantAt(RetVal, RI, LVI)) {
902 ++NumReturns;
903 RI->replaceUsesOfWith(RetVal, C);
904 BBChanged = true;
905 }
906 }
907 }
908
909 FnChanged |= BBChanged;
910 }
911
912 return FnChanged;
913 }
914
runOnFunction(Function & F)915 bool CorrelatedValuePropagation::runOnFunction(Function &F) {
916 if (skipFunction(F))
917 return false;
918
919 LazyValueInfo *LVI = &getAnalysis<LazyValueInfoWrapperPass>().getLVI();
920 DominatorTree *DT = &getAnalysis<DominatorTreeWrapperPass>().getDomTree();
921
922 return runImpl(F, LVI, DT, getBestSimplifyQuery(*this, F));
923 }
924
925 PreservedAnalyses
run(Function & F,FunctionAnalysisManager & AM)926 CorrelatedValuePropagationPass::run(Function &F, FunctionAnalysisManager &AM) {
927 LazyValueInfo *LVI = &AM.getResult<LazyValueAnalysis>(F);
928 DominatorTree *DT = &AM.getResult<DominatorTreeAnalysis>(F);
929
930 bool Changed = runImpl(F, LVI, DT, getBestSimplifyQuery(AM, F));
931
932 if (!Changed)
933 return PreservedAnalyses::all();
934 PreservedAnalyses PA;
935 PA.preserve<GlobalsAA>();
936 PA.preserve<DominatorTreeAnalysis>();
937 PA.preserve<LazyValueAnalysis>();
938 return PA;
939 }
940