1308:
There are more optimizations to do. Register r3 is the main variable in the innermost loop (0140-0260); it gets incremented by 1 each time through the loop. Register r8 (which is invariant in the innermost loop) is added to r3. Instead of using r3, the compiler can eliminate r3 and use r9. The loop,
76:
Loop invariants are essentially constants within a loop, but their value may change outside of the loop. Induction variables are changing by known amounts. The terms are relative to a particular loop. When loops are nested, an induction variable in the outer loop can be a loop invariant in the inner
886:
out of the loop. Constants can be loaded outside of both loops—such as floating point registers fr3 and fr4. Recognition that some variables don't change allows registers to be merged; n is constant, so r2, r4, r7, r12 can be hoisted and collapsed. The common value i*n is computed in (the hoisted)
3260:
At line 0320, r14 is the sum of r8 and r1, and r8 and r1 are being incremented in the loop. Register r8 is being bumped by r2 (=n) and r1 is being bumped by 1. Consequently, r14 is being bumped by n+1 each time through the loop. The last loop multiply at 0330 can be strength reduced by adding
2238:
Register r20 is being incremented by the invariant/constant r2 each time through the loop at 0117. After being incremented, it is multiplied by 8 to create r22 at 0119. That multiplication can be strength reduced by adding 8*r2 each time through the loop.
2231:
There are now four multiplications within the outer loop that increments r1. Register r8 = r1*r2 at 0190 can be strength reduced by setting it before entering the loop (0055) and incrementing it by r2 at the bottom of the loop (0385).
1481:
Now r9 is the loop variable, but it interacts with the multiply by 8. Here we get to do some strength reduction. The multiply by 8 can be reduced to some successive additions of 8. Now there are no multiplications inside the loop.
4387:
replacing integer division by a constant with a multiplication, taking advantage of the limited range of machine integers. This method also works if divisor is a non-integer sufficiently greater than 1, e.g. √2 or
4369:
to replace slow math operations with faster operations. The benefits depend on the target CPU and sometimes on the surrounding code (which can affect the availability of other functional units within the CPU).
3844:
Furthermore, r1 is only being used to control the loop, so r1 can be replaced by a different induction variable such as r40. Where i went 0 <= i < n, register r40 goes 0 <= r40 < 8 * n * n.
887:
r8 and r13, so they collapse. The innermost loop (0120-0260) has been reduced from 11 to 7 intermediate instructions. The only multiply that remains in the innermost loop is line 0210's multiply by 8.
4710:
In languages such as C and Java, integer division has round-towards-zero semantics, whereas a bit-shift always rounds down, requiring special treatment for negative numbers. For example, in Java,
1309:
instead of being controlled by r3 = 0 to n-1, can be controlled by r9=r8+0 to r8+n-1. That adds four instructions and kills four instructions, but there's one fewer instruction inside the loop.
80:
Strength reduction looks for expressions involving a loop invariant and an induction variable. Some of those expressions can be simplified. For example, the multiplication of loop invariant
3841:
There's still more to go. Constant folding will recognize that r1=0 in the preamble, so several instructions will clean up. Register r8 isn't used in the loop, so it can disappear.
65:
A compiler uses methods to identify loops and recognize the characteristics of register values within those loops. For strength reduction, the compiler is interested in:
4476:
or recursive strength reduction replaces a function of some systematically changing variable with a simpler calculation using previous values of the function. In a
4759:
882:
The compiler will start doing many optimizations – not just strength reduction. Expressions that are constant (invariant) within a loop will be
874:
as a 1-dimensional array of n*n size, so that whenever the high-level code expresses A it will internally be A for any given valid indices x and y.
4913:
5060:
2761:
That leaves the two loops with only one multiplication operation (at 0330) within the outer loop and no multiplications within the inner loop.
31:
where expensive operations are replaced with equivalent but less expensive operations. The classic example of strength reduction converts
2235:
The value r8*8 (at 0118) can be strength reduced by initializing it (0056) and adding 8*r2 to it when r8 gets incremented (0386).
5094:
280:
Below is an example that will strength-reduce all the loop multiplications that arose from array indexing address calculations.
4829:
4804:
4692:
4906:
4641:
takes a second parameter z = 3 ** x, allowing the expensive computation (3 ** x) to be replaced by the cheaper (3 * z).
4763:
5266:
1654:
Registers r9 and r10 (= 8*r9) aren't both needed; r9 can be eliminated in the loop. The loop is now 5 instructions.
5143:
5044:
4481:
5292:
5185:
4899:
4838:
4817:
4477:
59:
46:
Examples of strength reduction include replacing a multiplication within a loop with an addition and replacing
5080:
5164:
4485:
5215:
5180:
4820:; Kennedy, Ken (1981), "Reduction of Operator Strength", in Munchnik, Steven S.; Jones, Neil D. (eds.),
5104:
4979:
883:
4959:
4650:
4872:
4964:
5112:
5089:
5065:
4994:
4366:
4384:
replacing integer multiplication by a constant with a combination of shifts, adds or subtracts
5241:
5236:
5190:
5117:
4941:
4936:
4359:
28:
20:
5271:
5195:
5039:
58:
Most of a program's execution time is typically spent in a small section of code (called a
8:
5251:
5122:
5014:
4922:
4655:
5246:
5210:
5029:
4969:
4860:
4660:
4473:
5127:
4951:
4825:
4800:
4793:
4688:
4681:
72:
Induction variables: the values which are being iterated each time through the loop.
5261:
5200:
5070:
5049:
5009:
4989:
4864:
4850:
4841:; Kennedy, Ken (November 1977), "An algorithm for reduction of operator strength",
4375:
5256:
284:
5231:
5205:
5004:
4999:
4984:
4788:
4066:; cmp r1, r2 killed ; i < n; induction variable replaced
47:
5286:
4741:
4379:
4855:
69:
Loop invariants: the values which do not change within the body of a loop.
4974:
4891:
62:), and that code is often inside a loop that is executed over and over.
39:
additions – something that frequently occurs in array addressing.(
5054:
4813:
4784:
4780:
4258:; r1 = r1 + #1 killed ; dead code (r40 controls loop)
1407:; r9 = r8 + r3 killed ; calculate subscript i * n + j
4678:
5148:
4480:
this would apply to an expression involving a loop variable and in a
4374:
replacing integer division or multiplication by a power of 2 with an
4462:
y = (((uint32_t)x * (uint32_t)0x45F3) >> 16) + x) >> 2)
1033:; r13 = r1 * r2 killed; use r8 ; calculate subscript i * n
3973:; r14 = #0 killed ; r8 = 0, becomes dead code
3946:; r20 = r2 killed ; r8 = 0, becomes dead code
2442:; r8 = r1 * r2 killed ; calculate subscript i * n
4871:
Cooper, Keith; Simpson, Taylor; Vick, Christopher (October 1995),
1731:; cmp r9, r20 killed ; r8 + j < r8 + n = r20
3865:; r1 = #0 ; i = 0, becomes dead code
1586:; r10 = r9 * #8 killed ; calculate byte address
4679:
Steven
Muchnick; Muchnick and Associates (15 August 1997).
3910:; r8 = #0 killed ; r8 no longer used
2469:; r22 = r20 * #8 killed ; strength reduced
3689:; r15 = r14 * #8 killed ; strength reduced
4730:
optimize division by two by replacing it by a bit shift.
3922:#0 ; initial value for r8 * 8
4739:
1809:; r9 = r9 + #1 killed ; loop variable
4353:
4742:"Division by Invariant Integers Using Multiplication"
4672:
4358:
This material is disputed. It is better described as
3467:#8 ; initial value of r15 (0330)
4030:#8 ; strength reduced increment
3509:#8 ; strength reduced increment
4264:; r8 = r8 + r2 killed ; dead code
3365:#8 ; initial value for r8 * 8
2865:#8 ; initial value for r8 * 8
2343:#8 ; initial value for r8 * 8
4792:
4680:
4454:y = ((uint32_t)x * (uint32_t)0xCCCD) >> 19)
3683:; r14 = r8 + r1 killed ; dead code
1365:; cmp r3, r2 killed ; j < n
4870:
4812:
169:can be replaced with successive weaker additions
40:
5284:
3129:#8 ; calculate byte address
2625:#8 ; calculate byte address
2163:#8 ; calculate byte address
1240:#8 ; calculate byte address
790:#8 ; calculate byte address
283:Imagine a simple loop that sets an array to the
1317:; r3 = #0 killed ; j = 0
5061:Induction variable recognition and elimination
4822:Program Flow Analysis: Theory and Applications
4779:
4468:
4201:#8 ; strength reduced multiply
3650:#8 ; strength reduced multiply
3422:#8 ; initial value of r22
3063:#8 ; strength reduced multiply
2922:#8 ; initial value of r22
2559:#8 ; strength reduced multiply
2400:#8 ; initial value of r22
2097:#8 ; strength reduced multiply
1989:#8 ; initial value of r10
1803:#8 ; strength reduced multiply
1622:#8 ; strength reduced multiply
4907:
1449:; r3 = r3 + #1 killed ; j++
275:
4837:
4795:Compilers: Principles, Techniques, and Tools
3940:#8 ; increment for r40
3383:#8 ; increment for r40
2883:#8 ; increment for r40
2361:#8 ; increment for r40
1425:#8 ; calculate byte address
1138:#8 ; calculate byte address
643:#8 ; calculate byte address
4921:
4914:
4900:
4854:
4740:Granlund, Torbjörn; Peter L. Montgomery.
1701:#8 ; initial value of r10
1538:#8 ; initial value of r10
4147:; r10 = 8*(r8 + j) < 8*(r8 + n) = r22
3596:; r10 = 8*(r8 + j) < 8*(r8 + n) = r22
3009:; r10 = 8*(r8 + j) < 8*(r8 + n) = r22
2505:; r10 = 8*(r8 + j) < 8*(r8 + n) = r22
2043:; r10 = 8*(r8 + j) < 8*(r8 + n) = r22
1749:; r10 = 8*(r8 + j) < 8*(r8 + n) = r22
1467:#1 ; new loop variable
5095:Sparse conditional constant propagation
4683:Advanced Compiler Design Implementation
2448:; r20 = r8 + r2 killed - dead code
5285:
3287:#0 ; i = 0
2787:#0 ; i = 0
2265:#0 ; i = 0
1854:#0 ; i = 0
913:#0 ; i = 0
439:#0 ; i = 0
4895:
3261:(r2+1)*8 each time through the loop.
877:
50:within a loop with a multiplication.
4484:it would apply to the argument of a
4111:; strength reduced expression to r40
3560:; strength reduced expression to r40
2973:; strength reduced expression to r40
2756:
2463:; strength reduced expression to r40
1640:#1 ; loop variable
413:The compiler will view this code as
408:
4760:"Division of integers by constants"
4354:Other strength reduction operations
4285:; strength reduce expression r8 * 8
3773:; strength reduce expression r8 * 8
3213:; strength reduce expression r8 * 8
2709:; strength reduce expression r8 * 8
870:This expresses 2-dimensional array
35:multiplications inside a loop into
13:
4637:Here modified recursive function f
3964:#8 ; r20 = r2
2007:#8 ; new limit
14:
5304:
4757:
4365:Operator strength reduction uses
3988:#0 ; r14 = 0
946:; load r12, n killed; use r2
940:; load r7, n killed; use r2
934:; load r4, n killed; use r2
5045:Common subexpression elimination
4726:. So in this case, the compiler
1662:; r9 = r8 killed
53:
5186:Compile-time function execution
4478:procedural programming language
4327:; strength reduce r15 = r14 * 8
4306:; strength reduce r22 = r20 * 8
3815:; strength reduce r15 = r14 * 8
3794:; strength reduce r22 = r20 * 8
3234:; strength reduce r22 = r20 * 8
3111:; calculate subscript i * n + i
2730:; strength reduce r22 = r20 * 8
2607:; calculate subscript i * n + i
2145:; calculate subscript i * n + i
1222:; calculate subscript i * n + i
1120:; calculate subscript i * n + j
1057:#0 ; j = 0
736:; calculate subscript i * n + i
607:; calculate subscript i * n + j
514:#0 ; j = 0
41:Cooper, Simpson & Vick 1995
4751:
4733:
4704:
3752:; strength reduce r8 = r1 * r2
3192:; strength reduce r8 = r1 * r2
2688:; strength reduce r8 = r1 * r2
1:
4773:
1823:
1719:#8 ; new limit
5165:Interprocedural optimization
4117:; for (j = 0; j < n; j++)
3853:; for (i = 0, i < n; i++)
3566:; for (j = 0; j < n; j++)
3269:; for (i = 0, i < n; i++)
2979:; for (j = 0; j < n; j++)
2769:; for (i = 0, i < n; i++)
2475:; for (j = 0; j < n; j++)
2247:; for (i = 0, i < n; i++)
2013:; for (j = 0; j < n; j++)
1836:; for (i = 0, i < n; i++)
1039:; for (j = 0; j < n; j++)
895:; for (i = 0, i < n; i++)
496:; for (j = 0; j < n; j++)
421:; for (i = 0, i < n; i++)
7:
5216:Profile-guided optimization
5181:Bounds-checking elimination
4874:Operator Strength Reduction
4644:
4469:Induction variable (orphan)
4362:and instruction assignment.
1950:; calculate subscript i * n
1828:Back to the whole picture:
1027:; calculate subscript i * n
10:
5309:
4980:Loop-invariant code motion
4357:
4084:; i * 8 * n < 8 * n * n
3347:; set initial value for r8
2847:; set initial value for r8
2325:; set initial value for r8
1562:; r8 + j < r8 + n = r20
1383:; r8 + j < r8 + n = r20
1174:#1 ; j++
691:#1 ; j++
276:Strength reduction example
5224:
5173:
5157:
5136:
5103:
5079:
5028:
4960:Automatic parallelization
4950:
4929:
4843:Communications of the ACM
4666:
4651:Fast inverse square root
4551:
4490:
4398:Replacement calculation
3847:
3263:
2763:
2241:
1830:
1656:
1484:
1311:
889:
415:
289:
171:
89:
4965:Automatic vectorization
4446:y = (x << 4) - x
4367:mathematical identities
84:and induction variable
5293:Compiler optimizations
5113:Instruction scheduling
5090:Global value numbering
5066:Live-variable analysis
4995:Loop nest optimization
4923:Compiler optimizations
5242:Control-flow analysis
5237:Array-access analysis
5191:Dead-code elimination
5149:Tail-call elimination
5118:Instruction selection
4942:Local value numbering
4937:Peephole optimization
4856:10.1145/359863.359888
4451:y = (uint16_t)x / 10
4395:Original calculation
4360:peephole optimization
29:compiler optimization
21:compiler construction
16:Compiler optimization
5272:Value range analysis
5196:Expression templates
5040:Available expression
4482:declarative language
4459:y = (uint16_t)x / π
5252:Dependence analysis
5123:Register allocation
5015:Software pipelining
4699:Strength reduction.
4687:. Morgan Kaufmann.
4054:; new limit for r40
5247:Data-flow analysis
5211:Partial evaluation
5020:Strength reduction
4970:Induction variable
4789:Ullman, Jeffrey D.
4661:Partial evaluation
4486:recursive function
4474:Induction variable
3446:; copied from 0320
3404:; copied from 0117
2904:; copied from 0117
2382:; copied from 0117
878:Many optimizations
25:strength reduction
5280:
5279:
5128:Rematerialization
4880:, Rice University
4831:978-0-13-729681-1
4824:, Prentice-Hall,
4814:Allen, Francis E.
4806:978-0-201-10088-4
4766:on 26 March 2024.
4694:978-1-55860-320-2
4466:
4465:
4430:y = x >> 1
4422:y = x << 1
2757:The last multiply
409:Intermediate code
5300:
5262:Pointer analysis
5201:Inline expansion
5071:Use-define chain
5050:Constant folding
5010:Loop unswitching
4990:Loop interchange
4916:
4909:
4902:
4893:
4892:
4888:
4887:
4885:
4879:
4867:
4858:
4834:
4809:
4799:(2nd ed.),
4798:
4768:
4767:
4762:. Archived from
4755:
4749:
4748:
4746:
4737:
4731:
4725:
4721:
4717:
4713:
4708:
4702:
4701:
4686:
4676:
4656:Hacker's Delight
4640:
4633:
4630:
4627:
4624:
4621:
4618:
4615:
4612:
4609:
4606:
4603:
4600:
4597:
4594:
4591:
4588:
4585:
4582:
4579:
4576:
4573:
4570:
4567:
4564:
4561:
4558:
4555:
4545:
4542:
4539:
4536:
4533:
4530:
4527:
4524:
4521:
4518:
4515:
4512:
4509:
4506:
4503:
4500:
4497:
4494:
4392:
4391:
4376:arithmetic shift
4349:
4346:
4343:
4340:
4337:
4334:
4331:
4328:
4325:
4322:
4319:
4316:
4313:
4310:
4307:
4304:
4301:
4298:
4295:
4292:
4289:
4286:
4283:
4280:
4277:
4274:
4271:
4268:
4265:
4262:
4259:
4256:
4253:
4250:
4247:
4244:
4241:
4238:
4235:
4232:
4229:
4226:
4223:
4220:
4217:
4214:
4211:
4208:
4205:
4202:
4199:
4196:
4193:
4190:
4187:
4184:
4181:
4178:
4175:
4172:
4169:
4166:
4163:
4160:
4157:
4154:
4151:
4148:
4145:
4142:
4139:
4136:
4133:
4130:
4127:
4124:
4121:
4118:
4115:
4112:
4109:
4106:
4103:
4100:
4097:
4094:
4091:
4088:
4085:
4082:
4079:
4076:
4073:
4070:
4067:
4064:
4061:
4058:
4055:
4052:
4049:
4046:
4043:
4040:
4037:
4034:
4031:
4028:
4025:
4022:
4019:
4016:
4013:
4010:
4007:
4004:
4001:
3998:
3995:
3992:
3989:
3986:
3983:
3980:
3977:
3974:
3971:
3968:
3965:
3962:
3959:
3956:
3953:
3950:
3947:
3944:
3941:
3938:
3935:
3932:
3929:
3926:
3923:
3920:
3917:
3914:
3911:
3908:
3905:
3902:
3899:
3896:
3893:
3890:
3887:
3884:
3881:
3878:
3875:
3872:
3869:
3866:
3863:
3860:
3857:
3854:
3851:
3837:
3834:
3831:
3828:
3825:
3822:
3819:
3816:
3813:
3810:
3807:
3804:
3801:
3798:
3795:
3792:
3789:
3786:
3783:
3780:
3777:
3774:
3771:
3768:
3765:
3762:
3759:
3756:
3753:
3750:
3747:
3744:
3741:
3738:
3735:
3732:
3729:
3726:
3723:
3720:
3717:
3714:
3711:
3708:
3705:
3702:
3699:
3696:
3693:
3690:
3687:
3684:
3681:
3678:
3675:
3672:
3669:
3666:
3663:
3660:
3657:
3654:
3651:
3648:
3645:
3642:
3639:
3636:
3633:
3630:
3627:
3624:
3621:
3618:
3615:
3612:
3609:
3606:
3603:
3600:
3597:
3594:
3591:
3588:
3585:
3582:
3579:
3576:
3573:
3570:
3567:
3564:
3561:
3558:
3555:
3552:
3549:
3546:
3543:
3540:
3537:
3534:
3531:
3528:
3525:
3522:
3519:
3516:
3513:
3510:
3507:
3504:
3501:
3498:
3495:
3492:
3489:
3486:
3483:
3480:
3477:
3474:
3471:
3468:
3465:
3462:
3459:
3456:
3453:
3450:
3447:
3444:
3441:
3438:
3435:
3432:
3429:
3426:
3423:
3420:
3417:
3414:
3411:
3408:
3405:
3402:
3399:
3396:
3393:
3390:
3387:
3384:
3381:
3378:
3375:
3372:
3369:
3366:
3363:
3360:
3357:
3354:
3351:
3348:
3345:
3342:
3339:
3336:
3333:
3330:
3327:
3324:
3321:
3318:
3315:
3312:
3309:
3306:
3303:
3300:
3297:
3294:
3291:
3288:
3285:
3282:
3279:
3276:
3273:
3270:
3267:
3256:
3253:
3250:
3247:
3244:
3241:
3238:
3235:
3232:
3229:
3226:
3223:
3220:
3217:
3214:
3211:
3208:
3205:
3202:
3199:
3196:
3193:
3190:
3187:
3184:
3181:
3178:
3175:
3172:
3169:
3166:
3163:
3160:
3157:
3154:
3151:
3148:
3145:
3142:
3139:
3136:
3133:
3130:
3127:
3124:
3121:
3118:
3115:
3112:
3109:
3106:
3103:
3100:
3097:
3094:
3091:
3088:
3085:
3082:
3079:
3076:
3073:
3070:
3067:
3064:
3061:
3058:
3055:
3052:
3049:
3046:
3043:
3040:
3037:
3034:
3031:
3028:
3025:
3022:
3019:
3016:
3013:
3010:
3007:
3004:
3001:
2998:
2995:
2992:
2989:
2986:
2983:
2980:
2977:
2974:
2971:
2968:
2965:
2962:
2959:
2956:
2953:
2950:
2947:
2944:
2941:
2938:
2935:
2932:
2929:
2926:
2923:
2920:
2917:
2914:
2911:
2908:
2905:
2902:
2899:
2896:
2893:
2890:
2887:
2884:
2881:
2878:
2875:
2872:
2869:
2866:
2863:
2860:
2857:
2854:
2851:
2848:
2845:
2842:
2839:
2836:
2833:
2830:
2827:
2824:
2821:
2818:
2815:
2812:
2809:
2806:
2803:
2800:
2797:
2794:
2791:
2788:
2785:
2782:
2779:
2776:
2773:
2770:
2767:
2752:
2749:
2746:
2743:
2740:
2737:
2734:
2731:
2728:
2725:
2722:
2719:
2716:
2713:
2710:
2707:
2704:
2701:
2698:
2695:
2692:
2689:
2686:
2683:
2680:
2677:
2674:
2671:
2668:
2665:
2662:
2659:
2656:
2653:
2650:
2647:
2644:
2641:
2638:
2635:
2632:
2629:
2626:
2623:
2620:
2617:
2614:
2611:
2608:
2605:
2602:
2599:
2596:
2593:
2590:
2587:
2584:
2581:
2578:
2575:
2572:
2569:
2566:
2563:
2560:
2557:
2554:
2551:
2548:
2545:
2542:
2539:
2536:
2533:
2530:
2527:
2524:
2521:
2518:
2515:
2512:
2509:
2506:
2503:
2500:
2497:
2494:
2491:
2488:
2485:
2482:
2479:
2476:
2473:
2470:
2467:
2464:
2461:
2458:
2455:
2452:
2449:
2446:
2443:
2440:
2437:
2434:
2431:
2428:
2425:
2422:
2419:
2416:
2413:
2410:
2407:
2404:
2401:
2398:
2395:
2392:
2389:
2386:
2383:
2380:
2377:
2374:
2371:
2368:
2365:
2362:
2359:
2356:
2353:
2350:
2347:
2344:
2341:
2338:
2335:
2332:
2329:
2326:
2323:
2320:
2317:
2314:
2311:
2308:
2305:
2302:
2299:
2296:
2293:
2290:
2287:
2284:
2281:
2278:
2275:
2272:
2269:
2266:
2263:
2260:
2257:
2254:
2251:
2248:
2245:
2227:
2224:
2221:
2218:
2215:
2212:
2209:
2206:
2203:
2200:
2197:
2194:
2191:
2188:
2185:
2182:
2179:
2176:
2173:
2170:
2167:
2164:
2161:
2158:
2155:
2152:
2149:
2146:
2143:
2140:
2137:
2134:
2131:
2128:
2125:
2122:
2119:
2116:
2113:
2110:
2107:
2104:
2101:
2098:
2095:
2092:
2089:
2086:
2083:
2080:
2077:
2074:
2071:
2068:
2065:
2062:
2059:
2056:
2053:
2050:
2047:
2044:
2041:
2038:
2035:
2032:
2029:
2026:
2023:
2020:
2017:
2014:
2011:
2008:
2005:
2002:
1999:
1996:
1993:
1990:
1987:
1984:
1981:
1978:
1975:
1972:
1969:
1966:
1963:
1960:
1957:
1954:
1951:
1948:
1945:
1942:
1939:
1936:
1933:
1930:
1927:
1924:
1921:
1918:
1915:
1912:
1909:
1906:
1903:
1900:
1897:
1894:
1891:
1888:
1885:
1882:
1879:
1876:
1873:
1870:
1867:
1864:
1861:
1858:
1855:
1852:
1849:
1846:
1843:
1840:
1837:
1834:
1819:
1816:
1813:
1810:
1807:
1804:
1801:
1798:
1795:
1792:
1789:
1786:
1783:
1780:
1777:
1774:
1771:
1768:
1765:
1762:
1759:
1756:
1753:
1750:
1747:
1744:
1741:
1738:
1735:
1732:
1729:
1726:
1723:
1720:
1717:
1714:
1711:
1708:
1705:
1702:
1699:
1696:
1693:
1690:
1687:
1684:
1681:
1678:
1675:
1672:
1669:
1666:
1663:
1660:
1650:
1647:
1644:
1641:
1638:
1635:
1632:
1629:
1626:
1623:
1620:
1617:
1614:
1611:
1608:
1605:
1602:
1599:
1596:
1593:
1590:
1587:
1584:
1581:
1578:
1575:
1572:
1569:
1566:
1563:
1560:
1557:
1554:
1551:
1548:
1545:
1542:
1539:
1536:
1533:
1530:
1527:
1524:
1521:
1518:
1515:
1512:
1509:
1506:
1503:
1500:
1499:; new assignment
1497:
1494:
1491:
1488:
1477:
1474:
1471:
1468:
1465:
1462:
1459:
1456:
1453:
1450:
1447:
1444:
1441:
1438:
1435:
1432:
1429:
1426:
1423:
1420:
1417:
1414:
1411:
1408:
1405:
1402:
1399:
1396:
1393:
1390:
1387:
1384:
1381:
1378:
1375:
1372:
1369:
1366:
1363:
1360:
1357:
1354:
1351:
1348:
1345:
1342:
1339:
1336:
1333:
1332:; new assignment
1330:
1327:
1324:
1321:
1318:
1315:
1304:
1301:
1298:
1295:
1292:
1289:
1286:
1283:
1280:
1277:
1274:
1271:
1268:
1265:
1262:
1259:
1256:
1253:
1250:
1247:
1244:
1241:
1238:
1235:
1232:
1229:
1226:
1223:
1220:
1217:
1214:
1211:
1208:
1205:
1202:
1199:
1196:
1193:
1190:
1187:
1184:
1181:
1178:
1175:
1172:
1169:
1166:
1163:
1160:
1157:
1154:
1151:
1148:
1145:
1142:
1139:
1136:
1133:
1130:
1127:
1124:
1121:
1118:
1115:
1112:
1109:
1106:
1103:
1100:
1097:
1094:
1091:
1088:
1085:
1082:
1079:
1076:
1073:
1070:
1067:
1064:
1061:
1058:
1055:
1052:
1049:
1046:
1043:
1040:
1037:
1034:
1031:
1028:
1025:
1022:
1019:
1016:
1013:
1010:
1007:
1004:
1001:
998:
995:
992:
989:
986:
983:
980:
977:
974:
971:
968:
965:
962:
959:
956:
953:
950:
947:
944:
941:
938:
935:
932:
929:
926:
923:
920:
917:
914:
911:
908:
905:
902:
899:
896:
893:
866:
863:
860:
857:
854:
851:
848:
845:
842:
839:
836:
833:
830:
827:
824:
821:
818:
815:
812:
809:
806:
803:
800:
797:
794:
791:
788:
785:
782:
779:
776:
773:
770:
767:
764:
761:
758:
755:
752:
749:
746:
743:
740:
737:
734:
731:
728:
725:
722:
719:
716:
713:
710:
707:
704:
701:
698:
695:
692:
689:
686:
683:
680:
677:
674:
671:
668:
665:
662:
659:
656:
653:
650:
647:
644:
641:
638:
635:
632:
629:
626:
623:
620:
617:
614:
611:
608:
605:
602:
599:
596:
593:
590:
587:
584:
581:
578:
575:
572:
569:
566:
563:
560:
557:
554:
551:
548:
545:
542:
539:
536:
533:
530:
527:
524:
521:
518:
515:
512:
509:
506:
503:
500:
497:
494:
491:
488:
485:
482:
479:
476:
473:
470:
467:
464:
461:
458:
455:
452:
449:
446:
443:
440:
437:
434:
431:
428:
425:
422:
419:
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:
305:
302:
299:
296:
293:
271:
268:
265:
262:
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:
165:
162:
159:
156:
153:
150:
147:
144:
141:
138:
135:
132:
129:
126:
123:
120:
117:
114:
111:
108:
105:
102:
99:
96:
93:
87:
83:
5308:
5307:
5303:
5302:
5301:
5299:
5298:
5297:
5283:
5282:
5281:
5276:
5257:Escape analysis
5225:Static analysis
5220:
5169:
5153:
5132:
5105:Code generation
5099:
5075:
5031:
5024:
4946:
4925:
4920:
4883:
4881:
4877:
4849:(11): 850–856,
4832:
4807:
4776:
4771:
4756:
4752:
4744:
4738:
4734:
4723:
4719:
4715:
4711:
4709:
4705:
4695:
4677:
4673:
4669:
4647:
4638:
4635:
4634:
4631:
4628:
4625:
4622:
4619:
4616:
4613:
4610:
4607:
4604:
4601:
4598:
4595:
4592:
4589:
4586:
4583:
4580:
4577:
4574:
4571:
4568:
4565:
4562:
4559:
4556:
4553:
4547:
4546:
4543:
4540:
4537:
4534:
4531:
4528:
4525:
4522:
4519:
4516:
4513:
4510:
4507:
4504:
4501:
4498:
4495:
4492:
4488:. For example,
4471:
4435:y = x % 2
4363:
4356:
4351:
4350:
4347:
4344:
4341:
4338:
4335:
4332:
4329:
4326:
4323:
4320:
4317:
4314:
4311:
4308:
4305:
4302:
4299:
4296:
4293:
4290:
4287:
4284:
4281:
4278:
4275:
4272:
4269:
4266:
4263:
4260:
4257:
4254:
4251:
4248:
4245:
4242:
4239:
4236:
4233:
4230:
4227:
4224:
4221:
4218:
4215:
4212:
4209:
4206:
4203:
4200:
4197:
4194:
4191:
4188:
4185:
4182:
4179:
4176:
4173:
4170:
4167:
4164:
4161:
4158:
4155:
4152:
4149:
4146:
4143:
4140:
4137:
4134:
4131:
4128:
4125:
4122:
4119:
4116:
4113:
4110:
4107:
4104:
4101:
4098:
4095:
4092:
4089:
4086:
4083:
4080:
4077:
4074:
4071:
4068:
4065:
4062:
4059:
4056:
4053:
4050:
4047:
4044:
4041:
4038:
4035:
4032:
4029:
4026:
4023:
4020:
4017:
4014:
4011:
4008:
4005:
4002:
3999:
3996:
3993:
3990:
3987:
3984:
3981:
3978:
3975:
3972:
3969:
3966:
3963:
3960:
3957:
3954:
3951:
3948:
3945:
3942:
3939:
3936:
3933:
3930:
3927:
3924:
3921:
3918:
3915:
3912:
3909:
3906:
3903:
3900:
3897:
3894:
3891:
3888:
3885:
3882:
3879:
3876:
3873:
3870:
3867:
3864:
3861:
3858:
3855:
3852:
3849:
3839:
3838:
3835:
3832:
3829:
3826:
3823:
3820:
3817:
3814:
3811:
3808:
3805:
3802:
3799:
3796:
3793:
3790:
3787:
3784:
3781:
3778:
3775:
3772:
3769:
3766:
3763:
3760:
3757:
3754:
3751:
3748:
3745:
3742:
3739:
3736:
3733:
3730:
3727:
3724:
3721:
3718:
3715:
3712:
3709:
3706:
3703:
3700:
3697:
3694:
3691:
3688:
3685:
3682:
3679:
3676:
3673:
3670:
3667:
3664:
3661:
3658:
3655:
3652:
3649:
3646:
3643:
3640:
3637:
3634:
3631:
3628:
3625:
3622:
3619:
3616:
3613:
3610:
3607:
3604:
3601:
3598:
3595:
3592:
3589:
3586:
3583:
3580:
3577:
3574:
3571:
3568:
3565:
3562:
3559:
3556:
3553:
3550:
3547:
3544:
3541:
3538:
3535:
3532:
3529:
3526:
3523:
3520:
3517:
3514:
3511:
3508:
3505:
3502:
3499:
3496:
3493:
3490:
3487:
3484:
3481:
3478:
3475:
3472:
3469:
3466:
3463:
3460:
3457:
3454:
3451:
3448:
3445:
3442:
3439:
3436:
3433:
3430:
3427:
3424:
3421:
3418:
3415:
3412:
3409:
3406:
3403:
3400:
3397:
3394:
3391:
3388:
3385:
3382:
3379:
3376:
3373:
3370:
3367:
3364:
3361:
3358:
3355:
3352:
3349:
3346:
3343:
3340:
3337:
3334:
3331:
3328:
3325:
3322:
3319:
3316:
3313:
3310:
3307:
3304:
3301:
3298:
3295:
3292:
3289:
3286:
3283:
3280:
3277:
3274:
3271:
3268:
3265:
3258:
3257:
3254:
3251:
3248:
3245:
3242:
3239:
3236:
3233:
3230:
3227:
3224:
3221:
3218:
3215:
3212:
3209:
3206:
3203:
3200:
3197:
3194:
3191:
3188:
3185:
3182:
3179:
3176:
3173:
3170:
3167:
3164:
3161:
3158:
3155:
3152:
3149:
3146:
3143:
3140:
3137:
3134:
3131:
3128:
3125:
3122:
3119:
3116:
3113:
3110:
3107:
3104:
3101:
3098:
3095:
3092:
3089:
3086:
3083:
3080:
3077:
3074:
3071:
3068:
3065:
3062:
3059:
3056:
3053:
3050:
3047:
3044:
3041:
3038:
3035:
3032:
3029:
3026:
3023:
3020:
3017:
3014:
3011:
3008:
3005:
3002:
2999:
2996:
2993:
2990:
2987:
2984:
2981:
2978:
2975:
2972:
2969:
2966:
2963:
2960:
2957:
2954:
2951:
2948:
2945:
2942:
2939:
2936:
2933:
2930:
2927:
2924:
2921:
2918:
2915:
2912:
2909:
2906:
2903:
2900:
2897:
2894:
2891:
2888:
2885:
2882:
2879:
2876:
2873:
2870:
2867:
2864:
2861:
2858:
2855:
2852:
2849:
2846:
2843:
2840:
2837:
2834:
2831:
2828:
2825:
2822:
2819:
2816:
2813:
2810:
2807:
2804:
2801:
2798:
2795:
2792:
2789:
2786:
2783:
2780:
2777:
2774:
2771:
2768:
2765:
2759:
2754:
2753:
2750:
2747:
2744:
2741:
2738:
2735:
2732:
2729:
2726:
2723:
2720:
2717:
2714:
2711:
2708:
2705:
2702:
2699:
2696:
2693:
2690:
2687:
2684:
2681:
2678:
2675:
2672:
2669:
2666:
2663:
2660:
2657:
2654:
2651:
2648:
2645:
2642:
2639:
2636:
2633:
2630:
2627:
2624:
2621:
2618:
2615:
2612:
2609:
2606:
2603:
2600:
2597:
2594:
2591:
2588:
2585:
2582:
2579:
2576:
2573:
2570:
2567:
2564:
2561:
2558:
2555:
2552:
2549:
2546:
2543:
2540:
2537:
2534:
2531:
2528:
2525:
2522:
2519:
2516:
2513:
2510:
2507:
2504:
2501:
2498:
2495:
2492:
2489:
2486:
2483:
2480:
2477:
2474:
2471:
2468:
2465:
2462:
2459:
2456:
2453:
2450:
2447:
2444:
2441:
2438:
2435:
2432:
2429:
2426:
2423:
2420:
2417:
2414:
2411:
2408:
2405:
2402:
2399:
2396:
2393:
2390:
2387:
2384:
2381:
2378:
2375:
2372:
2369:
2366:
2363:
2360:
2357:
2354:
2351:
2348:
2345:
2342:
2339:
2336:
2333:
2330:
2327:
2324:
2321:
2318:
2315:
2312:
2309:
2306:
2303:
2300:
2297:
2294:
2291:
2288:
2285:
2282:
2279:
2276:
2273:
2270:
2267:
2264:
2261:
2258:
2255:
2252:
2249:
2246:
2243:
2229:
2228:
2225:
2222:
2219:
2216:
2213:
2210:
2207:
2204:
2201:
2198:
2195:
2192:
2189:
2186:
2183:
2180:
2177:
2174:
2171:
2168:
2165:
2162:
2159:
2156:
2153:
2150:
2147:
2144:
2141:
2138:
2135:
2132:
2129:
2126:
2123:
2120:
2117:
2114:
2111:
2108:
2105:
2102:
2099:
2096:
2093:
2090:
2087:
2084:
2081:
2078:
2075:
2072:
2069:
2066:
2063:
2060:
2057:
2054:
2051:
2048:
2045:
2042:
2039:
2036:
2033:
2030:
2027:
2024:
2021:
2018:
2015:
2012:
2009:
2006:
2003:
2000:
1997:
1994:
1991:
1988:
1985:
1982:
1979:
1976:
1973:
1970:
1967:
1964:
1961:
1958:
1955:
1952:
1949:
1946:
1943:
1940:
1937:
1934:
1931:
1928:
1925:
1922:
1919:
1916:
1913:
1910:
1907:
1904:
1901:
1898:
1895:
1892:
1889:
1886:
1883:
1880:
1877:
1874:
1871:
1868:
1865:
1862:
1859:
1856:
1853:
1850:
1847:
1844:
1841:
1838:
1835:
1832:
1826:
1821:
1820:
1817:
1814:
1811:
1808:
1805:
1802:
1799:
1796:
1793:
1790:
1787:
1784:
1781:
1778:
1775:
1772:
1769:
1766:
1763:
1760:
1757:
1754:
1751:
1748:
1745:
1742:
1739:
1736:
1733:
1730:
1727:
1724:
1721:
1718:
1715:
1712:
1709:
1706:
1703:
1700:
1697:
1694:
1691:
1688:
1685:
1682:
1679:
1676:
1673:
1670:
1667:
1664:
1661:
1658:
1652:
1651:
1648:
1645:
1642:
1639:
1636:
1633:
1630:
1627:
1624:
1621:
1618:
1615:
1612:
1609:
1606:
1603:
1600:
1597:
1594:
1591:
1588:
1585:
1582:
1579:
1576:
1573:
1570:
1567:
1564:
1561:
1558:
1555:
1552:
1549:
1546:
1543:
1540:
1537:
1534:
1531:
1528:
1525:
1522:
1519:
1516:
1513:
1510:
1507:
1504:
1501:
1498:
1495:
1492:
1489:
1486:
1479:
1478:
1475:
1472:
1469:
1466:
1463:
1460:
1457:
1454:
1451:
1448:
1445:
1442:
1439:
1436:
1433:
1430:
1427:
1424:
1421:
1418:
1415:
1412:
1409:
1406:
1403:
1400:
1397:
1394:
1391:
1388:
1385:
1382:
1379:
1376:
1373:
1370:
1367:
1364:
1361:
1358:
1355:
1352:
1349:
1346:
1343:
1340:
1337:
1334:
1331:
1328:
1325:
1322:
1319:
1316:
1313:
1306:
1305:
1302:
1299:
1296:
1293:
1290:
1287:
1284:
1281:
1278:
1275:
1272:
1269:
1266:
1263:
1260:
1257:
1254:
1251:
1248:
1245:
1242:
1239:
1236:
1233:
1230:
1227:
1224:
1221:
1218:
1215:
1212:
1209:
1206:
1203:
1200:
1197:
1194:
1191:
1188:
1185:
1182:
1179:
1176:
1173:
1170:
1167:
1164:
1161:
1158:
1155:
1152:
1149:
1146:
1143:
1140:
1137:
1134:
1131:
1128:
1125:
1122:
1119:
1116:
1113:
1110:
1107:
1104:
1101:
1098:
1095:
1092:
1089:
1086:
1083:
1080:
1077:
1074:
1071:
1068:
1065:
1062:
1059:
1056:
1053:
1050:
1047:
1044:
1041:
1038:
1035:
1032:
1029:
1026:
1023:
1020:
1017:
1014:
1011:
1008:
1005:
1002:
999:
996:
993:
990:
987:
984:
981:
978:
975:
972:
969:
966:
963:
960:
957:
954:
951:
948:
945:
942:
939:
936:
933:
930:
927:
924:
921:
918:
915:
912:
909:
906:
903:
900:
897:
894:
891:
880:
868:
867:
864:
861:
858:
855:
852:
849:
846:
843:
840:
837:
834:
831:
828:
825:
822:
819:
816:
813:
810:
807:
804:
801:
798:
795:
792:
789:
786:
783:
780:
777:
774:
771:
768:
765:
762:
759:
756:
753:
750:
747:
744:
741:
738:
735:
732:
729:
726:
723:
720:
717:
714:
711:
708:
705:
702:
699:
696:
693:
690:
687:
684:
681:
678:
675:
672:
669:
666:
663:
660:
657:
654:
651:
648:
645:
642:
639:
636:
633:
630:
627:
624:
621:
618:
615:
612:
609:
606:
603:
600:
597:
594:
591:
588:
585:
582:
579:
576:
573:
570:
567:
564:
561:
558:
555:
552:
549:
546:
543:
540:
537:
534:
531:
528:
525:
522:
519:
516:
513:
510:
507:
504:
501:
498:
495:
492:
489:
486:
483:
480:
477:
474:
471:
468:
465:
462:
459:
456:
453:
450:
447:
444:
441:
438:
435:
432:
429:
426:
423:
420:
417:
411:
406:
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:
303:
300:
297:
294:
291:
285:identity matrix
278:
273:
272:
269:
266:
263:
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:
167:
166:
163:
160:
157:
154:
151:
148:
145:
142:
139:
136:
133:
130:
127:
124:
121:
118:
115:
112:
109:
106:
103:
100:
97:
94:
91:
85:
81:
56:
17:
12:
11:
5:
5306:
5296:
5295:
5278:
5277:
5275:
5274:
5269:
5267:Shape analysis
5264:
5259:
5254:
5249:
5244:
5239:
5234:
5232:Alias analysis
5228:
5226:
5222:
5221:
5219:
5218:
5213:
5208:
5206:Jump threading
5203:
5198:
5193:
5188:
5183:
5177:
5175:
5171:
5170:
5168:
5167:
5161:
5159:
5155:
5154:
5152:
5151:
5146:
5140:
5138:
5134:
5133:
5131:
5130:
5125:
5120:
5115:
5109:
5107:
5101:
5100:
5098:
5097:
5092:
5086:
5084:
5077:
5076:
5074:
5073:
5068:
5063:
5058:
5052:
5047:
5042:
5036:
5034:
5026:
5025:
5023:
5022:
5017:
5012:
5007:
5005:Loop unrolling
5002:
5000:Loop splitting
4997:
4992:
4987:
4985:Loop inversion
4982:
4977:
4972:
4967:
4962:
4956:
4954:
4948:
4947:
4945:
4944:
4939:
4933:
4931:
4927:
4926:
4919:
4918:
4911:
4904:
4896:
4890:
4889:
4868:
4835:
4830:
4810:
4805:
4781:Aho, Alfred V.
4775:
4772:
4770:
4769:
4758:Jones, Nigel.
4750:
4732:
4703:
4693:
4670:
4668:
4665:
4664:
4663:
4658:
4653:
4646:
4643:
4552:
4491:
4470:
4467:
4464:
4463:
4460:
4456:
4455:
4452:
4448:
4447:
4444:
4440:
4439:
4438:y = x & 1
4436:
4432:
4431:
4428:
4424:
4423:
4420:
4416:
4415:
4412:
4411:y%2 != 0
4408:
4407:
4404:
4400:
4399:
4396:
4390:
4389:
4385:
4382:
4355:
4352:
3848:
3264:
2764:
2758:
2755:
2242:
1831:
1825:
1822:
1657:
1485:
1312:
890:
879:
876:
416:
410:
407:
290:
277:
274:
172:
90:
74:
73:
70:
55:
52:
48:exponentiation
15:
9:
6:
4:
3:
2:
5305:
5294:
5291:
5290:
5288:
5273:
5270:
5268:
5265:
5263:
5260:
5258:
5255:
5253:
5250:
5248:
5245:
5243:
5240:
5238:
5235:
5233:
5230:
5229:
5227:
5223:
5217:
5214:
5212:
5209:
5207:
5204:
5202:
5199:
5197:
5194:
5192:
5189:
5187:
5184:
5182:
5179:
5178:
5176:
5172:
5166:
5163:
5162:
5160:
5156:
5150:
5147:
5145:
5144:Deforestation
5142:
5141:
5139:
5135:
5129:
5126:
5124:
5121:
5119:
5116:
5114:
5111:
5110:
5108:
5106:
5102:
5096:
5093:
5091:
5088:
5087:
5085:
5082:
5078:
5072:
5069:
5067:
5064:
5062:
5059:
5056:
5053:
5051:
5048:
5046:
5043:
5041:
5038:
5037:
5035:
5033:
5027:
5021:
5018:
5016:
5013:
5011:
5008:
5006:
5003:
5001:
4998:
4996:
4993:
4991:
4988:
4986:
4983:
4981:
4978:
4976:
4973:
4971:
4968:
4966:
4963:
4961:
4958:
4957:
4955:
4953:
4949:
4943:
4940:
4938:
4935:
4934:
4932:
4928:
4924:
4917:
4912:
4910:
4905:
4903:
4898:
4897:
4894:
4876:
4875:
4869:
4866:
4862:
4857:
4852:
4848:
4844:
4840:
4836:
4833:
4827:
4823:
4819:
4815:
4811:
4808:
4802:
4797:
4796:
4790:
4786:
4782:
4778:
4777:
4765:
4761:
4754:
4743:
4736:
4729:
4722:evaluates to
4720:-3 >> 1
4714:evaluates to
4707:
4700:
4696:
4690:
4685:
4684:
4675:
4671:
4662:
4659:
4657:
4654:
4652:
4649:
4648:
4642:
4550:
4489:
4487:
4483:
4479:
4475:
4461:
4458:
4457:
4453:
4450:
4449:
4445:
4442:
4441:
4437:
4434:
4433:
4429:
4426:
4425:
4421:
4418:
4417:
4413:
4410:
4409:
4405:
4402:
4401:
4397:
4394:
4393:
4386:
4383:
4381:
4380:logical shift
4377:
4373:
4372:
4371:
4368:
4361:
3846:
3842:
3262:
2762:
2240:
2236:
2233:
1829:
1655:
1483:
1310:
888:
885:
875:
873:
414:
288:
286:
281:
170:
88:
78:
71:
68:
67:
66:
63:
61:
54:Code analysis
51:
49:
44:
43:, p. 1)
42:
38:
34:
30:
26:
22:
5019:
4882:, retrieved
4873:
4846:
4842:
4821:
4794:
4764:the original
4753:
4735:
4727:
4706:
4698:
4682:
4674:
4636:
4548:
4472:
4364:
3843:
3840:
3259:
2760:
2237:
2234:
2230:
1827:
1653:
1480:
1307:
881:
871:
869:
412:
282:
279:
168:
79:
75:
64:
57:
45:
36:
32:
24:
18:
5057:elimination
4975:Loop fusion
4930:Basic block
4839:Cocke, John
4818:Cocke, John
4785:Sethi, Ravi
4443:y = x * 15
1520:; new limit
1353:; new limit
5137:Functional
5055:Dead store
4774:References
4718:, whereas
4427:y = x / 2
4419:y = x * 2
4414:y & 1
4228:; A = 1.0;
4165:; A = 0.0;
3677:; A = 1.0;
3614:; A = 0.0;
3533:; i < n
3090:; A = 1.0;
3027:; A = 0.0;
2946:; i < n
2586:; A = 1.0;
2523:; A = 0.0;
2424:; i < n
2124:; A = 1.0;
2061:; A = 0.0;
1917:; i < n
1824:Outer loop
1767:; A = 0.0;
1580:; A = 0.0;
1401:; A = 0.0;
1201:; A = 1.0;
1099:; A = 0.0;
1081:; j < n
994:; i < n
718:; A = 1.0;
571:; A = 0.0;
538:; j < n
463:; i < n
5030:Data-flow
4884:April 22,
5287:Category
5032:analysis
4791:(1986),
4645:See also
4549:becomes
60:hot spot
4865:1092505
1971:; limit
1683:; limit
884:hoisted
5158:Global
5083:-based
4863:
4828:
4803:
4728:cannot
4712:-3 / 2
4691:
4599:f'
4575:f'
4563:f'
4403:y+= 1
4348:G0001:
4234:fstore
4222:G0003:
4171:fstore
4129:G0002:
4060:G0000:
3836:G0001:
3695:fstore
3671:G0003:
3620:fstore
3578:G0002:
3515:G0000:
3255:G0001:
3135:fstore
3084:G0003:
3033:fstore
2991:G0002:
2928:G0000:
2751:G0001:
2631:fstore
2580:G0003:
2529:fstore
2487:G0002:
2406:G0000:
2226:G0001:
2169:fstore
2118:G0003:
2067:fstore
2025:G0002:
1899:G0000:
1773:fstore
1725:G0002:
1592:fstore
1544:G0002:
1431:fstore
1359:G0002:
1303:G0001:
1246:fstore
1195:G0003:
1144:fstore
1063:G0002:
976:G0000:
865:G0001:
808:fstore
712:G0003:
661:fstore
520:G0002:
445:G0000:
77:loop.
37:weaker
33:strong
5174:Other
4878:(PDF)
4861:S2CID
4745:(PDF)
4667:Notes
4572:where
4336:G0000
4210:G0002
4156:G0003
4093:G0001
3824:G0000
3659:G0002
3605:G0003
3542:G0001
3243:G0000
3072:G0002
3018:G0003
2955:G0001
2739:G0000
2568:G0002
2514:G0003
2433:G0001
2214:G0000
2106:G0002
2052:G0003
1926:G0001
1818:G0002
1758:G0003
1649:G0002
1571:G0003
1476:G0002
1392:G0003
1291:G0000
1183:G0002
1090:G0003
1003:G0001
853:G0000
826:; i++
700:G0002
562:G0003
487:G0001
27:is a
4952:Loop
4886:2010
4826:ISBN
4801:ISBN
4689:ISBN
4406:y++
4345:0410
4339:0400
4330:0390
4309:0389
4288:0388
4267:0386
4261:0385
4255:0380
4252:;i++
4249:0370
4246:0360
4231:0350
4225:0290
4219:0280
4213:0270
4204:0260
4186:0245
4183:0240
4168:0230
4162:0170
4159:0160
4150:0150
4132:0147
4126:0120
4120:0100
4114:0090
4099:0118
4096:0080
4087:0070
4069:0065
4063:0060
4057:0040
3949:0058
3943:0058
3925:0057
3913:0056
3907:0055
3904:#1.0
3895:0340
3892:#0.0
3883:0220
3871:load
3868:0050
3862:0030
3856:0020
3850:0010
3833:0410
3827:0400
3818:0390
3797:0389
3776:0388
3755:0386
3734:0385
3716:0380
3713:;i++
3710:0370
3707:0360
3692:0350
3686:0330
3680:0320
3674:0290
3668:0280
3662:0270
3653:0260
3635:0245
3632:0240
3617:0230
3611:0170
3608:0160
3599:0150
3581:0147
3575:0120
3569:0100
3563:0090
3548:0118
3545:0080
3536:0070
3518:0060
3512:0040
3407:0058
3386:0058
3368:0057
3350:0056
3329:0055
3326:#1.0
3317:0340
3314:#0.0
3305:0220
3293:load
3290:0050
3278:0030
3272:0020
3266:0010
3252:0410
3246:0400
3237:0390
3216:0388
3195:0386
3174:0385
3156:0380
3153:;i++
3150:0370
3147:0360
3132:0350
3114:0330
3093:0320
3087:0290
3081:0280
3075:0270
3066:0260
3048:0245
3045:0240
3030:0230
3024:0170
3021:0160
3012:0150
2994:0147
2988:0120
2982:0100
2976:0090
2961:0118
2958:0080
2949:0070
2931:0060
2925:0040
2907:0058
2886:0058
2868:0057
2850:0056
2829:0055
2826:#1.0
2817:0340
2814:#0.0
2805:0220
2793:load
2790:0050
2778:0030
2772:0020
2766:0010
2748:0410
2742:0400
2733:0390
2712:0388
2691:0386
2670:0385
2652:0380
2649:;i++
2646:0370
2643:0360
2628:0350
2610:0330
2589:0320
2583:0290
2577:0280
2571:0270
2562:0260
2544:0245
2541:0240
2526:0230
2520:0170
2517:0160
2508:0150
2490:0147
2484:0120
2478:0100
2472:0090
2466:0119
2451:0118
2445:0117
2439:0190
2436:0080
2427:0070
2409:0060
2403:0040
2385:0058
2364:0058
2346:0057
2328:0056
2307:0055
2304:#1.0
2295:0340
2292:#0.0
2283:0220
2271:load
2268:0050
2256:0030
2250:0020
2244:0010
2223:0410
2217:0400
2208:0390
2190:0380
2187:;i++
2184:0370
2181:0360
2166:0350
2148:0330
2127:0320
2121:0290
2115:0280
2109:0270
2100:0260
2082:0245
2079:0240
2064:0230
2058:0170
2055:0160
2046:0150
2028:0147
2022:0120
2016:0100
2010:0090
1992:0119
1974:0118
1953:0117
1932:0190
1929:0080
1920:0070
1902:0060
1896:0040
1893:#1.0
1884:0340
1881:#0.0
1872:0220
1860:load
1857:0050
1845:0030
1839:0020
1833:0010
1812:0260
1806:0255
1788:0245
1785:0240
1770:0230
1764:0170
1761:0160
1752:0150
1734:0147
1728:0145
1722:0120
1704:0119
1686:0118
1665:0117
1659:0115
1643:0260
1625:0255
1607:0245
1604:0240
1589:0230
1583:0210
1577:0170
1574:0160
1565:0150
1547:0145
1541:0120
1523:0118
1502:0117
1487:0115
1470:0260
1452:0255
1446:0250
1443:0240
1428:0230
1410:0210
1404:0200
1398:0170
1395:0160
1386:0150
1368:0145
1362:0140
1356:0120
1335:0117
1320:0115
1314:0110
1300:0410
1294:0400
1285:0390
1267:0380
1264:;i++
1261:0370
1258:0360
1243:0350
1225:0330
1204:0320
1198:0290
1192:0280
1186:0270
1177:0260
1159:0250
1156:0240
1141:0230
1123:0210
1102:0200
1096:0170
1093:0160
1084:0150
1066:0140
1060:0120
1048:0110
1042:0100
1036:0090
1030:0310
1009:0190
1006:0080
997:0070
979:0060
973:0040
970:#1.0
961:0340
958:#0.0
949:0220
943:0300
937:0180
931:0130
919:load
916:0050
904:0030
898:0020
892:0010
862:0410
856:0400
847:0390
829:0380
823:0370
820:0360
805:0350
802:#1.0
793:0340
775:0330
757:0320
739:0310
724:load
721:0300
715:0290
709:0280
703:0270
694:0260
676:0250
673:0240
658:0230
655:#0.0
646:0220
628:0210
610:0200
589:0190
577:load
574:0180
568:0170
565:0160
556:0150
541:0140
526:load
523:0130
517:0120
505:0110
499:0100
493:0090
490:0080
481:0070
466:0060
451:load
448:0050
442:0040
430:0030
424:0020
418:0010
355:<
313:<
219:<
125:<
5081:SSA
4851:doi
4632:...
4593:...
4587:...
4544:...
4520:...
4502:...
4378:or
4324:r50
4318:r15
4312:r15
4303:r30
4297:r22
4291:r22
4282:r30
4276:r40
4270:r40
4237:fr4
4195:r10
4189:r10
4174:fr3
4153:bge
4144:r22
4138:r10
4135:cmp
4108:r40
4102:r10
4090:bge
4081:r60
4075:r40
4072:cmp
4051:r30
4039:r60
4033:005
4024:r49
4018:r50
4012:005
3997:r49
3991:005
3982:r15
3976:005
3967:005
3952:r22
3928:r30
3916:r40
3898:fr4
3886:fr3
3812:r50
3806:r15
3800:r15
3791:r30
3785:r22
3779:r22
3770:r30
3764:r40
3758:r40
3698:fr4
3644:r10
3638:r10
3623:fr3
3602:bge
3593:r22
3587:r10
3584:cmp
3557:r40
3551:r10
3539:bge
3521:cmp
3503:r49
3497:r50
3491:005
3476:r49
3470:005
3461:r14
3455:r15
3449:005
3431:r14
3425:005
3416:r20
3410:r22
3389:r20
3371:r30
3353:r40
3320:fr4
3308:fr3
3231:r30
3225:r22
3219:r22
3210:r30
3204:r40
3198:r40
3138:fr4
3123:r14
3117:r15
3096:r14
3057:r10
3051:r10
3036:fr3
3015:bge
3006:r22
3000:r10
2997:cmp
2970:r40
2964:r10
2952:bge
2934:cmp
2916:r20
2910:r22
2889:r20
2871:r30
2853:r40
2820:fr4
2808:fr3
2727:r30
2721:r22
2715:r22
2706:r30
2700:r40
2694:r40
2634:fr4
2619:r14
2613:r15
2592:r14
2553:r10
2547:r10
2532:fr3
2511:bge
2502:r22
2496:r10
2493:cmp
2460:r40
2454:r10
2430:bge
2412:cmp
2394:r20
2388:r22
2367:r20
2349:r30
2331:r40
2298:fr4
2286:fr3
2172:fr4
2157:r14
2151:r15
2130:r14
2091:r10
2085:r10
2070:fr3
2049:bge
2040:r22
2034:r10
2031:cmp
2001:r20
1995:r22
1977:r10
1956:r20
1923:bge
1905:cmp
1887:fr4
1875:fr3
1797:r10
1791:r10
1776:fr3
1755:bge
1746:r22
1740:r10
1737:cmp
1713:r20
1707:r22
1689:r10
1668:r20
1616:r10
1610:r10
1595:fr3
1568:bge
1559:r20
1550:cmp
1526:r10
1505:r20
1434:fr3
1413:r10
1389:bge
1380:r20
1371:cmp
1338:r20
1249:fr4
1234:r14
1228:r15
1207:r14
1147:fr3
1126:r10
1087:bge
1069:cmp
1000:bge
982:cmp
964:fr4
952:fr3
859:; }
811:fr4
796:fr4
784:r14
778:r15
766:r13
760:r14
754:r12
742:r13
727:r12
706:; }
664:fr3
649:fr3
631:r10
559:bge
544:cmp
502:; {
484:bge
469:cmp
427:; {
397:1.0
382:0.0
334:for
292:for
198:for
104:for
19:In
5289::
4859:,
4847:20
4845:,
4816:;
4787:;
4783:;
4724:-2
4716:-1
4697:.
4629:))
4541:))
4511:**
4388:π.
4333:br
4207:br
4045:r2
4009:#1
4003:r2
3958:r2
3934:r2
3874:r2
3821:br
3749:r2
3743:r8
3737:r8
3731:#1
3725:r1
3719:r1
3656:br
3530:r2
3524:r1
3488:#1
3482:r2
3443:r1
3437:r8
3401:r2
3395:r8
3377:r2
3359:r8
3344:r2
3338:r1
3332:r8
3296:r2
3281:r1
3240:br
3189:r2
3183:r8
3177:r8
3171:#1
3165:r1
3159:r1
3108:r1
3102:r8
3069:br
2943:r2
2937:r1
2901:r2
2895:r8
2877:r2
2859:r8
2844:r2
2838:r1
2832:r8
2796:r2
2781:r1
2736:br
2685:r2
2679:r8
2673:r8
2667:#1
2661:r1
2655:r1
2604:r1
2598:r8
2565:br
2421:r2
2415:r1
2379:r2
2373:r8
2355:r2
2337:r8
2322:r2
2316:r1
2310:r8
2274:r2
2259:r1
2211:br
2205:#1
2199:r1
2193:r1
2142:r1
2136:r8
2103:br
1983:r8
1968:r2
1962:r8
1947:r2
1941:r1
1935:r8
1914:r2
1908:r1
1863:r2
1848:r1
1815:br
1695:r8
1680:r2
1674:r8
1646:br
1634:r9
1628:r9
1553:r9
1532:r8
1517:r2
1511:r8
1496:r8
1490:r9
1473:br
1461:r9
1455:r9
1419:r9
1374:r9
1350:r2
1344:r8
1329:r8
1323:r9
1288:br
1282:#1
1276:r1
1270:r1
1219:r1
1213:r8
1180:br
1168:r3
1162:r3
1132:r9
1117:r3
1111:r8
1105:r9
1078:r2
1072:r3
1051:r3
1024:r2
1018:r1
1012:r8
991:r2
985:r1
922:r2
907:r1
850:br
844:#1
838:r1
832:r1
772:r1
748:r1
697:br
685:r3
679:r3
637:r9
625:r3
619:r8
613:r9
604:r7
598:r1
592:r8
580:r7
553:r4
547:r3
529:r4
508:r3
478:r2
472:r1
454:r2
433:r1
367:++
325:++
287:.
231:++
137:++
23:,
4915:e
4908:t
4901:v
4853::
4747:.
4639:′
4626:z
4623:*
4620:3
4617:(
4614:)
4611:1
4608:+
4605:x
4602:(
4596:(
4590:z
4584:=
4581:z
4578:x
4569:1
4566:x
4560:=
4557:x
4554:f
4538:1
4535:+
4532:x
4529:(
4526:f
4523:(
4517:)
4514:x
4508:3
4505:(
4499:=
4496:x
4493:f
4342:}
4321:+
4315:=
4300:+
4294:=
4279:+
4273:=
4243:A
4240:,
4216:}
4198:+
4192:=
4180:A
4177:,
4141:,
4123:{
4105:=
4078:,
4048:*
4042:=
4036:D
4027:*
4021:=
4015:D
4006:+
4000:=
3994:C
3985:=
3979:B
3970:A
3961:*
3955:=
3937:*
3931:=
3919:=
3901:=
3889:=
3880:n
3877:,
3859:{
3830:}
3809:+
3803:=
3788:+
3782:=
3767:+
3761:=
3746:+
3740:=
3728:+
3722:=
3704:A
3701:,
3665:}
3647:+
3641:=
3629:A
3626:,
3590:,
3572:{
3554:=
3527:,
3506:*
3500:=
3494:D
3485:+
3479:=
3473:C
3464:*
3458:=
3452:B
3440:+
3434:=
3428:A
3419:*
3413:=
3398:+
3392:=
3380:*
3374:=
3362:*
3356:=
3341:*
3335:=
3323:=
3311:=
3302:n
3299:,
3284:=
3275:{
3249:}
3228:+
3222:=
3207:+
3201:=
3186:+
3180:=
3168:+
3162:=
3144:A
3141:,
3126:*
3120:=
3105:+
3099:=
3078:}
3060:+
3054:=
3042:A
3039:,
3003:,
2985:{
2967:=
2940:,
2919:*
2913:=
2898:+
2892:=
2880:*
2874:=
2862:*
2856:=
2841:*
2835:=
2823:=
2811:=
2802:n
2799:,
2784:=
2775:{
2745:}
2724:+
2718:=
2703:+
2697:=
2682:+
2676:=
2664:+
2658:=
2640:A
2637:,
2622:*
2616:=
2601:+
2595:=
2574:}
2556:+
2550:=
2538:A
2535:,
2499:,
2481:{
2457:=
2418:,
2397:*
2391:=
2376:+
2370:=
2358:*
2352:=
2340:*
2334:=
2319:*
2313:=
2301:=
2289:=
2280:n
2277:,
2262:=
2253:{
2220:}
2202:+
2196:=
2178:A
2175:,
2160:*
2154:=
2139:+
2133:=
2112:}
2094:+
2088:=
2076:A
2073:,
2037:,
2019:{
2004:*
1998:=
1986:*
1980:=
1965:+
1959:=
1944:*
1938:=
1911:,
1890:=
1878:=
1869:n
1866:,
1851:=
1842:{
1800:+
1794:=
1782:A
1779:,
1743:,
1716:*
1710:=
1698:*
1692:=
1677:+
1671:=
1637:+
1631:=
1619:+
1613:=
1601:A
1598:,
1556:,
1535:*
1529:=
1514:+
1508:=
1493:=
1464:+
1458:=
1440:A
1437:,
1422:*
1416:=
1377:,
1347:+
1341:=
1326:=
1297:}
1279:+
1273:=
1255:A
1252:,
1237:*
1231:=
1216:+
1210:=
1189:}
1171:+
1165:=
1153:A
1150:,
1135:*
1129:=
1114:+
1108:=
1075:,
1054:=
1045:{
1021:*
1015:=
988:,
967:=
955:=
928:n
925:,
910:=
901:{
872:A
841:+
835:=
817:A
814:,
799:=
787:*
781:=
769:+
763:=
751:*
745:=
733:n
730:,
688:+
682:=
670:A
667:,
652:=
640:*
634:=
622:+
616:=
601:*
595:=
586:n
583:,
550:,
535:n
532:,
511:=
475:,
460:n
457:,
436:=
403:}
400:;
394:=
391:A
388:}
385:;
379:=
376:A
373:{
370:)
364:j
361:;
358:n
352:j
349:;
346:0
343:=
340:j
337:(
331:{
328:)
322:i
319:;
316:n
310:i
307:;
304:0
301:=
298:i
295:(
270:}
267:;
264:c
261:+
258:k
255:=
252:k
249:;
246:k
243:=
240:y
237:{
234:)
228:i
225:;
222:N
216:i
213:;
210:0
207:=
204:i
201:(
195:;
192:0
189:=
186:k
183:;
180:7
177:=
174:c
164:}
161:;
158:i
155:*
152:c
149:=
146:y
143:{
140:)
134:i
131:;
128:N
122:i
119:;
116:0
113:=
110:i
107:(
101:;
98:7
95:=
92:c
86:i
82:c
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.