2266 lines · plain
1Target Independent Opportunities:2 3//===---------------------------------------------------------------------===//4 5Get the C front-end to expand hypot(x,y) -> llvm.sqrt(x*x+y*y) when errno and6precision don't matter (ffastmath). Misc/mandel will like this. :) This isn't7safe in general, even on darwin. See the libm implementation of hypot for8examples (which special case when x/y are exactly zero to get signed zeros etc9right).10 11//===---------------------------------------------------------------------===//12 13On targets with expensive 64-bit multiply, we could LSR this:14 15for (i = ...; ++i) {16 x = 1ULL << i;17 18into:19 long long tmp = 1;20 for (i = ...; ++i, tmp+=tmp)21 x = tmp;22 23This would be a win on ppc32, but not x86 or ppc64.24 25//===---------------------------------------------------------------------===//26 27Shrink: (setlt (loadi32 P), 0) -> (setlt (loadi8 Phi), 0)28 29//===---------------------------------------------------------------------===//30 31Reassociate should turn things like:32 33int factorial(int X) {34 return X*X*X*X*X*X*X*X;35}36 37into llvm.powi calls, allowing the code generator to produce balanced38multiplication trees.39 40First, the intrinsic needs to be extended to support integers, and second the41code generator needs to be enhanced to lower these to multiplication trees.42 43//===---------------------------------------------------------------------===//44 45Interesting? testcase for add/shift/mul reassoc:46 47int bar(int x, int y) {48 return x*x*x+y+x*x*x*x*x*y*y*y*y;49}50int foo(int z, int n) {51 return bar(z, n) + bar(2*z, 2*n);52}53 54This is blocked on not handling X*X*X -> powi(X, 3) (see note above). The issue55is that we end up getting t = 2*X s = t*t and don't turn this into 4*X*X,56which is the same number of multiplies and is canonical, because the 2*X has57multiple uses. Here's a simple example:58 59define i32 @test15(i32 %X1) {60 %B = mul i32 %X1, 47 ; X1*4761 %C = mul i32 %B, %B62 ret i32 %C63}64 65 66//===---------------------------------------------------------------------===//67 68Reassociate should handle the example in GCC PR16157:69 70extern int a0, a1, a2, a3, a4; extern int b0, b1, b2, b3, b4; 71void f () { /* this can be optimized to four additions... */ 72 b4 = a4 + a3 + a2 + a1 + a0; 73 b3 = a3 + a2 + a1 + a0; 74 b2 = a2 + a1 + a0; 75 b1 = a1 + a0; 76} 77 78This requires reassociating to forms of expressions that are already available,79something that reassoc doesn't think about yet.80 81 82//===---------------------------------------------------------------------===//83 84These two functions should generate the same code on big-endian systems:85 86int g(int *j,int *l) { return memcmp(j,l,4); }87int h(int *j, int *l) { return *j - *l; }88 89this could be done in SelectionDAGISel.cpp, along with other special cases,90for 1,2,4,8 bytes.91 92//===---------------------------------------------------------------------===//93 94It would be nice to revert this patch:95http://lists.llvm.org/pipermail/llvm-commits/Week-of-Mon-20060213/031986.html96 97And teach the dag combiner enough to simplify the code expanded before 98legalize. It seems plausible that this knowledge would let it simplify other99stuff too.100 101//===---------------------------------------------------------------------===//102 103For vector types, DataLayout.cpp::getTypeInfo() returns alignment that is equal104to the type size. It works but can be overly conservative as the alignment of105specific vector types are target dependent.106 107//===---------------------------------------------------------------------===//108 109We should produce an unaligned load from code like this:110 111v4sf example(float *P) {112 return (v4sf){P[0], P[1], P[2], P[3] };113}114 115//===---------------------------------------------------------------------===//116 117Add support for conditional increments, and other related patterns. Instead118of:119 120 movl 136(%esp), %eax121 cmpl $0, %eax122 je LBB16_2 #cond_next123LBB16_1: #cond_true124 incl _foo125LBB16_2: #cond_next126 127emit:128 movl _foo, %eax129 cmpl $1, %edi130 sbbl $-1, %eax131 movl %eax, _foo132 133//===---------------------------------------------------------------------===//134 135Combine: a = sin(x), b = cos(x) into a,b = sincos(x).136 137Expand these to calls of sin/cos and stores:138 double sincos(double x, double *sin, double *cos);139 float sincosf(float x, float *sin, float *cos);140 long double sincosl(long double x, long double *sin, long double *cos);141 142Doing so could allow SROA of the destination pointers. See also:143http://gcc.gnu.org/bugzilla/show_bug.cgi?id=17687144 145This is now easily doable with MRVs. We could even make an intrinsic for this146if anyone cared enough about sincos.147 148//===---------------------------------------------------------------------===//149 150quantum_sigma_x in 462.libquantum contains the following loop:151 152 for(i=0; i<reg->size; i++)153 {154 /* Flip the target bit of each basis state */155 reg->node[i].state ^= ((MAX_UNSIGNED) 1 << target);156 } 157 158Where MAX_UNSIGNED/state is a 64-bit int. On a 32-bit platform it would be just159so cool to turn it into something like:160 161 long long Res = ((MAX_UNSIGNED) 1 << target);162 if (target < 32) {163 for(i=0; i<reg->size; i++)164 reg->node[i].state ^= Res & 0xFFFFFFFFULL;165 } else {166 for(i=0; i<reg->size; i++)167 reg->node[i].state ^= Res & 0xFFFFFFFF00000000ULL168 }169 170... which would only do one 32-bit XOR per loop iteration instead of two.171 172It would also be nice to recognize the reg->size doesn't alias reg->node[i],173but this requires TBAA.174 175//===---------------------------------------------------------------------===//176 177This isn't recognized as bswap by instcombine (yes, it really is bswap):178 179unsigned long reverse(unsigned v) {180 unsigned t;181 t = v ^ ((v << 16) | (v >> 16));182 t &= ~0xff0000;183 v = (v << 24) | (v >> 8);184 return v ^ (t >> 8);185}186 187//===---------------------------------------------------------------------===//188 189[LOOP DELETION]190 191We don't delete this output free loop, because trip count analysis doesn't192realize that it is finite (if it were infinite, it would be undefined). Not193having this blocks Loop Idiom from matching strlen and friends. 194 195void foo(char *C) {196 int x = 0;197 while (*C)198 ++x,++C;199}200 201//===---------------------------------------------------------------------===//202 203[LOOP RECOGNITION]204 205These idioms should be recognized as popcount (see PR1488):206 207unsigned countbits_slow(unsigned v) {208 unsigned c;209 for (c = 0; v; v >>= 1)210 c += v & 1;211 return c;212}213 214unsigned int popcount(unsigned int input) {215 unsigned int count = 0;216 for (unsigned int i = 0; i < 4 * 8; i++)217 count += (input >> i) & i;218 return count;219}220 221This should be recognized as CLZ: https://github.com/llvm/llvm-project/issues/64167222 223unsigned clz_a(unsigned a) {224 int i;225 for (i=0;i<32;i++)226 if (a & (1<<(31-i)))227 return i;228 return 32;229}230 231This sort of thing should be added to the loop idiom pass.232 233//===---------------------------------------------------------------------===//234 235These should turn into single 16-bit (unaligned?) loads on little/big endian236processors.237 238unsigned short read_16_le(const unsigned char *adr) {239 return adr[0] | (adr[1] << 8);240}241unsigned short read_16_be(const unsigned char *adr) {242 return (adr[0] << 8) | adr[1];243}244 245//===---------------------------------------------------------------------===//246 247-instcombine should handle this transform:248 icmp pred (sdiv X / C1 ), C2249when X, C1, and C2 are unsigned. Similarly for udiv and signed operands. 250 251Currently InstCombine avoids this transform but will do it when the signs of252the operands and the sign of the divide match. See the FIXME in 253InstructionCombining.cpp in the visitSetCondInst method after the switch case 254for Instruction::UDiv (around line 4447) for more details.255 256The SingleSource/Benchmarks/Shootout-C++/hash and hash2 tests have examples of257this construct. 258 259//===---------------------------------------------------------------------===//260 261[LOOP OPTIMIZATION]262 263SingleSource/Benchmarks/Misc/dt.c shows several interesting optimization264opportunities in its double_array_divs_variable function: it needs loop265interchange, memory promotion (which LICM already does), vectorization and266variable trip count loop unrolling (since it has a constant trip count). ICC267apparently produces this very nice code with -ffast-math:268 269..B1.70: # Preds ..B1.70 ..B1.69270 mulpd %xmm0, %xmm1 #108.2271 mulpd %xmm0, %xmm1 #108.2272 mulpd %xmm0, %xmm1 #108.2273 mulpd %xmm0, %xmm1 #108.2274 addl $8, %edx #275 cmpl $131072, %edx #108.2276 jb ..B1.70 # Prob 99% #108.2277 278It would be better to count down to zero, but this is a lot better than what we279do.280 281//===---------------------------------------------------------------------===//282 283Consider:284 285typedef unsigned U32;286typedef unsigned long long U64;287int test (U32 *inst, U64 *regs) {288 U64 effective_addr2;289 U32 temp = *inst;290 int r1 = (temp >> 20) & 0xf;291 int b2 = (temp >> 16) & 0xf;292 effective_addr2 = temp & 0xfff;293 if (b2) effective_addr2 += regs[b2];294 b2 = (temp >> 12) & 0xf;295 if (b2) effective_addr2 += regs[b2];296 effective_addr2 &= regs[4];297 if ((effective_addr2 & 3) == 0)298 return 1;299 return 0;300}301 302Note that only the low 2 bits of effective_addr2 are used. On 32-bit systems,303we don't eliminate the computation of the top half of effective_addr2 because304we don't have whole-function selection dags. On x86, this means we use one305extra register for the function when effective_addr2 is declared as U64 than306when it is declared U32.307 308PHI Slicing could be extended to do this.309 310//===---------------------------------------------------------------------===//311 312Tail call elim should be more aggressive, checking to see if the call is313followed by an uncond branch to an exit block.314 315; This testcase is due to tail-duplication not wanting to copy the return316; instruction into the terminating blocks because there was other code317; optimized out of the function after the taildup happened.318; RUN: llvm-as < %s | opt -tailcallelim | llvm-dis | not grep call319 320define i32 @t4(i32 %a) {321entry:322 %tmp.1 = and i32 %a, 1 ; <i32> [#uses=1]323 %tmp.2 = icmp ne i32 %tmp.1, 0 ; <i1> [#uses=1]324 br i1 %tmp.2, label %then.0, label %else.0325 326then.0: ; preds = %entry327 %tmp.5 = add i32 %a, -1 ; <i32> [#uses=1]328 %tmp.3 = call i32 @t4( i32 %tmp.5 ) ; <i32> [#uses=1]329 br label %return330 331else.0: ; preds = %entry332 %tmp.7 = icmp ne i32 %a, 0 ; <i1> [#uses=1]333 br i1 %tmp.7, label %then.1, label %return334 335then.1: ; preds = %else.0336 %tmp.11 = add i32 %a, -2 ; <i32> [#uses=1]337 %tmp.9 = call i32 @t4( i32 %tmp.11 ) ; <i32> [#uses=1]338 br label %return339 340return: ; preds = %then.1, %else.0, %then.0341 %result.0 = phi i32 [ 0, %else.0 ], [ %tmp.3, %then.0 ],342 [ %tmp.9, %then.1 ]343 ret i32 %result.0344}345 346//===---------------------------------------------------------------------===//347 348Tail recursion elimination should handle:349 350int pow2m1(int n) {351 if (n == 0)352 return 0;353 return 2 * pow2m1 (n - 1) + 1;354}355 356Also, multiplies can be turned into SHL's, so they should be handled as if357they were associative. "return foo() << 1" can be tail recursion eliminated.358 359//===---------------------------------------------------------------------===//360 361Argument promotion should promote arguments for recursive functions, like 362this:363 364; RUN: llvm-as < %s | opt -argpromotion | llvm-dis | grep x.val365 366define internal i32 @foo(i32* %x) {367entry:368 %tmp = load i32* %x ; <i32> [#uses=0]369 %tmp.foo = call i32 @foo( i32* %x ) ; <i32> [#uses=1]370 ret i32 %tmp.foo371}372 373define i32 @bar(i32* %x) {374entry:375 %tmp3 = call i32 @foo( i32* %x ) ; <i32> [#uses=1]376 ret i32 %tmp3377}378 379//===---------------------------------------------------------------------===//380 381We should investigate an instruction sinking pass. Consider this silly382example in pic mode:383 384#include <assert.h>385void foo(int x) {386 assert(x);387 //...388}389 390we compile this to:391_foo:392 subl $28, %esp393 call "L1$pb"394"L1$pb":395 popl %eax396 cmpl $0, 32(%esp)397 je LBB1_2 # cond_true398LBB1_1: # return399 # ...400 addl $28, %esp401 ret402LBB1_2: # cond_true403...404 405The PIC base computation (call+popl) is only used on one path through the 406code, but is currently always computed in the entry block. It would be 407better to sink the picbase computation down into the block for the 408assertion, as it is the only one that uses it. This happens for a lot of 409code with early outs.410 411Another example is loads of arguments, which are usually emitted into the 412entry block on targets like x86. If not used in all paths through a 413function, they should be sunk into the ones that do.414 415In this case, whole-function-isel would also handle this.416 417//===---------------------------------------------------------------------===//418 419Investigate lowering of sparse switch statements into perfect hash tables:420http://burtleburtle.net/bob/hash/perfect.html421 422//===---------------------------------------------------------------------===//423 424We should turn things like "load+fabs+store" and "load+fneg+store" into the425corresponding integer operations. On a yonah, this loop:426 427double a[256];428void foo() {429 int i, b;430 for (b = 0; b < 10000000; b++)431 for (i = 0; i < 256; i++)432 a[i] = -a[i];433}434 435is twice as slow as this loop:436 437long long a[256];438void foo() {439 int i, b;440 for (b = 0; b < 10000000; b++)441 for (i = 0; i < 256; i++)442 a[i] ^= (1ULL << 63);443}444 445and I suspect other processors are similar. On X86 in particular this is a446big win because doing this with integers allows the use of read/modify/write447instructions.448 449//===---------------------------------------------------------------------===//450 451DAG Combiner should try to combine small loads into larger loads when 452profitable. For example, we compile this C++ example:453 454struct THotKey { short Key; bool Control; bool Shift; bool Alt; };455extern THotKey m_HotKey;456THotKey GetHotKey () { return m_HotKey; }457 458into (-m64 -O3 -fno-exceptions -static -fomit-frame-pointer):459 460__Z9GetHotKeyv: ## @_Z9GetHotKeyv461 movq _m_HotKey@GOTPCREL(%rip), %rax462 movzwl (%rax), %ecx463 movzbl 2(%rax), %edx464 shlq $16, %rdx465 orq %rcx, %rdx466 movzbl 3(%rax), %ecx467 shlq $24, %rcx468 orq %rdx, %rcx469 movzbl 4(%rax), %eax470 shlq $32, %rax471 orq %rcx, %rax472 ret473 474//===---------------------------------------------------------------------===//475 476We should add an FRINT node to the DAG to model targets that have legal477implementations of ceil/floor/rint.478 479//===---------------------------------------------------------------------===//480 481Consider:482 483int test() {484 long long input[8] = {1,0,1,0,1,0,1,0};485 foo(input);486}487 488Clang compiles this into:489 490 call void @llvm.memset.p0i8.i64(i8* %tmp, i8 0, i64 64, i32 16, i1 false)491 %0 = getelementptr [8 x i64]* %input, i64 0, i64 0492 store i64 1, i64* %0, align 16493 %1 = getelementptr [8 x i64]* %input, i64 0, i64 2494 store i64 1, i64* %1, align 16495 %2 = getelementptr [8 x i64]* %input, i64 0, i64 4496 store i64 1, i64* %2, align 16497 %3 = getelementptr [8 x i64]* %input, i64 0, i64 6498 store i64 1, i64* %3, align 16499 500Which gets codegen'd into:501 502 pxor %xmm0, %xmm0503 movaps %xmm0, -16(%rbp)504 movaps %xmm0, -32(%rbp)505 movaps %xmm0, -48(%rbp)506 movaps %xmm0, -64(%rbp)507 movq $1, -64(%rbp)508 movq $1, -48(%rbp)509 movq $1, -32(%rbp)510 movq $1, -16(%rbp)511 512It would be better to have 4 movq's of 0 instead of the movaps's.513 514//===---------------------------------------------------------------------===//515 516http://llvm.org/PR717:517 518The following code should compile into "ret int undef". Instead, LLVM519produces "ret int 0":520 521int f() {522 int x = 4;523 int y;524 if (x == 3) y = 0;525 return y;526}527 528//===---------------------------------------------------------------------===//529 530The loop unroller should partially unroll loops (instead of peeling them)531when code growth isn't too bad and when an unroll count allows simplification532of some code within the loop. One trivial example is:533 534#include <stdio.h>535int main() {536 int nRet = 17;537 int nLoop;538 for ( nLoop = 0; nLoop < 1000; nLoop++ ) {539 if ( nLoop & 1 )540 nRet += 2;541 else542 nRet -= 1;543 }544 return nRet;545}546 547Unrolling by 2 would eliminate the '&1' in both copies, leading to a net548reduction in code size. The resultant code would then also be suitable for549exit value computation.550 551//===---------------------------------------------------------------------===//552 553We miss a bunch of rotate opportunities on various targets, including ppc, x86,554etc. On X86, we miss a bunch of 'rotate by variable' cases because the rotate555matching code in dag combine doesn't look through truncates aggressively 556enough. Here are some testcases reduces from GCC PR17886:557 558unsigned long long f5(unsigned long long x, unsigned long long y) {559 return (x << 8) | ((y >> 48) & 0xffull);560}561unsigned long long f6(unsigned long long x, unsigned long long y, int z) {562 switch(z) {563 case 1:564 return (x << 8) | ((y >> 48) & 0xffull);565 case 2:566 return (x << 16) | ((y >> 40) & 0xffffull);567 case 3:568 return (x << 24) | ((y >> 32) & 0xffffffull);569 case 4:570 return (x << 32) | ((y >> 24) & 0xffffffffull);571 default:572 return (x << 40) | ((y >> 16) & 0xffffffffffull);573 }574}575 576//===---------------------------------------------------------------------===//577 578This (and similar related idioms):579 580unsigned int foo(unsigned char i) {581 return i | (i<<8) | (i<<16) | (i<<24);582} 583 584compiles into:585 586define i32 @foo(i8 zeroext %i) nounwind readnone ssp noredzone {587entry:588 %conv = zext i8 %i to i32589 %shl = shl i32 %conv, 8590 %shl5 = shl i32 %conv, 16591 %shl9 = shl i32 %conv, 24592 %or = or i32 %shl9, %conv593 %or6 = or i32 %or, %shl5594 %or10 = or i32 %or6, %shl595 ret i32 %or10596}597 598it would be better as:599 600unsigned int bar(unsigned char i) {601 unsigned int j=i | (i << 8); 602 return j | (j<<16);603}604 605aka:606 607define i32 @bar(i8 zeroext %i) nounwind readnone ssp noredzone {608entry:609 %conv = zext i8 %i to i32610 %shl = shl i32 %conv, 8611 %or = or i32 %shl, %conv612 %shl5 = shl i32 %or, 16613 %or6 = or i32 %shl5, %or614 ret i32 %or6615}616 617or even i*0x01010101, depending on the speed of the multiplier. The best way to618handle this is to canonicalize it to a multiply in IR and have codegen handle619lowering multiplies to shifts on cpus where shifts are faster.620 621//===---------------------------------------------------------------------===//622 623We do a number of simplifications in simplify libcalls to strength reduce624standard library functions, but we don't currently merge them together. For625example, it is useful to merge memcpy(a,b,strlen(b)) -> strcpy. This can only626be done safely if "b" isn't modified between the strlen and memcpy of course.627 628//===---------------------------------------------------------------------===//629 630We compile this program: (from GCC PR11680)631http://gcc.gnu.org/bugzilla/attachment.cgi?id=4487632 633Into code that runs the same speed in fast/slow modes, but both modes run 2x634slower than when compile with GCC (either 4.0 or 4.2):635 636$ llvm-g++ perf.cpp -O3 -fno-exceptions637$ time ./a.out fast6381.821u 0.003s 0:01.82 100.0% 0+0k 0+0io 0pf+0w639 640$ g++ perf.cpp -O3 -fno-exceptions641$ time ./a.out fast6420.821u 0.001s 0:00.82 100.0% 0+0k 0+0io 0pf+0w643 644It looks like we are making the same inlining decisions, so this may be raw645codegen badness or something else (haven't investigated).646 647//===---------------------------------------------------------------------===//648 649Divisibility by constant can be simplified (according to GCC PR12849) from650being a mulhi to being a mul lo (cheaper). Testcase:651 652void bar(unsigned n) {653 if (n % 3 == 0)654 true();655}656 657This is equivalent to the following, where 2863311531 is the multiplicative658inverse of 3, and 1431655766 is ((2^32)-1)/3+1:659void bar(unsigned n) {660 if (n * 2863311531U < 1431655766U)661 true();662}663 664The same transformation can work with an even modulo with the addition of a665rotate: rotate the result of the multiply to the right by the number of bits666which need to be zero for the condition to be true, and shrink the compare RHS667by the same amount. Unless the target supports rotates, though, that668transformation probably isn't worthwhile.669 670The transformation can also easily be made to work with non-zero equality671comparisons: just transform, for example, "n % 3 == 1" to "(n-1) % 3 == 0".672 673//===---------------------------------------------------------------------===//674 675Better mod/ref analysis for scanf would allow us to eliminate the vtable and a676bunch of other stuff from this example (see PR1604): 677 678#include <cstdio>679struct test {680 int val;681 virtual ~test() {}682};683 684int main() {685 test t;686 std::scanf("%d", &t.val);687 std::printf("%d\n", t.val);688}689 690//===---------------------------------------------------------------------===//691 692These functions perform the same computation, but produce different assembly.693 694define i8 @select(i8 %x) readnone nounwind {695 %A = icmp ult i8 %x, 250696 %B = select i1 %A, i8 0, i8 1697 ret i8 %B 698}699 700define i8 @addshr(i8 %x) readnone nounwind {701 %A = zext i8 %x to i9702 %B = add i9 %A, 6 ;; 256 - 250 == 6703 %C = lshr i9 %B, 8704 %D = trunc i9 %C to i8705 ret i8 %D706}707 708//===---------------------------------------------------------------------===//709 710From gcc bug 24696:711int712f (unsigned long a, unsigned long b, unsigned long c)713{714 return ((a & (c - 1)) != 0) || ((b & (c - 1)) != 0);715}716int717f (unsigned long a, unsigned long b, unsigned long c)718{719 return ((a & (c - 1)) != 0) | ((b & (c - 1)) != 0);720}721Both should combine to ((a|b) & (c-1)) != 0. Currently not optimized with722"clang -emit-llvm-bc | opt -O3".723 724//===---------------------------------------------------------------------===//725 726From GCC Bug 20192:727#define PMD_MASK (~((1UL << 23) - 1))728void clear_pmd_range(unsigned long start, unsigned long end)729{730 if (!(start & ~PMD_MASK) && !(end & ~PMD_MASK))731 f();732}733The expression should optimize to something like734"!((start|end)&~PMD_MASK). Currently not optimized with "clang735-emit-llvm-bc | opt -O3".736 737//===---------------------------------------------------------------------===//738 739unsigned int f(unsigned int i, unsigned int n) {++i; if (i == n) ++i; return740i;}741unsigned int f2(unsigned int i, unsigned int n) {++i; i += i == n; return i;}742These should combine to the same thing. Currently, the first function743produces better code on X86.744 745//===---------------------------------------------------------------------===//746 747From GCC Bug 15784:748#define abs(x) x>0?x:-x749int f(int x, int y)750{751 return (abs(x)) >= 0;752}753This should optimize to x == INT_MIN. (With -fwrapv.) Currently not754optimized with "clang -emit-llvm-bc | opt -O3".755 756//===---------------------------------------------------------------------===//757 758From GCC Bug 14753:759void760rotate_cst (unsigned int a)761{762 a = (a << 10) | (a >> 22);763 if (a == 123)764 bar ();765}766void767minus_cst (unsigned int a)768{769 unsigned int tem;770 771 tem = 20 - a;772 if (tem == 5)773 bar ();774}775void776mask_gt (unsigned int a)777{778 /* This is equivalent to a > 15. */779 if ((a & ~7) > 8)780 bar ();781}782void783rshift_gt (unsigned int a)784{785 /* This is equivalent to a > 23. */786 if ((a >> 2) > 5)787 bar ();788}789 790All should simplify to a single comparison. All of these are791currently not optimized with "clang -emit-llvm-bc | opt792-O3".793 794//===---------------------------------------------------------------------===//795 796From GCC Bug 32605:797int c(int* x) {return (char*)x+2 == (char*)x;}798Should combine to 0. Currently not optimized with "clang799-emit-llvm-bc | opt -O3" (although llc can optimize it).800 801//===---------------------------------------------------------------------===//802 803int a(unsigned b) {return ((b << 31) | (b << 30)) >> 31;}804Should be combined to "((b >> 1) | b) & 1". Currently not optimized805with "clang -emit-llvm-bc | opt -O3".806 807//===---------------------------------------------------------------------===//808 809unsigned a(unsigned x, unsigned y) { return x | (y & 1) | (y & 2);}810Should combine to "x | (y & 3)". Currently not optimized with "clang811-emit-llvm-bc | opt -O3".812 813//===---------------------------------------------------------------------===//814 815int a(int a, int b, int c) {return (~a & c) | ((c|a) & b);}816Should fold to "(~a & c) | (a & b)". Currently not optimized with817"clang -emit-llvm-bc | opt -O3".818 819//===---------------------------------------------------------------------===//820 821int a(int a,int b) {return (~(a|b))|a;}822Should fold to "a|~b". Currently not optimized with "clang823-emit-llvm-bc | opt -O3".824 825//===---------------------------------------------------------------------===//826 827int a(int a, int b) {return (a&&b) || (a&&!b);}828Should fold to "a". Currently not optimized with "clang -emit-llvm-bc829| opt -O3".830 831//===---------------------------------------------------------------------===//832 833int a(int a, int b, int c) {return (a&&b) || (!a&&c);}834Should fold to "a ? b : c", or at least something sane. Currently not835optimized with "clang -emit-llvm-bc | opt -O3".836 837//===---------------------------------------------------------------------===//838 839int a(int a, int b, int c) {return (a&&b) || (a&&c) || (a&&b&&c);}840Should fold to a && (b || c). Currently not optimized with "clang841-emit-llvm-bc | opt -O3".842 843//===---------------------------------------------------------------------===//844 845int a(int x) {return x | ((x & 8) ^ 8);}846Should combine to x | 8. Currently not optimized with "clang847-emit-llvm-bc | opt -O3".848 849//===---------------------------------------------------------------------===//850 851int a(int x) {return x ^ ((x & 8) ^ 8);}852Should also combine to x | 8. Currently not optimized with "clang853-emit-llvm-bc | opt -O3".854 855//===---------------------------------------------------------------------===//856 857int a(int x) {return ((x | -9) ^ 8) & x;}858Should combine to x & -9. Currently not optimized with "clang859-emit-llvm-bc | opt -O3".860 861//===---------------------------------------------------------------------===//862 863unsigned a(unsigned a) {return a * 0x11111111 >> 28 & 1;}864Should combine to "a * 0x88888888 >> 31". Currently not optimized865with "clang -emit-llvm-bc | opt -O3".866 867//===---------------------------------------------------------------------===//868 869unsigned a(char* x) {if ((*x & 32) == 0) return b();}870There's an unnecessary zext in the generated code with "clang871-emit-llvm-bc | opt -O3".872 873//===---------------------------------------------------------------------===//874 875unsigned a(unsigned long long x) {return 40 * (x >> 1);}876Should combine to "20 * (((unsigned)x) & -2)". Currently not877optimized with "clang -emit-llvm-bc | opt -O3".878 879//===---------------------------------------------------------------------===//880 881int g(int x) { return (x - 10) < 0; }882Should combine to "x <= 9" (the sub has nsw). Currently not883optimized with "clang -emit-llvm-bc | opt -O3".884 885//===---------------------------------------------------------------------===//886 887int g(int x) { return (x + 10) < 0; }888Should combine to "x < -10" (the add has nsw). Currently not889optimized with "clang -emit-llvm-bc | opt -O3".890 891//===---------------------------------------------------------------------===//892 893int f(int i, int j) { return i < j + 1; }894int g(int i, int j) { return j > i - 1; }895Should combine to "i <= j" (the add/sub has nsw). Currently not896optimized with "clang -emit-llvm-bc | opt -O3".897 898//===---------------------------------------------------------------------===//899 900unsigned f(unsigned x) { return ((x & 7) + 1) & 15; }901The & 15 part should be optimized away, it doesn't change the result. Currently902not optimized with "clang -emit-llvm-bc | opt -O3".903 904//===---------------------------------------------------------------------===//905 906This was noticed in the entryblock for grokdeclarator in 403.gcc:907 908 %tmp = icmp eq i32 %decl_context, 4 909 %decl_context_addr.0 = select i1 %tmp, i32 3, i32 %decl_context 910 %tmp1 = icmp eq i32 %decl_context_addr.0, 1 911 %decl_context_addr.1 = select i1 %tmp1, i32 0, i32 %decl_context_addr.0912 913tmp1 should be simplified to something like:914 (!tmp || decl_context == 1)915 916This allows recursive simplifications, tmp1 is used all over the place in917the function, e.g. by:918 919 %tmp23 = icmp eq i32 %decl_context_addr.1, 0 ; <i1> [#uses=1]920 %tmp24 = xor i1 %tmp1, true ; <i1> [#uses=1]921 %or.cond8 = and i1 %tmp23, %tmp24 ; <i1> [#uses=1]922 923later.924 925//===---------------------------------------------------------------------===//926 927[STORE SINKING]928 929Store sinking: This code:930 931void f (int n, int *cond, int *res) {932 int i;933 *res = 0;934 for (i = 0; i < n; i++)935 if (*cond)936 *res ^= 234; /* (*) */937}938 939On this function GVN hoists the fully redundant value of *res, but nothing940moves the store out. This gives us this code:941 942bb: ; preds = %bb2, %entry943 %.rle = phi i32 [ 0, %entry ], [ %.rle6, %bb2 ] 944 %i.05 = phi i32 [ 0, %entry ], [ %indvar.next, %bb2 ]945 %1 = load i32* %cond, align 4946 %2 = icmp eq i32 %1, 0947 br i1 %2, label %bb2, label %bb1948 949bb1: ; preds = %bb950 %3 = xor i32 %.rle, 234 951 store i32 %3, i32* %res, align 4952 br label %bb2953 954bb2: ; preds = %bb, %bb1955 %.rle6 = phi i32 [ %3, %bb1 ], [ %.rle, %bb ] 956 %indvar.next = add i32 %i.05, 1 957 %exitcond = icmp eq i32 %indvar.next, %n958 br i1 %exitcond, label %return, label %bb959 960DSE should sink partially dead stores to get the store out of the loop.961 962Here's another partial dead case:963http://gcc.gnu.org/bugzilla/show_bug.cgi?id=12395964 965//===---------------------------------------------------------------------===//966 967Scalar PRE hoists the mul in the common block up to the else:968 969int test (int a, int b, int c, int g) {970 int d, e;971 if (a)972 d = b * c;973 else974 d = b - c;975 e = b * c + g;976 return d + e;977}978 979It would be better to do the mul once to reduce codesize above the if.980This is GCC PR38204.981 982 983//===---------------------------------------------------------------------===//984This simple function from 179.art:985 986int winner, numf2s;987struct { double y; int reset; } *Y;988 989void find_match() {990 int i;991 winner = 0;992 for (i=0;i<numf2s;i++)993 if (Y[i].y > Y[winner].y)994 winner =i;995}996 997Compiles into (with clang TBAA):998 999for.body: ; preds = %for.inc, %bb.nph1000 %indvar = phi i64 [ 0, %bb.nph ], [ %indvar.next, %for.inc ]1001 %i.01718 = phi i32 [ 0, %bb.nph ], [ %i.01719, %for.inc ]1002 %tmp4 = getelementptr inbounds %struct.anon* %tmp3, i64 %indvar, i32 01003 %tmp5 = load double* %tmp4, align 8, !tbaa !41004 %idxprom7 = sext i32 %i.01718 to i641005 %tmp10 = getelementptr inbounds %struct.anon* %tmp3, i64 %idxprom7, i32 01006 %tmp11 = load double* %tmp10, align 8, !tbaa !41007 %cmp12 = fcmp ogt double %tmp5, %tmp111008 br i1 %cmp12, label %if.then, label %for.inc1009 1010if.then: ; preds = %for.body1011 %i.017 = trunc i64 %indvar to i321012 br label %for.inc1013 1014for.inc: ; preds = %for.body, %if.then1015 %i.01719 = phi i32 [ %i.01718, %for.body ], [ %i.017, %if.then ]1016 %indvar.next = add i64 %indvar, 11017 %exitcond = icmp eq i64 %indvar.next, %tmp221018 br i1 %exitcond, label %for.cond.for.end_crit_edge, label %for.body1019 1020 1021It is good that we hoisted the reloads of numf2's, and Y out of the loop and1022sunk the store to winner out.1023 1024However, this is awful on several levels: the conditional truncate in the loop1025(-indvars at fault? why can't we completely promote the IV to i64?).1026 1027Beyond that, we have a partially redundant load in the loop: if "winner" (aka 1028%i.01718) isn't updated, we reload Y[winner].y the next time through the loop.1029Similarly, the addressing that feeds it (including the sext) is redundant. In1030the end we get this generated assembly:1031 1032LBB0_2: ## %for.body1033 ## =>This Inner Loop Header: Depth=11034 movsd (%rdi), %xmm01035 movslq %edx, %r81036 shlq $4, %r81037 ucomisd (%rcx,%r8), %xmm01038 jbe LBB0_41039 movl %esi, %edx1040LBB0_4: ## %for.inc1041 addq $16, %rdi1042 incq %rsi1043 cmpq %rsi, %rax1044 jne LBB0_21045 1046All things considered this isn't too bad, but we shouldn't need the movslq or1047the shlq instruction, or the load folded into ucomisd every time through the1048loop.1049 1050On an x86-specific topic, if the loop can't be restructure, the movl should be a1051cmov.1052 1053//===---------------------------------------------------------------------===//1054 1055[STORE SINKING]1056 1057GCC PR37810 is an interesting case where we should sink load/store reload1058into the if block and outside the loop, so we don't reload/store it on the1059non-call path.1060 1061for () {1062 *P += 1;1063 if ()1064 call();1065 else1066 ...1067->1068tmp = *P1069for () {1070 tmp += 1;1071 if () {1072 *P = tmp;1073 call();1074 tmp = *P;1075 } else ...1076}1077*P = tmp;1078 1079We now hoist the reload after the call (Transforms/GVN/lpre-call-wrap.ll), but1080we don't sink the store. We need partially dead store sinking.1081 1082//===---------------------------------------------------------------------===//1083 1084[LOAD PRE CRIT EDGE SPLITTING]1085 1086GCC PR37166: Sinking of loads prevents SROA'ing the "g" struct on the stack1087leading to excess stack traffic. This could be handled by GVN with some crazy1088symbolic phi translation. The code we get looks like (g is on the stack):1089 1090bb2: ; preds = %bb11091..1092 %9 = getelementptr %struct.f* %g, i32 0, i32 0 1093 store i32 %8, i32* %9, align bel %bb31094 1095bb3: ; preds = %bb1, %bb2, %bb1096 %c_addr.0 = phi %struct.f* [ %g, %bb2 ], [ %c, %bb ], [ %c, %bb1 ]1097 %b_addr.0 = phi %struct.f* [ %b, %bb2 ], [ %g, %bb ], [ %b, %bb1 ]1098 %10 = getelementptr %struct.f* %c_addr.0, i32 0, i32 01099 %11 = load i32* %10, align 41100 1101%11 is partially redundant, an in BB2 it should have the value %8.1102 1103GCC PR33344 and PR35287 are similar cases.1104 1105 1106//===---------------------------------------------------------------------===//1107 1108[LOAD PRE]1109 1110There are many load PRE testcases in testsuite/gcc.dg/tree-ssa/loadpre* in the1111GCC testsuite, ones we don't get yet are (checked through loadpre25):1112 1113[CRIT EDGE BREAKING]1114predcom-4.c1115 1116[PRE OF READONLY CALL]1117loadpre5.c1118 1119[TURN SELECT INTO BRANCH]1120loadpre14.c loadpre15.c 1121 1122actually a conditional increment: loadpre18.c loadpre19.c1123 1124//===---------------------------------------------------------------------===//1125 1126[LOAD PRE / STORE SINKING / SPEC HACK]1127 1128This is a chunk of code from 456.hmmer:1129 1130int f(int M, int *mc, int *mpp, int *tpmm, int *ip, int *tpim, int *dpp,1131 int *tpdm, int xmb, int *bp, int *ms) {1132 int k, sc;1133 for (k = 1; k <= M; k++) {1134 mc[k] = mpp[k-1] + tpmm[k-1];1135 if ((sc = ip[k-1] + tpim[k-1]) > mc[k]) mc[k] = sc;1136 if ((sc = dpp[k-1] + tpdm[k-1]) > mc[k]) mc[k] = sc;1137 if ((sc = xmb + bp[k]) > mc[k]) mc[k] = sc;1138 mc[k] += ms[k];1139 }1140}1141 1142It is very profitable for this benchmark to turn the conditional stores to mc[k]1143into a conditional move (select instr in IR) and allow the final store to do the1144store. See GCC PR27313 for more details. Note that this is valid to xform even1145with the new C++ memory model, since mc[k] is previously loaded and later1146stored.1147 1148//===---------------------------------------------------------------------===//1149 1150[SCALAR PRE]1151There are many PRE testcases in testsuite/gcc.dg/tree-ssa/ssa-pre-*.c in the1152GCC testsuite.1153 1154//===---------------------------------------------------------------------===//1155 1156There are some interesting cases in testsuite/gcc.dg/tree-ssa/pred-comm* in the1157GCC testsuite. For example, we get the first example in predcom-1.c, but 1158miss the second one:1159 1160unsigned fib[1000];1161unsigned avg[1000];1162 1163__attribute__ ((noinline))1164void count_averages(int n) {1165 int i;1166 for (i = 1; i < n; i++)1167 avg[i] = (((unsigned long) fib[i - 1] + fib[i] + fib[i + 1]) / 3) & 0xffff;1168}1169 1170which compiles into two loads instead of one in the loop.1171 1172predcom-2.c is the same as predcom-1.c1173 1174predcom-3.c is very similar but needs loads feeding each other instead of1175store->load.1176 1177 1178//===---------------------------------------------------------------------===//1179 1180[ALIAS ANALYSIS]1181 1182Type based alias analysis:1183http://gcc.gnu.org/bugzilla/show_bug.cgi?id=147051184 1185We should do better analysis of posix_memalign. At the least it should1186no-capture its pointer argument, at best, we should know that the out-value1187result doesn't point to anything (like malloc). One example of this is in1188SingleSource/Benchmarks/Misc/dt.c1189 1190//===---------------------------------------------------------------------===//1191 1192Interesting missed case because of control flow flattening (should be 2 loads):1193http://gcc.gnu.org/bugzilla/show_bug.cgi?id=266291194With: llvm-gcc t2.c -S -o - -O0 -emit-llvm | llvm-as | 1195 opt -mem2reg -gvn -instcombine | llvm-dis1196we miss it because we need 1) CRIT EDGE 2) MULTIPLE DIFFERENT1197VALS PRODUCED BY ONE BLOCK OVER DIFFERENT PATHS1198 1199//===---------------------------------------------------------------------===//1200 1201http://gcc.gnu.org/bugzilla/show_bug.cgi?id=196331202We could eliminate the branch condition here, loading from null is undefined:1203 1204struct S { int w, x, y, z; };1205struct T { int r; struct S s; };1206void bar (struct S, int);1207void foo (int a, struct T b)1208{1209 struct S *c = 0;1210 if (a)1211 c = &b.s;1212 bar (*c, a);1213}1214 1215//===---------------------------------------------------------------------===//1216 1217simplifylibcalls should do several optimizations for strspn/strcspn:1218 1219strcspn(x, "a") -> inlined loop for up to 3 letters (similarly for strspn):1220 1221size_t __strcspn_c3 (__const char *__s, int __reject1, int __reject2,1222 int __reject3) {1223 register size_t __result = 0;1224 while (__s[__result] != '\0' && __s[__result] != __reject1 &&1225 __s[__result] != __reject2 && __s[__result] != __reject3)1226 ++__result;1227 return __result;1228}1229 1230This should turn into a switch on the character. See PR3253 for some notes on1231codegen.1232 1233456.hmmer apparently uses strcspn and strspn a lot. 471.omnetpp uses strspn.1234 1235//===---------------------------------------------------------------------===//1236 1237simplifylibcalls should turn these snprintf idioms into memcpy (GCC PR47917)1238 1239char buf1[6], buf2[6], buf3[4], buf4[4];1240int i;1241 1242int foo (void) {1243 int ret = snprintf (buf1, sizeof buf1, "abcde");1244 ret += snprintf (buf2, sizeof buf2, "abcdef") * 16;1245 ret += snprintf (buf3, sizeof buf3, "%s", i++ < 6 ? "abc" : "def") * 256;1246 ret += snprintf (buf4, sizeof buf4, "%s", i++ > 10 ? "abcde" : "defgh")*4096;1247 return ret;1248}1249 1250//===---------------------------------------------------------------------===//1251 1252"gas" uses this idiom:1253 else if (strchr ("+-/*%|&^:[]()~", *intel_parser.op_string))1254..1255 else if (strchr ("<>", *intel_parser.op_string)1256 1257Those should be turned into a switch. SimplifyLibCalls only gets the second1258case.1259 1260//===---------------------------------------------------------------------===//1261 1262252.eon contains this interesting code:1263 1264 %3072 = getelementptr [100 x i8]* %tempString, i32 0, i32 01265 %3073 = call i8* @strcpy(i8* %3072, i8* %3071) nounwind1266 %strlen = call i32 @strlen(i8* %3072) ; uses = 11267 %endptr = getelementptr [100 x i8]* %tempString, i32 0, i32 %strlen1268 call void @llvm.memcpy.i32(i8* %endptr, 1269 i8* getelementptr ([5 x i8]* @"\01LC42", i32 0, i32 0), i32 5, i32 1)1270 %3074 = call i32 @strlen(i8* %endptr) nounwind readonly 1271 1272This is interesting for a couple reasons. First, in this:1273 1274The memcpy+strlen strlen can be replaced with:1275 1276 %3074 = call i32 @strlen([5 x i8]* @"\01LC42") nounwind readonly 1277 1278Because the destination was just copied into the specified memory buffer. This,1279in turn, can be constant folded to "4".1280 1281In other code, it contains:1282 1283 %endptr6978 = bitcast i8* %endptr69 to i32* 1284 store i32 7107374, i32* %endptr6978, align 11285 %3167 = call i32 @strlen(i8* %endptr69) nounwind readonly 1286 1287Which could also be constant folded. Whatever is producing this should probably1288be fixed to leave this as a memcpy from a string.1289 1290Further, eon also has an interesting partially redundant strlen call:1291 1292bb8: ; preds = %_ZN18eonImageCalculatorC1Ev.exit1293 %682 = getelementptr i8** %argv, i32 6 ; <i8**> [#uses=2]1294 %683 = load i8** %682, align 4 ; <i8*> [#uses=4]1295 %684 = load i8* %683, align 1 ; <i8> [#uses=1]1296 %685 = icmp eq i8 %684, 0 ; <i1> [#uses=1]1297 br i1 %685, label %bb10, label %bb91298 1299bb9: ; preds = %bb81300 %686 = call i32 @strlen(i8* %683) nounwind readonly 1301 %687 = icmp ugt i32 %686, 254 ; <i1> [#uses=1]1302 br i1 %687, label %bb10, label %bb111303 1304bb10: ; preds = %bb9, %bb81305 %688 = call i32 @strlen(i8* %683) nounwind readonly 1306 1307This could be eliminated by doing the strlen once in bb8, saving code size and1308improving perf on the bb8->9->10 path.1309 1310//===---------------------------------------------------------------------===//1311 1312I see an interesting fully redundant call to strlen left in 186.crafty:InputMove1313which looks like:1314 %movetext11 = getelementptr [128 x i8]* %movetext, i32 0, i32 0 1315 1316 1317bb62: ; preds = %bb55, %bb531318 %promote.0 = phi i32 [ %169, %bb55 ], [ 0, %bb53 ] 1319 %171 = call i32 @strlen(i8* %movetext11) nounwind readonly align 11320 %172 = add i32 %171, -1 ; <i32> [#uses=1]1321 %173 = getelementptr [128 x i8]* %movetext, i32 0, i32 %172 1322 1323... no stores ...1324 br i1 %or.cond, label %bb65, label %bb721325 1326bb65: ; preds = %bb621327 store i8 0, i8* %173, align 11328 br label %bb721329 1330bb72: ; preds = %bb65, %bb621331 %trank.1 = phi i32 [ %176, %bb65 ], [ -1, %bb62 ] 1332 %177 = call i32 @strlen(i8* %movetext11) nounwind readonly align 11333 1334Note that on the bb62->bb72 path, that the %177 strlen call is partially1335redundant with the %171 call. At worst, we could shove the %177 strlen call1336up into the bb65 block moving it out of the bb62->bb72 path. However, note1337that bb65 stores to the string, zeroing out the last byte. This means that on1338that path the value of %177 is actually just %171-1. A sub is cheaper than a1339strlen!1340 1341This pattern repeats several times, basically doing:1342 1343 A = strlen(P);1344 P[A-1] = 0;1345 B = strlen(P);1346 where it is "obvious" that B = A-1.1347 1348//===---------------------------------------------------------------------===//1349 1350186.crafty has this interesting pattern with the "out.4543" variable:1351 1352call void @llvm.memcpy.i32(1353 i8* getelementptr ([10 x i8]* @out.4543, i32 0, i32 0),1354 i8* getelementptr ([7 x i8]* @"\01LC28700", i32 0, i32 0), i32 7, i32 1) 1355%101 = call@printf(i8* ... @out.4543, i32 0, i32 0)) nounwind 1356 1357It is basically doing:1358 1359 memcpy(globalarray, "string");1360 printf(..., globalarray);1361 1362Anyway, by knowing that printf just reads the memory and forward substituting1363the string directly into the printf, this eliminates reads from globalarray.1364Since this pattern occurs frequently in crafty (due to the "DisplayTime" and1365other similar functions) there are many stores to "out". Once all the printfs1366stop using "out", all that is left is the memcpy's into it. This should allow1367globalopt to remove the "stored only" global.1368 1369//===---------------------------------------------------------------------===//1370 1371This code:1372 1373define inreg i32 @foo(i8* inreg %p) nounwind {1374 %tmp0 = load i8* %p1375 %tmp1 = ashr i8 %tmp0, 51376 %tmp2 = sext i8 %tmp1 to i321377 ret i32 %tmp21378}1379 1380could be dagcombine'd to a sign-extending load with a shift.1381For example, on x86 this currently gets this:1382 1383 movb (%eax), %al1384 sarb $5, %al1385 movsbl %al, %eax1386 1387while it could get this:1388 1389 movsbl (%eax), %eax1390 sarl $5, %eax1391 1392//===---------------------------------------------------------------------===//1393 1394GCC PR31029:1395 1396int test(int x) { return 1-x == x; } // --> return false1397int test2(int x) { return 2-x == x; } // --> return x == 1 ?1398 1399Always foldable for odd constants, what is the rule for even?1400 1401//===---------------------------------------------------------------------===//1402 1403PR 3381: GEP to field of size 0 inside a struct could be turned into GEP1404for next field in struct (which is at same address).1405 1406For example: store of float into { {{}}, float } could be turned into a store to1407the float directly.1408 1409//===---------------------------------------------------------------------===//1410 1411The arg promotion pass should make use of nocapture to make its alias analysis1412stuff much more precise.1413 1414//===---------------------------------------------------------------------===//1415 1416The following functions should be optimized to use a select instead of a1417branch (from gcc PR40072):1418 1419char char_int(int m) {if(m>7) return 0; return m;}1420int int_char(char m) {if(m>7) return 0; return m;}1421 1422//===---------------------------------------------------------------------===//1423 1424int func(int a, int b) { if (a & 0x80) b |= 0x80; else b &= ~0x80; return b; }1425 1426Generates this:1427 1428define i32 @func(i32 %a, i32 %b) nounwind readnone ssp {1429entry:1430 %0 = and i32 %a, 128 ; <i32> [#uses=1]1431 %1 = icmp eq i32 %0, 0 ; <i1> [#uses=1]1432 %2 = or i32 %b, 128 ; <i32> [#uses=1]1433 %3 = and i32 %b, -129 ; <i32> [#uses=1]1434 %b_addr.0 = select i1 %1, i32 %3, i32 %2 ; <i32> [#uses=1]1435 ret i32 %b_addr.01436}1437 1438However, it's functionally equivalent to:1439 1440 b = (b & ~0x80) | (a & 0x80);1441 1442Which generates this:1443 1444define i32 @func(i32 %a, i32 %b) nounwind readnone ssp {1445entry:1446 %0 = and i32 %b, -129 ; <i32> [#uses=1]1447 %1 = and i32 %a, 128 ; <i32> [#uses=1]1448 %2 = or i32 %0, %1 ; <i32> [#uses=1]1449 ret i32 %21450}1451 1452This can be generalized for other forms:1453 1454 b = (b & ~0x80) | (a & 0x40) << 1;1455 1456//===---------------------------------------------------------------------===//1457 1458These two functions produce different code. They shouldn't:1459 1460#include <stdint.h>1461 1462uint8_t p1(uint8_t b, uint8_t a) {1463 b = (b & ~0xc0) | (a & 0xc0);1464 return (b);1465}1466 1467uint8_t p2(uint8_t b, uint8_t a) {1468 b = (b & ~0x40) | (a & 0x40);1469 b = (b & ~0x80) | (a & 0x80);1470 return (b);1471}1472 1473define zeroext i8 @p1(i8 zeroext %b, i8 zeroext %a) nounwind readnone ssp {1474entry:1475 %0 = and i8 %b, 63 ; <i8> [#uses=1]1476 %1 = and i8 %a, -64 ; <i8> [#uses=1]1477 %2 = or i8 %1, %0 ; <i8> [#uses=1]1478 ret i8 %21479}1480 1481define zeroext i8 @p2(i8 zeroext %b, i8 zeroext %a) nounwind readnone ssp {1482entry:1483 %0 = and i8 %b, 63 ; <i8> [#uses=1]1484 %.masked = and i8 %a, 64 ; <i8> [#uses=1]1485 %1 = and i8 %a, -128 ; <i8> [#uses=1]1486 %2 = or i8 %1, %0 ; <i8> [#uses=1]1487 %3 = or i8 %2, %.masked ; <i8> [#uses=1]1488 ret i8 %31489}1490 1491//===---------------------------------------------------------------------===//1492 1493IPSCCP does not currently propagate argument dependent constants through1494functions where it does not not all of the callers. This includes functions1495with normal external linkage as well as templates, C99 inline functions etc.1496Specifically, it does nothing to:1497 1498define i32 @test(i32 %x, i32 %y, i32 %z) nounwind {1499entry:1500 %0 = add nsw i32 %y, %z 1501 %1 = mul i32 %0, %x 1502 %2 = mul i32 %y, %z 1503 %3 = add nsw i32 %1, %2 1504 ret i32 %31505}1506 1507define i32 @test2() nounwind {1508entry:1509 %0 = call i32 @test(i32 1, i32 2, i32 4) nounwind1510 ret i32 %01511}1512 1513It would be interesting extend IPSCCP to be able to handle simple cases like1514this, where all of the arguments to a call are constant. Because IPSCCP runs1515before inlining, trivial templates and inline functions are not yet inlined.1516The results for a function + set of constant arguments should be memoized in a1517map.1518 1519//===---------------------------------------------------------------------===//1520 1521The libcall constant folding stuff should be moved out of SimplifyLibcalls into1522libanalysis' constantfolding logic. This would allow IPSCCP to be able to1523handle simple things like this:1524 1525static int foo(const char *X) { return strlen(X); }1526int bar() { return foo("abcd"); }1527 1528//===---------------------------------------------------------------------===//1529 1530function-attrs doesn't know much about memcpy/memset. This function should be1531marked readnone rather than readonly, since it only twiddles local memory, but1532function-attrs doesn't handle memset/memcpy/memmove aggressively:1533 1534struct X { int *p; int *q; };1535int foo() {1536 int i = 0, j = 1;1537 struct X x, y;1538 int **p;1539 y.p = &i;1540 x.q = &j;1541 p = __builtin_memcpy (&x, &y, sizeof (int *));1542 return **p;1543}1544 1545This can be seen at:1546$ clang t.c -S -o - -mkernel -O0 -emit-llvm | opt -function-attrs -S1547 1548 1549//===---------------------------------------------------------------------===//1550 1551Missed instcombine transformation:1552define i1 @a(i32 %x) nounwind readnone {1553entry:1554 %cmp = icmp eq i32 %x, 301555 %sub = add i32 %x, -301556 %cmp2 = icmp ugt i32 %sub, 91557 %or = or i1 %cmp, %cmp21558 ret i1 %or1559}1560This should be optimized to a single compare. Testcase derived from gcc.1561 1562//===---------------------------------------------------------------------===//1563 1564Missed instcombine or reassociate transformation:1565int a(int a, int b) { return (a==12)&(b>47)&(b<58); }1566 1567The sgt and slt should be combined into a single comparison. Testcase derived1568from gcc.1569 1570//===---------------------------------------------------------------------===//1571 1572Missed instcombine transformation:1573 1574 %382 = srem i32 %tmp14.i, 64 ; [#uses=1]1575 %383 = zext i32 %382 to i64 ; [#uses=1]1576 %384 = shl i64 %381, %383 ; [#uses=1]1577 %385 = icmp slt i32 %tmp14.i, 64 ; [#uses=1]1578 1579The srem can be transformed to an and because if %tmp14.i is negative, the1580shift is undefined. Testcase derived from 403.gcc.1581 1582//===---------------------------------------------------------------------===//1583 1584This is a range comparison on a divided result (from 403.gcc):1585 1586 %1337 = sdiv i32 %1336, 8 ; [#uses=1]1587 %.off.i208 = add i32 %1336, 7 ; [#uses=1]1588 %1338 = icmp ult i32 %.off.i208, 15 ; [#uses=1]1589 1590We already catch this (removing the sdiv) if there isn't an add, we should1591handle the 'add' as well. This is a common idiom with it's builtin_alloca code.1592C testcase:1593 1594int a(int x) { return (unsigned)(x/16+7) < 15; }1595 1596Another similar case involves truncations on 64-bit targets:1597 1598 %361 = sdiv i64 %.046, 8 ; [#uses=1]1599 %362 = trunc i64 %361 to i32 ; [#uses=2]1600...1601 %367 = icmp eq i32 %362, 0 ; [#uses=1]1602 1603//===---------------------------------------------------------------------===//1604 1605Missed instcombine/dagcombine transformation:1606define void @lshift_lt(i8 zeroext %a) nounwind {1607entry:1608 %conv = zext i8 %a to i321609 %shl = shl i32 %conv, 31610 %cmp = icmp ult i32 %shl, 331611 br i1 %cmp, label %if.then, label %if.end1612 1613if.then:1614 tail call void @bar() nounwind1615 ret void1616 1617if.end:1618 ret void1619}1620declare void @bar() nounwind1621 1622The shift should be eliminated. Testcase derived from gcc.1623 1624//===---------------------------------------------------------------------===//1625 1626These compile into different code, one gets recognized as a switch and the1627other doesn't due to phase ordering issues (PR6212):1628 1629int test1(int mainType, int subType) {1630 if (mainType == 7)1631 subType = 4;1632 else if (mainType == 9)1633 subType = 6;1634 else if (mainType == 11)1635 subType = 9;1636 return subType;1637}1638 1639int test2(int mainType, int subType) {1640 if (mainType == 7)1641 subType = 4;1642 if (mainType == 9)1643 subType = 6;1644 if (mainType == 11)1645 subType = 9;1646 return subType;1647}1648 1649//===---------------------------------------------------------------------===//1650 1651The following test case (from PR6576):1652 1653define i32 @mul(i32 %a, i32 %b) nounwind readnone {1654entry:1655 %cond1 = icmp eq i32 %b, 0 ; <i1> [#uses=1]1656 br i1 %cond1, label %exit, label %bb.nph1657bb.nph: ; preds = %entry1658 %tmp = mul i32 %b, %a ; <i32> [#uses=1]1659 ret i32 %tmp1660exit: ; preds = %entry1661 ret i32 01662}1663 1664could be reduced to:1665 1666define i32 @mul(i32 %a, i32 %b) nounwind readnone {1667entry:1668 %tmp = mul i32 %b, %a1669 ret i32 %tmp1670}1671 1672//===---------------------------------------------------------------------===//1673 1674We should use DSE + llvm.lifetime.end to delete dead vtable pointer updates.1675See GCC PR349491676 1677Another interesting case is that something related could be used for variables1678that go const after their ctor has finished. In these cases, globalopt (which1679can statically run the constructor) could mark the global const (so it gets put1680in the readonly section). A testcase would be:1681 1682#include <complex>1683using namespace std;1684const complex<char> should_be_in_rodata (42,-42);1685complex<char> should_be_in_data (42,-42);1686complex<char> should_be_in_bss;1687 1688Where we currently evaluate the ctors but the globals don't become const because1689the optimizer doesn't know they "become const" after the ctor is done. See1690GCC PR4131 for more examples.1691 1692//===---------------------------------------------------------------------===//1693 1694In this code:1695 1696long foo(long x) {1697 return x > 1 ? x : 1;1698}1699 1700LLVM emits a comparison with 1 instead of 0. 0 would be equivalent1701and cheaper on most targets.1702 1703LLVM prefers comparisons with zero over non-zero in general, but in this1704case it choses instead to keep the max operation obvious.1705 1706//===---------------------------------------------------------------------===//1707 1708define void @a(i32 %x) nounwind {1709entry:1710 switch i32 %x, label %if.end [1711 i32 0, label %if.then1712 i32 1, label %if.then1713 i32 2, label %if.then1714 i32 3, label %if.then1715 i32 5, label %if.then1716 ]1717if.then:1718 tail call void @foo() nounwind1719 ret void1720if.end:1721 ret void1722}1723declare void @foo()1724 1725Generated code on x86-64 (other platforms give similar results):1726a:1727 cmpl $5, %edi1728 ja LBB2_21729 cmpl $4, %edi1730 jne LBB2_31731.LBB0_2:1732 ret1733.LBB0_3:1734 jmp foo # TAILCALL1735 1736If we wanted to be really clever, we could simplify the whole thing to1737something like the following, which eliminates a branch:1738 xorl $1, %edi1739 cmpl $4, %edi1740 ja .LBB0_21741 ret1742.LBB0_2:1743 jmp foo # TAILCALL1744 1745//===---------------------------------------------------------------------===//1746 1747We compile this:1748 1749int foo(int a) { return (a & (~15)) / 16; }1750 1751Into:1752 1753define i32 @foo(i32 %a) nounwind readnone ssp {1754entry:1755 %and = and i32 %a, -161756 %div = sdiv i32 %and, 161757 ret i32 %div1758}1759 1760but this code (X & -A)/A is X >> log2(A) when A is a power of 2, so this case1761should be instcombined into just "a >> 4".1762 1763We do get this at the codegen level, so something knows about it, but 1764instcombine should catch it earlier:1765 1766_foo: ## @foo1767## %bb.0: ## %entry1768 movl %edi, %eax1769 sarl $4, %eax1770 ret1771 1772//===---------------------------------------------------------------------===//1773 1774This code (from GCC PR28685):1775 1776int test(int a, int b) {1777 int lt = a < b;1778 int eq = a == b;1779 if (lt)1780 return 1;1781 return eq;1782}1783 1784Is compiled to:1785 1786define i32 @test(i32 %a, i32 %b) nounwind readnone ssp {1787entry:1788 %cmp = icmp slt i32 %a, %b1789 br i1 %cmp, label %return, label %if.end1790 1791if.end: ; preds = %entry1792 %cmp5 = icmp eq i32 %a, %b1793 %conv6 = zext i1 %cmp5 to i321794 ret i32 %conv61795 1796return: ; preds = %entry1797 ret i32 11798}1799 1800it could be:1801 1802define i32 @test__(i32 %a, i32 %b) nounwind readnone ssp {1803entry:1804 %0 = icmp sle i32 %a, %b1805 %retval = zext i1 %0 to i321806 ret i32 %retval1807}1808 1809//===---------------------------------------------------------------------===//1810 1811This code can be seen in viterbi:1812 1813 %64 = call noalias i8* @malloc(i64 %62) nounwind1814...1815 %67 = call i64 @llvm.objectsize.i64(i8* %64, i1 false) nounwind1816 %68 = call i8* @__memset_chk(i8* %64, i32 0, i64 %62, i64 %67) nounwind1817 1818llvm.objectsize.i64 should be taught about malloc/calloc, allowing it to1819fold to %62. This is a security win (overflows of malloc will get caught)1820and also a performance win by exposing more memsets to the optimizer.1821 1822This occurs several times in viterbi.1823 1824Note that this would change the semantics of @llvm.objectsize which by its1825current definition always folds to a constant. We also should make sure that1826we remove checking in code like1827 1828 char *p = malloc(strlen(s)+1);1829 __strcpy_chk(p, s, __builtin_object_size(p, 0));1830 1831//===---------------------------------------------------------------------===//1832 1833clang -O3 currently compiles this code1834 1835int g(unsigned int a) {1836 unsigned int c[100];1837 c[10] = a;1838 c[11] = a;1839 unsigned int b = c[10] + c[11];1840 if(b > a*2) a = 4;1841 else a = 8;1842 return a + 7;1843}1844 1845into1846 1847define i32 @g(i32 a) nounwind readnone {1848 %add = shl i32 %a, 11849 %mul = shl i32 %a, 11850 %cmp = icmp ugt i32 %add, %mul1851 %a.addr.0 = select i1 %cmp, i32 11, i32 151852 ret i32 %a.addr.01853}1854 1855The icmp should fold to false. This CSE opportunity is only available1856after GVN and InstCombine have run.1857 1858//===---------------------------------------------------------------------===//1859 1860memcpyopt should turn this:1861 1862define i8* @test10(i32 %x) {1863 %alloc = call noalias i8* @malloc(i32 %x) nounwind1864 call void @llvm.memset.p0i8.i32(i8* %alloc, i8 0, i32 %x, i32 1, i1 false)1865 ret i8* %alloc1866}1867 1868into a call to calloc. We should make sure that we analyze calloc as1869aggressively as malloc though.1870 1871//===---------------------------------------------------------------------===//1872 1873clang -O3 doesn't optimize this:1874 1875void f1(int* begin, int* end) {1876 std::fill(begin, end, 0);1877}1878 1879into a memset. This is PR8942.1880 1881//===---------------------------------------------------------------------===//1882 1883clang -O3 -fno-exceptions currently compiles this code:1884 1885void f(int N) {1886 std::vector<int> v(N);1887 1888 extern void sink(void*); sink(&v);1889}1890 1891into1892 1893define void @_Z1fi(i32 %N) nounwind {1894entry:1895 %v2 = alloca [3 x i32*], align 81896 %v2.sub = getelementptr inbounds [3 x i32*]* %v2, i64 0, i64 01897 %tmpcast = bitcast [3 x i32*]* %v2 to %"class.std::vector"*1898 %conv = sext i32 %N to i641899 store i32* null, i32** %v2.sub, align 8, !tbaa !01900 %tmp3.i.i.i.i.i = getelementptr inbounds [3 x i32*]* %v2, i64 0, i64 11901 store i32* null, i32** %tmp3.i.i.i.i.i, align 8, !tbaa !01902 %tmp4.i.i.i.i.i = getelementptr inbounds [3 x i32*]* %v2, i64 0, i64 21903 store i32* null, i32** %tmp4.i.i.i.i.i, align 8, !tbaa !01904 %cmp.i.i.i.i = icmp eq i32 %N, 01905 br i1 %cmp.i.i.i.i, label %_ZNSt12_Vector_baseIiSaIiEEC2EmRKS0_.exit.thread.i.i, label %cond.true.i.i.i.i1906 1907_ZNSt12_Vector_baseIiSaIiEEC2EmRKS0_.exit.thread.i.i: ; preds = %entry1908 store i32* null, i32** %v2.sub, align 8, !tbaa !01909 store i32* null, i32** %tmp3.i.i.i.i.i, align 8, !tbaa !01910 %add.ptr.i5.i.i = getelementptr inbounds i32* null, i64 %conv1911 store i32* %add.ptr.i5.i.i, i32** %tmp4.i.i.i.i.i, align 8, !tbaa !01912 br label %_ZNSt6vectorIiSaIiEEC1EmRKiRKS0_.exit1913 1914cond.true.i.i.i.i: ; preds = %entry1915 %cmp.i.i.i.i.i = icmp slt i32 %N, 01916 br i1 %cmp.i.i.i.i.i, label %if.then.i.i.i.i.i, label %_ZNSt12_Vector_baseIiSaIiEEC2EmRKS0_.exit.i.i1917 1918if.then.i.i.i.i.i: ; preds = %cond.true.i.i.i.i1919 call void @_ZSt17__throw_bad_allocv() noreturn nounwind1920 unreachable1921 1922_ZNSt12_Vector_baseIiSaIiEEC2EmRKS0_.exit.i.i: ; preds = %cond.true.i.i.i.i1923 %mul.i.i.i.i.i = shl i64 %conv, 21924 %call3.i.i.i.i.i = call noalias i8* @_Znwm(i64 %mul.i.i.i.i.i) nounwind1925 %0 = bitcast i8* %call3.i.i.i.i.i to i32*1926 store i32* %0, i32** %v2.sub, align 8, !tbaa !01927 store i32* %0, i32** %tmp3.i.i.i.i.i, align 8, !tbaa !01928 %add.ptr.i.i.i = getelementptr inbounds i32* %0, i64 %conv1929 store i32* %add.ptr.i.i.i, i32** %tmp4.i.i.i.i.i, align 8, !tbaa !01930 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)1931 br label %_ZNSt6vectorIiSaIiEEC1EmRKiRKS0_.exit1932 1933This is just the handling the construction of the vector. Most surprising here1934is the fact that all three null stores in %entry are dead (because we do no1935cross-block DSE).1936 1937Also surprising is that %conv isn't simplified to 0 in %....exit.thread.i.i.1938This is a because the client of LazyValueInfo doesn't simplify all instruction1939operands, just selected ones.1940 1941//===---------------------------------------------------------------------===//1942 1943clang -O3 -fno-exceptions currently compiles this code:1944 1945void f(char* a, int n) {1946 __builtin_memset(a, 0, n);1947 for (int i = 0; i < n; ++i)1948 a[i] = 0;1949}1950 1951into:1952 1953define void @_Z1fPci(i8* nocapture %a, i32 %n) nounwind {1954entry:1955 %conv = sext i32 %n to i641956 tail call void @llvm.memset.p0i8.i64(i8* %a, i8 0, i64 %conv, i32 1, i1 false)1957 %cmp8 = icmp sgt i32 %n, 01958 br i1 %cmp8, label %for.body.lr.ph, label %for.end1959 1960for.body.lr.ph: ; preds = %entry1961 %tmp10 = add i32 %n, -11962 %tmp11 = zext i32 %tmp10 to i641963 %tmp12 = add i64 %tmp11, 11964 call void @llvm.memset.p0i8.i64(i8* %a, i8 0, i64 %tmp12, i32 1, i1 false)1965 ret void1966 1967for.end: ; preds = %entry1968 ret void1969}1970 1971This shouldn't need the ((zext (%n - 1)) + 1) game, and it should ideally fold1972the two memset's together.1973 1974The issue with the addition only occurs in 64-bit mode, and appears to be at1975least partially caused by Scalar Evolution not keeping its cache updated: it1976returns the "wrong" result immediately after indvars runs, but figures out the1977expected result if it is run from scratch on IR resulting from running indvars.1978 1979//===---------------------------------------------------------------------===//1980 1981clang -O3 -fno-exceptions currently compiles this code:1982 1983struct S {1984 unsigned short m1, m2;1985 unsigned char m3, m4;1986};1987 1988void f(int N) {1989 std::vector<S> v(N);1990 extern void sink(void*); sink(&v);1991}1992 1993into poor code for zero-initializing 'v' when N is >0. The problem is that1994S is only 6 bytes, but each element is 8 byte-aligned. We generate a loop and19954 stores on each iteration. If the struct were 8 bytes, this gets turned into1996a memset.1997 1998In order to handle this we have to:1999 A) Teach clang to generate metadata for memsets of structs that have holes in2000 them.2001 B) Teach clang to use such a memset for zero init of this struct (since it has2002 a hole), instead of doing elementwise zeroing.2003 2004//===---------------------------------------------------------------------===//2005 2006clang -O3 currently compiles this code:2007 2008extern const int magic;2009double f() { return 0.0 * magic; }2010 2011into2012 2013@magic = external constant i322014 2015define double @_Z1fv() nounwind readnone {2016entry:2017 %tmp = load i32* @magic, align 4, !tbaa !02018 %conv = sitofp i32 %tmp to double2019 %mul = fmul double %conv, 0.000000e+002020 ret double %mul2021}2022 2023We should be able to fold away this fmul to 0.0. More generally, fmul(x,0.0)2024can be folded to 0.0 if we can prove that the LHS is not -0.0, not a NaN, and2025not an INF. The CannotBeNegativeZero predicate in value tracking should be2026extended to support general "fpclassify" operations that can return 2027yes/no/unknown for each of these predicates.2028 2029In this predicate, we know that uitofp is trivially never NaN or -0.0, and2030we know that it isn't +/-Inf if the floating point type has enough exponent bits2031to represent the largest integer value as < inf.2032 2033//===---------------------------------------------------------------------===//2034 2035When optimizing a transformation that can change the sign of 0.0 (such as the20360.0*val -> 0.0 transformation above), it might be provable that the sign of the2037expression doesn't matter. For example, by the above rules, we can't transform2038fmul(sitofp(x), 0.0) into 0.0, because x might be -1 and the result of the2039expression is defined to be -0.0.2040 2041If we look at the uses of the fmul for example, we might be able to prove that2042all uses don't care about the sign of zero. For example, if we have:2043 2044 fadd(fmul(sitofp(x), 0.0), 2.0)2045 2046Since we know that x+2.0 doesn't care about the sign of any zeros in X, we can2047transform the fmul to 0.0, and then the fadd to 2.0.2048 2049//===---------------------------------------------------------------------===//2050 2051We should enhance memcpy/memcpy/memset to allow a metadata node on them2052indicating that some bytes of the transfer are undefined. This is useful for2053frontends like clang when lowering struct copies, when some elements of the2054struct are undefined. Consider something like this:2055 2056struct x {2057 char a;2058 int b[4];2059};2060void foo(struct x*P);2061struct x testfunc() {2062 struct x V1, V2;2063 foo(&V1);2064 V2 = V1;2065 2066 return V2;2067}2068 2069We currently compile this to:2070$ clang t.c -S -o - -O0 -emit-llvm | opt -sroa -S2071 2072 2073%struct.x = type { i8, [4 x i32] }2074 2075define void @testfunc(%struct.x* sret %agg.result) nounwind ssp {2076entry:2077 %V1 = alloca %struct.x, align 42078 call void @foo(%struct.x* %V1)2079 %tmp1 = bitcast %struct.x* %V1 to i8*2080 %0 = bitcast %struct.x* %V1 to i160*2081 %srcval1 = load i160* %0, align 42082 %tmp2 = bitcast %struct.x* %agg.result to i8*2083 %1 = bitcast %struct.x* %agg.result to i160*2084 store i160 %srcval1, i160* %1, align 42085 ret void2086}2087 2088This happens because SRoA sees that the temp alloca has is being memcpy'd into2089and out of and it has holes and it has to be conservative. If we knew about the2090holes, then this could be much much better.2091 2092Having information about these holes would also improve memcpy (etc) lowering at2093llc time when it gets inlined, because we can use smaller transfers. This also2094avoids partial register stalls in some important cases.2095 2096//===---------------------------------------------------------------------===//2097 2098We don't fold (icmp (add) (add)) unless the two adds only have a single use.2099There are a lot of cases that we're refusing to fold in (e.g.) 256.bzip2, for2100example:2101 2102 %indvar.next90 = add i64 %indvar89, 1 ;; Has 2 uses2103 %tmp96 = add i64 %tmp95, 1 ;; Has 1 use2104 %exitcond97 = icmp eq i64 %indvar.next90, %tmp962105 2106We don't fold this because we don't want to introduce an overlapped live range2107of the ivar. However if we can make this more aggressive without causing2108performance issues in two ways:2109 21101. If *either* the LHS or RHS has a single use, we can definitely do the2111 transformation. In the overlapping liverange case we're trading one register2112 use for one fewer operation, which is a reasonable trade. Before doing this2113 we should verify that the llc output actually shrinks for some benchmarks.21142. If both ops have multiple uses, we can still fold it if the operations are2115 both sinkable to *after* the icmp (e.g. in a subsequent block) which doesn't2116 increase register pressure.2117 2118There are a ton of icmp's we aren't simplifying because of the reg pressure2119concern. Care is warranted here though because many of these are induction2120variables and other cases that matter a lot to performance, like the above.2121Here's a blob of code that you can drop into the bottom of visitICmp to see some2122missed cases:2123 2124 { Value *A, *B, *C, *D;2125 if (match(Op0, m_Add(m_Value(A), m_Value(B))) && 2126 match(Op1, m_Add(m_Value(C), m_Value(D))) &&2127 (A == C || A == D || B == C || B == D)) {2128 errs() << "OP0 = " << *Op0 << " U=" << Op0->getNumUses() << "\n";2129 errs() << "OP1 = " << *Op1 << " U=" << Op1->getNumUses() << "\n";2130 errs() << "CMP = " << I << "\n\n";2131 }2132 }2133 2134//===---------------------------------------------------------------------===//2135 2136define i1 @test1(i32 %x) nounwind {2137 %and = and i32 %x, 32138 %cmp = icmp ult i32 %and, 22139 ret i1 %cmp2140}2141 2142Can be folded to (x & 2) == 0.2143 2144define i1 @test2(i32 %x) nounwind {2145 %and = and i32 %x, 32146 %cmp = icmp ugt i32 %and, 12147 ret i1 %cmp2148}2149 2150Can be folded to (x & 2) != 0.2151 2152SimplifyDemandedBits shrinks the "and" constant to 2 but instcombine misses the2153icmp transform.2154 2155//===---------------------------------------------------------------------===//2156 2157This code:2158 2159typedef struct {2160int f1:1;2161int f2:1;2162int f3:1;2163int f4:29;2164} t1;2165 2166typedef struct {2167int f1:1;2168int f2:1;2169int f3:30;2170} t2;2171 2172t1 s1;2173t2 s2;2174 2175void func1(void)2176{2177s1.f1 = s2.f1;2178s1.f2 = s2.f2;2179}2180 2181Compiles into this IR (on x86-64 at least):2182 2183%struct.t1 = type { i8, [3 x i8] }2184@s2 = global %struct.t1 zeroinitializer, align 42185@s1 = global %struct.t1 zeroinitializer, align 42186define void @func1() nounwind ssp noredzone {2187entry:2188 %0 = load i32* bitcast (%struct.t1* @s2 to i32*), align 42189 %bf.val.sext5 = and i32 %0, 12190 %1 = load i32* bitcast (%struct.t1* @s1 to i32*), align 42191 %2 = and i32 %1, -42192 %3 = or i32 %2, %bf.val.sext52193 %bf.val.sext26 = and i32 %0, 22194 %4 = or i32 %3, %bf.val.sext262195 store i32 %4, i32* bitcast (%struct.t1* @s1 to i32*), align 42196 ret void2197}2198 2199The two or/and's should be merged into one each.2200 2201//===---------------------------------------------------------------------===//2202 2203Machine level code hoisting can be useful in some cases. For example, PR94082204is about:2205 2206typedef union {2207 void (*f1)(int);2208 void (*f2)(long);2209} funcs;2210 2211void foo(funcs f, int which) {2212 int a = 5;2213 if (which) {2214 f.f1(a);2215 } else {2216 f.f2(a);2217 }2218}2219 2220which we compile to:2221 2222foo: # @foo2223# %bb.0: # %entry2224 pushq %rbp2225 movq %rsp, %rbp2226 testl %esi, %esi2227 movq %rdi, %rax2228 je .LBB0_22229# %bb.1: # %if.then2230 movl $5, %edi2231 callq *%rax2232 popq %rbp2233 ret2234.LBB0_2: # %if.else2235 movl $5, %edi2236 callq *%rax2237 popq %rbp2238 ret2239 2240Note that bb1 and bb2 are the same. This doesn't happen at the IR level2241because one call is passing an i32 and the other is passing an i64.2242 2243//===---------------------------------------------------------------------===//2244 2245I see this sort of pattern in 176.gcc in a few places (e.g. the start of2246store_bit_field). The rem should be replaced with a multiply and subtract:2247 2248 %3 = sdiv i32 %A, %B2249 %4 = srem i32 %A, %B2250 2251Similarly for udiv/urem. Note that this shouldn't be done on X86 or ARM,2252which can do this in a single operation (instruction or libcall). It is2253probably best to do this in the code generator.2254 2255//===---------------------------------------------------------------------===//2256 2257unsigned foo(unsigned x, unsigned y) { return (x & y) == 0 || x == 0; }2258should fold to (x & y) == 0.2259 2260//===---------------------------------------------------------------------===//2261 2262unsigned foo(unsigned x, unsigned y) { return x > y && x != 0; }2263should fold to x > y.2264 2265//===---------------------------------------------------------------------===//2266