[MemCpyOpt] The store instruction should not be removed by DSE.

 

패치 링크 :

https://github.com/llvm/llvm-project/issues/70578

[MemCpyOpt] The store instruction should not be removed by DSE. · Issue #70578 · llvm/llvm-project

 

 

문제 IR

https://llvm.godbolt.org/z/qMncEEseK

Compiler Explorer - LLVM IR (opt 17.0.1)

 

 

 

문제가 생기는 지점을 추적해 봅니다.

$ cat test.ll
define void @byval_param_noalias_metadata(ptr align 4 byval(i32) %ptr) {
  %tmp = alloca i32, align 4
  store i32 1, ptr %ptr, !noalias !2
  call void @llvm.memcpy.p0.p0.i64(ptr align 4 %tmp, ptr align 4 %ptr, i64 4, i1 false)
  call void @f_byval(ptr align 4 byval(i32) %tmp), !alias.scope !2
  ret void
}


$ build-llvm/bin/opt -passes=memcpyopt,dse test.ll -S -print-after-all
; *** IR Dump After MemCpyOptPass on byval_param_noalias_metadata ***
define void @byval_param_noalias_metadata(ptr byval(i32) align 4 %ptr) {
  %tmp = alloca i32, align 4
  store i32 1, ptr %ptr, align 4, !noalias !0
  call void @llvm.memcpy.p0.p0.i64(ptr align 4 %tmp, ptr align 4 %ptr, i64 4, i1 false)
  call void @f_byval(ptr byval(i32) align 4 %ptr), !alias.scope !0
  ret void
}
; *** IR Dump After DSEPass on byval_param_noalias_metadata ***
define void @byval_param_noalias_metadata(ptr byval(i32) align 4 %ptr) {
  call void @f_byval(ptr byval(i32) align 4 %ptr), !alias.scope !0
  ret void
}

 

DSE 에서 문제가 생기는군요.
부연설명 더합니다.

 

memcpy 최적화에서

call void @f_byval(ptr align 4 byval(i32) %tmp), !alias.scope !2
=> call void @f_byval(ptr byval(i32) align 4 %ptr), !alias.scope !0
이렇게 바뀝니다.

 

이것도 궁금하긴 하지만 일단 이 패치의 범위는 아니므로 넘어가겠습니다.

 

문제가 생기는 부분은 다음 IR이 제거되선 안되는데 제거되기 때문입니다.

store i32 1, ptr %ptr, align 4, !noalias !0

 

 

기도하면서 다음과 같은 샘플을 만듭니다 (사실 몇 번의 시행착오로 만든겁니다 ^^;)

define void @byval_param_noalias_metadata(ptr byval(i32) align 4 %ptr) {
  store i32 1, ptr %ptr, align 4
  call void @f_byval(ptr byval(i32) align 4 %ptr), !alias.scope !0
  ret void
}

 

비교하자면 store 가 제거되는 코드와의 차이는 오직 !noalias !0 이 없다는 것 뿐 입니다.

이는 Metadata Attribute 입니다. 다음에서 참고하세요 (TBD)

https://die4taoam.tistory.com/141

[TODO] Metadata & Attribute

 

샘플에서는 store가 제거되지 않습니다.

이 샘플을 통해 UFTRACE 로 차이점을 찾아갑니다.

 

적합한 샘플을 만들 수 있다면 쉽게 차이점을 찾을 수 있게 됩니다.

 

다음 지점에서 차이가 생기고

        if (isWriteAtEndOfFunction(Def)) {
          // See through pointer-to-pointer bitcasts
          LLVM_DEBUG(dbgs() << "   ... MemoryDef is not accessed until the end "
                               "of the function\n");
          deleteDeadInstruction(DefI);

 

해당 함수 주석에는 설명이 달려있습니다.

  /// Returns true if \p Def is not read before returning from the function.
  bool isWriteAtEndOfFunction(MemoryDef *Def) {

 

 

여기까지 찾아가봅니다.

 

      // TODO: Checking for aliasing is expensive. Consider reducing the amount
      // of times this is called and/or caching it.
      Instruction *UseInst = cast<MemoryUseOrDef>(UseAccess)->getMemoryInst();
      if (isReadClobber(*MaybeLoc, UseInst)) {
        LLVM_DEBUG(dbgs() << "  ... hit read clobber " << *UseInst << ".\n");
        return false;
      }

 

(디버그 메시지로도 위 지점을 찾아올 수 있었겠네요. 다음번에는 디버그 메시지로 다뤄보겠습니다.)

 

 

둘의 실행 흐름은 같고

 

  // Returns true if \p Use may read from \p DefLoc.
  bool isReadClobber(const MemoryLocation &DefLoc, Instruction *UseInst) {
    if (isNoopIntrinsic(UseInst))
      return false;

    // Monotonic or weaker atomic stores can be re-ordered and do not need to be
    // treated as read clobber.
    if (auto SI = dyn_cast<StoreInst>(UseInst))
      return isStrongerThan(SI->getOrdering(), AtomicOrdering::Monotonic);

    if (!UseInst->mayReadFromMemory())
      return false;

    if (auto *CB = dyn_cast<CallBase>(UseInst))
      if (CB->onlyAccessesInaccessibleMemory())
        return false;

    return isRefSet(BatchAA.getModRefInfo(UseInst, DefLoc));
  }

 

여기서 갈린다는걸 알 수 있습니다.

return isRefSet(BatchAA.getModRefInfo(UseInst, DefLoc));

 

정확히 어떤 일을 하는지는 모르지만, Ref Info 유무를 검사하는 것 같고,

여기서 True 가 반환되면 isWriteAtEndOfFunction() 이 false => store를 지우지 않음

여기서 False가 반환되면 isWriteAtEndOfFunction() 이 true => store를 지움

 

디버거로 추적해보면 `!noalias !0` 가 있는 경우 다음 코드에서 리턴되는 것을 확인할 수 있다.

 for (const auto &AA : AAs) {
    Result &= AA->getModRefInfo(Call, Loc, AAQI);

    // Early-exit the moment we reach the bottom of the lattice.
    if (isNoModRef(Result))
      return ModRefInfo::NoModRef;
  }

 

alias 가 없는 경우는 다음에서 리턴된다.

  // Apply the ModRef mask. This ensures that if Loc is a constant memory
  // location, we take into account the fact that the call definitely could not
  // modify the memory location.
  if (!isNoModRef(Result))
    Result &= getModRefInfoMask(Loc);

 

 

문제가 생기는 부분의 패치 내역

https://reviews.llvm.org/D72631

⚙ D72631 [DSE] Eliminate stores at the end of the function.

 

  DSEState(Function &F, AliasAnalysis &AA, MemorySSA &MSSA, DominatorTree &DT,
           PostDominatorTree &PDT, AssumptionCache &AC,
           const TargetLibraryInfo &TLI, const LoopInfo &LI)
      : F(F), AA(AA), EI(DT, &LI, &EphValues), BatchAA(AA, &EI), MSSA(MSSA),
        DT(DT), PDT(PDT), TLI(TLI), DL(F.getParent()->getDataLayout()), LI(LI) {
    // Collect blocks with throwing instructions not modeled in MemorySSA and
    // alloc-like objects.
    unsigned PO = 0;
    for (BasicBlock *BB : post_order(&F)) {
      PostOrderNumbers[BB] = PO++;
      for (Instruction &I : *BB) {
        MemoryAccess *MA = MSSA.getMemoryAccess(&I);
        if (I.mayThrow() && !MA)
          ThrowingBlocks.insert(I.getParent());

        auto *MD = dyn_cast_or_null<MemoryDef>(MA);
        if (MD && MemDefs.size() < MemorySSADefsPerBlockLimit &&
            (getLocForWrite(&I) || isMemTerminatorInst(&I)))
          MemDefs.push_back(MD);
      }
    }

 

DSE는 MemorySSA 로부터 MemoryAccess에 대한 정보를 받아와 MemDefs에 보관한다.

 

MemorySSA에 대한 설명은 다음 링크 참고 (TBD)

https://die4taoam.tistory.com/142

[TODO] MemorySSAAnalysis

        if (isWriteAtEndOfFunction(Def)) {
          // See through pointer-to-pointer bitcasts
          LLVM_DEBUG(dbgs() << "   ... MemoryDef is not accessed until the end "
                               "of the function\n");
          deleteDeadInstruction(DefI);
          ++NumFastStores;
          MadeChange = true;
        }

 

 

패치 내역에 따르면, 위 코드는 Aliasing Users 가 없는 경우 MemoryDef 를 제거하는 기능을 한다.

 

문제가 발생하는 메커니즘은,

memcpyopt 를 거치면서 변경된 부분이 다음 코드에서 Alias에 대한 User를 찾지 못하게 된다는 것. 

 for (const auto &AA : AAs) {
    Result &= AA->getModRefInfo(Call, Loc, AAQI);

    // Early-exit the moment we reach the bottom of the lattice.
    if (isNoModRef(Result))
      return ModRefInfo::NoModRef;
  }

 

 

이런 변화는 byval 인 경우에 생긴다.

 

byval 이란 무엇일까? (TBD)

https://die4taoam.tistory.com/143

byval

 

다음처럼 byval 로 지정된 인자는 memcpyopt 에서 처리를 해준다.

define void @byval_param_noalias_metadata(ptr align 4 byval(i32) %ptr) {
  %tmp = alloca i32, align 4
  store i32 1, ptr %ptr, !noalias !2
  call void @llvm.memcpy.p0.p0.i64(ptr align 4 %tmp, ptr align 4 %ptr, i64 4, i1 false)
  call void @f_byval(ptr align 4 byval(i32) %tmp), !alias.scope !2
  ret void
}

 

다음 주석을 보면 이해할 수 있을 것 같다.

 

  // Verify that the copied-from memory doesn't change in between the memcpy and
  // the byval call.
  //    memcpy(a <- b)
  //    *b = 42;
  //    foo(*a)
  // It would be invalid to transform the second memcpy into foo(*b).
  if (writtenBetween(MSSA, BAA, MemoryLocation::getForSource(MDep),
                     MSSA->getMemoryAccess(MDep), CallAccess))
    return false;

  LLVM_DEBUG(dbgs() << "MemCpyOptPass: Forwarding memcpy to byval:\n"
                    << "  " << *MDep << "\n"
                    << "  " << CB << "\n");

  // Otherwise we're good!  Update the byval argument.
  CB.setArgOperand(ArgNo, MDep->getSource());

 

byval 로 선언된 인자가 있을 경우에, 주석과 같이

  //    memcpy(a <- b)
  //    *b = 42;

이런 상황이 없으면, memcpy를 제거하기 위해서

  //    foo(*a)

를

  //    foo(*b)

 로 바꾸는 것.

 

 

이제 문제를 해결한 패치를 보면 아주 간단하다.

  // Otherwise we're good!  Update the byval argument.
  combineAAMetadata(&CB, MDep);
  CB.setArgOperand(ArgNo, MDep->getSource());
  ++NumMemCpyInstr;
  return true;

 

f_byval의 인자 %tmp를 memcpyopt에서 %ptr로 변경할 때 AliasAnalysis 데이터를 추가시키는 것이다.

  combineAAMetadata(&CB, MDep);

 

 

 

아직 관련 내용을 다 이해하지 못하고 있어 글 또한 뭉뚱그려진 내용들이 많네요.

몇 가지 몰랐던 키워들에 대한 공부를 추가하고 글을 업데이트 해야할 것 같습니다.