25:
496:
Recent work using data-flow dependence analysis allows to detect not only invariant commands but larger code fragments such as an inner loop. The analysis also detects quasi-invariants of arbitrary degrees, that is commands or code fragments that become invariant after a fixed number of iterations
505:
Loop-invariant code which has been hoisted out of a loop is executed less often, providing a speedup. Another effect of this transformation is allowing constants to be stored in registers and not having to calculate the address and access the memory (or cache line) at each iteration.
279:
holds a negative value), and in such case, the loop body should not be executed at all. One way of guaranteeing correct behaviour is using a conditional branch outside of the loop. Evaluating the loop condition can have
493:
For example, if all reaching definitions for the operands of some simple expression are outside of the loop, the expression can be moved out of the loop.
644:
791:
89:
42:
617:
61:
68:
825:
271:
is loop-invariant, precautions must be taken before moving the code outside the loop. It is possible that the loop condition is
598:
551:
Aho, Alfred V.; Sethi, Ravi; & Ullman, Jeffrey D. (1986). Compilers: Principles, Techniques, and Tools. Addison Wesley.
75:
637:
302:
in the first place, the whole guarding process is not needed, as the loop body is guaranteed to execute at least once.
57:
997:
556:
108:
874:
775:
1023:
916:
630:
281:
46:
811:
895:
946:
911:
82:
835:
690:
577:
Moyen, Jean-Yves; Rubiano, Thomas; Seiller, Thomas (2017). "Loop Quasi-Invariant Chunk
Detection".
695:
35:
843:
820:
796:
725:
136:) that can be moved outside the body of a loop without affecting the semantics of the program.
130:
972:
967:
921:
848:
672:
667:
149:
1002:
926:
770:
133:
122:
8:
982:
853:
745:
653:
487:
126:
977:
941:
760:
750:
700:
463:
451:
858:
682:
594:
552:
522:
518:
510:
992:
931:
801:
780:
740:
720:
586:
987:
590:
962:
936:
735:
730:
715:
539:
1017:
294:
705:
622:
534:
785:
490:
is used to detect whether a statement or expression is loop invariant.
879:
24:
521:. To counteract this, the inverse optimization can be performed,
517:. If the compiler runs out of registers, some variables will be
160:
In the following code sample, two optimizations can be applied.
513:, especially on processors with few registers, like the 32-bit
509:
However, if too many variables are created, there will be high
514:
454:
could remove the two multiplications inside the loop (
576:
49:. Unsourced material may be challenged and removed.
579:Automated Technology for Verification and Analysis
450:This code can be optimized further. For example,
288:construct should be compensated by replacing the
1015:
792:Induction variable recognition and elimination
638:
129:consists of statements or expressions (in an
481:
152:that performs this movement automatically.
652:
645:
631:
109:Learn how and when to remove this message
826:Sparse conditional constant propagation
618:Compiler Optimizations — Hoisting
478:itself, there is no need to have both.
1016:
626:
581:. Lecture Notes in Computer Science.
284:, so an additional evaluation by the
47:adding citations to reliable sources
18:
13:
545:
14:
1035:
611:
776:Common subexpression elimination
23:
917:Compile-time function execution
34:needs additional citations for
570:
1:
563:
488:reaching definitions analysis
466:elimination could then elide
16:Type of compiler optimization
896:Interprocedural optimization
58:"Loop-invariant code motion"
7:
947:Profile-guided optimization
912:Bounds-checking elimination
591:10.1007/978-3-319-68167-2_7
528:
500:
10:
1040:
711:Loop-invariant code motion
474:must be in lock step with
155:
138:Loop-invariant code motion
955:
904:
888:
867:
834:
810:
759:
691:Automatic parallelization
681:
660:
263:Although the calculation
482:Invariant code detection
304:
162:
696:Automatic vectorization
1024:Compiler optimizations
844:Instruction scheduling
821:Global value numbering
797:Live-variable analysis
726:Loop nest optimization
654:Compiler optimizations
973:Control-flow analysis
968:Array-access analysis
922:Dead-code elimination
880:Tail-call elimination
849:Instruction selection
673:Local value numbering
668:Peephole optimization
150:compiler optimization
1003:Value range analysis
927:Expression templates
771:Available expression
134:programming language
123:computer programming
43:improve this article
983:Dependence analysis
854:Register allocation
746:Software pipelining
298:. If the code used
127:loop-invariant code
978:Data-flow analysis
942:Partial evaluation
751:Strength reduction
701:Induction variable
497:of the loop body.
470:completely. Since
464:induction variable
452:strength reduction
1011:
1010:
859:Rematerialization
600:978-3-319-68166-5
523:rematerialization
511:register pressure
275:(for example, if
119:
118:
111:
93:
1031:
993:Pointer analysis
932:Inline expansion
802:Use-define chain
781:Constant folding
741:Loop unswitching
721:Loop interchange
647:
640:
633:
624:
623:
605:
604:
574:
477:
473:
469:
461:
457:
446:
443:
440:
437:
434:
431:
428:
425:
422:
419:
416:
413:
410:
407:
404:
401:
398:
395:
392:
389:
386:
383:
380:
377:
374:
371:
368:
365:
362:
359:
356:
353:
350:
347:
344:
341:
338:
335:
332:
329:
326:
323:
320:
317:
314:
311:
308:
301:
297:
291:
287:
278:
274:
270:
266:
259:
256:
253:
250:
247:
244:
241:
238:
235:
232:
229:
226:
223:
220:
217:
214:
211:
208:
205:
202:
199:
196:
193:
190:
187:
184:
181:
178:
175:
172:
169:
166:
146:scalar promotion
114:
107:
103:
100:
94:
92:
51:
27:
19:
1039:
1038:
1034:
1033:
1032:
1030:
1029:
1028:
1014:
1013:
1012:
1007:
988:Escape analysis
956:Static analysis
951:
900:
884:
863:
836:Code generation
830:
806:
762:
755:
677:
656:
651:
614:
609:
608:
601:
575:
571:
566:
548:
546:Further reading
531:
503:
484:
475:
471:
467:
459:
455:
448:
447:
444:
441:
438:
435:
432:
429:
426:
423:
420:
417:
414:
411:
408:
405:
402:
399:
396:
393:
390:
387:
384:
381:
378:
375:
372:
369:
366:
363:
360:
357:
354:
351:
348:
345:
342:
339:
336:
333:
330:
327:
324:
321:
318:
315:
312:
309:
306:
299:
293:
289:
285:
276:
272:
268:
264:
261:
260:
257:
254:
251:
248:
245:
242:
239:
236:
233:
230:
227:
224:
221:
218:
215:
212:
209:
206:
203:
200:
197:
194:
191:
188:
185:
182:
179:
176:
173:
170:
167:
164:
158:
115:
104:
98:
95:
52:
50:
40:
28:
17:
12:
11:
5:
1037:
1027:
1026:
1009:
1008:
1006:
1005:
1000:
998:Shape analysis
995:
990:
985:
980:
975:
970:
965:
963:Alias analysis
959:
957:
953:
952:
950:
949:
944:
939:
937:Jump threading
934:
929:
924:
919:
914:
908:
906:
902:
901:
899:
898:
892:
890:
886:
885:
883:
882:
877:
871:
869:
865:
864:
862:
861:
856:
851:
846:
840:
838:
832:
831:
829:
828:
823:
817:
815:
808:
807:
805:
804:
799:
794:
789:
783:
778:
773:
767:
765:
757:
756:
754:
753:
748:
743:
738:
736:Loop unrolling
733:
731:Loop splitting
728:
723:
718:
716:Loop inversion
713:
708:
703:
698:
693:
687:
685:
679:
678:
676:
675:
670:
664:
662:
658:
657:
650:
649:
642:
635:
627:
621:
620:
613:
612:External links
610:
607:
606:
599:
568:
567:
565:
562:
561:
560:
547:
544:
543:
542:
540:Loop invariant
537:
530:
527:
502:
499:
483:
480:
305:
163:
157:
154:
117:
116:
31:
29:
22:
15:
9:
6:
4:
3:
2:
1036:
1025:
1022:
1021:
1019:
1004:
1001:
999:
996:
994:
991:
989:
986:
984:
981:
979:
976:
974:
971:
969:
966:
964:
961:
960:
958:
954:
948:
945:
943:
940:
938:
935:
933:
930:
928:
925:
923:
920:
918:
915:
913:
910:
909:
907:
903:
897:
894:
893:
891:
887:
881:
878:
876:
875:Deforestation
873:
872:
870:
866:
860:
857:
855:
852:
850:
847:
845:
842:
841:
839:
837:
833:
827:
824:
822:
819:
818:
816:
813:
809:
803:
800:
798:
795:
793:
790:
787:
784:
782:
779:
777:
774:
772:
769:
768:
766:
764:
758:
752:
749:
747:
744:
742:
739:
737:
734:
732:
729:
727:
724:
722:
719:
717:
714:
712:
709:
707:
704:
702:
699:
697:
694:
692:
689:
688:
686:
684:
680:
674:
671:
669:
666:
665:
663:
659:
655:
648:
643:
641:
636:
634:
629:
628:
625:
619:
616:
615:
602:
596:
592:
588:
584:
580:
573:
569:
558:
557:0-201-10088-6
554:
550:
549:
541:
538:
536:
533:
532:
526:
524:
520:
516:
512:
507:
498:
494:
491:
489:
479:
465:
453:
303:
296:
283:
161:
153:
151:
147:
143:
140:(also called
139:
135:
132:
128:
124:
113:
110:
102:
91:
88:
84:
81:
77:
74:
70:
67:
63:
60: –
59:
55:
54:Find sources:
48:
44:
38:
37:
32:This article
30:
26:
21:
20:
710:
582:
578:
572:
508:
504:
495:
492:
485:
449:
292:loop with a
282:side effects
262:
159:
145:
141:
137:
120:
105:
99:January 2021
96:
86:
79:
72:
65:
53:
41:Please help
36:verification
33:
788:elimination
706:Loop fusion
661:Basic block
535:Code motion
486:Usually, a
300:do {} while
295:do {} while
868:Functional
786:Dead store
585:: 91–108.
564:References
131:imperative
69:newspapers
761:Data-flow
265:x = y + z
1018:Category
763:analysis
529:See also
501:Benefits
142:hoisting
519:spilled
462:), and
156:Example
148:) is a
83:scholar
889:Global
814:-based
597:
555:
85:
78:
71:
64:
56:
905:Other
583:10482
472:6 * i
427:while
364:const
290:while
273:false
269:x * x
180:while
90:JSTOR
76:books
683:Loop
595:ISBN
553:ISBN
458:and
436:<
331:<
267:and
189:<
62:news
812:SSA
587:doi
515:x86
456:6*i
361:int
307:int
165:int
144:or
121:In
45:by
1020::
593:.
525:.
442:);
415:++
409:t1
385:do
367:t1
322:if
286:if
249:++
125:,
646:e
639:t
632:v
603:.
589::
559:.
476:i
468:i
460:a
445:}
439:n
433:i
430:(
424:}
421:;
418:i
412:;
406:+
403:i
400:*
397:6
394:=
391:a
388:{
382:;
379:x
376:*
373:x
370:=
358:;
355:z
352:+
349:y
346:=
343:x
340:{
337:)
334:n
328:i
325:(
319:;
316:0
313:=
310:i
277:n
258:}
255:;
252:i
246:;
243:x
240:*
237:x
234:+
231:i
228:*
225:6
222:=
219:a
216:;
213:z
210:+
207:y
204:=
201:x
198:{
195:)
192:n
186:i
183:(
177:;
174:0
171:=
168:i
112:)
106:(
101:)
97:(
87:·
80:·
73:·
66:·
39:.
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.
