Index: llvm/lib/Transforms/Scalar/MemCpyOptimizer.cpp =================================================================== --- llvm/lib/Transforms/Scalar/MemCpyOptimizer.cpp +++ llvm/lib/Transforms/Scalar/MemCpyOptimizer.cpp @@ -1428,7 +1428,6 @@ namespace { -// TODO: rename enum Liveness { LiveUse, LiveDef }; using LiveDefOrUseInst = PointerIntPair; @@ -1452,6 +1451,7 @@ LiveDefOrUseInst FirstLiveUseOrDefInst; // All LiveUse or LiveDef Instructions on this block. + // FIXME: BSTMap for lookup and appearance order. SmallVector BBUsesOrDefs; // Records a first def or use instruction. @@ -1481,14 +1481,6 @@ // Returns the all LiveUses and LiveDefs. SmallVector &getBBUsesOrDefs() { return BBUsesOrDefs; } - // Sort the all LiveUses and LiveDefs by appearance. - void sortBBUsesOrDefs() { - auto isLess = [](const LiveDefOrUseInst &L, const LiveDefOrUseInst &R) { - return L.getPointer()->comesBefore(R.getPointer()); - }; - std::sort(BBUsesOrDefs.begin(), BBUsesOrDefs.end(), isLess); - } - // Returns true if there's a definition or use of the memory in this block. bool hasDefUseInst() const { return FirstLiveUseOrDefInst.getPointer() != nullptr; @@ -1516,16 +1508,16 @@ // Records a new definition or use of the alloca being tracked within this // basic block. void update(Instruction *I, Liveness L) { + // Set use or def for the first instruction, BB is LiveIn if the first user + // is use. if (!hasDefUseInst() || I->comesBefore(getFirstLiveUseOrDefInst().getPointer())) { - dbgs() << "set first use or def\n"; setFirstLiveDefOrUseInst(I, L); setLiveIn(L == LiveUse); } if (L == LiveUse) setHasUse(true); - dbgs() << "add use or def\n"; addLiveDefOrUseInst(I, L); } }; @@ -1620,42 +1612,24 @@ BasicBlockLivenessMap &DestLivenessMap, BasicBlockLivenessMap &SrcLivenessMap, BasicBlock *BB, Instruction *Load, Instruction *Store) { - dbgs() << "hi from instruction level conflict on\n" - << BB->getNameOrAsOperand() << "\n"; - // Check liveness inside the BB + // Check liveness inside the BB, check the uses in the order of appearance. auto SrcBBLiveness = SrcLivenessMap.lookup(BB); auto DestBBLiveness = DestLivenessMap.lookup(BB); bool SrcLive = SrcBBLiveness.isLiveOut(); bool DestLive = DestBBLiveness.isLiveOut(); - SrcBBLiveness.sortBBUsesOrDefs(); - DestBBLiveness.sortBBUsesOrDefs(); auto &SrcBBUsesOrDefs = SrcBBLiveness.getBBUsesOrDefs(); auto &DestBBUsesOrDefs = DestBBLiveness.getBBUsesOrDefs(); - LiveDefOrUseInst IL(nullptr); - bool IsSrc; - // This is destructive, but it's ok because there is no use for later. - while (!SrcBBUsesOrDefs.empty() || !DestBBUsesOrDefs.empty()) { - if (SrcBBUsesOrDefs.empty() || - (!DestBBUsesOrDefs.empty() && - SrcBBUsesOrDefs.back().getPointer()->comesBefore( - DestBBUsesOrDefs.back().getPointer()))) { - IL = DestBBUsesOrDefs.back(); - DestBBUsesOrDefs.pop_back(); - IsSrc = false; - } else { - IL = SrcBBUsesOrDefs.back(); - SrcBBUsesOrDefs.pop_back(); - IsSrc = true; - } - - dbgs() << "use or def\n"; - IL.getPointer()->print(dbgs()); - dbgs() << "\n"; - dbgs() << "DestLive=" << DestLive << "\n"; - dbgs() << "SrcLive=" << SrcLive << "\n"; + auto AllBBUsesOrDefs = SrcBBUsesOrDefs; + // FIXME: memcpy (Store, Load) is duplicated, so sorting is UB. + AllBBUsesOrDefs.insert(AllBBUsesOrDefs.end(), DestBBUsesOrDefs.begin(), + DestBBUsesOrDefs.end()); + auto isLess = [](const LiveDefOrUseInst &L, const LiveDefOrUseInst &R) { + return R.getPointer()->comesBefore(L.getPointer()); + }; + std::sort(AllBBUsesOrDefs.begin(), AllBBUsesOrDefs.end(), isLess); + for (auto IL : AllBBUsesOrDefs) { // FIXME: is this OK to exclude Load and store? - if (DestLive && SrcLive && IL.getPointer() != Load && - IL.getPointer() != Store) { + if (DestLive && SrcLive) { LLVM_DEBUG( dbgs() << "Stack Move: Detected liveness conflict inside the basic " "block \n Instruction: " @@ -1663,9 +1637,14 @@ return false; } Liveness L = IL.getInt(); - if (IsSrc) + // FIXME: these equality check takes linear time, also failed because IL is + // not instruction but with LivenessInfo + if (std::find(SrcBBUsesOrDefs.begin(), SrcBBUsesOrDefs.end(), IL) != + SrcBBUsesOrDefs.end()) SrcLive = L == Liveness::LiveUse; - else + + if (std::find(DestBBUsesOrDefs.begin(), DestBBUsesOrDefs.end(), IL) != + DestBBUsesOrDefs.end()) DestLive = L == Liveness::LiveUse; } return true; @@ -1674,21 +1653,9 @@ bool checkBBLevelLivenessConflict(BasicBlockLivenessMap &DestLivenessMap, BasicBlockLivenessMap &SrcLivenessMap, Instruction *Load, Instruction *Store) { - - dbgs() << "hi from bb level conflict\n"; - dbgs() << "src size is\n"; - dbgs() << SrcLivenessMap.size(); - dbgs() << "\nDest size is\n"; - dbgs() << DestLivenessMap.size(); // Check for liveness conflicts on the basic block level (with the exception // of the basic block containing the memcpy). for (const auto &[BB, DestLiveness] : DestLivenessMap) { - dbgs() << "Basic Block: " << BB->getNameOrAsOperand() << "\n"; - dbgs() << "islivenayware: " << DestLiveness.isLiveAnywhereOrHasUses() - << "\n"; - dbgs() << "corresponding src islivenayware: " - << SrcLivenessMap.lookup(BB).isLiveAnywhereOrHasUses() << "\n"; - if (DestLiveness.isLiveAnywhereOrHasUses() && SrcLivenessMap.lookup(BB).isLiveAnywhereOrHasUses()) { LLVM_DEBUG( @@ -1815,7 +1782,7 @@ switch (DetermineUseCaptureKind(U, IsDereferenceableOrNull)) { case UseCaptureKind::MAY_CAPTURE: LLVM_DEBUG({ - dbgs() << "Stack Move: Alloca was captured:"; + dbgs() << "Stack Move: Alloca may be captured:"; dbgs() << "\n" << U; dbgs() << "\n"; }); @@ -1836,9 +1803,6 @@ PDom = findNearestCommonPostDominator(PDom, UI, PDT); } - dbgs() << "this is nocapture\n"; - UI->print(dbgs()); - dbgs() << "\n"; // If an instruction overwrites all bytes of the alloca, it's a // definition, not a use. Detect those cases here. if (IntrinsicInst *II = dyn_cast(UI)) { @@ -1852,10 +1816,7 @@ int64_t Size = cast(II->getArgOperand(0))->getSExtValue(); - dbgs() << "hello from ll capture tracking\n"; if (Size < 0 || uint64_t(Size) == SrcSize) { - dbgs() << "lifeitme is counted as LiveDef\n"; - II->print(dbgs()); BBLivenessMap[II->getParent()].update(II, Liveness::LiveDef); LifetimeMarkers.push_back(II); continue; @@ -1865,9 +1826,6 @@ if (ConstantInt *CI = dyn_cast(MI->getLength())) { if (CI->getZExtValue() == (*SrcSize).getFixedValue()) { - dbgs() << "hi from memintrinsic def\n"; - MI->print(dbgs()); - dbgs() << "\n"; // Memcpy, memmove, and memset instructions that fill every // byte of the alloca are definitions. BBLivenessMap[MI->getParent()].update(MI, @@ -1891,9 +1849,6 @@ continue; } } - dbgs() << "BB found live use\n"; - UI->print(dbgs()); - dbgs() << "\n"; BBLivenessMap[UI->getParent()].update(UI, Liveness::LiveUse); if (UI->hasMetadata(LLVMContext::MD_noalias)) NoAliasInstrs.insert(UI);