Оптимизаторы C и С++ обычно знают, какие функции не имеют побочных эффектов?

Ответ 1

GCC имеет два attributes, pure и const, которые могут использоваться для обозначения такой функции. Если функция не имеет побочного эффекта, и ее результат зависит только от ее аргументов, функция должна быть объявлена ​​const, если результаты могут также зависеть от некоторой глобальной переменной, функция должна быть объявлена ​​pure. В последних версиях также есть опция -Wsuggest-attribute предупреждения, которая может указывать функции, которые должны быть объявлены const или pure.

Ответ 2

На самом деле, сегодняшние общие компиляторы будут выполнять оптимизацию цикла-инвариантного кода, о которой вы спрашиваете. Для демонстрации этого, см. Второе упражнение в в этой статье, озаглавленной "Будет ли она оптимизирована?" . Если ваш компилятор VS2010 не выполняет эту оптимизацию, не имеет значения; LLVM/Clang "интегрируется с MSVC 2010, 2012, 2013 и 14 CTP" .

Из теоретического положения эти два кавычка объясняют объем или запас, который имеет компилятор при выполнении оптимизаций. Они из стандарта C11. IIRC С++ 11 имеет нечто подобное.

§5.1.2.3p4:

В абстрактной машине все выражения оцениваются в соответствии с семантика. Фактическая реализация не должна оценивать часть выражение, если оно может вывести, что его значение не используется и что нет требуются побочные эффекты (в том числе вызванные вызовом функция или доступ к энергозависимому объекту).

§5.1.2.3p6:

Наименьшие требования к соответствующей реализации:

- Доступ к изменчивым объектам оценивается строго в соответствии с правила абстрактной машины.

- При завершении программы все данные, записанные в файлы, должны быть идентичный результату, что выполнение программы в соответствии с абстрактная семантика.

- Динамика ввода и вывода интерактивных устройств место, указанное в 7.21.3. Цель этих требований состоит в том, чтобы как можно скорее появился небуферизованный или строковый буфер, чтобы на самом деле появляются сообщения перед программой, ожидающие вход.

Это наблюдаемое поведение программы.

Таким образом, компилятор может поднять вашу всю программу во время оценки времени компиляции, если это возможно. Рассмотрим следующую программу, например:

double YSinX(double x,int y)
{
    double total = 0.0;
    for (int i = 0; i < y; i++)
        total += sin(x);
    return total;
}

int main(void) {
    printf("%lf\n", YSinX(PI, 4));
}

Ваш компилятор может понять, что эта программа печатает 0.0\n каждый раз и оптимизирует вашу программу в:

int main(void) { puts("0.0"); }

То есть, если ваш компилятор может доказать, что ни sin, ни YsinX не вызывают никаких необходимых побочных эффектов. Обратите внимание, что они могут (и, вероятно, делать) по-прежнему вызывать побочные эффекты, но они не нужны для вывода результатов этой программы.

Вы задали вопрос о компиляторе. Если вы имеете в виду все реализации C или С++, нет никаких гарантированных оптимизаций, и реализация C не обязательно должна быть компилятором. Вам нужно сообщить нам, какая конкретная реализация C или С++; как я упоминал ранее, LLVM/Clang "интегрируется с MSVC 2010, 2012, 2013 и 14 CTP", поэтому вы можете использовать это. Если ваш компилятор C или С++ не создает оптимальный код, получите новый компилятор (например, LLVM/Clang) или создайте оптимизацию самостоятельно, предпочтительно, изменив свой компилятор, чтобы вы могли отправить патч разработчикам и автоматически оптимизировать оптимизацию другие проекты.

Ответ 3

Что необходимо для того, чтобы разрешить подъем этого подвыражения вне цикла, это не чистота, а idempotence.

Idempotence означает, что функция будет иметь одинаковые побочные эффекты и результат, если она вызывается один раз, как если бы она вызывалась много раз с теми же аргументами. Следовательно, компилятор может вывести вызов функции за пределы цикла, защищенный только условным (будет ли цикл повторяться хотя бы один раз?). Фактический код после оптимизации подъема будет следующим:

double YSinX(double x,int y)
{
   double total = 0.0;
   int i = 0;
   if (i < y) {
       double sinx = sin(x);  // <- this goes between the loop-initialization
                              // first test of the condition expression
                              // and the loop body
       do {
          total += sinx;
          i++;
       } while (i < y);
   }
   return total;
}

Различие между __attribute__(pure) и idempotent важно, поскольку, как отмечает adl в своем комментарии, эти функции имеют побочный эффект установки errno.

Будьте осторожны, поскольку идемпотентность применяется только к повторным вызовам без промежуточных инструкций. Компилятор должен будет выполнить анализ потока данных, чтобы доказать, что функция и промежуточный код не взаимодействуют (например, промежуточный код использует только локали, адреса которых никогда не принимаются), прежде чем он сможет использовать идемпотенцию. Это не обязательно, когда функция известна как чистая. Но чистота - это гораздо более сильное условие, которое не распространяется на очень многие функции.

Ответ 4

Думаю, да. Если вы получаете вывод разборки компилятора, вы можете видеть, что sin вызывается в другой метке, чем метка цикла для "for": (скомпилировано с g++ -O1 -O2-O3)

Leh_func_begin1:
        pushq   %rbp
Ltmp0:
        movq    %rsp, %rbp
Ltmp1:
        pushq   %rbx
        subq    $8, %rsp
Ltmp2:
        testl   %edi, %edi
        jg      LBB1_2
        pxor    %xmm1, %xmm1
        jmp     LBB1_4
LBB1_2:
        movl    %edi, %ebx
        callq   _sin ;sin calculated
        pxor    %xmm1, %xmm1
        .align  4, 0x90
LBB1_3:
        addsd   %xmm0, %xmm1
        decl    %ebx
        jne     LBB1_3 ;loops here till i reaches y
LBB1_4:
        movapd  %xmm1, %xmm0

Надеюсь, я прав.