컴파일 타임에 런타임 다형성을 해결할 수없는 이유는 무엇입니까?

컴파일 타임에 런타임 다형성을 해결할 수없는 이유는 무엇입니까?

---

중히 여기다:

#include<iostream>
using namespace std;

class Base
{
    public:
        virtual void show() { cout<<" In Base \n"; }
};

class Derived: public Base
{
    public:
       void show() { cout<<"In Derived \n"; }
};

int main(void)
{
    Base *bp = new Derived;
    bp->show();  // RUN-TIME POLYMORPHISM
    return 0;
}

이 코드가 왜 런타임 다형성을 유발하고 컴파일 타임에 해결할 수 없습니까?

---

일반적인 경우 에는 컴파일 타임에 런타임에 어떤 유형이 될지 결정하는 것이 불가능 하기 때문입니다. 예제는 컴파일 타임에 해결 될 수 있지만 (@Quentin의 답변 참조) 다음과 같이 불가능한 경우를 구성 할 수 있습니다.

Base *bp;
if (rand() % 10 < 5)
    bp = new Derived;
else
    bp = new Base;
bp->show(); // only known at run time

편집 : @nwp 덕분에 여기에 훨씬 더 나은 경우가 있습니다. 다음과 같은 것 :

Base *bp;
char c;
std::cin >> c;
if (c == 'd')
    bp = new Derived;
else
    bp = new Base;
bp->show(); // only known at run time 

또한,의 추론에 의해 튜링의 증거 , 그것이 있음을 알 수있다 일반적인 경우에 그것은 C에 대한 수학적으로 불가능 ++ 컴파일러는 무엇을 알고 실행시에 기본 클래스 포인터가 포인트.

C ++ 컴파일러와 같은 함수가 있다고 가정합니다.

bool bp_points_to_base(const string& program_file);

그 입력 은 포인터 (OP에서와 같이)가 멤버 함수를 호출 하는 C ++ 소스 코드 텍스트 파일 program_file의 이름입니다 . 그리고 일반적인 경우 ( 멤버 함수 가 처음 호출 되는 시퀀스 지점 에서 ) : 포인터 가의 인스턴스를 가리키는 지 여부를 결정할 수 있습니다.bpvirtualshow()Avirtualshow()bpbpBase

C ++ 프로그램 "q.cpp"의 다음 부분을 고려하십시오.

Base *bp;
if (bp_points_to_base("q.cpp")) // invokes bp_points_to_base on itself
    bp = new Derived;
else
    bp = new Base;
bp->show();  // sequence point A

이제 bp_points_to_base"q.cpp"에서 결정하면 at bp인스턴스를 가리키고 "q.cpp" 는 Base에서 다른 것을 A가리 킵니다 . 그리고 그것은 "q.cpp"에 있다고 판단 할 경우 : 인스턴스를 가리 키지 않습니다 에서 , 다음 "q.cpp"포인트 의 인스턴스 에서 . 이것은 모순입니다. 따라서 우리의 초기 가정은 올바르지 않습니다. 그래서 일반적인 경우에 쓸 수 없습니다 .bpAbpBaseAbpBaseAbp_points_to_base

---

컴파일러는 객체의 정적 유형이 알려진 경우 이러한 호출을 일상적으로 비 가상화합니다. 코드를있는 그대로 컴파일러 탐색기에 붙여 넣으면 다음 어셈블리가 생성됩니다.

main:                                   # @main
        pushq   %rax
        movl    std::cout, %edi
        movl    $.L.str, %esi
        movl    $12, %edx
        callq   std::basic_ostream<char, std::char_traits<char> >& std::__ostream_insert<char, std::char_traits<char> >(std::basic_ostream<char, std::char_traits<char> >&, char const*, long)
        xorl    %eax, %eax
        popq    %rdx
        retq

        pushq   %rax
        movl    std::__ioinit, %edi
        callq   std::ios_base::Init::Init()
        movl    std::ios_base::Init::~Init(), %edi
        movl    std::__ioinit, %esi
        movl    $__dso_handle, %edx
        popq    %rax
        jmp     __cxa_atexit            # TAILCALL

.L.str:
        .asciz  "In Derived \n"

어셈블리를 읽을 수 없더라도 "In Derived \n"실행 파일 에만 있음을 알 수 있습니다 . 동적 디스패치가 최적화되었을뿐만 아니라 전체 기본 클래스도 마찬가지입니다.

---

이 코드가 런타임 다형성을 유발하는 이유는 무엇이며 컴파일 타임에 해결할 수없는 이유는 무엇입니까?

그렇게 생각하는 이유는 무엇입니까?

일반적인 가정을하고 있습니다. 언어 가이 경우를 런타임 다형성을 사용하는 것으로 식별한다고해서 구현 이 런타임에 디스패치로 유지 된다는 의미는 아닙니다 . C ++ 표준에는 소위 "as-if"규칙이 있습니다. C ++ 표준 규칙 의 관찰 가능한 효과 는 추상 기계와 관련하여 설명되며 구현은 원하는대로 관찰 가능한 효과를 얻을 수 있습니다.

---

실제로 devirtualization 은 컴파일 타임에 가상 메서드 호출을 해결하는 것을 목표로하는 컴파일러 최적화에 대해 말하는 데 사용되는 일반적인 단어입니다.

목표는 거의 눈에 띄지 않는 가상 호출 오버 헤드를 줄이는 것이 아니라 (분기 예측이 잘 작동하는 경우) 블랙 박스를 제거하는 것입니다. 최적화 측면에서 가장 좋은 점은 호출 을 인라인 하는 것입니다. 이것은 지속적인 전파와 많은 최적화를 열어 주며, 호출되는 함수의 본문이 컴파일 타임에 알려진 경우에만 인라인을 달성 할 수 있습니다. 호출을 제거하고 함수 본문으로 대체하는 것이 포함되었습니다.)

일부 비 가상화 기회 :

• final메서드 또는 클래스 의 virtual메서드에 대한 호출 final이 사소하게 비 가상화 됨
• a call to a virtual method of a class defined in an anonymous namespace may be devirtualized if that class is a leaf in the hierarchy
• a call to a virtual method via a base class may be devirtualized if the dynamic type of the object can be established at compile time (which is the case of your example, with the construction being in the same function)

For the state of the art, however, you will want to read Honza Hubička's Blog. Honza is a gcc developer and last year he worked on speculative devirtualization: the goal is to compute the probabilities of the dynamic type being either A, B or C and then speculatively devirtualize the calls somewhat like transforming:

Base& b = ...;
b.call();

into:

Base& b = ...;
if      (b.vptr == &VTableOfA) { static_cast<A&>(b).call(); }
else if (b.vptr == &VTableOfB) { static_cast<B&>(b).call(); }
else if (b.vptr == &VTableOfC) { static_cast<C&>(b).call(); }
else                           { b.call(); } // virtual call as last resort

Honza did a 5-part post:

• Devirtualization in C++, part 1
• Devirtualization in C++, part 2 (low-level middle-end devirtualization by forwarding stores to loads)
• Devirtualization in C++, part 3 (building the type hierarchy)
• Devirtualization in C++, part 4 (analyzing the type inheritance graph for fun and profit)
• Devirtualization in C++, part 5 (feedback driven devirtualization)

---

There are many reasons why compilers cannot in general replace the runtime decision with static calls, mostly because it involves information not available at compile time, e.g. configuration or user input. Aside from that, I want to point out two additional reasons why this is not possible in general.

First, the C++ compilation model is based on separate compilation units. When one unit is compiled, the compiler only knows what is defined in the source file(s) being compiled. Consider a compilation unit with a base class and a function taken a reference to the base class:

struct Base {
    virtual void polymorphic() = 0;
};
void foo(Base& b) {b.polymorphic();}

When compiled separately, the compiler has no knowledge about the types that implement Base and thus cannot remove the dynamic dispatch. It also not something we want because we want to able to extend the program with new functionality by implementing the interface. It may be possible to do that at link time, but only under the assumption that the program is fully complete. Dynamic libraries can break this assumption, and as can be seen in the following, there will always be cases were it is not possible at all.

A more fundamental reason comes from Computability theory. Even with complete information, it is not possible to define an algorithm that computes if a certain line in a program will be reached or not. If you could you could solve the Halting Problem: for a program P, I create a new program P' by adding an additional line to the end of P. The algorithm would now be able to decide if that line is reached, which solves the Halting Problem.

Being unable to decide in general means that compilers cannot decide which value is assigned to variables in general, e.g.

bool someFunction( /* arbitrary parameters */ ) {
     // ...
}

// ...
Base* b = nullptr;
if (someFunction( ... ))
    b = new Derived1();
else
    b = new Derived2();

b->polymorphicFunction();

Even when all parameters are known at compile time, it is not possible to prove in general which path through the program will be taken and which static type b will have. Approximations can and are made by optimizing compilers, but there are always cases where it does not work.

Having said that, C++ compilers try very hard to remove dynamic dispatch because it opens many other optimization chances mainly from being able to inline and propagate knowledge through the code. If you are interesting, you can find an interesting serious of blog posts for the GCC devirtualization implementation.

---

That could easily be resolved at compile time if the optimizer chose to do so.

The standard specifies the same behavior as if the run-time polymorphism had occurred. It does not specific that be achieved through actual run-time polymorphism.

---

Basically the compiler should be able to figure out that this should not result in runtime polymorphism in your very simple case. Most probably there are compilers that actually do that but that is mostly a conjecture.

The problematic is the General case when you are actually building a complex, and apart of the cases with library dependencies, or complexity of analysing post-compilation multiple compilation units, which would require keeping multiple versions of the same code, which would blow out AST generation, the real issue boils down to decidability and the halting problem.

The latter does not permit to solve the problem if a call can be devirtualized in the general case.

The halting problem is to decide if a program given an input will halt ( we say the program-input pair halts). It is known that there is no general algorithm , e.g. a compiler, that solves for all possible program-input pairs.

In order for the compiler to decide for any program if a call should be made virtual or not, it should be able to decide that for all possible program-input pairs.

In order to do that the compiler would need to have an algorithm A that decides that given program P1 and program P2 where P2 makes a virtual call, then program P3 { while( {P1,I} != {P2,I} ) } halts for any input I.

Thus the compiler to be able to figure out all possible devirtualization should be able to decide that for any pair (P3,I) over all possible P3 and I;which is undecidable for all because A does not exist. However it can be decided for specific cases that can be eye-balled.

That is why in your case the call can be devirtualized, but not any case.

참고URL : https://stackoverflow.com/questions/34354516/why-cant-run-time-polymorphism-be-solved-at-compile-time