do-while 양식 루프를 LLVM의 while 양식 루프로 변경하는 방법 IR

Question

do-while 양식의 루프를 LLVM IR의 while 양식의 루프로 변경하려면 어떻게합니까?

Answer 1

여기에 약간의 루프 예가 있습니다. 루프는 true의 첫 번째 항목을 찾을 때까지 부울 배열을 통해 실행됩니다. 최적화 된 llvm IR을 얻으려면 clang -emit-llvm으로 컴파일했습니다.

; Function Attrs: nounwind uwtable 
define i32 @_Z3fooPb(i8* %start) #0 { 
    %1 = alloca i8*, align 8 
    %cond = alloca i8*, align 8 
    store i8* %start, i8** %1, align 8 
    %2 = load i8** %1, align 8 
    store i8* %2, i8** %cond, align 8 
    br label %3 

; <label>:3          ; preds = %9, %0 
    %4 = load i8** %cond, align 8 
    %5 = load i8* %4, align 1 
    %6 = trunc i8 %5 to i1 
    %7 = zext i1 %6 to i32 
    %8 = icmp ne i32 %7, 1 
    br i1 %8, label %9, label %12 

; <label>:9          ; preds = %3 
    %10 = load i8** %cond, align 8 
    %11 = getelementptr inbounds i8* %10, i32 1 
    store i8* %11, i8** %cond, align 8 
    br label %3 

; <label>:12          ; preds = %3 
    %13 = load i8** %cond, align 8 
    %14 = load i8** %1, align 8 
    %15 = ptrtoint i8* %13 to i64 
    %16 = ptrtoint i8* %14 to i64 
    %17 = sub i64 %15, %16 
    %18 = trunc i64 %17 to i32 
    ret i32 %18 
} 

와 DO를 사용하는 바, 대한

우리가 얻을 때 :

; Function Attrs: nounwind uwtable 
define i32 @_Z3barPb(i8* %start) #0 { 
    %1 = alloca i8*, align 8 
    %cond = alloca i8*, align 8 
    store i8* %start, i8** %1, align 8 
    %2 = load i8** %1, align 8 
    store i8* %2, i8** %cond, align 8 
    br label %3 

; <label>:3          ; preds = %4, %0 
    br label %4 

; <label>:4          ; preds = %3 
    %5 = load i8** %cond, align 8 
    %6 = getelementptr inbounds i8* %5, i32 1 
    store i8* %6, i8** %cond, align 8 
    %7 = load i8* %6, align 1 
    %8 = trunc i8 %7 to i1 
    %9 = zext i1 %8 to i32 
    %10 = icmp ne i32 %9, 1 
    br i1 %10, label %3, label %11 

; <label>:11          ; preds = %4 
    %12 = load i8** %cond, align 8 
    %13 = load i8** %1, align 8 
    %14 = ptrtoint i8* %12 to i64 
    %15 = ptrtoint i8* %13 to i64 
    %16 = sub i64 %14, %15 
    %17 = trunc i64 %16 to i32 
    ret i32 %17 
} 

#include <stdio.h> 
#include <string.h> 

int foo(bool* start){ 
     bool* cond = start;; 
     while (*cond != true) 
       cond++; 
     return cond - start; 
} 

int bar(bool* start){ 
     bool* cond = start; 
     do { 
     }while (*(++cond) != true); 
     return cond - start; 
} 

int main(){ 
     bool cond[8]; 
     memset(&cond, 0, sizeof(bool)*8); 
     cond[5] = true; 
     printf("%i %i\n", foo(cond), bar(cond)); 
} 

(단지 while 루프를 사용하여) foo는 함수의 IR은 다음과 같습니다

bar에 대한 차이는 매우 작습니다. 우리는 하나의 추가 레이블과 br을 추가로 가지고 있습니다. 왜냐하면 우리가 협곡을 평가하기 전에 해협을 루프 본문으로 건너 뛰고 실행하기 때문입니다 .

그래서 do를 변형하는 첫 번째 작업은 분기를 제거하고 조건으로 바로 이동하는 것입니다. 이제 condition이 먼저 평가되는 while 루프. 쉽습니다. 이제 조건을 처리하는 방법은 두 가지가 있습니다. 거의 모든 것을 루프 조건에 넣을 수 있기 때문에 실제 상황을 수정하려고 할 수 있습니다. 쉬운 방법은 루프의 첫 번째 분기 전에 루프 본문을 한 번만 복사하는 것입니다 (;<label>:4부터 ;<label>:11까지 모두). 그래서 코드의 정확성을 바꿔주기를 원한다면 do-while 루프는 루프의 앞쪽에 루프가 될 것이다.

당신은 llvm/Transforms/Utils/Cloning.h에서 CloneBasicBlock와 루프 본문을 복사 할 수 있습니다 :

/// CloneBasicBlock - Return a copy of the specified basic block, but without 
/// embedding the block into a particular function. The block returned is an 
/// exact copy of the specified basic block, without any remapping having been 
/// performed. Because of this, this is only suitable for applications where 
/// the basic block will be inserted into the same function that it was cloned 
/// from (loop unrolling would use this, for example). 
/// 
/// Also, note that this function makes a direct copy of the basic block, and 
/// can thus produce illegal LLVM code. In particular, it will copy any PHI 
/// nodes from the original block, even though there are no predecessors for the 
/// newly cloned block (thus, phi nodes will have to be updated). Also, this 
/// block will branch to the old successors of the original block: these 
/// successors will have to have any PHI nodes updated to account for the new 
/// incoming edges. 
/// 
/// The correlation between instructions in the source and result basic blocks 
/// is recorded in the VMap map. 
/// 
/// If you have a particular suffix you'd like to use to add to any cloned 
/// names, specify it as the optional third parameter. 
/// 
/// If you would like the basic block to be auto-inserted into the end of a 
/// function, you can specify it as the optional fourth parameter. 
/// 
/// If you would like to collect additional information about the cloned 
/// function, you can specify a ClonedCodeInfo object with the optional fifth 
/// parameter. 
/// 
BasicBlock *CloneBasicBlock(const BasicBlock *BB, 
          ValueToValueMapTy &VMap, 
          const Twine &NameSuffix = "", Function *F = nullptr, 
          ClonedCodeInfo *CodeInfo = nullptr); 

나는 이것이 약간의 도움 바랍니다. 재미있게 보내십시오!