LoopLatch

Loop에서 Latch란 다음과 같이 정의되어 있다.

https://llvm.org/docs/LoopTerminology.html

LLVM Loop Terminology (and Canonical Forms) — LLVM 17.0.0git documentation

A latch is a loop node that has an edge to the header.

 

 

 

예를 들어 다음과 같은 IR이 존재한다고 하면, (loop-flatten.ll 중 test1 )

define i32 @test1(i32 %val, i16* nocapture %A) {
entry:
  br label %for.body
for.body:                                         ; preds = %entry, %for.inc6
  %i.018 = phi i32 [ 0, %entry ], [ %inc7, %for.inc6 ]
  %mul = mul nuw nsw i32 %i.018, 20
  br label %for.body3
for.body3:                                        ; preds = %for.body, %for.body3
  %j.017 = phi i32 [ 0, %for.body ], [ %inc, %for.body3 ]
  %add = add nuw nsw i32 %j.017, %mul
  %arrayidx = getelementptr inbounds i16, i16* %A, i32 %add
  %0 = load i16, i16* %arrayidx, align 2
  %conv16 = zext i16 %0 to i32
  %add4 = add i32 %conv16, %val
  %conv5 = trunc i32 %add4 to i16
  store i16 %conv5, i16* %arrayidx, align 2
  %inc = add nuw nsw i32 %j.017, 1
  %exitcond = icmp ne i32 %inc, 20
  br i1 %exitcond, label %for.body3, label %for.inc6
for.inc6:                                         ; preds = %for.body3
  %inc7 = add nuw nsw i32 %i.018, 1
  %exitcond19 = icmp ne i32 %inc7, 10
  br i1 %exitcond19, label %for.body, label %for.end8
for.end8:                                         ; preds = %for.inc6
  ret i32 10
}

 

다음과 같이 시각화를 할 수 있다.

bin/opt test1.ll -S -loop-flatten -verify-loop-info -verify-dom-info -verify-scev -verify --dot-cfg

 

여기서 Latch는 for.inc6 이고exiting/latch block 이다.

Latch를 찾는 getLoopLatch 함수는 다음처럼 구현되어 있다.

 

// LoopLatch - LoopInfoImpl.h:212

/// getLoopLatch - If there is a single latch block for this loop, return it.
/// A latch block is a block that contains a branch back to the header.
template <class BlockT, class LoopT>
BlockT *LoopBase<BlockT, LoopT>::getLoopLatch() const {
  assert(!isInvalid() && "Loop not in a valid state!");
  BlockT *Header = getHeader();
  BlockT *Latch = nullptr;
  for (const auto Pred : children<Inverse<BlockT *>>(Header)) {
    if (contains(Pred)) {
      if (Latch)
        return nullptr;
      Latch = Pred;
    }
  }
  return Latch;
}

 

getHeader로 반환되는 Header는 for.body이다. 

LoopHeader :                                                                 
for.body:                                         ; preds = %for.inc6, %entry
  %i.018 = phi i32 [ 0, %entry ], [ %inc7, %for.inc6 ]                       
  %mul = mul nuw nsw i32 %i.018, 20                                          
  br label %for.body3                                                        

 

주석과 같이 LoopLatch를 찾는 코드는 위의 Loop Header 인 for.body의 pred들을 역방향으로 탐색하여

Pred가 Loop문 내에 포함되어 있는 경우 해당 Pred basicblock을 반환한다.
하지만 만약 Latch가 둘 이상 존재하는 경우에는 nullptr을 반환한다.