112:
52:
183:
83:
954:
66:, is a term for a technique that reduces wasted instructions by moving instructions to branches in which they are used: If an operation is executed before a branch, and only one of the branch paths use the result of that operation, then code sinking entails moving that operation into the branch where it will be used.
236:
uses code sinking under the name "Allocation sinking", to reduce the amount of time compiled code spends allocating and collecting temporary objects within a loop. Allocation sinking moves allocations to execution paths where the allocated object may escape the executing code, and will thus require
156:
are able to schedule five or more instructions per clock cycle. However, a CPU cannot schedule an instruction that relies on data from a currently (or not yet executed) instruction. Compilers will interleave dependencies in a manner that maximizes the amount of instructions a CPU can process at any
73:
in the sense that it removes code when its results are discarded or unused, but in contrast to dead code elimination, it can remove pointless instructions even if there is a possible use of that instruction’s results in an execution code path.
224:
implements code motion under the name "code factoring", with the purpose of reducing the size of a compiled program. GCC will move any code upwards or downwards if it " invalidate any existing dependences nor introduce new ones".
190:
Loop-invariant code motion is the process of moving loop-invariant code to a position outside the loop, which may reduce the execution time of the loop by preventing some computations from being done twice for the same result.
207:
has a sinking pass in its single static assignment form. LLVM 15.0 will not sink an operation if any of its code paths include a store instruction, or if it may throw an error. Additionally, LLVM will not sink an instruction
168:(BRP) instruction is manually hoisted above branches by the compiler to enable the branch to be immediately taken by the CPU. Itanium relies on additional code scheduling from the CPU to maximize efficiency in the processor.
27:, also known as code hoisting, code sinking, loop-invariant code motion, or code factoring, is a blanket term for any process that moves code within a program for performance or size benefits, and is a common
97:
decomposes a number into its smallest possible forms (as factors), code factorization transforms the code into the smallest possible form, by merging common "factors" until no duplicates remain.
390:
Chang, Pohua P., et al. "The importance of prepass code scheduling for superscalar and superpipelined processors." IEEE Transactions on
Computers 44.3 (1995): 353-370.
334:
Fasse, Justus, et al. Code
Transformations to Increase Prepass Scheduling Opportunities in CompCert. Diss. Master Thesis of Science. Université Grenoble Alpes.
86:
A diagram that demonstrates optimizing for size using code factoring, assuming all operations are not dependent on other operations executing before it.
578:
975:
725:
55:
A diagram depicting an optimizing compiler removing a potentially useless call to assembly instruction "b" by sinking it to its point of use.
35:. It can be difficult to differentiate between different types of code motion, due to the inconsistent meaning of the terms surrounding it.
759:
186:
A diagram depicting loop-invariant code motion over an execution graph. This assumes that D is invariant between loop executions.
375:
93:
is a term for a size-optimization technique that merges common dependencies in branches into the branch above it. Just like
571:
931:
111:
808:
709:
115:
An example of how a compiler might prevent dependency stalls in assembled code with code movement, by observing a
1004:
850:
564:
148:
are all terms for a technique where instructions are rearranged (or "scheduled") to improve the efficiency of
745:
51:
829:
43:
Code motion has a variety of uses and benefits, many of which overlap each other in their implementation.
880:
845:
769:
644:
517:
250:
177:
624:
964:
325:
Lóki, Gábor, et al. "Code factoring in GCC." Proceedings of the 2004 GCC Developers’ Summit. 2004.
629:
221:
777:
754:
730:
659:
489:
255:
149:
140:
120:
106:
281:
906:
901:
855:
782:
606:
601:
94:
70:
936:
860:
704:
32:
8:
916:
787:
679:
587:
542:
241:. All removed allocations are filled in with load-to-store forwarding over their fields.
911:
875:
694:
684:
634:
301:
971:
792:
616:
421:
371:
305:
926:
865:
735:
714:
674:
654:
413:
361:
293:
260:
165:
116:
20:
921:
439:
238:
896:
870:
669:
664:
649:
401:
998:
425:
182:
297:
82:
28:
639:
556:
464:
719:
366:
349:
417:
813:
338:. imag. fr/~ boulme/CPP_2022/FASSE-Justus-MSc-Thesis_2021. pdf, 2021.
282:"Using compiler optimization techniques to detect equivalent mutants"
123:
advancements, optimization may not have any benefit on modern CPUs.
161:
953:
233:
350:"A code motion framework for global instruction scheduling"
204:
153:
335:
978:
to it so that it can be listed with similar articles.
518:"Allocation sinking in git HEAD - luajit - FreeLists"
46:
77:
490:"GCC Developer's Summit 2004 - Code Factoring.pdf"
440:"LLVM: lib/Transforms/Scalar/Sink.cpp Source File"
996:
399:
286:Software Testing, Verification & Reliability
726:Induction variable recognition and elimination
572:
400:Sharangpani, H.; Arora, H. (September 2000).
171:
100:
465:"Code Factoring Optimizations - GNU Project"
586:
579:
565:
279:
365:
280:Craft, Michael; Offut, Jefferson (1994).
181:
110:
81:
50:
760:Sparse conditional constant propagation
997:
16:Generic term for compiler optimization
560:
402:"Itanium processor microarchitecture"
356:. Lecture Notes in Computer Science.
347:
947:
194:
13:
963:needs additional or more specific
47:Removing unused/useless operations
14:
1016:
543:"Allocation Sinking Optimization"
952:
710:Common subexpression elimination
78:Reducing the size of the program
851:Compile-time function execution
535:
510:
482:
457:
432:
393:
384:
341:
328:
319:
273:
1:
266:
830:Interprocedural optimization
69:This technique is a form of
7:
881:Profile-guided optimization
846:Bounds-checking elimination
244:
10:
1021:
645:Loop-invariant code motion
251:Loop-invariant code motion
178:Loop-invariant code motion
175:
172:Loop-invariant code motion
104:
101:Reducing dependency stalls
889:
838:
822:
801:
768:
744:
693:
625:Automatic parallelization
615:
594:
228:
630:Automatic vectorization
298:10.1002/stvr.4370040303
222:GNU Compiler Collection
199:
152:within the CPU. Modern
38:
1005:Compiler optimizations
778:Instruction scheduling
755:Global value numbering
731:Live-variable analysis
660:Loop nest optimization
588:Compiler optimizations
256:Instruction scheduling
215:
187:
141:Instruction scheduling
124:
121:Out-of-order execution
107:Instruction scheduling
87:
56:
907:Control-flow analysis
902:Array-access analysis
856:Dead-code elimination
814:Tail-call elimination
783:Instruction selection
607:Local value numbering
602:Peephole optimization
354:Compiler Construction
348:Gupta, Rajiv (1998).
185:
146:code hoisting/sinking
114:
85:
71:dead code elimination
54:
937:Value range analysis
861:Expression templates
705:Available expression
95:factorizing integers
33:optimizing compilers
917:Dependence analysis
788:Register allocation
680:Software pipelining
336:https://www-verimag
912:Data-flow analysis
876:Partial evaluation
685:Strength reduction
635:Induction variable
367:10.1007/BFb0026434
188:
164:architecture, the
128:Global code motion
125:
88:
57:
31:performed in most
993:
992:
976:adding categories
945:
944:
793:Rematerialization
522:www.freelists.org
418:10.1109/40.877948
377:978-3-540-64304-3
195:Compiler examples
132:local code motion
1012:
988:
985:
979:
956:
948:
927:Pointer analysis
866:Inline expansion
736:Use-define chain
715:Constant folding
675:Loop unswitching
655:Loop interchange
581:
574:
567:
558:
557:
551:
550:
539:
533:
532:
530:
528:
514:
508:
507:
505:
503:
494:
486:
480:
479:
477:
475:
461:
455:
454:
452:
450:
436:
430:
429:
397:
391:
388:
382:
381:
369:
345:
339:
332:
326:
323:
317:
316:
314:
312:
277:
261:Dependency graph
117:dependency graph
64:lazy code motion
62:, also known as
21:computer science
1020:
1019:
1015:
1014:
1013:
1011:
1010:
1009:
995:
994:
989:
983:
980:
969:
957:
946:
941:
922:Escape analysis
890:Static analysis
885:
834:
818:
797:
770:Code generation
764:
740:
696:
689:
611:
590:
585:
555:
554:
547:wiki.luajit.org
541:
540:
536:
526:
524:
516:
515:
511:
501:
499:
492:
488:
487:
483:
473:
471:
463:
462:
458:
448:
446:
438:
437:
433:
398:
394:
389:
385:
378:
346:
342:
333:
329:
324:
320:
310:
308:
278:
274:
269:
247:
239:heap allocation
231:
218:
202:
197:
180:
174:
160:On the defunct
157:point in time.
136:code scheduling
109:
103:
80:
49:
41:
17:
12:
11:
5:
1018:
1008:
1007:
991:
990:
960:
958:
951:
943:
942:
940:
939:
934:
932:Shape analysis
929:
924:
919:
914:
909:
904:
899:
897:Alias analysis
893:
891:
887:
886:
884:
883:
878:
873:
871:Jump threading
868:
863:
858:
853:
848:
842:
840:
836:
835:
833:
832:
826:
824:
820:
819:
817:
816:
811:
805:
803:
799:
798:
796:
795:
790:
785:
780:
774:
772:
766:
765:
763:
762:
757:
751:
749:
742:
741:
739:
738:
733:
728:
723:
717:
712:
707:
701:
699:
691:
690:
688:
687:
682:
677:
672:
670:Loop unrolling
667:
665:Loop splitting
662:
657:
652:
650:Loop inversion
647:
642:
637:
632:
627:
621:
619:
613:
612:
610:
609:
604:
598:
596:
592:
591:
584:
583:
576:
569:
561:
553:
552:
534:
509:
481:
456:
431:
392:
383:
376:
340:
327:
318:
292:(3): 131–154.
271:
270:
268:
265:
264:
263:
258:
253:
246:
243:
230:
227:
217:
214:
201:
198:
196:
193:
176:Main article:
173:
170:
166:branch predict
105:Main article:
102:
99:
91:Code Factoring
79:
76:
48:
45:
40:
37:
15:
9:
6:
4:
3:
2:
1017:
1006:
1003:
1002:
1000:
987:
977:
973:
967:
966:
961:This article
959:
955:
950:
949:
938:
935:
933:
930:
928:
925:
923:
920:
918:
915:
913:
910:
908:
905:
903:
900:
898:
895:
894:
892:
888:
882:
879:
877:
874:
872:
869:
867:
864:
862:
859:
857:
854:
852:
849:
847:
844:
843:
841:
837:
831:
828:
827:
825:
821:
815:
812:
810:
809:Deforestation
807:
806:
804:
800:
794:
791:
789:
786:
784:
781:
779:
776:
775:
773:
771:
767:
761:
758:
756:
753:
752:
750:
747:
743:
737:
734:
732:
729:
727:
724:
721:
718:
716:
713:
711:
708:
706:
703:
702:
700:
698:
692:
686:
683:
681:
678:
676:
673:
671:
668:
666:
663:
661:
658:
656:
653:
651:
648:
646:
643:
641:
638:
636:
633:
631:
628:
626:
623:
622:
620:
618:
614:
608:
605:
603:
600:
599:
597:
593:
589:
582:
577:
575:
570:
568:
563:
562:
559:
548:
544:
538:
523:
519:
513:
498:
491:
485:
470:
466:
460:
445:
441:
435:
427:
423:
419:
415:
411:
407:
403:
396:
387:
379:
373:
368:
363:
359:
355:
351:
344:
337:
331:
322:
307:
303:
299:
295:
291:
287:
283:
276:
272:
262:
259:
257:
254:
252:
249:
248:
242:
240:
235:
226:
223:
213:
211:
206:
192:
184:
179:
169:
167:
163:
162:Intel Itanium
158:
155:
151:
147:
143:
142:
137:
133:
129:
122:
118:
113:
108:
98:
96:
92:
84:
75:
72:
67:
65:
61:
53:
44:
36:
34:
30:
26:
22:
981:
962:
546:
537:
525:. Retrieved
521:
512:
500:. Retrieved
496:
484:
472:. Retrieved
468:
459:
447:. Retrieved
443:
434:
412:(5): 24–43.
409:
405:
395:
386:
357:
353:
343:
330:
321:
309:. Retrieved
289:
285:
275:
232:
219:
209:
203:
189:
159:
145:
139:
135:
131:
127:
126:
90:
89:
68:
63:
60:Code Sinking
59:
58:
42:
29:optimization
24:
18:
722:elimination
640:Loop fusion
595:Basic block
527:25 February
502:25 February
474:25 February
469:gcc.gnu.org
449:25 February
360:: 219–233.
311:25 February
25:code motion
984:March 2022
965:categories
802:Functional
720:Dead store
406:IEEE Micro
267:References
695:Data-flow
426:1937-4143
150:execution
119:. Due to
999:Category
972:help out
697:analysis
444:llvm.org
306:35717348
245:See also
212:a loop.
970:Please
497:gnu.org
823:Global
748:-based
424:
374:
304:
234:LuaJIT
229:LuaJIT
839:Other
493:(PDF)
302:S2CID
617:Loop
529:2022
504:2022
476:2022
451:2022
422:ISSN
372:ISBN
358:1383
313:2022
220:The
210:into
205:LLVM
200:LLVM
154:CPUs
144:and
39:Uses
974:by
746:SSA
414:doi
362:doi
294:doi
216:GCC
19:In
1001::
545:.
520:.
495:.
467:.
442:.
420:.
410:20
408:.
404:.
370:.
352:.
300:.
288:.
284:.
138:,
134:,
130:,
23:,
986:)
982:(
968:.
580:e
573:t
566:v
549:.
531:.
506:.
478:.
453:.
428:.
416::
380:.
364::
315:.
296::
290:4
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.
