Спец часть (часть 2) (3 поток) (2015) (by Кибитова) (1161602), страница 33
Текст из файла (страница 33)
Арифметические преобразования. Компилятор может изменять характер иВычисление выражений из известных операндов (свертка операций)порядок следования операций на основании известных алгебраических и логическихвыполняетсятождеств,в случаях:например, заменять выражение A=B*C+B*D выражением A=B*(C+D).Некоторыеоперации могутзаменяться более“простыми”,что делает их выполнение• непосредственногоиспользованияконстантпрограммистом:более эффективным:A = sin (2 * 3.14 * B);x := y ** 2=>x := y * y;• возникновенияx := yконстант-операндов*2=>x после:= y + макрорасширений,y;#define общихPi 3.1415926Устранениеподвыражений (избыточных вычислений). ОперацияA=sin(2*Pi*B);линейного участка может оказатьсяизбыточной, если ранее на этом же линейномучастке уже выполнялась идентичная операция, и никакой операнд данной операции не• возникновения констант-операндов в результате компиляции языковыхбыл изменен в промежутке между двумя идентичными операциями.конструкций, например, многомерных массивов:Удаление ненужных присваиваний и других операций.
Если на некоторомint a [10][10][10],b [10][10][10],c [10][10][10];линейном участкемежду двумяоперациямиприсваивания какой-либо переменнойa[3][4][i]=b[8][3][k]*c[3][2][j];значений (одинаковых или разных, не имеет значения) не было ни одного оператора, вa’ [((3 * 10) бы+ 4)первое* 10 + i]значение:= b’ [((8переменной,* 10) + 3) * 10k] *котором использовалосьэто+ присваиваниеявляетсяc’[((3*10)+2)*10+j];бесполезным и может быть удалено из программы без изменения ее смысла.Иногда подолженналичиювыполнитьоператороввычисленияприсваиваниязначенийКомпилятори однимвнести переменнымзаписи о новыхдругих переменныхисключитьиспользованиенекоторыхпеременных,заменив литеральныхконстантахудаетсяв таблицуконстант,как если бы этиконстантыбыли введенысамим программистом.
Более сложные варианты алгоритмов свертки принимают вовнимание известные им значения переменных44(например, сразу после присваивания) идаже функций.Арифметические преобразования. Компилятор может изменять характер ипорядок следования операций на основании известных алгебраических и логическихтождеств, например, заменять выражение A=B*C+B*D выражением A=B*(C+D).Некоторые операции могут заменяться более “простыми”, что делает их выполнениеихихиспользованиемиспользованиемихихкопийкопий(метод(методноситноситназваниеназвание“распространение“распространениекопий”).копий”).ВВВтакихтакихихиспользованиемихкопий(методноситназвание“распространениекопий”).такихслучаяхслучаях происходитпроисходит каккак экономияэкономия временивремени исполненияисполнения программ,программ, тактак иии экономияэкономияслучаяхпроисходиткакэкономиявремениисполненияпрограмм,такэкономияпамяти,памяти, отведеннойотведенной подпод хранениехранение данныхданных программы.программы.
Например,Например, послепосле присваиванияприсваиванияпамяти,отведеннойподхранениеданныхпрограммы.Например,послеприсваиванияf:=gможновместопеременнойfиспользоватьпеременнуюg,априсваиваниеf:=g можноможно вместовместо переменнойпеременной ff использоватьиспользовать переменнуюпеременную g,g, аа присваиваниеприсваиваниепростопростоf:=gпростоисключитьизпрограммы.ВВнаилучшемслучаепеременнаяff совсемстанетненужной,исключитьизпрограммы.наилучшемслучаепеременнаясовсемстанетненужной,исключить из программы. В наилучшем случае переменная f совсем станет ненужной,значит,значит, иии памятьпамять длядля неенее тожетоже распределятьраспределять нене придется.придется.
ПодобныеПодобные преобразованияпреобразованиязначит,памятьдлянеетожераспределятьнепридется.Подобныепреобразованиястановятсяособенноактуальнымиприкомпиляцииавтоматическисгенерированныхстановятся особенноособенно актуальнымиактуальными припри компиляциикомпиляции автоматическиавтоматически сгенерированныхсгенерированныхстановятсяпрограмм,работающихсмногочисленнымипеременнымипрограмм, работающихработающих сс многочисленнымимногочисленными переменнымипеременными иии “цепными”“цепными”программ,“цепными”присваиваниямиприсваиваниямиприсваиваниямиПерестановкаПерестановка независимыхнезависимых смежныхсмежных участковучастков программ.программ. ИногдаИногдаПерестановканезависимыхсмежныхучастковпрограмм.Иногдакомпиляторамудаетсятакимобразомпереставитьследующиедругзадругомоперации,компиляторам удаетсяудается такимтаким образомобразом переставитьпереставить следующиеследующие другдруг заза другомдругом операции,операции,компиляторамчтобезизменениясмыслапрограммыудаетсяприменитькакие-либочто безбез измененияизменения смысласмысла программыпрограммы удаетсяудается применитьприменить какие-либокакие-либо другиедругиечтодругиепреобразования.Например,имеявыражениеA=2*B*3*C,можнопреобразоватьегопреобразования.Например,имеявыражениеA=2*B*3*C,можнопреобразоватьегопреобразования.
Например, имея выражение A=2*B*3*C, можно преобразовать егоперестановкойперестановкой ввв A=(B*C)*(2*3),A=(B*C)*(2*3), ааа затемзатем вычислитьвычислить значениезначение подвыраженияподвыражения изизперестановкойA=(B*C)*(2*3),затемвычислитьзначениеподвыраженияизконстант.Дажеесливыражениеизконстантполучитьнеудается,перестановкаконстант. ДажеДаже еслиесли выражениевыражение изиз константконстант получитьполучить нене удается,удается, перестановкаперестановкаконстант.операцийможетпривестикэкономиивременныхпеременных,которыепорождаютсяопераций можетможет привестипривести кк экономииэкономии временныхвременных переменных,переменных, которыекоторые порождаютсяпорождаютсяоперацийкомпиляторомдляхраненияпромежуточныхрезультатоввычислений.Например,компиляторомдляхраненияпромежуточныхрезультатоввычислений.Например,компилятором для хранения промежуточных результатов вычислений.
Например,непосредственноенепосредственное вычислениевычисление выражениявыражения A=(B+C)+(D+E)A=(B+C)+(D+E) можетможет потребовать,потребовать, попонепосредственноевычислениевыраженияA=(B+C)+(D+E)можетпотребовать,покрайнеймере,однойвременнойпеременнойдляхраненияпромежуточногорезультатакрайней мере,мере, однойодной временнойвременной переменнойпеременной длядля храненияхранения промежуточногопромежуточного результатарезультатакрайнейсложенияBиC.Еслижепровестиперестановкуопераций,этапеременнаясложения BB ии C.C.
ЕслиЕсли жеже провестипровести перестановкуперестановку операций,операций, этаэта переменнаяпеременная будетбудет ненесложениябудетненужна,аарезультатостанетсяпрежним:A=((B+C)+D)+E.нужна,результатостанетсяпрежним:A=((B+C)+D)+E.нужна, а результат останется прежним: A=((B+C)+D)+E. ВВ некоторыхслучаяхперестановкаоперацийможетприводитькк потеренекоторыхслучаяхперестановкаоперацийможетприводитьпотереВ некоторых случаях перестановка операций может приводить к потереточноститочности вычислений.вычислений.
НекоторыеНекоторые типытипы операндовоперандов могутмогут сделатьсделать переупорядочениепереупорядочениеточностивычислений.Некоторыетипыоперандовмогутсделатьпереупорядочениевыраженийневозможным.Например,перестановкацелочисленныхвыражений невозможным.невозможным. Например,Например, перестановкаперестановка целочисленныхцелочисленных операцийопераций ввввыраженийоперацийвыражениивыраженииI/J*KI/J*Kможетможетпривестипривестикккневерномуневерномувычислениювычислениювыражениявыражения10*3/8.10*3/8.выраженииI/J*Kможетпривестиневерномувычислениювыражения10*3/8.УдалениенедостижимыхфрагментовпрограммычастотребуетУдаление недостижимыхнедостижимых фрагментовфрагментов программыпрограммы часточасто требуеттребует глобальногоглобальногоУдалениеглобальногоанализапрограммыдляопределения“достижимости”.Восноветакогоанализаанализа программыпрограммы длядля определенияопределения “достижимости”.“достижимости”.
ВВ основеоснове такоготакого анализаанализа лежатлежатанализалежатидеитеорииграфов,связанныесанализомпотокауправленияипотокаданных.идеи теориитеории графов,графов, связанныесвязанные сс анализоманализом потокапотока управленияуправления ии потокапотока данных.данных.идеиПростейшийвариант–– удалениенедостижимыхфрагментов,выделяемыхсс помощьюПростейшийвариантудалениенедостижимыхфрагментов,выделяемыхпомощьюПростейший вариант – удаление недостижимых фрагментов, выделяемых с помощьюпрепроцессорныхпрепроцессорныхоператоров.операторов.препроцессорныхоператоров.ОптимизацияОптимизация вычислениявычисления логическихлогических выражений.выражений. ОсобенностьюОсобенностьюОптимизациявычислениялогическихвыражений.Особенностьюоптимизациилогическихвыраженийявляетсято,чтодляполученияихоптимизации логическихлогических выраженийвыражений являетсяявляется то,то, чточто длядля полученияполучения ихих значенийзначений ненеоптимизациизначенийневсегдатребуетсяпроводитьвычислениевсеговыражениядоконца.Иногдаповсегдатребуетсяпроводитьвычислениевсеговыражениядоконца.Иногдаповсегда требуетсяпроводитьвычислениевсеговыражениядо конца.
Иногдапорезультатупервыхжеоперацийможнозаранееопределитьокончательныйрезультат.результатупервыхжеоперацийможнозаранееопределитьокончательныйрезультат.результату операциюпервых же операций можнозаранее определитьокончательныйрезультат.Например,Например, операциюоперацию логическогологического сложениясложения можноможно нене проводить,проводить, еслиесли известно,известно, чточтоНапример,логическогосложенияможнонепроводить,еслиизвестно,чтоодинизееоперандовимеетзначение“истина”.Еслиэторазрешаетсяправиламиязыка,один изиз ееее операндовоперандов имеетимеет значениезначение “истина”.“истина”.
ЕслиЕсли этоэто разрешаетсяразрешается правиламиправилами языка,языка,одинкомпиляторытакстроятвнутренниепредставлениялогическихвыражений,чтобыихкомпиляторытакстроятвнутренниепредставлениялогическихвыражений,чтобыихкомпиляторытак строят внутренниепредставлениялогическихвыражений,чтобы ихвычисленияпрекращалисьсразуже,кактолькозначениевсеговыражениястановитсявычисления прекращалисьпрекращались сразусразу же,же, каккак толькотолько значениезначение всеговсего выражениявыражения становитсястановитсявычисленияпредопределенным.Аналогичныерассужденияотносятсяикарифметическимпредопределенным. АналогичныеАналогичные рассуждениярассуждения относятсяотносятся ии кк арифметическимарифметическимпредопределенным.выражениям,ноумноженияна0встречаютсягораздореже,чемлогическоевыражениям, ноно умноженияумножения нана 00 встречаютсявстречаются гораздогораздо реже,реже, чемчем логическоелогическое “И”“И” сосовыражениям,“И”созначением“ложь”.значением“ложь”.значением“ложь”.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
