1Target Independent Opportunities: 2 3//===---------------------------------------------------------------------===// 4 5We should recognized various "overflow detection" idioms and translate them into 6llvm.uadd.with.overflow and similar intrinsics. Here is a multiply idiom: 7 8unsigned int mul(unsigned int a,unsigned int b) { 9 if ((unsigned long long)a*b>0xffffffff) 10 exit(0); 11 return a*b; 12} 13 14The legalization code for mul-with-overflow needs to be made more robust before 15this can be implemented though. 16 17//===---------------------------------------------------------------------===// 18 19Get the C front-end to expand hypot(x,y) -> llvm.sqrt(x*x+y*y) when errno and 20precision don't matter (ffastmath). Misc/mandel will like this. :) This isn't 21safe in general, even on darwin. See the libm implementation of hypot for 22examples (which special case when x/y are exactly zero to get signed zeros etc 23right). 24 25//===---------------------------------------------------------------------===// 26 27On targets with expensive 64-bit multiply, we could LSR this: 28 29for (i = ...; ++i) { 30 x = 1ULL << i; 31 32into: 33 long long tmp = 1; 34 for (i = ...; ++i, tmp+=tmp) 35 x = tmp; 36 37This would be a win on ppc32, but not x86 or ppc64. 38 39//===---------------------------------------------------------------------===// 40 41Shrink: (setlt (loadi32 P), 0) -> (setlt (loadi8 Phi), 0) 42 43//===---------------------------------------------------------------------===// 44 45Reassociate should turn things like: 46 47int factorial(int X) { 48 return X*X*X*X*X*X*X*X; 49} 50 51into llvm.powi calls, allowing the code generator to produce balanced 52multiplication trees. 53 54First, the intrinsic needs to be extended to support integers, and second the 55code generator needs to be enhanced to lower these to multiplication trees. 56 57//===---------------------------------------------------------------------===// 58 59Interesting? testcase for add/shift/mul reassoc: 60 61int bar(int x, int y) { 62 return x*x*x+y+x*x*x*x*x*y*y*y*y; 63} 64int foo(int z, int n) { 65 return bar(z, n) + bar(2*z, 2*n); 66} 67 68This is blocked on not handling X*X*X -> powi(X, 3) (see note above). The issue 69is that we end up getting t = 2*X s = t*t and don't turn this into 4*X*X, 70which is the same number of multiplies and is canonical, because the 2*X has 71multiple uses. Here's a simple example: 72 73define i32 @test15(i32 %X1) { 74 %B = mul i32 %X1, 47 ; X1*47 75 %C = mul i32 %B, %B 76 ret i32 %C 77} 78 79 80//===---------------------------------------------------------------------===// 81 82Reassociate should handle the example in GCC PR16157: 83 84extern int a0, a1, a2, a3, a4; extern int b0, b1, b2, b3, b4; 85void f () { /* this can be optimized to four additions... */ 86 b4 = a4 + a3 + a2 + a1 + a0; 87 b3 = a3 + a2 + a1 + a0; 88 b2 = a2 + a1 + a0; 89 b1 = a1 + a0; 90} 91 92This requires reassociating to forms of expressions that are already available, 93something that reassoc doesn't think about yet. 94 95 96//===---------------------------------------------------------------------===// 97 98These two functions should generate the same code on big-endian systems: 99 100int g(int *j,int *l) { return memcmp(j,l,4); } 101int h(int *j, int *l) { return *j - *l; } 102 103this could be done in SelectionDAGISel.cpp, along with other special cases, 104for 1,2,4,8 bytes. 105 106//===---------------------------------------------------------------------===// 107 108It would be nice to revert this patch: 109http://lists.llvm.org/pipermail/llvm-commits/Week-of-Mon-20060213/031986.html 110 111And teach the dag combiner enough to simplify the code expanded before 112legalize. It seems plausible that this knowledge would let it simplify other 113stuff too. 114 115//===---------------------------------------------------------------------===// 116 117For vector types, DataLayout.cpp::getTypeInfo() returns alignment that is equal 118to the type size. It works but can be overly conservative as the alignment of 119specific vector types are target dependent. 120 121//===---------------------------------------------------------------------===// 122 123We should produce an unaligned load from code like this: 124 125v4sf example(float *P) { 126 return (v4sf){P[0], P[1], P[2], P[3] }; 127} 128 129//===---------------------------------------------------------------------===// 130 131Add support for conditional increments, and other related patterns. Instead 132of: 133 134 movl 136(%esp), %eax 135 cmpl $0, %eax 136 je LBB16_2 #cond_next 137LBB16_1: #cond_true 138 incl _foo 139LBB16_2: #cond_next 140 141emit: 142 movl _foo, %eax 143 cmpl $1, %edi 144 sbbl $-1, %eax 145 movl %eax, _foo 146 147//===---------------------------------------------------------------------===// 148 149Combine: a = sin(x), b = cos(x) into a,b = sincos(x). 150 151Expand these to calls of sin/cos and stores: 152 double sincos(double x, double *sin, double *cos); 153 float sincosf(float x, float *sin, float *cos); 154 long double sincosl(long double x, long double *sin, long double *cos); 155 156Doing so could allow SROA of the destination pointers. See also: 157http://gcc.gnu.org/bugzilla/show_bug.cgi?id=17687 158 159This is now easily doable with MRVs. We could even make an intrinsic for this 160if anyone cared enough about sincos. 161 162//===---------------------------------------------------------------------===// 163 164quantum_sigma_x in 462.libquantum contains the following loop: 165 166 for(i=0; i<reg->size; i++) 167 { 168 /* Flip the target bit of each basis state */ 169 reg->node[i].state ^= ((MAX_UNSIGNED) 1 << target); 170 } 171 172Where MAX_UNSIGNED/state is a 64-bit int. On a 32-bit platform it would be just 173so cool to turn it into something like: 174 175 long long Res = ((MAX_UNSIGNED) 1 << target); 176 if (target < 32) { 177 for(i=0; i<reg->size; i++) 178 reg->node[i].state ^= Res & 0xFFFFFFFFULL; 179 } else { 180 for(i=0; i<reg->size; i++) 181 reg->node[i].state ^= Res & 0xFFFFFFFF00000000ULL 182 } 183 184... which would only do one 32-bit XOR per loop iteration instead of two. 185 186It would also be nice to recognize the reg->size doesn't alias reg->node[i], but 187this requires TBAA. 188 189//===---------------------------------------------------------------------===// 190 191This isn't recognized as bswap by instcombine (yes, it really is bswap): 192 193unsigned long reverse(unsigned v) { 194 unsigned t; 195 t = v ^ ((v << 16) | (v >> 16)); 196 t &= ~0xff0000; 197 v = (v << 24) | (v >> 8); 198 return v ^ (t >> 8); 199} 200 201//===---------------------------------------------------------------------===// 202 203[LOOP DELETION] 204 205We don't delete this output free loop, because trip count analysis doesn't 206realize that it is finite (if it were infinite, it would be undefined). Not 207having this blocks Loop Idiom from matching strlen and friends. 208 209void foo(char *C) { 210 int x = 0; 211 while (*C) 212 ++x,++C; 213} 214 215//===---------------------------------------------------------------------===// 216 217[LOOP RECOGNITION] 218 219These idioms should be recognized as popcount (see PR1488): 220 221unsigned countbits_slow(unsigned v) { 222 unsigned c; 223 for (c = 0; v; v >>= 1) 224 c += v & 1; 225 return c; 226} 227 228unsigned int popcount(unsigned int input) { 229 unsigned int count = 0; 230 for (unsigned int i = 0; i < 4 * 8; i++) 231 count += (input >> i) & i; 232 return count; 233} 234 235This should be recognized as CLZ: rdar://8459039 236 237unsigned clz_a(unsigned a) { 238 int i; 239 for (i=0;i<32;i++) 240 if (a & (1<<(31-i))) 241 return i; 242 return 32; 243} 244 245This sort of thing should be added to the loop idiom pass. 246 247//===---------------------------------------------------------------------===// 248 249These should turn into single 16-bit (unaligned?) loads on little/big endian 250processors. 251 252unsigned short read_16_le(const unsigned char *adr) { 253 return adr[0] | (adr[1] << 8); 254} 255unsigned short read_16_be(const unsigned char *adr) { 256 return (adr[0] << 8) | adr[1]; 257} 258 259//===---------------------------------------------------------------------===// 260 261-instcombine should handle this transform: 262 icmp pred (sdiv X / C1 ), C2 263when X, C1, and C2 are unsigned. Similarly for udiv and signed operands. 264 265Currently InstCombine avoids this transform but will do it when the signs of 266the operands and the sign of the divide match. See the FIXME in 267InstructionCombining.cpp in the visitSetCondInst method after the switch case 268for Instruction::UDiv (around line 4447) for more details. 269 270The SingleSource/Benchmarks/Shootout-C++/hash and hash2 tests have examples of 271this construct. 272 273//===---------------------------------------------------------------------===// 274 275[LOOP OPTIMIZATION] 276 277SingleSource/Benchmarks/Misc/dt.c shows several interesting optimization 278opportunities in its double_array_divs_variable function: it needs loop 279interchange, memory promotion (which LICM already does), vectorization and 280variable trip count loop unrolling (since it has a constant trip count). ICC 281apparently produces this very nice code with -ffast-math: 282 283..B1.70: # Preds ..B1.70 ..B1.69 284 mulpd %xmm0, %xmm1 #108.2 285 mulpd %xmm0, %xmm1 #108.2 286 mulpd %xmm0, %xmm1 #108.2 287 mulpd %xmm0, %xmm1 #108.2 288 addl $8, %edx # 289 cmpl $131072, %edx #108.2 290 jb ..B1.70 # Prob 99% #108.2 291 292It would be better to count down to zero, but this is a lot better than what we 293do. 294 295//===---------------------------------------------------------------------===// 296 297Consider: 298 299typedef unsigned U32; 300typedef unsigned long long U64; 301int test (U32 *inst, U64 *regs) { 302 U64 effective_addr2; 303 U32 temp = *inst; 304 int r1 = (temp >> 20) & 0xf; 305 int b2 = (temp >> 16) & 0xf; 306 effective_addr2 = temp & 0xfff; 307 if (b2) effective_addr2 += regs[b2]; 308 b2 = (temp >> 12) & 0xf; 309 if (b2) effective_addr2 += regs[b2]; 310 effective_addr2 &= regs[4]; 311 if ((effective_addr2 & 3) == 0) 312 return 1; 313 return 0; 314} 315 316Note that only the low 2 bits of effective_addr2 are used. On 32-bit systems, 317we don't eliminate the computation of the top half of effective_addr2 because 318we don't have whole-function selection dags. On x86, this means we use one 319extra register for the function when effective_addr2 is declared as U64 than 320when it is declared U32. 321 322PHI Slicing could be extended to do this. 323 324//===---------------------------------------------------------------------===// 325 326Tail call elim should be more aggressive, checking to see if the call is 327followed by an uncond branch to an exit block. 328 329; This testcase is due to tail-duplication not wanting to copy the return 330; instruction into the terminating blocks because there was other code 331; optimized out of the function after the taildup happened. 332; RUN: llvm-as < %s | opt -tailcallelim | llvm-dis | not grep call 333 334define i32 @t4(i32 %a) { 335entry: 336 %tmp.1 = and i32 %a, 1 ; <i32> [#uses=1] 337 %tmp.2 = icmp ne i32 %tmp.1, 0 ; <i1> [#uses=1] 338 br i1 %tmp.2, label %then.0, label %else.0 339 340then.0: ; preds = %entry 341 %tmp.5 = add i32 %a, -1 ; <i32> [#uses=1] 342 %tmp.3 = call i32 @t4( i32 %tmp.5 ) ; <i32> [#uses=1] 343 br label %return 344 345else.0: ; preds = %entry 346 %tmp.7 = icmp ne i32 %a, 0 ; <i1> [#uses=1] 347 br i1 %tmp.7, label %then.1, label %return 348 349then.1: ; preds = %else.0 350 %tmp.11 = add i32 %a, -2 ; <i32> [#uses=1] 351 %tmp.9 = call i32 @t4( i32 %tmp.11 ) ; <i32> [#uses=1] 352 br label %return 353 354return: ; preds = %then.1, %else.0, %then.0 355 %result.0 = phi i32 [ 0, %else.0 ], [ %tmp.3, %then.0 ], 356 [ %tmp.9, %then.1 ] 357 ret i32 %result.0 358} 359 360//===---------------------------------------------------------------------===// 361 362Tail recursion elimination should handle: 363 364int pow2m1(int n) { 365 if (n == 0) 366 return 0; 367 return 2 * pow2m1 (n - 1) + 1; 368} 369 370Also, multiplies can be turned into SHL's, so they should be handled as if 371they were associative. "return foo() << 1" can be tail recursion eliminated. 372 373//===---------------------------------------------------------------------===// 374 375Argument promotion should promote arguments for recursive functions, like 376this: 377 378; RUN: llvm-as < %s | opt -argpromotion | llvm-dis | grep x.val 379 380define internal i32 @foo(i32* %x) { 381entry: 382 %tmp = load i32* %x ; <i32> [#uses=0] 383 %tmp.foo = call i32 @foo( i32* %x ) ; <i32> [#uses=1] 384 ret i32 %tmp.foo 385} 386 387define i32 @bar(i32* %x) { 388entry: 389 %tmp3 = call i32 @foo( i32* %x ) ; <i32> [#uses=1] 390 ret i32 %tmp3 391} 392 393//===---------------------------------------------------------------------===// 394 395We should investigate an instruction sinking pass. Consider this silly 396example in pic mode: 397 398#include <assert.h> 399void foo(int x) { 400 assert(x); 401 //... 402} 403 404we compile this to: 405_foo: 406 subl $28, %esp 407 call "L1$pb" 408"L1$pb": 409 popl %eax 410 cmpl $0, 32(%esp) 411 je LBB1_2 # cond_true 412LBB1_1: # return 413 # ... 414 addl $28, %esp 415 ret 416LBB1_2: # cond_true 417... 418 419The PIC base computation (call+popl) is only used on one path through the 420code, but is currently always computed in the entry block. It would be 421better to sink the picbase computation down into the block for the 422assertion, as it is the only one that uses it. This happens for a lot of 423code with early outs. 424 425Another example is loads of arguments, which are usually emitted into the 426entry block on targets like x86. If not used in all paths through a 427function, they should be sunk into the ones that do. 428 429In this case, whole-function-isel would also handle this. 430 431//===---------------------------------------------------------------------===// 432 433Investigate lowering of sparse switch statements into perfect hash tables: 434http://burtleburtle.net/bob/hash/perfect.html 435 436//===---------------------------------------------------------------------===// 437 438We should turn things like "load+fabs+store" and "load+fneg+store" into the 439corresponding integer operations. On a yonah, this loop: 440 441double a[256]; 442void foo() { 443 int i, b; 444 for (b = 0; b < 10000000; b++) 445 for (i = 0; i < 256; i++) 446 a[i] = -a[i]; 447} 448 449is twice as slow as this loop: 450 451long long a[256]; 452void foo() { 453 int i, b; 454 for (b = 0; b < 10000000; b++) 455 for (i = 0; i < 256; i++) 456 a[i] ^= (1ULL << 63); 457} 458 459and I suspect other processors are similar. On X86 in particular this is a 460big win because doing this with integers allows the use of read/modify/write 461instructions. 462 463//===---------------------------------------------------------------------===// 464 465DAG Combiner should try to combine small loads into larger loads when 466profitable. For example, we compile this C++ example: 467 468struct THotKey { short Key; bool Control; bool Shift; bool Alt; }; 469extern THotKey m_HotKey; 470THotKey GetHotKey () { return m_HotKey; } 471 472into (-m64 -O3 -fno-exceptions -static -fomit-frame-pointer): 473 474__Z9GetHotKeyv: ## @_Z9GetHotKeyv 475 movq _m_HotKey@GOTPCREL(%rip), %rax 476 movzwl (%rax), %ecx 477 movzbl 2(%rax), %edx 478 shlq $16, %rdx 479 orq %rcx, %rdx 480 movzbl 3(%rax), %ecx 481 shlq $24, %rcx 482 orq %rdx, %rcx 483 movzbl 4(%rax), %eax 484 shlq $32, %rax 485 orq %rcx, %rax 486 ret 487 488//===---------------------------------------------------------------------===// 489 490We should add an FRINT node to the DAG to model targets that have legal 491implementations of ceil/floor/rint. 492 493//===---------------------------------------------------------------------===// 494 495Consider: 496 497int test() { 498 long long input[8] = {1,0,1,0,1,0,1,0}; 499 foo(input); 500} 501 502Clang compiles this into: 503 504 call void @llvm.memset.p0i8.i64(i8* %tmp, i8 0, i64 64, i32 16, i1 false) 505 %0 = getelementptr [8 x i64]* %input, i64 0, i64 0 506 store i64 1, i64* %0, align 16 507 %1 = getelementptr [8 x i64]* %input, i64 0, i64 2 508 store i64 1, i64* %1, align 16 509 %2 = getelementptr [8 x i64]* %input, i64 0, i64 4 510 store i64 1, i64* %2, align 16 511 %3 = getelementptr [8 x i64]* %input, i64 0, i64 6 512 store i64 1, i64* %3, align 16 513 514Which gets codegen'd into: 515 516 pxor %xmm0, %xmm0 517 movaps %xmm0, -16(%rbp) 518 movaps %xmm0, -32(%rbp) 519 movaps %xmm0, -48(%rbp) 520 movaps %xmm0, -64(%rbp) 521 movq $1, -64(%rbp) 522 movq $1, -48(%rbp) 523 movq $1, -32(%rbp) 524 movq $1, -16(%rbp) 525 526It would be better to have 4 movq's of 0 instead of the movaps's. 527 528//===---------------------------------------------------------------------===// 529 530http://llvm.org/PR717: 531 532The following code should compile into "ret int undef". Instead, LLVM 533produces "ret int 0": 534 535int f() { 536 int x = 4; 537 int y; 538 if (x == 3) y = 0; 539 return y; 540} 541 542//===---------------------------------------------------------------------===// 543 544The loop unroller should partially unroll loops (instead of peeling them) 545when code growth isn't too bad and when an unroll count allows simplification 546of some code within the loop. One trivial example is: 547 548#include <stdio.h> 549int main() { 550 int nRet = 17; 551 int nLoop; 552 for ( nLoop = 0; nLoop < 1000; nLoop++ ) { 553 if ( nLoop & 1 ) 554 nRet += 2; 555 else 556 nRet -= 1; 557 } 558 return nRet; 559} 560 561Unrolling by 2 would eliminate the '&1' in both copies, leading to a net 562reduction in code size. The resultant code would then also be suitable for 563exit value computation. 564 565//===---------------------------------------------------------------------===// 566 567We miss a bunch of rotate opportunities on various targets, including ppc, x86, 568etc. On X86, we miss a bunch of 'rotate by variable' cases because the rotate 569matching code in dag combine doesn't look through truncates aggressively 570enough. Here are some testcases reduces from GCC PR17886: 571 572unsigned long long f5(unsigned long long x, unsigned long long y) { 573 return (x << 8) | ((y >> 48) & 0xffull); 574} 575unsigned long long f6(unsigned long long x, unsigned long long y, int z) { 576 switch(z) { 577 case 1: 578 return (x << 8) | ((y >> 48) & 0xffull); 579 case 2: 580 return (x << 16) | ((y >> 40) & 0xffffull); 581 case 3: 582 return (x << 24) | ((y >> 32) & 0xffffffull); 583 case 4: 584 return (x << 32) | ((y >> 24) & 0xffffffffull); 585 default: 586 return (x << 40) | ((y >> 16) & 0xffffffffffull); 587 } 588} 589 590//===---------------------------------------------------------------------===// 591 592This (and similar related idioms): 593 594unsigned int foo(unsigned char i) { 595 return i | (i<<8) | (i<<16) | (i<<24); 596} 597 598compiles into: 599 600define i32 @foo(i8 zeroext %i) nounwind readnone ssp noredzone { 601entry: 602 %conv = zext i8 %i to i32 603 %shl = shl i32 %conv, 8 604 %shl5 = shl i32 %conv, 16 605 %shl9 = shl i32 %conv, 24 606 %or = or i32 %shl9, %conv 607 %or6 = or i32 %or, %shl5 608 %or10 = or i32 %or6, %shl 609 ret i32 %or10 610} 611 612it would be better as: 613 614unsigned int bar(unsigned char i) { 615 unsigned int j=i | (i << 8); 616 return j | (j<<16); 617} 618 619aka: 620 621define i32 @bar(i8 zeroext %i) nounwind readnone ssp noredzone { 622entry: 623 %conv = zext i8 %i to i32 624 %shl = shl i32 %conv, 8 625 %or = or i32 %shl, %conv 626 %shl5 = shl i32 %or, 16 627 %or6 = or i32 %shl5, %or 628 ret i32 %or6 629} 630 631or even i*0x01010101, depending on the speed of the multiplier. The best way to 632handle this is to canonicalize it to a multiply in IR and have codegen handle 633lowering multiplies to shifts on cpus where shifts are faster. 634 635//===---------------------------------------------------------------------===// 636 637We do a number of simplifications in simplify libcalls to strength reduce 638standard library functions, but we don't currently merge them together. For 639example, it is useful to merge memcpy(a,b,strlen(b)) -> strcpy. This can only 640be done safely if "b" isn't modified between the strlen and memcpy of course. 641 642//===---------------------------------------------------------------------===// 643 644We compile this program: (from GCC PR11680) 645http://gcc.gnu.org/bugzilla/attachment.cgi?id=4487 646 647Into code that runs the same speed in fast/slow modes, but both modes run 2x 648slower than when compile with GCC (either 4.0 or 4.2): 649 650$ llvm-g++ perf.cpp -O3 -fno-exceptions 651$ time ./a.out fast 6521.821u 0.003s 0:01.82 100.0% 0+0k 0+0io 0pf+0w 653 654$ g++ perf.cpp -O3 -fno-exceptions 655$ time ./a.out fast 6560.821u 0.001s 0:00.82 100.0% 0+0k 0+0io 0pf+0w 657 658It looks like we are making the same inlining decisions, so this may be raw 659codegen badness or something else (haven't investigated). 660 661//===---------------------------------------------------------------------===// 662 663Divisibility by constant can be simplified (according to GCC PR12849) from 664being a mulhi to being a mul lo (cheaper). Testcase: 665 666void bar(unsigned n) { 667 if (n % 3 == 0) 668 true(); 669} 670 671This is equivalent to the following, where 2863311531 is the multiplicative 672inverse of 3, and 1431655766 is ((2^32)-1)/3+1: 673void bar(unsigned n) { 674 if (n * 2863311531U < 1431655766U) 675 true(); 676} 677 678The same transformation can work with an even modulo with the addition of a 679rotate: rotate the result of the multiply to the right by the number of bits 680which need to be zero for the condition to be true, and shrink the compare RHS 681by the same amount. Unless the target supports rotates, though, that 682transformation probably isn't worthwhile. 683 684The transformation can also easily be made to work with non-zero equality 685comparisons: just transform, for example, "n % 3 == 1" to "(n-1) % 3 == 0". 686 687//===---------------------------------------------------------------------===// 688 689Better mod/ref analysis for scanf would allow us to eliminate the vtable and a 690bunch of other stuff from this example (see PR1604): 691 692#include <cstdio> 693struct test { 694 int val; 695 virtual ~test() {} 696}; 697 698int main() { 699 test t; 700 std::scanf("%d", &t.val); 701 std::printf("%d\n", t.val); 702} 703 704//===---------------------------------------------------------------------===// 705 706These functions perform the same computation, but produce different assembly. 707 708define i8 @select(i8 %x) readnone nounwind { 709 %A = icmp ult i8 %x, 250 710 %B = select i1 %A, i8 0, i8 1 711 ret i8 %B 712} 713 714define i8 @addshr(i8 %x) readnone nounwind { 715 %A = zext i8 %x to i9 716 %B = add i9 %A, 6 ;; 256 - 250 == 6 717 %C = lshr i9 %B, 8 718 %D = trunc i9 %C to i8 719 ret i8 %D 720} 721 722//===---------------------------------------------------------------------===// 723 724From gcc bug 24696: 725int 726f (unsigned long a, unsigned long b, unsigned long c) 727{ 728 return ((a & (c - 1)) != 0) || ((b & (c - 1)) != 0); 729} 730int 731f (unsigned long a, unsigned long b, unsigned long c) 732{ 733 return ((a & (c - 1)) != 0) | ((b & (c - 1)) != 0); 734} 735Both should combine to ((a|b) & (c-1)) != 0. Currently not optimized with 736"clang -emit-llvm-bc | opt -O3". 737 738//===---------------------------------------------------------------------===// 739 740From GCC Bug 20192: 741#define PMD_MASK (~((1UL << 23) - 1)) 742void clear_pmd_range(unsigned long start, unsigned long end) 743{ 744 if (!(start & ~PMD_MASK) && !(end & ~PMD_MASK)) 745 f(); 746} 747The expression should optimize to something like 748"!((start|end)&~PMD_MASK). Currently not optimized with "clang 749-emit-llvm-bc | opt -O3". 750 751//===---------------------------------------------------------------------===// 752 753unsigned int f(unsigned int i, unsigned int n) {++i; if (i == n) ++i; return 754i;} 755unsigned int f2(unsigned int i, unsigned int n) {++i; i += i == n; return i;} 756These should combine to the same thing. Currently, the first function 757produces better code on X86. 758 759//===---------------------------------------------------------------------===// 760 761From GCC Bug 15784: 762#define abs(x) x>0?x:-x 763int f(int x, int y) 764{ 765 return (abs(x)) >= 0; 766} 767This should optimize to x == INT_MIN. (With -fwrapv.) Currently not 768optimized with "clang -emit-llvm-bc | opt -O3". 769 770//===---------------------------------------------------------------------===// 771 772From GCC Bug 14753: 773void 774rotate_cst (unsigned int a) 775{ 776 a = (a << 10) | (a >> 22); 777 if (a == 123) 778 bar (); 779} 780void 781minus_cst (unsigned int a) 782{ 783 unsigned int tem; 784 785 tem = 20 - a; 786 if (tem == 5) 787 bar (); 788} 789void 790mask_gt (unsigned int a) 791{ 792 /* This is equivalent to a > 15. */ 793 if ((a & ~7) > 8) 794 bar (); 795} 796void 797rshift_gt (unsigned int a) 798{ 799 /* This is equivalent to a > 23. */ 800 if ((a >> 2) > 5) 801 bar (); 802} 803 804All should simplify to a single comparison. All of these are 805currently not optimized with "clang -emit-llvm-bc | opt 806-O3". 807 808//===---------------------------------------------------------------------===// 809 810From GCC Bug 32605: 811int c(int* x) {return (char*)x+2 == (char*)x;} 812Should combine to 0. Currently not optimized with "clang 813-emit-llvm-bc | opt -O3" (although llc can optimize it). 814 815//===---------------------------------------------------------------------===// 816 817int a(unsigned b) {return ((b << 31) | (b << 30)) >> 31;} 818Should be combined to "((b >> 1) | b) & 1". Currently not optimized 819with "clang -emit-llvm-bc | opt -O3". 820 821//===---------------------------------------------------------------------===// 822 823unsigned a(unsigned x, unsigned y) { return x | (y & 1) | (y & 2);} 824Should combine to "x | (y & 3)". Currently not optimized with "clang 825-emit-llvm-bc | opt -O3". 826 827//===---------------------------------------------------------------------===// 828 829int a(int a, int b, int c) {return (~a & c) | ((c|a) & b);} 830Should fold to "(~a & c) | (a & b)". Currently not optimized with 831"clang -emit-llvm-bc | opt -O3". 832 833//===---------------------------------------------------------------------===// 834 835int a(int a,int b) {return (~(a|b))|a;} 836Should fold to "a|~b". Currently not optimized with "clang 837-emit-llvm-bc | opt -O3". 838 839//===---------------------------------------------------------------------===// 840 841int a(int a, int b) {return (a&&b) || (a&&!b);} 842Should fold to "a". Currently not optimized with "clang -emit-llvm-bc 843| opt -O3". 844 845//===---------------------------------------------------------------------===// 846 847int a(int a, int b, int c) {return (a&&b) || (!a&&c);} 848Should fold to "a ? b : c", or at least something sane. Currently not 849optimized with "clang -emit-llvm-bc | opt -O3". 850 851//===---------------------------------------------------------------------===// 852 853int a(int a, int b, int c) {return (a&&b) || (a&&c) || (a&&b&&c);} 854Should fold to a && (b || c). Currently not optimized with "clang 855-emit-llvm-bc | opt -O3". 856 857//===---------------------------------------------------------------------===// 858 859int a(int x) {return x | ((x & 8) ^ 8);} 860Should combine to x | 8. Currently not optimized with "clang 861-emit-llvm-bc | opt -O3". 862 863//===---------------------------------------------------------------------===// 864 865int a(int x) {return x ^ ((x & 8) ^ 8);} 866Should also combine to x | 8. Currently not optimized with "clang 867-emit-llvm-bc | opt -O3". 868 869//===---------------------------------------------------------------------===// 870 871int a(int x) {return ((x | -9) ^ 8) & x;} 872Should combine to x & -9. Currently not optimized with "clang 873-emit-llvm-bc | opt -O3". 874 875//===---------------------------------------------------------------------===// 876 877unsigned a(unsigned a) {return a * 0x11111111 >> 28 & 1;} 878Should combine to "a * 0x88888888 >> 31". Currently not optimized 879with "clang -emit-llvm-bc | opt -O3". 880 881//===---------------------------------------------------------------------===// 882 883unsigned a(char* x) {if ((*x & 32) == 0) return b();} 884There's an unnecessary zext in the generated code with "clang 885-emit-llvm-bc | opt -O3". 886 887//===---------------------------------------------------------------------===// 888 889unsigned a(unsigned long long x) {return 40 * (x >> 1);} 890Should combine to "20 * (((unsigned)x) & -2)". Currently not 891optimized with "clang -emit-llvm-bc | opt -O3". 892 893//===---------------------------------------------------------------------===// 894 895int g(int x) { return (x - 10) < 0; } 896Should combine to "x <= 9" (the sub has nsw). Currently not 897optimized with "clang -emit-llvm-bc | opt -O3". 898 899//===---------------------------------------------------------------------===// 900 901int g(int x) { return (x + 10) < 0; } 902Should combine to "x < -10" (the add has nsw). Currently not 903optimized with "clang -emit-llvm-bc | opt -O3". 904 905//===---------------------------------------------------------------------===// 906 907int f(int i, int j) { return i < j + 1; } 908int g(int i, int j) { return j > i - 1; } 909Should combine to "i <= j" (the add/sub has nsw). Currently not 910optimized with "clang -emit-llvm-bc | opt -O3". 911 912//===---------------------------------------------------------------------===// 913 914unsigned f(unsigned x) { return ((x & 7) + 1) & 15; } 915The & 15 part should be optimized away, it doesn't change the result. Currently 916not optimized with "clang -emit-llvm-bc | opt -O3". 917 918//===---------------------------------------------------------------------===// 919 920This was noticed in the entryblock for grokdeclarator in 403.gcc: 921 922 %tmp = icmp eq i32 %decl_context, 4 923 %decl_context_addr.0 = select i1 %tmp, i32 3, i32 %decl_context 924 %tmp1 = icmp eq i32 %decl_context_addr.0, 1 925 %decl_context_addr.1 = select i1 %tmp1, i32 0, i32 %decl_context_addr.0 926 927tmp1 should be simplified to something like: 928 (!tmp || decl_context == 1) 929 930This allows recursive simplifications, tmp1 is used all over the place in 931the function, e.g. by: 932 933 %tmp23 = icmp eq i32 %decl_context_addr.1, 0 ; <i1> [#uses=1] 934 %tmp24 = xor i1 %tmp1, true ; <i1> [#uses=1] 935 %or.cond8 = and i1 %tmp23, %tmp24 ; <i1> [#uses=1] 936 937later. 938 939//===---------------------------------------------------------------------===// 940 941[STORE SINKING] 942 943Store sinking: This code: 944 945void f (int n, int *cond, int *res) { 946 int i; 947 *res = 0; 948 for (i = 0; i < n; i++) 949 if (*cond) 950 *res ^= 234; /* (*) */ 951} 952 953On this function GVN hoists the fully redundant value of *res, but nothing 954moves the store out. This gives us this code: 955 956bb: ; preds = %bb2, %entry 957 %.rle = phi i32 [ 0, %entry ], [ %.rle6, %bb2 ] 958 %i.05 = phi i32 [ 0, %entry ], [ %indvar.next, %bb2 ] 959 %1 = load i32* %cond, align 4 960 %2 = icmp eq i32 %1, 0 961 br i1 %2, label %bb2, label %bb1 962 963bb1: ; preds = %bb 964 %3 = xor i32 %.rle, 234 965 store i32 %3, i32* %res, align 4 966 br label %bb2 967 968bb2: ; preds = %bb, %bb1 969 %.rle6 = phi i32 [ %3, %bb1 ], [ %.rle, %bb ] 970 %indvar.next = add i32 %i.05, 1 971 %exitcond = icmp eq i32 %indvar.next, %n 972 br i1 %exitcond, label %return, label %bb 973 974DSE should sink partially dead stores to get the store out of the loop. 975 976Here's another partial dead case: 977http://gcc.gnu.org/bugzilla/show_bug.cgi?id=12395 978 979//===---------------------------------------------------------------------===// 980 981Scalar PRE hoists the mul in the common block up to the else: 982 983int test (int a, int b, int c, int g) { 984 int d, e; 985 if (a) 986 d = b * c; 987 else 988 d = b - c; 989 e = b * c + g; 990 return d + e; 991} 992 993It would be better to do the mul once to reduce codesize above the if. 994This is GCC PR38204. 995 996 997//===---------------------------------------------------------------------===// 998This simple function from 179.art: 999 1000int winner, numf2s; 1001struct { double y; int reset; } *Y; 1002 1003void find_match() { 1004 int i; 1005 winner = 0; 1006 for (i=0;i<numf2s;i++) 1007 if (Y[i].y > Y[winner].y) 1008 winner =i; 1009} 1010 1011Compiles into (with clang TBAA): 1012 1013for.body: ; preds = %for.inc, %bb.nph 1014 %indvar = phi i64 [ 0, %bb.nph ], [ %indvar.next, %for.inc ] 1015 %i.01718 = phi i32 [ 0, %bb.nph ], [ %i.01719, %for.inc ] 1016 %tmp4 = getelementptr inbounds %struct.anon* %tmp3, i64 %indvar, i32 0 1017 %tmp5 = load double* %tmp4, align 8, !tbaa !4 1018 %idxprom7 = sext i32 %i.01718 to i64 1019 %tmp10 = getelementptr inbounds %struct.anon* %tmp3, i64 %idxprom7, i32 0 1020 %tmp11 = load double* %tmp10, align 8, !tbaa !4 1021 %cmp12 = fcmp ogt double %tmp5, %tmp11 1022 br i1 %cmp12, label %if.then, label %for.inc 1023 1024if.then: ; preds = %for.body 1025 %i.017 = trunc i64 %indvar to i32 1026 br label %for.inc 1027 1028for.inc: ; preds = %for.body, %if.then 1029 %i.01719 = phi i32 [ %i.01718, %for.body ], [ %i.017, %if.then ] 1030 %indvar.next = add i64 %indvar, 1 1031 %exitcond = icmp eq i64 %indvar.next, %tmp22 1032 br i1 %exitcond, label %for.cond.for.end_crit_edge, label %for.body 1033 1034 1035It is good that we hoisted the reloads of numf2's, and Y out of the loop and 1036sunk the store to winner out. 1037 1038However, this is awful on several levels: the conditional truncate in the loop 1039(-indvars at fault? why can't we completely promote the IV to i64?). 1040 1041Beyond that, we have a partially redundant load in the loop: if "winner" (aka 1042%i.01718) isn't updated, we reload Y[winner].y the next time through the loop. 1043Similarly, the addressing that feeds it (including the sext) is redundant. In 1044the end we get this generated assembly: 1045 1046LBB0_2: ## %for.body 1047 ## =>This Inner Loop Header: Depth=1 1048 movsd (%rdi), %xmm0 1049 movslq %edx, %r8 1050 shlq $4, %r8 1051 ucomisd (%rcx,%r8), %xmm0 1052 jbe LBB0_4 1053 movl %esi, %edx 1054LBB0_4: ## %for.inc 1055 addq $16, %rdi 1056 incq %rsi 1057 cmpq %rsi, %rax 1058 jne LBB0_2 1059 1060All things considered this isn't too bad, but we shouldn't need the movslq or 1061the shlq instruction, or the load folded into ucomisd every time through the 1062loop. 1063 1064On an x86-specific topic, if the loop can't be restructure, the movl should be a 1065cmov. 1066 1067//===---------------------------------------------------------------------===// 1068 1069[STORE SINKING] 1070 1071GCC PR37810 is an interesting case where we should sink load/store reload 1072into the if block and outside the loop, so we don't reload/store it on the 1073non-call path. 1074 1075for () { 1076 *P += 1; 1077 if () 1078 call(); 1079 else 1080 ... 1081-> 1082tmp = *P 1083for () { 1084 tmp += 1; 1085 if () { 1086 *P = tmp; 1087 call(); 1088 tmp = *P; 1089 } else ... 1090} 1091*P = tmp; 1092 1093We now hoist the reload after the call (Transforms/GVN/lpre-call-wrap.ll), but 1094we don't sink the store. We need partially dead store sinking. 1095 1096//===---------------------------------------------------------------------===// 1097 1098[LOAD PRE CRIT EDGE SPLITTING] 1099 1100GCC PR37166: Sinking of loads prevents SROA'ing the "g" struct on the stack 1101leading to excess stack traffic. This could be handled by GVN with some crazy 1102symbolic phi translation. The code we get looks like (g is on the stack): 1103 1104bb2: ; preds = %bb1 1105.. 1106 %9 = getelementptr %struct.f* %g, i32 0, i32 0 1107 store i32 %8, i32* %9, align bel %bb3 1108 1109bb3: ; preds = %bb1, %bb2, %bb 1110 %c_addr.0 = phi %struct.f* [ %g, %bb2 ], [ %c, %bb ], [ %c, %bb1 ] 1111 %b_addr.0 = phi %struct.f* [ %b, %bb2 ], [ %g, %bb ], [ %b, %bb1 ] 1112 %10 = getelementptr %struct.f* %c_addr.0, i32 0, i32 0 1113 %11 = load i32* %10, align 4 1114 1115%11 is partially redundant, an in BB2 it should have the value %8. 1116 1117GCC PR33344 and PR35287 are similar cases. 1118 1119 1120//===---------------------------------------------------------------------===// 1121 1122[LOAD PRE] 1123 1124There are many load PRE testcases in testsuite/gcc.dg/tree-ssa/loadpre* in the 1125GCC testsuite, ones we don't get yet are (checked through loadpre25): 1126 1127[CRIT EDGE BREAKING] 1128predcom-4.c 1129 1130[PRE OF READONLY CALL] 1131loadpre5.c 1132 1133[TURN SELECT INTO BRANCH] 1134loadpre14.c loadpre15.c 1135 1136actually a conditional increment: loadpre18.c loadpre19.c 1137 1138//===---------------------------------------------------------------------===// 1139 1140[LOAD PRE / STORE SINKING / SPEC HACK] 1141 1142This is a chunk of code from 456.hmmer: 1143 1144int f(int M, int *mc, int *mpp, int *tpmm, int *ip, int *tpim, int *dpp, 1145 int *tpdm, int xmb, int *bp, int *ms) { 1146 int k, sc; 1147 for (k = 1; k <= M; k++) { 1148 mc[k] = mpp[k-1] + tpmm[k-1]; 1149 if ((sc = ip[k-1] + tpim[k-1]) > mc[k]) mc[k] = sc; 1150 if ((sc = dpp[k-1] + tpdm[k-1]) > mc[k]) mc[k] = sc; 1151 if ((sc = xmb + bp[k]) > mc[k]) mc[k] = sc; 1152 mc[k] += ms[k]; 1153 } 1154} 1155 1156It is very profitable for this benchmark to turn the conditional stores to mc[k] 1157into a conditional move (select instr in IR) and allow the final store to do the 1158store. See GCC PR27313 for more details. Note that this is valid to xform even 1159with the new C++ memory model, since mc[k] is previously loaded and later 1160stored. 1161 1162//===---------------------------------------------------------------------===// 1163 1164[SCALAR PRE] 1165There are many PRE testcases in testsuite/gcc.dg/tree-ssa/ssa-pre-*.c in the 1166GCC testsuite. 1167 1168//===---------------------------------------------------------------------===// 1169 1170There are some interesting cases in testsuite/gcc.dg/tree-ssa/pred-comm* in the 1171GCC testsuite. For example, we get the first example in predcom-1.c, but 1172miss the second one: 1173 1174unsigned fib[1000]; 1175unsigned avg[1000]; 1176 1177__attribute__ ((noinline)) 1178void count_averages(int n) { 1179 int i; 1180 for (i = 1; i < n; i++) 1181 avg[i] = (((unsigned long) fib[i - 1] + fib[i] + fib[i + 1]) / 3) & 0xffff; 1182} 1183 1184which compiles into two loads instead of one in the loop. 1185 1186predcom-2.c is the same as predcom-1.c 1187 1188predcom-3.c is very similar but needs loads feeding each other instead of 1189store->load. 1190 1191 1192//===---------------------------------------------------------------------===// 1193 1194[ALIAS ANALYSIS] 1195 1196Type based alias analysis: 1197http://gcc.gnu.org/bugzilla/show_bug.cgi?id=14705 1198 1199We should do better analysis of posix_memalign. At the least it should 1200no-capture its pointer argument, at best, we should know that the out-value 1201result doesn't point to anything (like malloc). One example of this is in 1202SingleSource/Benchmarks/Misc/dt.c 1203 1204//===---------------------------------------------------------------------===// 1205 1206Interesting missed case because of control flow flattening (should be 2 loads): 1207http://gcc.gnu.org/bugzilla/show_bug.cgi?id=26629 1208With: llvm-gcc t2.c -S -o - -O0 -emit-llvm | llvm-as | 1209 opt -mem2reg -gvn -instcombine | llvm-dis 1210we miss it because we need 1) CRIT EDGE 2) MULTIPLE DIFFERENT 1211VALS PRODUCED BY ONE BLOCK OVER DIFFERENT PATHS 1212 1213//===---------------------------------------------------------------------===// 1214 1215http://gcc.gnu.org/bugzilla/show_bug.cgi?id=19633 1216We could eliminate the branch condition here, loading from null is undefined: 1217 1218struct S { int w, x, y, z; }; 1219struct T { int r; struct S s; }; 1220void bar (struct S, int); 1221void foo (int a, struct T b) 1222{ 1223 struct S *c = 0; 1224 if (a) 1225 c = &b.s; 1226 bar (*c, a); 1227} 1228 1229//===---------------------------------------------------------------------===// 1230 1231simplifylibcalls should do several optimizations for strspn/strcspn: 1232 1233strcspn(x, "a") -> inlined loop for up to 3 letters (similarly for strspn): 1234 1235size_t __strcspn_c3 (__const char *__s, int __reject1, int __reject2, 1236 int __reject3) { 1237 register size_t __result = 0; 1238 while (__s[__result] != '\0' && __s[__result] != __reject1 && 1239 __s[__result] != __reject2 && __s[__result] != __reject3) 1240 ++__result; 1241 return __result; 1242} 1243 1244This should turn into a switch on the character. See PR3253 for some notes on 1245codegen. 1246 1247456.hmmer apparently uses strcspn and strspn a lot. 471.omnetpp uses strspn. 1248 1249//===---------------------------------------------------------------------===// 1250 1251simplifylibcalls should turn these snprintf idioms into memcpy (GCC PR47917) 1252 1253char buf1[6], buf2[6], buf3[4], buf4[4]; 1254int i; 1255 1256int foo (void) { 1257 int ret = snprintf (buf1, sizeof buf1, "abcde"); 1258 ret += snprintf (buf2, sizeof buf2, "abcdef") * 16; 1259 ret += snprintf (buf3, sizeof buf3, "%s", i++ < 6 ? "abc" : "def") * 256; 1260 ret += snprintf (buf4, sizeof buf4, "%s", i++ > 10 ? "abcde" : "defgh")*4096; 1261 return ret; 1262} 1263 1264//===---------------------------------------------------------------------===// 1265 1266"gas" uses this idiom: 1267 else if (strchr ("+-/*%|&^:[]()~", *intel_parser.op_string)) 1268.. 1269 else if (strchr ("<>", *intel_parser.op_string) 1270 1271Those should be turned into a switch. SimplifyLibCalls only gets the second 1272case. 1273 1274//===---------------------------------------------------------------------===// 1275 1276252.eon contains this interesting code: 1277 1278 %3072 = getelementptr [100 x i8]* %tempString, i32 0, i32 0 1279 %3073 = call i8* @strcpy(i8* %3072, i8* %3071) nounwind 1280 %strlen = call i32 @strlen(i8* %3072) ; uses = 1 1281 %endptr = getelementptr [100 x i8]* %tempString, i32 0, i32 %strlen 1282 call void @llvm.memcpy.i32(i8* %endptr, 1283 i8* getelementptr ([5 x i8]* @"\01LC42", i32 0, i32 0), i32 5, i32 1) 1284 %3074 = call i32 @strlen(i8* %endptr) nounwind readonly 1285 1286This is interesting for a couple reasons. First, in this: 1287 1288The memcpy+strlen strlen can be replaced with: 1289 1290 %3074 = call i32 @strlen([5 x i8]* @"\01LC42") nounwind readonly 1291 1292Because the destination was just copied into the specified memory buffer. This, 1293in turn, can be constant folded to "4". 1294 1295In other code, it contains: 1296 1297 %endptr6978 = bitcast i8* %endptr69 to i32* 1298 store i32 7107374, i32* %endptr6978, align 1 1299 %3167 = call i32 @strlen(i8* %endptr69) nounwind readonly 1300 1301Which could also be constant folded. Whatever is producing this should probably 1302be fixed to leave this as a memcpy from a string. 1303 1304Further, eon also has an interesting partially redundant strlen call: 1305 1306bb8: ; preds = %_ZN18eonImageCalculatorC1Ev.exit 1307 %682 = getelementptr i8** %argv, i32 6 ; <i8**> [#uses=2] 1308 %683 = load i8** %682, align 4 ; <i8*> [#uses=4] 1309 %684 = load i8* %683, align 1 ; <i8> [#uses=1] 1310 %685 = icmp eq i8 %684, 0 ; <i1> [#uses=1] 1311 br i1 %685, label %bb10, label %bb9 1312 1313bb9: ; preds = %bb8 1314 %686 = call i32 @strlen(i8* %683) nounwind readonly 1315 %687 = icmp ugt i32 %686, 254 ; <i1> [#uses=1] 1316 br i1 %687, label %bb10, label %bb11 1317 1318bb10: ; preds = %bb9, %bb8 1319 %688 = call i32 @strlen(i8* %683) nounwind readonly 1320 1321This could be eliminated by doing the strlen once in bb8, saving code size and 1322improving perf on the bb8->9->10 path. 1323 1324//===---------------------------------------------------------------------===// 1325 1326I see an interesting fully redundant call to strlen left in 186.crafty:InputMove 1327which looks like: 1328 %movetext11 = getelementptr [128 x i8]* %movetext, i32 0, i32 0 1329 1330 1331bb62: ; preds = %bb55, %bb53 1332 %promote.0 = phi i32 [ %169, %bb55 ], [ 0, %bb53 ] 1333 %171 = call i32 @strlen(i8* %movetext11) nounwind readonly align 1 1334 %172 = add i32 %171, -1 ; <i32> [#uses=1] 1335 %173 = getelementptr [128 x i8]* %movetext, i32 0, i32 %172 1336 1337... no stores ... 1338 br i1 %or.cond, label %bb65, label %bb72 1339 1340bb65: ; preds = %bb62 1341 store i8 0, i8* %173, align 1 1342 br label %bb72 1343 1344bb72: ; preds = %bb65, %bb62 1345 %trank.1 = phi i32 [ %176, %bb65 ], [ -1, %bb62 ] 1346 %177 = call i32 @strlen(i8* %movetext11) nounwind readonly align 1 1347 1348Note that on the bb62->bb72 path, that the %177 strlen call is partially 1349redundant with the %171 call. At worst, we could shove the %177 strlen call 1350up into the bb65 block moving it out of the bb62->bb72 path. However, note 1351that bb65 stores to the string, zeroing out the last byte. This means that on 1352that path the value of %177 is actually just %171-1. A sub is cheaper than a 1353strlen! 1354 1355This pattern repeats several times, basically doing: 1356 1357 A = strlen(P); 1358 P[A-1] = 0; 1359 B = strlen(P); 1360 where it is "obvious" that B = A-1. 1361 1362//===---------------------------------------------------------------------===// 1363 1364186.crafty has this interesting pattern with the "out.4543" variable: 1365 1366call void @llvm.memcpy.i32( 1367 i8* getelementptr ([10 x i8]* @out.4543, i32 0, i32 0), 1368 i8* getelementptr ([7 x i8]* @"\01LC28700", i32 0, i32 0), i32 7, i32 1) 1369%101 = call@printf(i8* ... @out.4543, i32 0, i32 0)) nounwind 1370 1371It is basically doing: 1372 1373 memcpy(globalarray, "string"); 1374 printf(..., globalarray); 1375 1376Anyway, by knowing that printf just reads the memory and forward substituting 1377the string directly into the printf, this eliminates reads from globalarray. 1378Since this pattern occurs frequently in crafty (due to the "DisplayTime" and 1379other similar functions) there are many stores to "out". Once all the printfs 1380stop using "out", all that is left is the memcpy's into it. This should allow 1381globalopt to remove the "stored only" global. 1382 1383//===---------------------------------------------------------------------===// 1384 1385This code: 1386 1387define inreg i32 @foo(i8* inreg %p) nounwind { 1388 %tmp0 = load i8* %p 1389 %tmp1 = ashr i8 %tmp0, 5 1390 %tmp2 = sext i8 %tmp1 to i32 1391 ret i32 %tmp2 1392} 1393 1394could be dagcombine'd to a sign-extending load with a shift. 1395For example, on x86 this currently gets this: 1396 1397 movb (%eax), %al 1398 sarb $5, %al 1399 movsbl %al, %eax 1400 1401while it could get this: 1402 1403 movsbl (%eax), %eax 1404 sarl $5, %eax 1405 1406//===---------------------------------------------------------------------===// 1407 1408GCC PR31029: 1409 1410int test(int x) { return 1-x == x; } // --> return false 1411int test2(int x) { return 2-x == x; } // --> return x == 1 ? 1412 1413Always foldable for odd constants, what is the rule for even? 1414 1415//===---------------------------------------------------------------------===// 1416 1417PR 3381: GEP to field of size 0 inside a struct could be turned into GEP 1418for next field in struct (which is at same address). 1419 1420For example: store of float into { {{}}, float } could be turned into a store to 1421the float directly. 1422 1423//===---------------------------------------------------------------------===// 1424 1425The arg promotion pass should make use of nocapture to make its alias analysis 1426stuff much more precise. 1427 1428//===---------------------------------------------------------------------===// 1429 1430The following functions should be optimized to use a select instead of a 1431branch (from gcc PR40072): 1432 1433char char_int(int m) {if(m>7) return 0; return m;} 1434int int_char(char m) {if(m>7) return 0; return m;} 1435 1436//===---------------------------------------------------------------------===// 1437 1438int func(int a, int b) { if (a & 0x80) b |= 0x80; else b &= ~0x80; return b; } 1439 1440Generates this: 1441 1442define i32 @func(i32 %a, i32 %b) nounwind readnone ssp { 1443entry: 1444 %0 = and i32 %a, 128 ; <i32> [#uses=1] 1445 %1 = icmp eq i32 %0, 0 ; <i1> [#uses=1] 1446 %2 = or i32 %b, 128 ; <i32> [#uses=1] 1447 %3 = and i32 %b, -129 ; <i32> [#uses=1] 1448 %b_addr.0 = select i1 %1, i32 %3, i32 %2 ; <i32> [#uses=1] 1449 ret i32 %b_addr.0 1450} 1451 1452However, it's functionally equivalent to: 1453 1454 b = (b & ~0x80) | (a & 0x80); 1455 1456Which generates this: 1457 1458define i32 @func(i32 %a, i32 %b) nounwind readnone ssp { 1459entry: 1460 %0 = and i32 %b, -129 ; <i32> [#uses=1] 1461 %1 = and i32 %a, 128 ; <i32> [#uses=1] 1462 %2 = or i32 %0, %1 ; <i32> [#uses=1] 1463 ret i32 %2 1464} 1465 1466This can be generalized for other forms: 1467 1468 b = (b & ~0x80) | (a & 0x40) << 1; 1469 1470//===---------------------------------------------------------------------===// 1471 1472These two functions produce different code. They shouldn't: 1473 1474#include <stdint.h> 1475 1476uint8_t p1(uint8_t b, uint8_t a) { 1477 b = (b & ~0xc0) | (a & 0xc0); 1478 return (b); 1479} 1480 1481uint8_t p2(uint8_t b, uint8_t a) { 1482 b = (b & ~0x40) | (a & 0x40); 1483 b = (b & ~0x80) | (a & 0x80); 1484 return (b); 1485} 1486 1487define zeroext i8 @p1(i8 zeroext %b, i8 zeroext %a) nounwind readnone ssp { 1488entry: 1489 %0 = and i8 %b, 63 ; <i8> [#uses=1] 1490 %1 = and i8 %a, -64 ; <i8> [#uses=1] 1491 %2 = or i8 %1, %0 ; <i8> [#uses=1] 1492 ret i8 %2 1493} 1494 1495define zeroext i8 @p2(i8 zeroext %b, i8 zeroext %a) nounwind readnone ssp { 1496entry: 1497 %0 = and i8 %b, 63 ; <i8> [#uses=1] 1498 %.masked = and i8 %a, 64 ; <i8> [#uses=1] 1499 %1 = and i8 %a, -128 ; <i8> [#uses=1] 1500 %2 = or i8 %1, %0 ; <i8> [#uses=1] 1501 %3 = or i8 %2, %.masked ; <i8> [#uses=1] 1502 ret i8 %3 1503} 1504 1505//===---------------------------------------------------------------------===// 1506 1507IPSCCP does not currently propagate argument dependent constants through 1508functions where it does not not all of the callers. This includes functions 1509with normal external linkage as well as templates, C99 inline functions etc. 1510Specifically, it does nothing to: 1511 1512define i32 @test(i32 %x, i32 %y, i32 %z) nounwind { 1513entry: 1514 %0 = add nsw i32 %y, %z 1515 %1 = mul i32 %0, %x 1516 %2 = mul i32 %y, %z 1517 %3 = add nsw i32 %1, %2 1518 ret i32 %3 1519} 1520 1521define i32 @test2() nounwind { 1522entry: 1523 %0 = call i32 @test(i32 1, i32 2, i32 4) nounwind 1524 ret i32 %0 1525} 1526 1527It would be interesting extend IPSCCP to be able to handle simple cases like 1528this, where all of the arguments to a call are constant. Because IPSCCP runs 1529before inlining, trivial templates and inline functions are not yet inlined. 1530The results for a function + set of constant arguments should be memoized in a 1531map. 1532 1533//===---------------------------------------------------------------------===// 1534 1535The libcall constant folding stuff should be moved out of SimplifyLibcalls into 1536libanalysis' constantfolding logic. This would allow IPSCCP to be able to 1537handle simple things like this: 1538 1539static int foo(const char *X) { return strlen(X); } 1540int bar() { return foo("abcd"); } 1541 1542//===---------------------------------------------------------------------===// 1543 1544functionattrs doesn't know much about memcpy/memset. This function should be 1545marked readnone rather than readonly, since it only twiddles local memory, but 1546functionattrs doesn't handle memset/memcpy/memmove aggressively: 1547 1548struct X { int *p; int *q; }; 1549int foo() { 1550 int i = 0, j = 1; 1551 struct X x, y; 1552 int **p; 1553 y.p = &i; 1554 x.q = &j; 1555 p = __builtin_memcpy (&x, &y, sizeof (int *)); 1556 return **p; 1557} 1558 1559This can be seen at: 1560$ clang t.c -S -o - -mkernel -O0 -emit-llvm | opt -functionattrs -S 1561 1562 1563//===---------------------------------------------------------------------===// 1564 1565Missed instcombine transformation: 1566define i1 @a(i32 %x) nounwind readnone { 1567entry: 1568 %cmp = icmp eq i32 %x, 30 1569 %sub = add i32 %x, -30 1570 %cmp2 = icmp ugt i32 %sub, 9 1571 %or = or i1 %cmp, %cmp2 1572 ret i1 %or 1573} 1574This should be optimized to a single compare. Testcase derived from gcc. 1575 1576//===---------------------------------------------------------------------===// 1577 1578Missed instcombine or reassociate transformation: 1579int a(int a, int b) { return (a==12)&(b>47)&(b<58); } 1580 1581The sgt and slt should be combined into a single comparison. Testcase derived 1582from gcc. 1583 1584//===---------------------------------------------------------------------===// 1585 1586Missed instcombine transformation: 1587 1588 %382 = srem i32 %tmp14.i, 64 ; [#uses=1] 1589 %383 = zext i32 %382 to i64 ; [#uses=1] 1590 %384 = shl i64 %381, %383 ; [#uses=1] 1591 %385 = icmp slt i32 %tmp14.i, 64 ; [#uses=1] 1592 1593The srem can be transformed to an and because if %tmp14.i is negative, the 1594shift is undefined. Testcase derived from 403.gcc. 1595 1596//===---------------------------------------------------------------------===// 1597 1598This is a range comparison on a divided result (from 403.gcc): 1599 1600 %1337 = sdiv i32 %1336, 8 ; [#uses=1] 1601 %.off.i208 = add i32 %1336, 7 ; [#uses=1] 1602 %1338 = icmp ult i32 %.off.i208, 15 ; [#uses=1] 1603 1604We already catch this (removing the sdiv) if there isn't an add, we should 1605handle the 'add' as well. This is a common idiom with it's builtin_alloca code. 1606C testcase: 1607 1608int a(int x) { return (unsigned)(x/16+7) < 15; } 1609 1610Another similar case involves truncations on 64-bit targets: 1611 1612 %361 = sdiv i64 %.046, 8 ; [#uses=1] 1613 %362 = trunc i64 %361 to i32 ; [#uses=2] 1614... 1615 %367 = icmp eq i32 %362, 0 ; [#uses=1] 1616 1617//===---------------------------------------------------------------------===// 1618 1619Missed instcombine/dagcombine transformation: 1620define void @lshift_lt(i8 zeroext %a) nounwind { 1621entry: 1622 %conv = zext i8 %a to i32 1623 %shl = shl i32 %conv, 3 1624 %cmp = icmp ult i32 %shl, 33 1625 br i1 %cmp, label %if.then, label %if.end 1626 1627if.then: 1628 tail call void @bar() nounwind 1629 ret void 1630 1631if.end: 1632 ret void 1633} 1634declare void @bar() nounwind 1635 1636The shift should be eliminated. Testcase derived from gcc. 1637 1638//===---------------------------------------------------------------------===// 1639 1640These compile into different code, one gets recognized as a switch and the 1641other doesn't due to phase ordering issues (PR6212): 1642 1643int test1(int mainType, int subType) { 1644 if (mainType == 7) 1645 subType = 4; 1646 else if (mainType == 9) 1647 subType = 6; 1648 else if (mainType == 11) 1649 subType = 9; 1650 return subType; 1651} 1652 1653int test2(int mainType, int subType) { 1654 if (mainType == 7) 1655 subType = 4; 1656 if (mainType == 9) 1657 subType = 6; 1658 if (mainType == 11) 1659 subType = 9; 1660 return subType; 1661} 1662 1663//===---------------------------------------------------------------------===// 1664 1665The following test case (from PR6576): 1666 1667define i32 @mul(i32 %a, i32 %b) nounwind readnone { 1668entry: 1669 %cond1 = icmp eq i32 %b, 0 ; <i1> [#uses=1] 1670 br i1 %cond1, label %exit, label %bb.nph 1671bb.nph: ; preds = %entry 1672 %tmp = mul i32 %b, %a ; <i32> [#uses=1] 1673 ret i32 %tmp 1674exit: ; preds = %entry 1675 ret i32 0 1676} 1677 1678could be reduced to: 1679 1680define i32 @mul(i32 %a, i32 %b) nounwind readnone { 1681entry: 1682 %tmp = mul i32 %b, %a 1683 ret i32 %tmp 1684} 1685 1686//===---------------------------------------------------------------------===// 1687 1688We should use DSE + llvm.lifetime.end to delete dead vtable pointer updates. 1689See GCC PR34949 1690 1691Another interesting case is that something related could be used for variables 1692that go const after their ctor has finished. In these cases, globalopt (which 1693can statically run the constructor) could mark the global const (so it gets put 1694in the readonly section). A testcase would be: 1695 1696#include <complex> 1697using namespace std; 1698const complex<char> should_be_in_rodata (42,-42); 1699complex<char> should_be_in_data (42,-42); 1700complex<char> should_be_in_bss; 1701 1702Where we currently evaluate the ctors but the globals don't become const because 1703the optimizer doesn't know they "become const" after the ctor is done. See 1704GCC PR4131 for more examples. 1705 1706//===---------------------------------------------------------------------===// 1707 1708In this code: 1709 1710long foo(long x) { 1711 return x > 1 ? x : 1; 1712} 1713 1714LLVM emits a comparison with 1 instead of 0. 0 would be equivalent 1715and cheaper on most targets. 1716 1717LLVM prefers comparisons with zero over non-zero in general, but in this 1718case it choses instead to keep the max operation obvious. 1719 1720//===---------------------------------------------------------------------===// 1721 1722define void @a(i32 %x) nounwind { 1723entry: 1724 switch i32 %x, label %if.end [ 1725 i32 0, label %if.then 1726 i32 1, label %if.then 1727 i32 2, label %if.then 1728 i32 3, label %if.then 1729 i32 5, label %if.then 1730 ] 1731if.then: 1732 tail call void @foo() nounwind 1733 ret void 1734if.end: 1735 ret void 1736} 1737declare void @foo() 1738 1739Generated code on x86-64 (other platforms give similar results): 1740a: 1741 cmpl $5, %edi 1742 ja LBB2_2 1743 cmpl $4, %edi 1744 jne LBB2_3 1745.LBB0_2: 1746 ret 1747.LBB0_3: 1748 jmp foo # TAILCALL 1749 1750If we wanted to be really clever, we could simplify the whole thing to 1751something like the following, which eliminates a branch: 1752 xorl $1, %edi 1753 cmpl $4, %edi 1754 ja .LBB0_2 1755 ret 1756.LBB0_2: 1757 jmp foo # TAILCALL 1758 1759//===---------------------------------------------------------------------===// 1760 1761We compile this: 1762 1763int foo(int a) { return (a & (~15)) / 16; } 1764 1765Into: 1766 1767define i32 @foo(i32 %a) nounwind readnone ssp { 1768entry: 1769 %and = and i32 %a, -16 1770 %div = sdiv i32 %and, 16 1771 ret i32 %div 1772} 1773 1774but this code (X & -A)/A is X >> log2(A) when A is a power of 2, so this case 1775should be instcombined into just "a >> 4". 1776 1777We do get this at the codegen level, so something knows about it, but 1778instcombine should catch it earlier: 1779 1780_foo: ## @foo 1781## BB#0: ## %entry 1782 movl %edi, %eax 1783 sarl $4, %eax 1784 ret 1785 1786//===---------------------------------------------------------------------===// 1787 1788This code (from GCC PR28685): 1789 1790int test(int a, int b) { 1791 int lt = a < b; 1792 int eq = a == b; 1793 if (lt) 1794 return 1; 1795 return eq; 1796} 1797 1798Is compiled to: 1799 1800define i32 @test(i32 %a, i32 %b) nounwind readnone ssp { 1801entry: 1802 %cmp = icmp slt i32 %a, %b 1803 br i1 %cmp, label %return, label %if.end 1804 1805if.end: ; preds = %entry 1806 %cmp5 = icmp eq i32 %a, %b 1807 %conv6 = zext i1 %cmp5 to i32 1808 ret i32 %conv6 1809 1810return: ; preds = %entry 1811 ret i32 1 1812} 1813 1814it could be: 1815 1816define i32 @test__(i32 %a, i32 %b) nounwind readnone ssp { 1817entry: 1818 %0 = icmp sle i32 %a, %b 1819 %retval = zext i1 %0 to i32 1820 ret i32 %retval 1821} 1822 1823//===---------------------------------------------------------------------===// 1824 1825This code can be seen in viterbi: 1826 1827 %64 = call noalias i8* @malloc(i64 %62) nounwind 1828... 1829 %67 = call i64 @llvm.objectsize.i64(i8* %64, i1 false) nounwind 1830 %68 = call i8* @__memset_chk(i8* %64, i32 0, i64 %62, i64 %67) nounwind 1831 1832llvm.objectsize.i64 should be taught about malloc/calloc, allowing it to 1833fold to %62. This is a security win (overflows of malloc will get caught) 1834and also a performance win by exposing more memsets to the optimizer. 1835 1836This occurs several times in viterbi. 1837 1838Note that this would change the semantics of @llvm.objectsize which by its 1839current definition always folds to a constant. We also should make sure that 1840we remove checking in code like 1841 1842 char *p = malloc(strlen(s)+1); 1843 __strcpy_chk(p, s, __builtin_objectsize(p, 0)); 1844 1845//===---------------------------------------------------------------------===// 1846 1847clang -O3 currently compiles this code 1848 1849int g(unsigned int a) { 1850 unsigned int c[100]; 1851 c[10] = a; 1852 c[11] = a; 1853 unsigned int b = c[10] + c[11]; 1854 if(b > a*2) a = 4; 1855 else a = 8; 1856 return a + 7; 1857} 1858 1859into 1860 1861define i32 @g(i32 a) nounwind readnone { 1862 %add = shl i32 %a, 1 1863 %mul = shl i32 %a, 1 1864 %cmp = icmp ugt i32 %add, %mul 1865 %a.addr.0 = select i1 %cmp, i32 11, i32 15 1866 ret i32 %a.addr.0 1867} 1868 1869The icmp should fold to false. This CSE opportunity is only available 1870after GVN and InstCombine have run. 1871 1872//===---------------------------------------------------------------------===// 1873 1874memcpyopt should turn this: 1875 1876define i8* @test10(i32 %x) { 1877 %alloc = call noalias i8* @malloc(i32 %x) nounwind 1878 call void @llvm.memset.p0i8.i32(i8* %alloc, i8 0, i32 %x, i32 1, i1 false) 1879 ret i8* %alloc 1880} 1881 1882into a call to calloc. We should make sure that we analyze calloc as 1883aggressively as malloc though. 1884 1885//===---------------------------------------------------------------------===// 1886 1887clang -O3 doesn't optimize this: 1888 1889void f1(int* begin, int* end) { 1890 std::fill(begin, end, 0); 1891} 1892 1893into a memset. This is PR8942. 1894 1895//===---------------------------------------------------------------------===// 1896 1897clang -O3 -fno-exceptions currently compiles this code: 1898 1899void f(int N) { 1900 std::vector<int> v(N); 1901 1902 extern void sink(void*); sink(&v); 1903} 1904 1905into 1906 1907define void @_Z1fi(i32 %N) nounwind { 1908entry: 1909 %v2 = alloca [3 x i32*], align 8 1910 %v2.sub = getelementptr inbounds [3 x i32*]* %v2, i64 0, i64 0 1911 %tmpcast = bitcast [3 x i32*]* %v2 to %"class.std::vector"* 1912 %conv = sext i32 %N to i64 1913 store i32* null, i32** %v2.sub, align 8, !tbaa !0 1914 %tmp3.i.i.i.i.i = getelementptr inbounds [3 x i32*]* %v2, i64 0, i64 1 1915 store i32* null, i32** %tmp3.i.i.i.i.i, align 8, !tbaa !0 1916 %tmp4.i.i.i.i.i = getelementptr inbounds [3 x i32*]* %v2, i64 0, i64 2 1917 store i32* null, i32** %tmp4.i.i.i.i.i, align 8, !tbaa !0 1918 %cmp.i.i.i.i = icmp eq i32 %N, 0 1919 br i1 %cmp.i.i.i.i, label %_ZNSt12_Vector_baseIiSaIiEEC2EmRKS0_.exit.thread.i.i, label %cond.true.i.i.i.i 1920 1921_ZNSt12_Vector_baseIiSaIiEEC2EmRKS0_.exit.thread.i.i: ; preds = %entry 1922 store i32* null, i32** %v2.sub, align 8, !tbaa !0 1923 store i32* null, i32** %tmp3.i.i.i.i.i, align 8, !tbaa !0 1924 %add.ptr.i5.i.i = getelementptr inbounds i32* null, i64 %conv 1925 store i32* %add.ptr.i5.i.i, i32** %tmp4.i.i.i.i.i, align 8, !tbaa !0 1926 br label %_ZNSt6vectorIiSaIiEEC1EmRKiRKS0_.exit 1927 1928cond.true.i.i.i.i: ; preds = %entry 1929 %cmp.i.i.i.i.i = icmp slt i32 %N, 0 1930 br i1 %cmp.i.i.i.i.i, label %if.then.i.i.i.i.i, label %_ZNSt12_Vector_baseIiSaIiEEC2EmRKS0_.exit.i.i 1931 1932if.then.i.i.i.i.i: ; preds = %cond.true.i.i.i.i 1933 call void @_ZSt17__throw_bad_allocv() noreturn nounwind 1934 unreachable 1935 1936_ZNSt12_Vector_baseIiSaIiEEC2EmRKS0_.exit.i.i: ; preds = %cond.true.i.i.i.i 1937 %mul.i.i.i.i.i = shl i64 %conv, 2 1938 %call3.i.i.i.i.i = call noalias i8* @_Znwm(i64 %mul.i.i.i.i.i) nounwind 1939 %0 = bitcast i8* %call3.i.i.i.i.i to i32* 1940 store i32* %0, i32** %v2.sub, align 8, !tbaa !0 1941 store i32* %0, i32** %tmp3.i.i.i.i.i, align 8, !tbaa !0 1942 %add.ptr.i.i.i = getelementptr inbounds i32* %0, i64 %conv 1943 store i32* %add.ptr.i.i.i, i32** %tmp4.i.i.i.i.i, align 8, !tbaa !0 1944 call void @llvm.memset.p0i8.i64(i8* %call3.i.i.i.i.i, i8 0, i64 %mul.i.i.i.i.i, i32 4, i1 false) 1945 br label %_ZNSt6vectorIiSaIiEEC1EmRKiRKS0_.exit 1946 1947This is just the handling the construction of the vector. Most surprising here 1948is the fact that all three null stores in %entry are dead (because we do no 1949cross-block DSE). 1950 1951Also surprising is that %conv isn't simplified to 0 in %....exit.thread.i.i. 1952This is a because the client of LazyValueInfo doesn't simplify all instruction 1953operands, just selected ones. 1954 1955//===---------------------------------------------------------------------===// 1956 1957clang -O3 -fno-exceptions currently compiles this code: 1958 1959void f(char* a, int n) { 1960 __builtin_memset(a, 0, n); 1961 for (int i = 0; i < n; ++i) 1962 a[i] = 0; 1963} 1964 1965into: 1966 1967define void @_Z1fPci(i8* nocapture %a, i32 %n) nounwind { 1968entry: 1969 %conv = sext i32 %n to i64 1970 tail call void @llvm.memset.p0i8.i64(i8* %a, i8 0, i64 %conv, i32 1, i1 false) 1971 %cmp8 = icmp sgt i32 %n, 0 1972 br i1 %cmp8, label %for.body.lr.ph, label %for.end 1973 1974for.body.lr.ph: ; preds = %entry 1975 %tmp10 = add i32 %n, -1 1976 %tmp11 = zext i32 %tmp10 to i64 1977 %tmp12 = add i64 %tmp11, 1 1978 call void @llvm.memset.p0i8.i64(i8* %a, i8 0, i64 %tmp12, i32 1, i1 false) 1979 ret void 1980 1981for.end: ; preds = %entry 1982 ret void 1983} 1984 1985This shouldn't need the ((zext (%n - 1)) + 1) game, and it should ideally fold 1986the two memset's together. 1987 1988The issue with the addition only occurs in 64-bit mode, and appears to be at 1989least partially caused by Scalar Evolution not keeping its cache updated: it 1990returns the "wrong" result immediately after indvars runs, but figures out the 1991expected result if it is run from scratch on IR resulting from running indvars. 1992 1993//===---------------------------------------------------------------------===// 1994 1995clang -O3 -fno-exceptions currently compiles this code: 1996 1997struct S { 1998 unsigned short m1, m2; 1999 unsigned char m3, m4; 2000}; 2001 2002void f(int N) { 2003 std::vector<S> v(N); 2004 extern void sink(void*); sink(&v); 2005} 2006 2007into poor code for zero-initializing 'v' when N is >0. The problem is that 2008S is only 6 bytes, but each element is 8 byte-aligned. We generate a loop and 20094 stores on each iteration. If the struct were 8 bytes, this gets turned into 2010a memset. 2011 2012In order to handle this we have to: 2013 A) Teach clang to generate metadata for memsets of structs that have holes in 2014 them. 2015 B) Teach clang to use such a memset for zero init of this struct (since it has 2016 a hole), instead of doing elementwise zeroing. 2017 2018//===---------------------------------------------------------------------===// 2019 2020clang -O3 currently compiles this code: 2021 2022extern const int magic; 2023double f() { return 0.0 * magic; } 2024 2025into 2026 2027@magic = external constant i32 2028 2029define double @_Z1fv() nounwind readnone { 2030entry: 2031 %tmp = load i32* @magic, align 4, !tbaa !0 2032 %conv = sitofp i32 %tmp to double 2033 %mul = fmul double %conv, 0.000000e+00 2034 ret double %mul 2035} 2036 2037We should be able to fold away this fmul to 0.0. More generally, fmul(x,0.0) 2038can be folded to 0.0 if we can prove that the LHS is not -0.0, not a NaN, and 2039not an INF. The CannotBeNegativeZero predicate in value tracking should be 2040extended to support general "fpclassify" operations that can return 2041yes/no/unknown for each of these predicates. 2042 2043In this predicate, we know that uitofp is trivially never NaN or -0.0, and 2044we know that it isn't +/-Inf if the floating point type has enough exponent bits 2045to represent the largest integer value as < inf. 2046 2047//===---------------------------------------------------------------------===// 2048 2049When optimizing a transformation that can change the sign of 0.0 (such as the 20500.0*val -> 0.0 transformation above), it might be provable that the sign of the 2051expression doesn't matter. For example, by the above rules, we can't transform 2052fmul(sitofp(x), 0.0) into 0.0, because x might be -1 and the result of the 2053expression is defined to be -0.0. 2054 2055If we look at the uses of the fmul for example, we might be able to prove that 2056all uses don't care about the sign of zero. For example, if we have: 2057 2058 fadd(fmul(sitofp(x), 0.0), 2.0) 2059 2060Since we know that x+2.0 doesn't care about the sign of any zeros in X, we can 2061transform the fmul to 0.0, and then the fadd to 2.0. 2062 2063//===---------------------------------------------------------------------===// 2064 2065We should enhance memcpy/memcpy/memset to allow a metadata node on them 2066indicating that some bytes of the transfer are undefined. This is useful for 2067frontends like clang when lowering struct copies, when some elements of the 2068struct are undefined. Consider something like this: 2069 2070struct x { 2071 char a; 2072 int b[4]; 2073}; 2074void foo(struct x*P); 2075struct x testfunc() { 2076 struct x V1, V2; 2077 foo(&V1); 2078 V2 = V1; 2079 2080 return V2; 2081} 2082 2083We currently compile this to: 2084$ clang t.c -S -o - -O0 -emit-llvm | opt -scalarrepl -S 2085 2086 2087%struct.x = type { i8, [4 x i32] } 2088 2089define void @testfunc(%struct.x* sret %agg.result) nounwind ssp { 2090entry: 2091 %V1 = alloca %struct.x, align 4 2092 call void @foo(%struct.x* %V1) 2093 %tmp1 = bitcast %struct.x* %V1 to i8* 2094 %0 = bitcast %struct.x* %V1 to i160* 2095 %srcval1 = load i160* %0, align 4 2096 %tmp2 = bitcast %struct.x* %agg.result to i8* 2097 %1 = bitcast %struct.x* %agg.result to i160* 2098 store i160 %srcval1, i160* %1, align 4 2099 ret void 2100} 2101 2102This happens because SRoA sees that the temp alloca has is being memcpy'd into 2103and out of and it has holes and it has to be conservative. If we knew about the 2104holes, then this could be much much better. 2105 2106Having information about these holes would also improve memcpy (etc) lowering at 2107llc time when it gets inlined, because we can use smaller transfers. This also 2108avoids partial register stalls in some important cases. 2109 2110//===---------------------------------------------------------------------===// 2111 2112We don't fold (icmp (add) (add)) unless the two adds only have a single use. 2113There are a lot of cases that we're refusing to fold in (e.g.) 256.bzip2, for 2114example: 2115 2116 %indvar.next90 = add i64 %indvar89, 1 ;; Has 2 uses 2117 %tmp96 = add i64 %tmp95, 1 ;; Has 1 use 2118 %exitcond97 = icmp eq i64 %indvar.next90, %tmp96 2119 2120We don't fold this because we don't want to introduce an overlapped live range 2121of the ivar. However if we can make this more aggressive without causing 2122performance issues in two ways: 2123 21241. If *either* the LHS or RHS has a single use, we can definitely do the 2125 transformation. In the overlapping liverange case we're trading one register 2126 use for one fewer operation, which is a reasonable trade. Before doing this 2127 we should verify that the llc output actually shrinks for some benchmarks. 21282. If both ops have multiple uses, we can still fold it if the operations are 2129 both sinkable to *after* the icmp (e.g. in a subsequent block) which doesn't 2130 increase register pressure. 2131 2132There are a ton of icmp's we aren't simplifying because of the reg pressure 2133concern. Care is warranted here though because many of these are induction 2134variables and other cases that matter a lot to performance, like the above. 2135Here's a blob of code that you can drop into the bottom of visitICmp to see some 2136missed cases: 2137 2138 { Value *A, *B, *C, *D; 2139 if (match(Op0, m_Add(m_Value(A), m_Value(B))) && 2140 match(Op1, m_Add(m_Value(C), m_Value(D))) && 2141 (A == C || A == D || B == C || B == D)) { 2142 errs() << "OP0 = " << *Op0 << " U=" << Op0->getNumUses() << "\n"; 2143 errs() << "OP1 = " << *Op1 << " U=" << Op1->getNumUses() << "\n"; 2144 errs() << "CMP = " << I << "\n\n"; 2145 } 2146 } 2147 2148//===---------------------------------------------------------------------===// 2149 2150define i1 @test1(i32 %x) nounwind { 2151 %and = and i32 %x, 3 2152 %cmp = icmp ult i32 %and, 2 2153 ret i1 %cmp 2154} 2155 2156Can be folded to (x & 2) == 0. 2157 2158define i1 @test2(i32 %x) nounwind { 2159 %and = and i32 %x, 3 2160 %cmp = icmp ugt i32 %and, 1 2161 ret i1 %cmp 2162} 2163 2164Can be folded to (x & 2) != 0. 2165 2166SimplifyDemandedBits shrinks the "and" constant to 2 but instcombine misses the 2167icmp transform. 2168 2169//===---------------------------------------------------------------------===// 2170 2171This code: 2172 2173typedef struct { 2174int f1:1; 2175int f2:1; 2176int f3:1; 2177int f4:29; 2178} t1; 2179 2180typedef struct { 2181int f1:1; 2182int f2:1; 2183int f3:30; 2184} t2; 2185 2186t1 s1; 2187t2 s2; 2188 2189void func1(void) 2190{ 2191s1.f1 = s2.f1; 2192s1.f2 = s2.f2; 2193} 2194 2195Compiles into this IR (on x86-64 at least): 2196 2197%struct.t1 = type { i8, [3 x i8] } 2198@s2 = global %struct.t1 zeroinitializer, align 4 2199@s1 = global %struct.t1 zeroinitializer, align 4 2200define void @func1() nounwind ssp noredzone { 2201entry: 2202 %0 = load i32* bitcast (%struct.t1* @s2 to i32*), align 4 2203 %bf.val.sext5 = and i32 %0, 1 2204 %1 = load i32* bitcast (%struct.t1* @s1 to i32*), align 4 2205 %2 = and i32 %1, -4 2206 %3 = or i32 %2, %bf.val.sext5 2207 %bf.val.sext26 = and i32 %0, 2 2208 %4 = or i32 %3, %bf.val.sext26 2209 store i32 %4, i32* bitcast (%struct.t1* @s1 to i32*), align 4 2210 ret void 2211} 2212 2213The two or/and's should be merged into one each. 2214 2215//===---------------------------------------------------------------------===// 2216 2217Machine level code hoisting can be useful in some cases. For example, PR9408 2218is about: 2219 2220typedef union { 2221 void (*f1)(int); 2222 void (*f2)(long); 2223} funcs; 2224 2225void foo(funcs f, int which) { 2226 int a = 5; 2227 if (which) { 2228 f.f1(a); 2229 } else { 2230 f.f2(a); 2231 } 2232} 2233 2234which we compile to: 2235 2236foo: # @foo 2237# BB#0: # %entry 2238 pushq %rbp 2239 movq %rsp, %rbp 2240 testl %esi, %esi 2241 movq %rdi, %rax 2242 je .LBB0_2 2243# BB#1: # %if.then 2244 movl $5, %edi 2245 callq *%rax 2246 popq %rbp 2247 ret 2248.LBB0_2: # %if.else 2249 movl $5, %edi 2250 callq *%rax 2251 popq %rbp 2252 ret 2253 2254Note that bb1 and bb2 are the same. This doesn't happen at the IR level 2255because one call is passing an i32 and the other is passing an i64. 2256 2257//===---------------------------------------------------------------------===// 2258 2259I see this sort of pattern in 176.gcc in a few places (e.g. the start of 2260store_bit_field). The rem should be replaced with a multiply and subtract: 2261 2262 %3 = sdiv i32 %A, %B 2263 %4 = srem i32 %A, %B 2264 2265Similarly for udiv/urem. Note that this shouldn't be done on X86 or ARM, 2266which can do this in a single operation (instruction or libcall). It is 2267probably best to do this in the code generator. 2268 2269//===---------------------------------------------------------------------===// 2270 2271unsigned foo(unsigned x, unsigned y) { return (x & y) == 0 || x == 0; } 2272should fold to (x & y) == 0. 2273 2274//===---------------------------------------------------------------------===// 2275 2276unsigned foo(unsigned x, unsigned y) { return x > y && x != 0; } 2277should fold to x > y. 2278 2279//===---------------------------------------------------------------------===// 2280