Форум программистов, компьютерный форум CyberForum.ru

C++

Войти
Регистрация
Восстановить пароль
 
Vtulhu
369 / 375 / 96
Регистрация: 12.08.2011
Сообщений: 1,610
#1

Автоматическое преобразование китайского кода в нормальный - C++

30.06.2013, 15:15. Просмотров 604. Ответов 6
Метки нет (Все метки)

У меня есть огромный шмат кода примерно такого вида:

C++
1
2
3
4
if (x < 10 && y > 0 && z != 0)  return 1;
if (x < 10 && (y > 0 || z < 100))  return 2;
if (x > 9 && y == 0)  return 3;
return 4;
где x, y, z - целые неотрицательные числа. Очевидно, что запись можно оптимизировать. Например:

C++
1
2
3
4
5
6
7
8
9
10
if (x < 10) {
  if (y > 0) {
    if (z != 0)  return 1;
    return 2;
  }
  if (z < 100)  return 2;
  return 4;
}
if (y == 0)  return 3;
return 4;
Но это мне очевидно, человеку. Вопрос: как автоматизировать этот процесс? У меня тысячи строк такого кода, причём количество сравнений в одной строке часто превышает десяток, и это не просто числа, а вызовы функций.
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
diagon
Higher
1921 / 1187 / 49
Регистрация: 02.05.2010
Сообщений: 2,925
Записей в блоге: 2
30.06.2013, 18:29     Автоматическое преобразование китайского кода в нормальный #2
Язык об этом уже позаботился.
Ваш верхний код эквивалентен нижнему.
Т.е. && не будет вычислять правый аргумент, если его левой аргумент уже равен 0.
Еще можете взять какой-нибудь современный компилятор, он оптимизирует лучше, чем это сможет сделать простой смертный.
Vtulhu
369 / 375 / 96
Регистрация: 12.08.2011
Сообщений: 1,610
30.06.2013, 19:41  [ТС]     Автоматическое преобразование китайского кода в нормальный #3
Цитата Сообщение от diagon Посмотреть сообщение
Язык об этом уже позаботился. Ваш верхний код эквивалентен нижнему.
По смыслу - да. Но не по количеству сравнений. В первом коде они дублируются, во втором - нет.

Т.е. && не будет вычислять правый аргумент, если его левой аргумент уже равен 0.
Разумеется. Только какое это отношение имеет к вопросу? Вы обратили внимание, что во второй строчке, например, опять сравнивается x < 10? Неужели компилятор "запомнит", что такое сравнение уже было? Что-то не верится. Ещё меньше мне верится, что компилятор "догадается", что x < 10 противоположен по смыслу x > 9, потому что x - целое.

Еще можете взять какой-нибудь современный компилятор, он оптимизирует лучше, чем это сможет сделать простой смертный.
Вы хотите сказать, что если заменить в данном коде x, y и z на вызовы функций x(), y() и z(), то они гарантированно будут вызваны минимально возможное количество раз? Напишите такой код, и встройте в функции счётчики вызовов.
Nick Alte
Эксперт С++
1603 / 995 / 118
Регистрация: 27.09.2009
Сообщений: 1,918
Завершенные тесты: 1
01.07.2013, 17:40     Автоматическое преобразование китайского кода в нормальный #4
Цитата Сообщение от Vtulhu Посмотреть сообщение
Напишите такой код, и встройте в функции счётчики вызовов
Что воспрепятствует оптимизации. Счётчики, разумеется, будут обновлять так, как написано. Лучше уж не вносить изменений и просто сгенерировать и почитать ассемблерный листинг, скомпилировав в релизе с -O3.
TakeOver
41 / 31 / 1
Регистрация: 03.02.2013
Сообщений: 61
01.07.2013, 21:19     Автоматическое преобразование китайского кода в нормальный #5
Цитата Сообщение от Vtulhu Посмотреть сообщение
По смыслу - да. Но не по количеству сравнений. В первом коде они дублируются, во втором - нет.



Разумеется. Только какое это отношение имеет к вопросу? Вы обратили внимание, что во второй строчке, например, опять сравнивается x < 10? Неужели компилятор "запомнит", что такое сравнение уже было? Что-то не верится. Ещё меньше мне верится, что компилятор "догадается", что x < 10 противоположен по смыслу x > 9, потому что x - целое.



Вы хотите сказать, что если заменить в данном коде x, y и z на вызовы функций x(), y() и z(), то они гарантированно будут вызваны минимально возможное количество раз? Напишите такой код, и встройте в функции счётчики вызовов.
Извините конечно, но вы несете бред. вы ничего не знаете о методах оптимизации, о SSA и CFG, поэтому ваши домысли - бред. Есть такая вещь, как устранение общих подвыражений, к тому же в вашем варианте кол-во jmp инструкций увеличится, что наоборот приведет к уменьшению скорости работы, тк jmp и call - довольно дорогие инструкции с точки зрения процессора.
Vtulhu
369 / 375 / 96
Регистрация: 12.08.2011
Сообщений: 1,610
01.07.2013, 21:48  [ТС]     Автоматическое преобразование китайского кода в нормальный #6
Цитата Сообщение от TakeOver Посмотреть сообщение
Извините конечно, но вы несете бред. вы ничего не знаете о методах оптимизации
Да, не знаю. Но это не повод так грубить.

Хорошо. Допустим, я чего-то не понимаю. Ответьте мне на один простой вопрос. Вот у меня есть три строки:

C++
1
2
3
if (a==0) && (b==1) && (c==2) && (d==3) && (e==4) && (f==5) && (g==6) && (h==7) && (i==8) && (x==9) return 1;
if (a==0) && (b==1) && (c==2) && (d==3) && (e==4) && (f==5) && (g==6) && (h==7) && (i==8) && (y==10) return 2;
if (a==0) && (b==1) && (c==2) && (d==3) && (e==4) && (f==5) && (g==6) && (h==7) && (i==8) && (z==11) return 3;
Обратите внимание, что девять из десяти условий совпадают в каждой строке. Реальный случай, между прочим (сгенерированный код, конвертация из другого языка программирования). Правильно ли я понял, что преобразовывать это в

C++
1
2
3
4
5
if (a==0) && (b==1) && (c==2) && (d==3) && (e==4) && (f==5) && (g==6) && (h==7) && (i==8) {
  if (x==9) return 1;
  if (y==10) return 2;
  if (z==11) return 3;
}
смысла никакого нет? А то я уже придумал, как написать оптимизатор такого кода. Но если он не нужен, то Вы мне сэкономите кучу времени и сил. Вполне возможно, что я "изобрёл" крайне примитивную вариацию того, что уже есть.
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
01.07.2013, 22:11     Автоматическое преобразование китайского кода в нормальный
Еще ссылки по теме:

C++ Автоматическое редактирование кода в Visual Studio Express
C++ Преобразование кода
Преобразование последовательного кода в параллельный C++
Автоматическое понижающее преобразование типа C++
C++ Почему не происходит автоматическое преобразование стандартных типов?

Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
TakeOver
41 / 31 / 1
Регистрация: 03.02.2013
Сообщений: 61
01.07.2013, 22:11     Автоматическое преобразование китайского кода в нормальный #7
Цитата Сообщение от Vtulhu Посмотреть сообщение
Да, не знаю. Но это не повод так грубить.

Хорошо. Допустим, я чего-то не понимаю. Ответьте мне на один простой вопрос. Вот у меня есть три строки:

C++
1
2
3
if (a==0) && (b==1) && (c==2) && (d==3) && (e==4) && (f==5) && (g==6) && (h==7) && (i==8) && (x==9) return 1;
if (a==0) && (b==1) && (c==2) && (d==3) && (e==4) && (f==5) && (g==6) && (h==7) && (i==8) && (y==10) return 2;
if (a==0) && (b==1) && (c==2) && (d==3) && (e==4) && (f==5) && (g==6) && (h==7) && (i==8) && (z==11) return 3;
Обратите внимание, что девять из десяти условий совпадают в каждой строке. Реальный случай, между прочим (сгенерированный код, конвертация из другого языка программирования). Правильно ли я понял, что преобразовывать это в

C++
1
2
3
4
5
if (a==0) && (b==1) && (c==2) && (d==3) && (e==4) && (f==5) && (g==6) && (h==7) && (i==8) {
  if (x==9) return 1;
  if (y==10) return 2;
  if (z==11) return 3;
}
смысла никакого нет? А то я уже придумал, как написать оптимизатор такого кода. Но если он не нужен, то Вы мне сэкономите кучу времени и сил. Вполне возможно, что я "изобрёл" крайне примитивную вариацию того, что уже есть.
нормальные компиляторы(вряд ли VS++, но clang/llvm и gcc точно должны) умеют определять одинаковые подвыражения, все это будет вычислено 1 раз.
я взял ваш код 1к1(лишь переменные объявил и добавил мусора, что бы clang++ с -O3 не просчитал все в компайл тайме)
код(делал на скорую руку)
C++
1
2
3
4
5
6
int main(int argc, char* const argv[]){
        int a=argc,b=**argv,c=*argv[9],d=*argv[10],e=*argv[11],f=*argv[1],h=*argv[2],i=*argv[3],z=*argv[4],y=*argv[5],x=*argv[6],g=*argv[7];
        if ((a==0) && (b==1) && (c==2) && (d==3) && (e==4) && (f==5) && (g==6) && (h==7) && (i==8) && (x==9)) return 1;
if ((a==0) && (b==1) && (c==2) && (d==3) && (e==4) && (f==5) && (g==6) && (h==7) && (i==8) && (y==10)) return 2;
if ((a==0) && (b==1) && (c==2) && (d==3) && (e==4) && (f==5) && (g==6) && (h==7) && (i==8) && (z==11)) return 3;
}
вот llvm-ir выхлоп:
Assembler
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
%30 = icmp eq i32 %argc, 0
  %31 = icmp eq i8 %2, 1
  %or.cond = and i1 %30, %31
  %32 = icmp eq i8 %5, 2
  %or.cond1 = and i1 %or.cond, %32
  %33 = icmp eq i8 %8, 3
  %or.cond2 = and i1 %or.cond1, %33
  %34 = icmp eq i8 %11, 4
  %or.cond3 = and i1 %or.cond2, %34
  %35 = icmp eq i8 %14, 5
  %or.cond4 = and i1 %or.cond3, %35
  %36 = icmp eq i8 %29, 6
  %or.cond5 = and i1 %or.cond4, %36
  %37 = icmp eq i8 %17, 7
  %or.cond6 = and i1 %or.cond5, %37
  %38 = icmp eq i8 %20, 8
  %or.cond7 = and i1 %or.cond6, %38
  %39 = icmp eq i8 %26, 9
  %or.cond8 = and i1 %or.cond7, %39
  br i1 %or.cond8, label %47, label %40
 
; <label>:40                                      ; preds = %0
  %44 = icmp eq i8 %43, 10
  %or.cond17 = and i1 %or.cond7, %44
  %.not = xor i1 %30, true
  %brmerge = or i1 %or.cond17, %.not
  %.mux = select i1 %or.cond17, i32 2, i32 0
  br i1 %brmerge, label %47, label %45
 
; <label>:45                                      ; preds = %40
  %or.cond18 = and i1 %31, %32
  %or.cond19 = and i1 %or.cond18, %33
  %or.cond20 = and i1 %or.cond19, %34
  %or.cond21 = and i1 %or.cond20, %35
  %or.cond22 = and i1 %or.cond21, %36
  %or.cond23 = and i1 %or.cond22, %37
  %or.cond24 = and i1 %or.cond23, %38
  %46 = icmp eq i8 %23, 11
  %or.cond25 = and i1 %or.cond24, %46
  %. = select i1 %or.cond25, i32 3, i32 0
  ret i32 %.
 
; <label>:47                                      ; preds = %40, %0
  %.0 = phi i32 [ 1, %0 ], [ %.mux, %40 ]
  ret i32 %.0
как видите - компилятор(а точнее оптимизатор llvm) успешно вынес общее подвыражение и сравнений тут далеко не 30. и как видео в самом начале идет вычисление того самого общего подвыражения.
я вынес лишние участки байткода, если что полный листинг:
Кликните здесь для просмотра всего текста
Assembler
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
target datalayout = "e-p:64:64:64-i1:8:8-i8:8:8-i16:16:16-i32:32:32-i64:64:64-f32:32:32-f64:64:64-v64:64:64-v128:128:128-a0:0:64-s0:64:64-f80:128:128-n8:16:32:64-S128"
target triple = "x86_64-redhat-linux-gnu"
 
; Function Attrs: nounwind readonly uwtable
define i32 @main(i32 %argc, i8** nocapture %argv) #0 {
  %1 = load i8** %argv, align 8, !tbaa !0
  %2 = load i8* %1, align 1, !tbaa !1
  %3 = getelementptr inbounds i8** %argv, i64 9
  %4 = load i8** %3, align 8, !tbaa !0
  %5 = load i8* %4, align 1, !tbaa !1
  %6 = getelementptr inbounds i8** %argv, i64 10
  %7 = load i8** %6, align 8, !tbaa !0
  %8 = load i8* %7, align 1, !tbaa !1
  %9 = getelementptr inbounds i8** %argv, i64 11
  %10 = load i8** %9, align 8, !tbaa !0
  %11 = load i8* %10, align 1, !tbaa !1
  %12 = getelementptr inbounds i8** %argv, i64 1
  %13 = load i8** %12, align 8, !tbaa !0
  %14 = load i8* %13, align 1, !tbaa !1
  %15 = getelementptr inbounds i8** %argv, i64 2
  %16 = load i8** %15, align 8, !tbaa !0
  %17 = load i8* %16, align 1, !tbaa !1
  %18 = getelementptr inbounds i8** %argv, i64 3
  %19 = load i8** %18, align 8, !tbaa !0
  %20 = load i8* %19, align 1, !tbaa !1
  %21 = getelementptr inbounds i8** %argv, i64 4
  %22 = load i8** %21, align 8, !tbaa !0
  %23 = load i8* %22, align 1, !tbaa !1
  %24 = getelementptr inbounds i8** %argv, i64 6
  %25 = load i8** %24, align 8, !tbaa !0
  %26 = load i8* %25, align 1, !tbaa !1
  %27 = getelementptr inbounds i8** %argv, i64 7
  %28 = load i8** %27, align 8, !tbaa !0
  %29 = load i8* %28, align 1, !tbaa !1
  %30 = icmp eq i32 %argc, 0
  %31 = icmp eq i8 %2, 1
  %or.cond = and i1 %30, %31
  %32 = icmp eq i8 %5, 2
  %or.cond1 = and i1 %or.cond, %32
  %33 = icmp eq i8 %8, 3
  %or.cond2 = and i1 %or.cond1, %33
  %34 = icmp eq i8 %11, 4
  %or.cond3 = and i1 %or.cond2, %34
  %35 = icmp eq i8 %14, 5
  %or.cond4 = and i1 %or.cond3, %35
  %36 = icmp eq i8 %29, 6
  %or.cond5 = and i1 %or.cond4, %36
  %37 = icmp eq i8 %17, 7
  %or.cond6 = and i1 %or.cond5, %37
  %38 = icmp eq i8 %20, 8
  %or.cond7 = and i1 %or.cond6, %38
  %39 = icmp eq i8 %26, 9
  %or.cond8 = and i1 %or.cond7, %39
  br i1 %or.cond8, label %47, label %40
 
; <label>:40                                      ; preds = %0
  %41 = getelementptr inbounds i8** %argv, i64 5
  %42 = load i8** %41, align 8, !tbaa !0
  %43 = load i8* %42, align 1, !tbaa !1
  %44 = icmp eq i8 %43, 10
  %or.cond17 = and i1 %or.cond7, %44
  %.not = xor i1 %30, true
  %brmerge = or i1 %or.cond17, %.not
  %.mux = select i1 %or.cond17, i32 2, i32 0
  br i1 %brmerge, label %47, label %45
 
; <label>:45                                      ; preds = %40
  %or.cond18 = and i1 %31, %32
  %or.cond19 = and i1 %or.cond18, %33
  %or.cond20 = and i1 %or.cond19, %34
  %or.cond21 = and i1 %or.cond20, %35
  %or.cond22 = and i1 %or.cond21, %36
  %or.cond23 = and i1 %or.cond22, %37
  %or.cond24 = and i1 %or.cond23, %38
  %46 = icmp eq i8 %23, 11
  %or.cond25 = and i1 %or.cond24, %46
  %. = select i1 %or.cond25, i32 3, i32 0
  ret i32 %.
 
; <label>:47                                      ; preds = %40, %0
  %.0 = phi i32 [ 1, %0 ], [ %.mux, %40 ]
  ret i32 %.0
}
 
attributes #0 = { nounwind readonly uwtable "less-precise-fpmad"="false" "no-frame-pointer-elim"="false" "no-frame-pointer-elim-non-leaf"="false" "no-infs-fp-math"="false" "no-nans-fp-math"="false" "unsafe-fp-math"="false" "use-soft-float"="false" }
 
!0 = metadata !{metadata !"any pointer", metadata !1}
!1 = metadata !{metadata !"omnipotent char", metadata !2}
!2 = metadata !{metadata !"Simple C/C++ TBAA"}


Добавлено через 11 минут
Vtulhu, но тем не менее, такой код - нужно рефакторить, и ваша "оптимизация" скорее как увеличение читабельности/чистоты кода, что довольно хорошо, имхо.
Yandex
Объявления
01.07.2013, 22:11     Автоматическое преобразование китайского кода в нормальный
Ответ Создать тему
Опции темы

Текущее время: 11:20. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru