Lines Matching +full:csr +full:- +full:2 +full:l
1 //===-- DifferenceEngine.cpp - Structural function/module comparison ------===//
5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
7 //===----------------------------------------------------------------------===//
12 //===----------------------------------------------------------------------===//
55 unsigned Target = (Index + 1) / 2 - 1; in insert()
63 /// Remove the minimum value in the heap. Only valid on a non-empty heap.
68 unsigned NewSize = Storage.size() - 1; in remove_min()
79 // With a 1-based index, the children would be Index*2 and Index*2+1. in remove_min()
80 unsigned R = (Index + 1) * 2; in remove_min()
81 unsigned L = R - 1; in remove_min() local
85 // If L is also out of bounds, we're done immediately. in remove_min()
86 if (L >= NewSize) break; in remove_min()
88 // Otherwise, test whether we should swap L and Index. in remove_min()
89 if (Precedes(Storage[L], Storage[Index])) in remove_min()
90 std::swap(Storage[L], Storage[Index]); in remove_min()
94 // Otherwise, we need to compare with the smaller of L and R. in remove_min()
96 unsigned IndexToTest = (Precedes(Storage[L], Storage[R]) ? L : R); in remove_min()
98 // If Index is >= the min of L and R, then heap ordering is restored. in remove_min()
113 /// A function-scope difference engine.
151 // We aim to avoid false negatives in llvm-diff, that is, ensure that
163 // considering step-wise parallel execution, and incrementally proving
175 // Maps old values to assumed-to-be-equivalent new values
202 BlockDiffCandidate &Result = BlockDiffCandidates[It->second]; in getOrCreateBlockDiffCandidate()
245 bool tryUnify(const BasicBlock *L, const BasicBlock *R) { in tryUnify() argument
246 const BasicBlock *&Ref = Blocks[L]; in tryUnify()
251 Engine.logf("successor %l cannot be equivalent to %r; " in tryUnify()
253 << L << R << Ref; in tryUnify()
258 Queue.insert(BlockPair(L, R)); in tryUnify()
264 void unify(const Instruction *L, const Instruction *R) { in unify() argument
265 DifferenceEngine::Context C(Engine, L, R); in unify()
267 bool Result = diff(L, R, true, true, true); in unify()
270 if (!L->use_empty()) in unify()
271 Values[L] = R; in unify()
285 for (const auto &[L, R] : BDC.EquivalenceAssumptions) { in checkAndReportDiffCandidates()
286 auto It = Values.find(L); in checkAndReportDiffCandidates()
287 if (It == Values.end() || It->second != R) { in checkAndReportDiffCandidates()
296 runBlockDiff(BDC.LBB->begin(), BDC.RBB->begin()); in checkAndReportDiffCandidates()
301 void diff(const BasicBlock *L, const BasicBlock *R) { in diff() argument
302 DifferenceEngine::Context C(Engine, L, R); in diff()
304 BasicBlock::const_iterator LI = L->begin(), LE = L->end(); in diff()
305 BasicBlock::const_iterator RI = R->begin(); in diff()
308 assert(LI != LE && RI != R->end()); in diff()
315 // Register (L, R) as diffing pair. Note that we could directly emit a in diff()
319 getOrCreateBlockDiffCandidate(L, R).KnownToDiffer = true; in diff()
324 if (!LeftI->use_empty()) in diff()
332 // Unify everything in the block, non-tentatively this time. in diff()
334 for (LI = L->begin(), RI = R->begin(); LI != LE; ++LI, ++RI) in diff()
338 bool matchForBlockDiff(const Instruction *L, const Instruction *R);
342 bool diffCallSites(const CallBase &L, const CallBase &R, bool Complain) { in diffCallSites() argument
344 AssumptionContext AC = {L.getParent(), R.getParent()}; in diffCallSites()
345 if (!equivalentAsOperands(L.getCalledOperand(), R.getCalledOperand(), in diffCallSites()
350 if (L.arg_size() != R.arg_size()) { in diffCallSites()
354 for (unsigned I = 0, E = L.arg_size(); I != E; ++I) in diffCallSites()
355 if (!equivalentAsOperands(L.getArgOperand(I), R.getArgOperand(I), &AC)) { in diffCallSites()
357 Engine.logf("arguments %l and %r differ") in diffCallSites()
358 << L.getArgOperand(I) << R.getArgOperand(I); in diffCallSites()
367 bool diff(const Instruction *L, const Instruction *R, bool Complain, in diff() argument
370 AssumptionContext ACValue = {L->getParent(), R->getParent()}; in diff()
375 if (L->getOpcode() != R->getOpcode()) { in diff()
380 if (isa<CmpInst>(L)) { in diff()
381 if (cast<CmpInst>(L)->getPredicate() in diff()
382 != cast<CmpInst>(R)->getPredicate()) { in diff()
386 } else if (isa<CallInst>(L)) { in diff()
387 return diffCallSites(cast<CallInst>(*L), cast<CallInst>(*R), Complain); in diff()
388 } else if (isa<PHINode>(L)) { in diff()
389 const PHINode &LI = cast<PHINode>(*L); in diff()
394 if (!LI.getType()->isPointerTy() || !RI.getType()->isPointerTy()) { in diff()
421 } else if (isa<InvokeInst>(L)) { in diff()
422 const InvokeInst &LI = cast<InvokeInst>(*L); in diff()
433 } else if (isa<CallBrInst>(L)) { in diff()
434 const CallBrInst &LI = cast<CallBrInst>(*L); in diff()
454 } else if (isa<BranchInst>(L)) { in diff()
455 const BranchInst *LI = cast<BranchInst>(L); in diff()
457 if (LI->isConditional() != RI->isConditional()) { in diff()
462 if (LI->isConditional()) { in diff()
463 if (!equivalentAsOperands(LI->getCondition(), RI->getCondition(), AC)) { in diff()
467 if (TryUnify) tryUnify(LI->getSuccessor(1), RI->getSuccessor(1)); in diff()
469 if (TryUnify) tryUnify(LI->getSuccessor(0), RI->getSuccessor(0)); in diff()
472 } else if (isa<IndirectBrInst>(L)) { in diff()
473 const IndirectBrInst *LI = cast<IndirectBrInst>(L); in diff()
475 if (LI->getNumDestinations() != RI->getNumDestinations()) { in diff()
480 if (!equivalentAsOperands(LI->getAddress(), RI->getAddress(), AC)) { in diff()
486 for (unsigned i = 0; i < LI->getNumDestinations(); i++) { in diff()
487 tryUnify(LI->getDestination(i), RI->getDestination(i)); in diff()
492 } else if (isa<SwitchInst>(L)) { in diff()
493 const SwitchInst *LI = cast<SwitchInst>(L); in diff()
495 if (!equivalentAsOperands(LI->getCondition(), RI->getCondition(), AC)) { in diff()
499 if (TryUnify) tryUnify(LI->getDefaultDest(), RI->getDefaultDest()); in diff()
504 for (auto Case : LI->cases()) in diff()
507 for (auto Case : RI->cases()) { in diff()
526 Engine.logf("left switch has extra case %l") << I->first; in diff()
530 } else if (isa<UnreachableInst>(L)) { in diff()
534 if (L->getNumOperands() != R->getNumOperands()) { in diff()
539 for (unsigned I = 0, E = L->getNumOperands(); I != E; ++I) { in diff()
540 Value *LO = L->getOperand(I), *RO = R->getOperand(I); in diff()
542 if (Complain) Engine.logf("operands %l and %r differ") << LO << RO; in diff()
551 bool equivalentAsOperands(const Constant *L, const Constant *R, in equivalentAsOperands() argument
554 if (L == R) in equivalentAsOperands()
557 if (L->getValueID() != R->getValueID()) in equivalentAsOperands()
561 if (isa<GlobalValue>(L)) in equivalentAsOperands()
562 return Engine.equivalentAsOperands(cast<GlobalValue>(L), in equivalentAsOperands()
566 if (isa<ConstantExpr>(L)) in equivalentAsOperands()
567 return equivalentAsOperands(cast<ConstantExpr>(L), cast<ConstantExpr>(R), in equivalentAsOperands()
571 // type; I don't know why. Just white-list them. in equivalentAsOperands()
572 if (isa<ConstantPointerNull>(L) || isa<UndefValue>(L) || isa<ConstantAggregateZero>(L)) in equivalentAsOperands()
577 if (isa<BlockAddress>(L)) in equivalentAsOperands()
578 return Blocks[cast<BlockAddress>(L)->getBasicBlock()] in equivalentAsOperands()
579 == cast<BlockAddress>(R)->getBasicBlock(); in equivalentAsOperands()
581 // If L and R are ConstantVectors, compare each element in equivalentAsOperands()
582 if (isa<ConstantVector>(L)) { in equivalentAsOperands()
583 const ConstantVector *CVL = cast<ConstantVector>(L); in equivalentAsOperands()
585 if (CVL->getType()->getNumElements() != CVR->getType()->getNumElements()) in equivalentAsOperands()
587 for (unsigned i = 0; i < CVL->getType()->getNumElements(); i++) { in equivalentAsOperands()
588 if (!equivalentAsOperands(CVL->getOperand(i), CVR->getOperand(i), AC)) in equivalentAsOperands()
594 // If L and R are ConstantArrays, compare the element count and types. in equivalentAsOperands()
595 if (isa<ConstantArray>(L)) { in equivalentAsOperands()
596 const ConstantArray *CAL = cast<ConstantArray>(L); in equivalentAsOperands()
598 // Sometimes a type may be equivalent, but not uniquified---e.g. it may in equivalentAsOperands()
600 if (CAL->getType()->getNumElements() != CAR->getType()->getNumElements()) in equivalentAsOperands()
603 for (unsigned I = 0; I < CAL->getType()->getNumElements(); ++I) { in equivalentAsOperands()
604 if (!equivalentAsOperands(CAL->getAggregateElement(I), in equivalentAsOperands()
605 CAR->getAggregateElement(I), AC)) in equivalentAsOperands()
612 // If L and R are ConstantStructs, compare each field and type. in equivalentAsOperands()
613 if (isa<ConstantStruct>(L)) { in equivalentAsOperands()
614 const ConstantStruct *CSL = cast<ConstantStruct>(L); in equivalentAsOperands()
615 const ConstantStruct *CSR = cast<ConstantStruct>(R); in equivalentAsOperands() local
617 const StructType *LTy = cast<StructType>(CSL->getType()); in equivalentAsOperands()
618 const StructType *RTy = cast<StructType>(CSR->getType()); in equivalentAsOperands()
623 if (LTy->getNumElements() != RTy->getNumElements() || in equivalentAsOperands()
624 LTy->isPacked() != RTy->isPacked()) in equivalentAsOperands()
627 for (unsigned I = 0; I < LTy->getNumElements(); I++) { in equivalentAsOperands()
628 const Value *LAgg = CSL->getAggregateElement(I); in equivalentAsOperands()
629 const Value *RAgg = CSR->getAggregateElement(I); in equivalentAsOperands()
633 // If the left and right operands aren't both re-analyzing the in equivalentAsOperands()
652 bool equivalentAsOperands(const ConstantExpr *L, const ConstantExpr *R, in equivalentAsOperands() argument
654 if (L == R) in equivalentAsOperands()
657 if (L->getOpcode() != R->getOpcode()) in equivalentAsOperands()
660 switch (L->getOpcode()) { in equivalentAsOperands()
669 if (L->getNumOperands() != R->getNumOperands()) in equivalentAsOperands()
672 for (unsigned I = 0, E = L->getNumOperands(); I != E; ++I) { in equivalentAsOperands()
673 const auto *LOp = L->getOperand(I); in equivalentAsOperands()
674 const auto *ROp = R->getOperand(I); in equivalentAsOperands()
678 // If the left and right operands aren't both re-analyzing the in equivalentAsOperands()
694 // equivalent, because it depends on not yet processed basic blocks -- see the
700 // * If AC is nullptr, we treat the pair as non-equivalent.
703 bool equivalentAsOperands(const Value *L, const Value *R, in equivalentAsOperands() argument
707 if (L->getValueID() != R->getValueID()) in equivalentAsOperands()
713 if (isa<Constant>(L)) in equivalentAsOperands()
714 return equivalentAsOperands(cast<Constant>(L), cast<Constant>(R), AC); in equivalentAsOperands()
716 if (isa<Instruction>(L)) { in equivalentAsOperands()
717 auto It = Values.find(L); in equivalentAsOperands()
719 return It->second == R; in equivalentAsOperands()
721 if (TentativeValues.count(std::make_pair(L, R))) in equivalentAsOperands()
724 // L and R might be equivalent, this could depend on not yet processed in equivalentAsOperands()
729 getOrCreateBlockDiffCandidate(AC->LBB, AC->RBB); in equivalentAsOperands()
730 auto InsertionResult = BDC.EquivalenceAssumptions.insert({L, R}); in equivalentAsOperands()
731 if (!InsertionResult.second && InsertionResult.first->second != R) { in equivalentAsOperands()
732 // We already have a conflicting equivalence assumption for L, so at in equivalentAsOperands()
743 // Assumptions disabled, so pessimistically assume non-equivalence. in equivalentAsOperands()
747 if (isa<Argument>(L)) in equivalentAsOperands()
748 return Values[L] == R; in equivalentAsOperands()
750 if (isa<BasicBlock>(L)) in equivalentAsOperands()
751 return Blocks[cast<BasicBlock>(L)] != R; in equivalentAsOperands()
767 void diff(const Function *L, const Function *R) { in diff() argument
770 if (L->arg_size() != R->arg_size()) in diff()
774 for (Function::const_arg_iterator LI = L->arg_begin(), LE = L->arg_end(), in diff()
775 RI = R->arg_begin(), RE = R->arg_end(); in diff()
779 tryUnify(&*L->begin(), &*R->begin()); in diff()
792 bool FunctionDifferenceEngine::matchForBlockDiff(const Instruction *L, in matchForBlockDiff() argument
794 return !diff(L, R, false, false, false); in matchForBlockDiff()
799 BasicBlock::const_iterator LE = LStart->getParent()->end(); in runBlockDiff()
800 BasicBlock::const_iterator RE = RStart->getParent()->end(); in runBlockDiff()
810 const unsigned LeftCost = 2; in runBlockDiff()
811 const unsigned RightCost = 2; in runBlockDiff()
832 Next[Index] = Cur[Index-1]; in runBlockDiff()
836 } else if (Next[Index-1].Cost <= Cur[Index].Cost) { in runBlockDiff()
837 Next[Index] = Next[Index-1]; in runBlockDiff()
851 // on out should be non-tentative. in runBlockDiff()
878 const Instruction *L = &*LI, *R = &*RI; in runBlockDiff() local
879 unify(L, R); in runBlockDiff()
880 Diff.addMatch(L, R); in runBlockDiff()
911 const Instruction *LTerm = LStart->getParent()->getTerminator(); in runBlockDiff()
912 const Instruction *RTerm = RStart->getParent()->getTerminator(); in runBlockDiff()
914 if (cast<BranchInst>(LTerm)->isConditional()) return; in runBlockDiff()
915 BasicBlock::const_iterator I = LTerm->getIterator(); in runBlockDiff()
916 if (I == LStart->getParent()->begin()) return; in runBlockDiff()
917 --I; in runBlockDiff()
921 if (!equivalentAsOperands(LCall->getCalledOperand(), in runBlockDiff()
922 RInvoke->getCalledOperand(), nullptr)) in runBlockDiff()
924 if (!LCall->use_empty()) in runBlockDiff()
926 tryUnify(LTerm->getSuccessor(0), RInvoke->getNormalDest()); in runBlockDiff()
928 if (cast<BranchInst>(RTerm)->isConditional()) return; in runBlockDiff()
929 BasicBlock::const_iterator I = RTerm->getIterator(); in runBlockDiff()
930 if (I == RStart->getParent()->begin()) return; in runBlockDiff()
931 --I; in runBlockDiff()
935 if (!equivalentAsOperands(LInvoke->getCalledOperand(), in runBlockDiff()
936 RCall->getCalledOperand(), nullptr)) in runBlockDiff()
938 if (!LInvoke->use_empty()) in runBlockDiff()
940 tryUnify(LInvoke->getNormalDest(), RTerm->getSuccessor(0)); in runBlockDiff()
947 void DifferenceEngine::diff(const Function *L, const Function *R) { in diff() argument
948 Context C(*this, L, R); in diff()
955 if (L->empty() && R->empty()) in diff()
957 else if (L->empty()) in diff()
959 else if (R->empty()) in diff()
962 FunctionDifferenceEngine(*this).diff(L, R); in diff()
965 void DifferenceEngine::diff(const Module *L, const Module *R) { in diff() argument
972 for (Module::const_iterator I = L->begin(), E = L->end(); I != E; ++I) { in diff()
974 StringRef Name = LFn->getName(); in diff()
982 if (Function *RFn = R->getFunction(LFn->getName())) in diff()
985 logf("function %l exists only in left module") << LFn; in diff()
988 for (Module::const_iterator I = R->begin(), E = R->end(); I != E; ++I) { in diff()
990 StringRef Name = RFn->getName(); in diff()
1012 diff(I->first, I->second); in diff()
1015 bool DifferenceEngine::equivalentAsOperands(const GlobalValue *L, in equivalentAsOperands() argument
1017 if (globalValueOracle) return (*globalValueOracle)(L, R); in equivalentAsOperands()
1019 if (isa<GlobalVariable>(L) && isa<GlobalVariable>(R)) { in equivalentAsOperands()
1020 const GlobalVariable *GVL = cast<GlobalVariable>(L); in equivalentAsOperands()
1022 if (GVL->hasLocalLinkage() && GVL->hasUniqueInitializer() && in equivalentAsOperands()
1023 GVR->hasLocalLinkage() && GVR->hasUniqueInitializer()) in equivalentAsOperands()
1025 .equivalentAsOperands(GVL->getInitializer(), GVR->getInitializer(), in equivalentAsOperands()
1029 return L->getName() == R->getName(); in equivalentAsOperands()