lib/Target/README.txt

   1 Target Independent Opportunities:
   2
   3 //===---------------------------------------------------------------------===//
   4
   5 With the recent changes to make the implicit def/use set explicit in
   6 machineinstrs, we should change the target descriptions for 'call' instructions
   7 so that the .td files don't list all the call-clobbered registers as implicit
   8 defs.  Instead, these should be added by the code generator (e.g. on the dag).
   9
  10 This has a number of uses:
  11
  12 1. PPC32/64 and X86 32/64 can avoid having multiple copies of call instructions
  13    for their different impdef sets.
  14 2. Targets with multiple calling convs (e.g. x86) which have different clobber
  15    sets don't need copies of call instructions.
  16 3. 'Interprocedural register allocation' can be done to reduce the clobber sets
  17    of calls.
  18
  19 //===---------------------------------------------------------------------===//
  20
  21 Make the PPC branch selector target independant
  22
  23 //===---------------------------------------------------------------------===//
  24
  25 Get the C front-end to expand hypot(x,y) -> llvm.sqrt(x*x+y*y) when errno and
  26 precision don't matter (ffastmath).  Misc/mandel will like this. :)  This isn't
  27 safe in general, even on darwin.  See the libm implementation of hypot for
  28 examples (which special case when x/y are exactly zero to get signed zeros etc
  29 right).
  30
  31 //===---------------------------------------------------------------------===//
  32
  33 Solve this DAG isel folding deficiency:
  34
  35 int X, Y;
  36
  37 void fn1(void)
  38 {
  39   X = X | (Y << 3);
  40 }
  41
  42 compiles to
  43
  44 fn1:
  45         movl Y, %eax
  46         shll $3, %eax
  47         orl X, %eax
  48         movl %eax, X
  49         ret
  50
  51 The problem is the store's chain operand is not the load X but rather
  52 a TokenFactor of the load X and load Y, which prevents the folding.
  53
  54 There are two ways to fix this:
  55
  56 1. The dag combiner can start using alias analysis to realize that y/x
  57    don't alias, making the store to X not dependent on the load from Y.
  58 2. The generated isel could be made smarter in the case it can't
  59    disambiguate the pointers.
  60
  61 Number 1 is the preferred solution.
  62
  63 This has been "fixed" by a TableGen hack. But that is a short term workaround
  64 which will be removed once the proper fix is made.
  65
  66 //===---------------------------------------------------------------------===//
  67
  68 On targets with expensive 64-bit multiply, we could LSR this:
  69
  70 for (i = ...; ++i) {
  71    x = 1ULL << i;
  72
  73 into:
  74  long long tmp = 1;
  75  for (i = ...; ++i, tmp+=tmp)
  76    x = tmp;
  77
  78 This would be a win on ppc32, but not x86 or ppc64.
  79
  80 //===---------------------------------------------------------------------===//
  81
  82 Shrink: (setlt (loadi32 P), 0) -> (setlt (loadi8 Phi), 0)
  83
  84 //===---------------------------------------------------------------------===//
  85
  86 Reassociate should turn: X*X*X*X -> t=(X*X) (t*t) to eliminate a multiply.
  87
  88 //===---------------------------------------------------------------------===//
  89
  90 Interesting? testcase for add/shift/mul reassoc:
  91
  92 int bar(int x, int y) {
  93   return x*x*x+y+x*x*x*x*x*y*y*y*y;
  94 }
  95 int foo(int z, int n) {
  96   return bar(z, n) + bar(2*z, 2*n);
  97 }
  98
  99 Reassociate should handle the example in GCC PR16157.
 100
 101 //===---------------------------------------------------------------------===//
 102
 103 These two functions should generate the same code on big-endian systems:
 104
 105 int g(int *j,int *l)  {  return memcmp(j,l,4);  }
 106 int h(int *j, int *l) {  return *j - *l; }
 107
 108 this could be done in SelectionDAGISel.cpp, along with other special cases,
 109 for 1,2,4,8 bytes.
 110
 111 //===---------------------------------------------------------------------===//
 112
 113 It would be nice to revert this patch:
 114 http://lists.cs.uiuc.edu/pipermail/llvm-commits/Week-of-Mon-20060213/031986.html
 115
 116 And teach the dag combiner enough to simplify the code expanded before
 117 legalize.  It seems plausible that this knowledge would let it simplify other
 118 stuff too.
 119
 120 //===---------------------------------------------------------------------===//
 121
 122 For vector types, TargetData.cpp::getTypeInfo() returns alignment that is equal
 123 to the type size. It works but can be overly conservative as the alignment of
 124 specific vector types are target dependent.
 125
 126 //===---------------------------------------------------------------------===//
 127
 128 We should produce an unaligned load from code like this:
 129
 130 v4sf example(float *P) {
 131   return (v4sf){P[0], P[1], P[2], P[3] };
 132 }
 133
 134 //===---------------------------------------------------------------------===//
 135
 136 Add support for conditional increments, and other related patterns.  Instead
 137 of:
 138
 139         movl 136(%esp), %eax
 140         cmpl $0, %eax
 141         je LBB16_2      #cond_next
 142 LBB16_1:        #cond_true
 143         incl _foo
 144 LBB16_2:        #cond_next
 145
 146 emit:
 147         movl    _foo, %eax
 148         cmpl    $1, %edi
 149         sbbl    $-1, %eax
 150         movl    %eax, _foo
 151
 152 //===---------------------------------------------------------------------===//
 153
 154 Combine: a = sin(x), b = cos(x) into a,b = sincos(x).
 155
 156 Expand these to calls of sin/cos and stores:
 157       double sincos(double x, double *sin, double *cos);
 158       float sincosf(float x, float *sin, float *cos);
 159       long double sincosl(long double x, long double *sin, long double *cos);
 160
 161 Doing so could allow SROA of the destination pointers.  See also:
 162 http://gcc.gnu.org/bugzilla/show_bug.cgi?id=17687
 163
 164 This is now easily doable with MRVs.  We could even make an intrinsic for this
 165 if anyone cared enough about sincos.
 166
 167 //===---------------------------------------------------------------------===//
 168
 169 Turn this into a single byte store with no load (the other 3 bytes are
 170 unmodified):
 171
 172 define void @test(i32* %P) {
 173         %tmp = load i32* %P
 174         %tmp14 = or i32 %tmp, 3305111552
 175         %tmp15 = and i32 %tmp14, 3321888767
 176         store i32 %tmp15, i32* %P
 177         ret void
 178 }
 179
 180 //===---------------------------------------------------------------------===//
 181
 182 dag/inst combine "clz(x)>>5 -> x==0" for 32-bit x.
 183
 184 Compile:
 185
 186 int bar(int x)
 187 {
 188   int t = __builtin_clz(x);
 189   return -(t>>5);
 190 }
 191
 192 to:
 193
 194 _bar:   addic r3,r3,-1
 195         subfe r3,r3,r3
 196         blr
 197
 198 //===---------------------------------------------------------------------===//
 199
 200 quantum_sigma_x in 462.libquantum contains the following loop:
 201
 202       for(i=0; i<reg->size; i++)
 203         {
 204           /* Flip the target bit of each basis state */
 205           reg->node[i].state ^= ((MAX_UNSIGNED) 1 << target);
 206         }
 207
 208 Where MAX_UNSIGNED/state is a 64-bit int.  On a 32-bit platform it would be just
 209 so cool to turn it into something like:
 210
 211    long long Res = ((MAX_UNSIGNED) 1 << target);
 212    if (target < 32) {
 213      for(i=0; i<reg->size; i++)
 214        reg->node[i].state ^= Res & 0xFFFFFFFFULL;
 215    } else {
 216      for(i=0; i<reg->size; i++)
 217        reg->node[i].state ^= Res & 0xFFFFFFFF00000000ULL
 218    }
 219
 220 ... which would only do one 32-bit XOR per loop iteration instead of two.
 221
 222 It would also be nice to recognize the reg->size doesn't alias reg->node[i], but
 223 this requires TBAA.
 224
 225 //===---------------------------------------------------------------------===//
 226
 227 This should be optimized to one 'and' and one 'or', from PR4216:
 228
 229 define i32 @test_bitfield(i32 %bf.prev.low) nounwind ssp {
 230 entry:
 231   %bf.prev.lo.cleared10 = or i32 %bf.prev.low, 32962 ; <i32> [#uses=1]
 232   %0 = and i32 %bf.prev.low, -65536               ; <i32> [#uses=1]
 233   %1 = and i32 %bf.prev.lo.cleared10, 40186       ; <i32> [#uses=1]
 234   %2 = or i32 %1, %0                              ; <i32> [#uses=1]
 235   ret i32 %2
 236 }
 237
 238 //===---------------------------------------------------------------------===//
 239
 240 This isn't recognized as bswap by instcombine (yes, it really is bswap):
 241
 242 unsigned long reverse(unsigned v) {
 243     unsigned t;
 244     t = v ^ ((v << 16) | (v >> 16));
 245     t &= ~0xff0000;
 246     v = (v << 24) | (v >> 8);
 247     return v ^ (t >> 8);
 248 }
 249
 250 //===---------------------------------------------------------------------===//
 251
 252 These idioms should be recognized as popcount (see PR1488):
 253
 254 unsigned countbits_slow(unsigned v) {
 255   unsigned c;
 256   for (c = 0; v; v >>= 1)
 257     c += v & 1;
 258   return c;
 259 }
 260 unsigned countbits_fast(unsigned v){
 261   unsigned c;
 262   for (c = 0; v; c++)
 263     v &= v - 1; // clear the least significant bit set
 264   return c;
 265 }
 266
 267 BITBOARD = unsigned long long
 268 int PopCnt(register BITBOARD a) {
 269   register int c=0;
 270   while(a) {
 271     c++;
 272     a &= a - 1;
 273   }
 274   return c;
 275 }
 276 unsigned int popcount(unsigned int input) {
 277   unsigned int count = 0;
 278   for (unsigned int i =  0; i < 4 * 8; i++)
 279     count += (input >> i) & i;
 280   return count;
 281 }
 282
 283 This is a form of idiom recognition for loops, the same thing that could be
 284 useful for recognizing memset/memcpy.
 285
 286 //===---------------------------------------------------------------------===//
 287
 288 These should turn into single 16-bit (unaligned?) loads on little/big endian
 289 processors.
 290
 291 unsigned short read_16_le(const unsigned char *adr) {
 292   return adr[0] | (adr[1] << 8);
 293 }
 294 unsigned short read_16_be(const unsigned char *adr) {
 295   return (adr[0] << 8) | adr[1];
 296 }
 297
 298 //===---------------------------------------------------------------------===//
 299
 300 -instcombine should handle this transform:
 301    icmp pred (sdiv X / C1 ), C2
 302 when X, C1, and C2 are unsigned.  Similarly for udiv and signed operands.
 303
 304 Currently InstCombine avoids this transform but will do it when the signs of
 305 the operands and the sign of the divide match. See the FIXME in
 306 InstructionCombining.cpp in the visitSetCondInst method after the switch case
 307 for Instruction::UDiv (around line 4447) for more details.
 308
 309 The SingleSource/Benchmarks/Shootout-C++/hash and hash2 tests have examples of
 310 this construct.
 311
 312 //===---------------------------------------------------------------------===//
 313
 314 viterbi speeds up *significantly* if the various "history" related copy loops
 315 are turned into memcpy calls at the source level.  We need a "loops to memcpy"
 316 pass.
 317
 318 //===---------------------------------------------------------------------===//
 319
 320 Consider:
 321
 322 typedef unsigned U32;
 323 typedef unsigned long long U64;
 324 int test (U32 *inst, U64 *regs) {
 325     U64 effective_addr2;
 326     U32 temp = *inst;
 327     int r1 = (temp >> 20) & 0xf;
 328     int b2 = (temp >> 16) & 0xf;
 329     effective_addr2 = temp & 0xfff;
 330     if (b2) effective_addr2 += regs[b2];
 331     b2 = (temp >> 12) & 0xf;
 332     if (b2) effective_addr2 += regs[b2];
 333     effective_addr2 &= regs[4];
 334      if ((effective_addr2 & 3) == 0)
 335         return 1;
 336     return 0;
 337 }
 338
 339 Note that only the low 2 bits of effective_addr2 are used.  On 32-bit systems,
 340 we don't eliminate the computation of the top half of effective_addr2 because
 341 we don't have whole-function selection dags.  On x86, this means we use one
 342 extra register for the function when effective_addr2 is declared as U64 than
 343 when it is declared U32.
 344
 345 PHI Slicing could be extended to do this.
 346
 347 //===---------------------------------------------------------------------===//
 348
 349 LSR should know what GPR types a target has from TargetData.  This code:
 350
 351 volatile short X, Y; // globals
 352
 353 void foo(int N) {
 354   int i;
 355   for (i = 0; i < N; i++) { X = i; Y = i*4; }
 356 }
 357
 358 produces two near identical IV's (after promotion) on PPC/ARM:
 359
 360 LBB1_2:
 361         ldr r3, LCPI1_0
 362         ldr r3, [r3]
 363         strh r2, [r3]
 364         ldr r3, LCPI1_1
 365         ldr r3, [r3]
 366         strh r1, [r3]
 367         add r1, r1, #4
 368         add r2, r2, #1   <- [0,+,1]
 369         sub r0, r0, #1   <- [0,-,1]
 370         cmp r0, #0
 371         bne LBB1_2
 372
 373 LSR should reuse the "+" IV for the exit test.
 374
 375 //===---------------------------------------------------------------------===//
 376
 377 Tail call elim should be more aggressive, checking to see if the call is
 378 followed by an uncond branch to an exit block.
 379
 380 ; This testcase is due to tail-duplication not wanting to copy the return
 381 ; instruction into the terminating blocks because there was other code
 382 ; optimized out of the function after the taildup happened.
 383 ; RUN: llvm-as < %s | opt -tailcallelim | llvm-dis | not grep call
 384
 385 define i32 @t4(i32 %a) {
 386 entry:
 387         %tmp.1 = and i32 %a, 1          ; <i32> [#uses=1]
 388         %tmp.2 = icmp ne i32 %tmp.1, 0          ; <i1> [#uses=1]
 389         br i1 %tmp.2, label %then.0, label %else.0
 390
 391 then.0:         ; preds = %entry
 392         %tmp.5 = add i32 %a, -1         ; <i32> [#uses=1]
 393         %tmp.3 = call i32 @t4( i32 %tmp.5 )             ; <i32> [#uses=1]
 394         br label %return
 395
 396 else.0:         ; preds = %entry
 397         %tmp.7 = icmp ne i32 %a, 0              ; <i1> [#uses=1]
 398         br i1 %tmp.7, label %then.1, label %return
 399
 400 then.1:         ; preds = %else.0
 401         %tmp.11 = add i32 %a, -2                ; <i32> [#uses=1]
 402         %tmp.9 = call i32 @t4( i32 %tmp.11 )            ; <i32> [#uses=1]
 403         br label %return
 404
 405 return:         ; preds = %then.1, %else.0, %then.0
 406         %result.0 = phi i32 [ 0, %else.0 ], [ %tmp.3, %then.0 ],
 407                             [ %tmp.9, %then.1 ]
 408         ret i32 %result.0
 409 }
 410
 411 //===---------------------------------------------------------------------===//
 412
 413 Tail recursion elimination should handle:
 414
 415 int pow2m1(int n) {
 416  if (n == 0)
 417    return 0;
 418  return 2 * pow2m1 (n - 1) + 1;
 419 }
 420
 421 Also, multiplies can be turned into SHL's, so they should be handled as if
 422 they were associative.  "return foo() << 1" can be tail recursion eliminated.
 423
 424 //===---------------------------------------------------------------------===//
 425
 426 Argument promotion should promote arguments for recursive functions, like
 427 this:
 428
 429 ; RUN: llvm-as < %s | opt -argpromotion | llvm-dis | grep x.val
 430
 431 define internal i32 @foo(i32* %x) {
 432 entry:
 433         %tmp = load i32* %x             ; <i32> [#uses=0]
 434         %tmp.foo = call i32 @foo( i32* %x )             ; <i32> [#uses=1]
 435         ret i32 %tmp.foo
 436 }
 437
 438 define i32 @bar(i32* %x) {
 439 entry:
 440         %tmp3 = call i32 @foo( i32* %x )                ; <i32> [#uses=1]
 441         ret i32 %tmp3
 442 }
 443
 444 //===---------------------------------------------------------------------===//
 445
 446 "basicaa" should know how to look through "or" instructions that act like add
 447 instructions.  For example in this code, the x*4+1 is turned into x*4 | 1, and
 448 basicaa can't analyze the array subscript, leading to duplicated loads in the
 449 generated code:
 450
 451 void test(int X, int Y, int a[]) {
 452 int i;
 453   for (i=2; i<1000; i+=4) {
 454   a[i+0] = a[i-1+0]*a[i-2+0];
 455   a[i+1] = a[i-1+1]*a[i-2+1];
 456   a[i+2] = a[i-1+2]*a[i-2+2];
 457   a[i+3] = a[i-1+3]*a[i-2+3];
 458   }
 459 }
 460
 461 BasicAA also doesn't do this for add.  It needs to know that &A[i+1] != &A[i].
 462
 463 //===---------------------------------------------------------------------===//
 464
 465 We should investigate an instruction sinking pass.  Consider this silly
 466 example in pic mode:
 467
 468 #include <assert.h>
 469 void foo(int x) {
 470   assert(x);
 471   //...
 472 }
 473
 474 we compile this to:
 475 _foo:
 476         subl    $28, %esp
 477         call    "L1$pb"
 478 "L1$pb":
 479         popl    %eax
 480         cmpl    $0, 32(%esp)
 481         je      LBB1_2  # cond_true
 482 LBB1_1: # return
 483         # ...
 484         addl    $28, %esp
 485         ret
 486 LBB1_2: # cond_true
 487 ...
 488
 489 The PIC base computation (call+popl) is only used on one path through the
 490 code, but is currently always computed in the entry block.  It would be
 491 better to sink the picbase computation down into the block for the
 492 assertion, as it is the only one that uses it.  This happens for a lot of
 493 code with early outs.
 494
 495 Another example is loads of arguments, which are usually emitted into the
 496 entry block on targets like x86.  If not used in all paths through a
 497 function, they should be sunk into the ones that do.
 498
 499 In this case, whole-function-isel would also handle this.
 500
 501 //===---------------------------------------------------------------------===//
 502
 503 Investigate lowering of sparse switch statements into perfect hash tables:
 504 http://burtleburtle.net/bob/hash/perfect.html
 505
 506 //===---------------------------------------------------------------------===//
 507
 508 We should turn things like "load+fabs+store" and "load+fneg+store" into the
 509 corresponding integer operations.  On a yonah, this loop:
 510
 511 double a[256];
 512 void foo() {
 513   int i, b;
 514   for (b = 0; b < 10000000; b++)
 515   for (i = 0; i < 256; i++)
 516     a[i] = -a[i];
 517 }
 518
 519 is twice as slow as this loop:
 520
 521 long long a[256];
 522 void foo() {
 523   int i, b;
 524   for (b = 0; b < 10000000; b++)
 525   for (i = 0; i < 256; i++)
 526     a[i] ^= (1ULL << 63);
 527 }
 528
 529 and I suspect other processors are similar.  On X86 in particular this is a
 530 big win because doing this with integers allows the use of read/modify/write
 531 instructions.
 532
 533 //===---------------------------------------------------------------------===//
 534
 535 DAG Combiner should try to combine small loads into larger loads when
 536 profitable.  For example, we compile this C++ example:
 537
 538 struct THotKey { short Key; bool Control; bool Shift; bool Alt; };
 539 extern THotKey m_HotKey;
 540 THotKey GetHotKey () { return m_HotKey; }
 541
 542 into (-O3 -fno-exceptions -static -fomit-frame-pointer):
 543
 544 __Z9GetHotKeyv:
 545         pushl   %esi
 546         movl    8(%esp), %eax
 547         movb    _m_HotKey+3, %cl
 548         movb    _m_HotKey+4, %dl
 549         movb    _m_HotKey+2, %ch
 550         movw    _m_HotKey, %si
 551         movw    %si, (%eax)
 552         movb    %ch, 2(%eax)
 553         movb    %cl, 3(%eax)
 554         movb    %dl, 4(%eax)
 555         popl    %esi
 556         ret     $4
 557
 558 GCC produces:
 559
 560 __Z9GetHotKeyv:
 561         movl    _m_HotKey, %edx
 562         movl    4(%esp), %eax
 563         movl    %edx, (%eax)
 564         movzwl  _m_HotKey+4, %edx
 565         movw    %dx, 4(%eax)
 566         ret     $4
 567
 568 The LLVM IR contains the needed alignment info, so we should be able to
 569 merge the loads and stores into 4-byte loads:
 570
 571         %struct.THotKey = type { i16, i8, i8, i8 }
 572 define void @_Z9GetHotKeyv(%struct.THotKey* sret  %agg.result) nounwind  {
 573 ...
 574         %tmp2 = load i16* getelementptr (@m_HotKey, i32 0, i32 0), align 8
 575         %tmp5 = load i8* getelementptr (@m_HotKey, i32 0, i32 1), align 2
 576         %tmp8 = load i8* getelementptr (@m_HotKey, i32 0, i32 2), align 1
 577         %tmp11 = load i8* getelementptr (@m_HotKey, i32 0, i32 3), align 2
 578
 579 Alternatively, we should use a small amount of base-offset alias analysis
 580 to make it so the scheduler doesn't need to hold all the loads in regs at
 581 once.
 582
 583 //===---------------------------------------------------------------------===//
 584
 585 We should add an FRINT node to the DAG to model targets that have legal
 586 implementations of ceil/floor/rint.
 587
 588 //===---------------------------------------------------------------------===//
 589
 590 Consider:
 591
 592 int test() {
 593   long long input[8] = {1,1,1,1,1,1,1,1};
 594   foo(input);
 595 }
 596
 597 We currently compile this into a memcpy from a global array since the
 598 initializer is fairly large and not memset'able.  This is good, but the memcpy
 599 gets lowered to load/stores in the code generator.  This is also ok, except
 600 that the codegen lowering for memcpy doesn't handle the case when the source
 601 is a constant global.  This gives us atrocious code like this:
 602
 603         call    "L1$pb"
 604 "L1$pb":
 605         popl    %eax
 606         movl    _C.0.1444-"L1$pb"+32(%eax), %ecx
 607         movl    %ecx, 40(%esp)
 608         movl    _C.0.1444-"L1$pb"+20(%eax), %ecx
 609         movl    %ecx, 28(%esp)
 610         movl    _C.0.1444-"L1$pb"+36(%eax), %ecx
 611         movl    %ecx, 44(%esp)
 612         movl    _C.0.1444-"L1$pb"+44(%eax), %ecx
 613         movl    %ecx, 52(%esp)
 614         movl    _C.0.1444-"L1$pb"+40(%eax), %ecx
 615         movl    %ecx, 48(%esp)
 616         movl    _C.0.1444-"L1$pb"+12(%eax), %ecx
 617         movl    %ecx, 20(%esp)
 618         movl    _C.0.1444-"L1$pb"+4(%eax), %ecx
 619 ...
 620
 621 instead of:
 622         movl    $1, 16(%esp)
 623         movl    $0, 20(%esp)
 624         movl    $1, 24(%esp)
 625         movl    $0, 28(%esp)
 626         movl    $1, 32(%esp)
 627         movl    $0, 36(%esp)
 628         ...
 629
 630 //===---------------------------------------------------------------------===//
 631
 632 http://llvm.org/PR717:
 633
 634 The following code should compile into "ret int undef". Instead, LLVM
 635 produces "ret int 0":
 636
 637 int f() {
 638   int x = 4;
 639   int y;
 640   if (x == 3) y = 0;
 641   return y;
 642 }
 643
 644 //===---------------------------------------------------------------------===//
 645
 646 The loop unroller should partially unroll loops (instead of peeling them)
 647 when code growth isn't too bad and when an unroll count allows simplification
 648 of some code within the loop.  One trivial example is:
 649
 650 #include <stdio.h>
 651 int main() {
 652     int nRet = 17;
 653     int nLoop;
 654     for ( nLoop = 0; nLoop < 1000; nLoop++ ) {
 655         if ( nLoop & 1 )
 656             nRet += 2;
 657         else
 658             nRet -= 1;
 659     }
 660     return nRet;
 661 }
 662
 663 Unrolling by 2 would eliminate the '&1' in both copies, leading to a net
 664 reduction in code size.  The resultant code would then also be suitable for
 665 exit value computation.
 666
 667 //===---------------------------------------------------------------------===//
 668
 669 We miss a bunch of rotate opportunities on various targets, including ppc, x86,
 670 etc.  On X86, we miss a bunch of 'rotate by variable' cases because the rotate
 671 matching code in dag combine doesn't look through truncates aggressively
 672 enough.  Here are some testcases reduces from GCC PR17886:
 673
 674 unsigned long long f(unsigned long long x, int y) {
 675   return (x << y) | (x >> 64-y);
 676 }
 677 unsigned f2(unsigned x, int y){
 678   return (x << y) | (x >> 32-y);
 679 }
 680 unsigned long long f3(unsigned long long x){
 681   int y = 9;
 682   return (x << y) | (x >> 64-y);
 683 }
 684 unsigned f4(unsigned x){
 685   int y = 10;
 686   return (x << y) | (x >> 32-y);
 687 }
 688 unsigned long long f5(unsigned long long x, unsigned long long y) {
 689   return (x << 8) | ((y >> 48) & 0xffull);
 690 }
 691 unsigned long long f6(unsigned long long x, unsigned long long y, int z) {
 692   switch(z) {
 693   case 1:
 694     return (x << 8) | ((y >> 48) & 0xffull);
 695   case 2:
 696     return (x << 16) | ((y >> 40) & 0xffffull);
 697   case 3:
 698     return (x << 24) | ((y >> 32) & 0xffffffull);
 699   case 4:
 700     return (x << 32) | ((y >> 24) & 0xffffffffull);
 701   default:
 702     return (x << 40) | ((y >> 16) & 0xffffffffffull);
 703   }
 704 }
 705
 706 On X86-64, we only handle f2/f3/f4 right.  On x86-32, a few of these
 707 generate truly horrible code, instead of using shld and friends.  On
 708 ARM, we end up with calls to L___lshrdi3/L___ashldi3 in f, which is
 709 badness.  PPC64 misses f, f5 and f6.  CellSPU aborts in isel.
 710
 711 //===---------------------------------------------------------------------===//
 712
 713 We do a number of simplifications in simplify libcalls to strength reduce
 714 standard library functions, but we don't currently merge them together.  For
 715 example, it is useful to merge memcpy(a,b,strlen(b)) -> strcpy.  This can only
 716 be done safely if "b" isn't modified between the strlen and memcpy of course.
 717
 718 //===---------------------------------------------------------------------===//
 719
 720 Reassociate should turn things like:
 721
 722 int factorial(int X) {
 723  return X*X*X*X*X*X*X*X;
 724 }
 725
 726 into llvm.powi calls, allowing the code generator to produce balanced
 727 multiplication trees.
 728
 729 //===---------------------------------------------------------------------===//
 730
 731 We generate a horrible  libcall for llvm.powi.  For example, we compile:
 732
 733 #include <cmath>
 734 double f(double a) { return std::pow(a, 4); }
 735
 736 into:
 737
 738 __Z1fd:
 739         subl    $12, %esp
 740         movsd   16(%esp), %xmm0
 741         movsd   %xmm0, (%esp)
 742         movl    $4, 8(%esp)
 743         call    L___powidf2$stub
 744         addl    $12, %esp
 745         ret
 746
 747 GCC produces:
 748
 749 __Z1fd:
 750         subl    $12, %esp
 751         movsd   16(%esp), %xmm0
 752         mulsd   %xmm0, %xmm0
 753         mulsd   %xmm0, %xmm0
 754         movsd   %xmm0, (%esp)
 755         fldl    (%esp)
 756         addl    $12, %esp
 757         ret
 758
 759 //===---------------------------------------------------------------------===//
 760
 761 We compile this program: (from GCC PR11680)
 762 http://gcc.gnu.org/bugzilla/attachment.cgi?id=4487
 763
 764 Into code that runs the same speed in fast/slow modes, but both modes run 2x
 765 slower than when compile with GCC (either 4.0 or 4.2):
 766
 767 $ llvm-g++ perf.cpp -O3 -fno-exceptions
 768 $ time ./a.out fast
 769 1.821u 0.003s 0:01.82 100.0%    0+0k 0+0io 0pf+0w
 770
 771 $ g++ perf.cpp -O3 -fno-exceptions
 772 $ time ./a.out fast
 773 0.821u 0.001s 0:00.82 100.0%    0+0k 0+0io 0pf+0w
 774
 775 It looks like we are making the same inlining decisions, so this may be raw
 776 codegen badness or something else (haven't investigated).
 777
 778 //===---------------------------------------------------------------------===//
 779
 780 We miss some instcombines for stuff like this:
 781 void bar (void);
 782 void foo (unsigned int a) {
 783   /* This one is equivalent to a >= (3 << 2).  */
 784   if ((a >> 2) >= 3)
 785     bar ();
 786 }
 787
 788 A few other related ones are in GCC PR14753.
 789
 790 //===---------------------------------------------------------------------===//
 791
 792 Divisibility by constant can be simplified (according to GCC PR12849) from
 793 being a mulhi to being a mul lo (cheaper).  Testcase:
 794
 795 void bar(unsigned n) {
 796   if (n % 3 == 0)
 797     true();
 798 }
 799
 800 I think this basically amounts to a dag combine to simplify comparisons against
 801 multiply hi's into a comparison against the mullo.
 802
 803 //===---------------------------------------------------------------------===//
 804
 805 Better mod/ref analysis for scanf would allow us to eliminate the vtable and a
 806 bunch of other stuff from this example (see PR1604):
 807
 808 #include <cstdio>
 809 struct test {
 810     int val;
 811     virtual ~test() {}
 812 };
 813
 814 int main() {
 815     test t;
 816     std::scanf("%d", &t.val);
 817     std::printf("%d\n", t.val);
 818 }
 819
 820 //===---------------------------------------------------------------------===//
 821
 822 Instcombine will merge comparisons like (x >= 10) && (x < 20) by producing (x -
 823 10) u< 10, but only when the comparisons have matching sign.
 824
 825 This could be converted with a similiar technique. (PR1941)
 826
 827 define i1 @test(i8 %x) {
 828   %A = icmp uge i8 %x, 5
 829   %B = icmp slt i8 %x, 20
 830   %C = and i1 %A, %B
 831   ret i1 %C
 832 }
 833
 834 //===---------------------------------------------------------------------===//
 835
 836 These functions perform the same computation, but produce different assembly.
 837
 838 define i8 @select(i8 %x) readnone nounwind {
 839   %A = icmp ult i8 %x, 250
 840   %B = select i1 %A, i8 0, i8 1
 841   ret i8 %B
 842 }
 843
 844 define i8 @addshr(i8 %x) readnone nounwind {
 845   %A = zext i8 %x to i9
 846   %B = add i9 %A, 6       ;; 256 - 250 == 6
 847   %C = lshr i9 %B, 8
 848   %D = trunc i9 %C to i8
 849   ret i8 %D
 850 }
 851
 852 //===---------------------------------------------------------------------===//
 853
 854 From gcc bug 24696:
 855 int
 856 f (unsigned long a, unsigned long b, unsigned long c)
 857 {
 858   return ((a & (c - 1)) != 0) || ((b & (c - 1)) != 0);
 859 }
 860 int
 861 f (unsigned long a, unsigned long b, unsigned long c)
 862 {
 863   return ((a & (c - 1)) != 0) | ((b & (c - 1)) != 0);
 864 }
 865 Both should combine to ((a|b) & (c-1)) != 0.  Currently not optimized with
 866 "clang -emit-llvm-bc | opt -std-compile-opts".
 867
 868 //===---------------------------------------------------------------------===//
 869
 870 From GCC Bug 20192:
 871 #define PMD_MASK    (~((1UL << 23) - 1))
 872 void clear_pmd_range(unsigned long start, unsigned long end)
 873 {
 874    if (!(start & ~PMD_MASK) && !(end & ~PMD_MASK))
 875        f();
 876 }
 877 The expression should optimize to something like
 878 "!((start|end)&~PMD_MASK). Currently not optimized with "clang
 879 -emit-llvm-bc | opt -std-compile-opts".
 880
 881 //===---------------------------------------------------------------------===//
 882
 883 From GCC Bug 15241:
 884 unsigned int
 885 foo (unsigned int a, unsigned int b)
 886 {
 887  if (a <= 7 && b <= 7)
 888    baz ();
 889 }
 890 Should combine to "(a|b) <= 7".  Currently not optimized with "clang
 891 -emit-llvm-bc | opt -std-compile-opts".
 892
 893 //===---------------------------------------------------------------------===//
 894
 895 From GCC Bug 3756:
 896 int
 897 pn (int n)
 898 {
 899  return (n >= 0 ? 1 : -1);
 900 }
 901 Should combine to (n >> 31) | 1.  Currently not optimized with "clang
 902 -emit-llvm-bc | opt -std-compile-opts | llc".
 903
 904 //===---------------------------------------------------------------------===//
 905
 906 From GCC Bug 28685:
 907 int test(int a, int b)
 908 {
 909  int lt = a < b;
 910  int eq = a == b;
 911
 912  return (lt || eq);
 913 }
 914 Should combine to "a <= b".  Currently not optimized with "clang
 915 -emit-llvm-bc | opt -std-compile-opts | llc".
 916
 917 //===---------------------------------------------------------------------===//
 918
 919 void a(int variable)
 920 {
 921  if (variable == 4 || variable == 6)
 922    bar();
 923 }
 924 This should optimize to "if ((variable | 2) == 6)".  Currently not
 925 optimized with "clang -emit-llvm-bc | opt -std-compile-opts | llc".
 926
 927 //===---------------------------------------------------------------------===//
 928
 929 unsigned int f(unsigned int i, unsigned int n) {++i; if (i == n) ++i; return
 930 i;}
 931 unsigned int f2(unsigned int i, unsigned int n) {++i; i += i == n; return i;}
 932 These should combine to the same thing.  Currently, the first function
 933 produces better code on X86.
 934
 935 //===---------------------------------------------------------------------===//
 936
 937 From GCC Bug 15784:
 938 #define abs(x) x>0?x:-x
 939 int f(int x, int y)
 940 {
 941  return (abs(x)) >= 0;
 942 }
 943 This should optimize to x == INT_MIN. (With -fwrapv.)  Currently not
 944 optimized with "clang -emit-llvm-bc | opt -std-compile-opts".
 945
 946 //===---------------------------------------------------------------------===//
 947
 948 From GCC Bug 14753:
 949 void
 950 rotate_cst (unsigned int a)
 951 {
 952  a = (a << 10) | (a >> 22);
 953  if (a == 123)
 954    bar ();
 955 }
 956 void
 957 minus_cst (unsigned int a)
 958 {
 959  unsigned int tem;
 960
 961  tem = 20 - a;
 962  if (tem == 5)
 963    bar ();
 964 }
 965 void
 966 mask_gt (unsigned int a)
 967 {
 968  /* This is equivalent to a > 15.  */
 969  if ((a & ~7) > 8)
 970    bar ();
 971 }
 972 void
 973 rshift_gt (unsigned int a)
 974 {
 975  /* This is equivalent to a > 23.  */
 976  if ((a >> 2) > 5)
 977    bar ();
 978 }
 979 All should simplify to a single comparison.  All of these are
 980 currently not optimized with "clang -emit-llvm-bc | opt
 981 -std-compile-opts".
 982
 983 //===---------------------------------------------------------------------===//
 984
 985 From GCC Bug 32605:
 986 int c(int* x) {return (char*)x+2 == (char*)x;}
 987 Should combine to 0.  Currently not optimized with "clang
 988 -emit-llvm-bc | opt -std-compile-opts" (although llc can optimize it).
 989
 990 //===---------------------------------------------------------------------===//
 991
 992 int a(unsigned char* b) {return *b > 99;}
 993 There's an unnecessary zext in the generated code with "clang
 994 -emit-llvm-bc | opt -std-compile-opts".
 995
 996 //===---------------------------------------------------------------------===//
 997
 998 int a(unsigned b) {return ((b << 31) | (b << 30)) >> 31;}
 999 Should be combined to  "((b >> 1) | b) & 1".  Currently not optimized
1000 with "clang -emit-llvm-bc | opt -std-compile-opts".
1001
1002 //===---------------------------------------------------------------------===//
1003
1004 unsigned a(unsigned x, unsigned y) { return x | (y & 1) | (y & 2);}
1005 Should combine to "x | (y & 3)".  Currently not optimized with "clang
1006 -emit-llvm-bc | opt -std-compile-opts".
1007
1008 //===---------------------------------------------------------------------===//
1009
1010 unsigned a(unsigned a) {return ((a | 1) & 3) | (a & -4);}
1011 Should combine to "a | 1".  Currently not optimized with "clang
1012 -emit-llvm-bc | opt -std-compile-opts".
1013
1014 //===---------------------------------------------------------------------===//
1015
1016 int a(int a, int b, int c) {return (~a & c) | ((c|a) & b);}
1017 Should fold to "(~a & c) | (a & b)".  Currently not optimized with
1018 "clang -emit-llvm-bc | opt -std-compile-opts".
1019
1020 //===---------------------------------------------------------------------===//
1021
1022 int a(int a,int b) {return (~(a|b))|a;}
1023 Should fold to "a|~b".  Currently not optimized with "clang
1024 -emit-llvm-bc | opt -std-compile-opts".
1025
1026 //===---------------------------------------------------------------------===//
1027
1028 int a(int a, int b) {return (a&&b) || (a&&!b);}
1029 Should fold to "a".  Currently not optimized with "clang -emit-llvm-bc
1030 | opt -std-compile-opts".
1031
1032 //===---------------------------------------------------------------------===//
1033
1034 int a(int a, int b, int c) {return (a&&b) || (!a&&c);}
1035 Should fold to "a ? b : c", or at least something sane.  Currently not
1036 optimized with "clang -emit-llvm-bc | opt -std-compile-opts".
1037
1038 //===---------------------------------------------------------------------===//
1039
1040 int a(int a, int b, int c) {return (a&&b) || (a&&c) || (a&&b&&c);}
1041 Should fold to a && (b || c).  Currently not optimized with "clang
1042 -emit-llvm-bc | opt -std-compile-opts".
1043
1044 //===---------------------------------------------------------------------===//
1045
1046 int a(int x) {return x | ((x & 8) ^ 8);}
1047 Should combine to x | 8.  Currently not optimized with "clang
1048 -emit-llvm-bc | opt -std-compile-opts".
1049
1050 //===---------------------------------------------------------------------===//
1051
1052 int a(int x) {return x ^ ((x & 8) ^ 8);}
1053 Should also combine to x | 8.  Currently not optimized with "clang
1054 -emit-llvm-bc | opt -std-compile-opts".
1055
1056 //===---------------------------------------------------------------------===//
1057
1058 int a(int x) {return (x & 8) == 0 ? -1 : -9;}
1059 Should combine to (x | -9) ^ 8.  Currently not optimized with "clang
1060 -emit-llvm-bc | opt -std-compile-opts".
1061
1062 //===---------------------------------------------------------------------===//
1063
1064 int a(int x) {return (x & 8) == 0 ? -9 : -1;}
1065 Should combine to x | -9.  Currently not optimized with "clang
1066 -emit-llvm-bc | opt -std-compile-opts".
1067
1068 //===---------------------------------------------------------------------===//
1069
1070 int a(int x) {return ((x | -9) ^ 8) & x;}
1071 Should combine to x & -9.  Currently not optimized with "clang
1072 -emit-llvm-bc | opt -std-compile-opts".
1073
1074 //===---------------------------------------------------------------------===//
1075
1076 unsigned a(unsigned a) {return a * 0x11111111 >> 28 & 1;}
1077 Should combine to "a * 0x88888888 >> 31".  Currently not optimized
1078 with "clang -emit-llvm-bc | opt -std-compile-opts".
1079
1080 //===---------------------------------------------------------------------===//
1081
1082 unsigned a(char* x) {if ((*x & 32) == 0) return b();}
1083 There's an unnecessary zext in the generated code with "clang
1084 -emit-llvm-bc | opt -std-compile-opts".
1085
1086 //===---------------------------------------------------------------------===//
1087
1088 unsigned a(unsigned long long x) {return 40 * (x >> 1);}
1089 Should combine to "20 * (((unsigned)x) & -2)".  Currently not
1090 optimized with "clang -emit-llvm-bc | opt -std-compile-opts".
1091
1092 //===---------------------------------------------------------------------===//
1093
1094 This was noticed in the entryblock for grokdeclarator in 403.gcc:
1095
1096         %tmp = icmp eq i32 %decl_context, 4
1097         %decl_context_addr.0 = select i1 %tmp, i32 3, i32 %decl_context
1098         %tmp1 = icmp eq i32 %decl_context_addr.0, 1
1099         %decl_context_addr.1 = select i1 %tmp1, i32 0, i32 %decl_context_addr.0
1100
1101 tmp1 should be simplified to something like:
1102   (!tmp || decl_context == 1)
1103
1104 This allows recursive simplifications, tmp1 is used all over the place in
1105 the function, e.g. by:
1106
1107         %tmp23 = icmp eq i32 %decl_context_addr.1, 0            ; <i1> [#uses=1]
1108         %tmp24 = xor i1 %tmp1, true             ; <i1> [#uses=1]
1109         %or.cond8 = and i1 %tmp23, %tmp24               ; <i1> [#uses=1]
1110
1111 later.
1112
1113 //===---------------------------------------------------------------------===//
1114
1115 Store sinking: This code:
1116
1117 void f (int n, int *cond, int *res) {
1118     int i;
1119     *res = 0;
1120     for (i = 0; i < n; i++)
1121         if (*cond)
1122             *res ^= 234; /* (*) */
1123 }
1124
1125 On this function GVN hoists the fully redundant value of *res, but nothing
1126 moves the store out.  This gives us this code:
1127
1128 bb:             ; preds = %bb2, %entry
1129         %.rle = phi i32 [ 0, %entry ], [ %.rle6, %bb2 ]
1130         %i.05 = phi i32 [ 0, %entry ], [ %indvar.next, %bb2 ]
1131         %1 = load i32* %cond, align 4
1132         %2 = icmp eq i32 %1, 0
1133         br i1 %2, label %bb2, label %bb1
1134
1135 bb1:            ; preds = %bb
1136         %3 = xor i32 %.rle, 234
1137         store i32 %3, i32* %res, align 4
1138         br label %bb2
1139
1140 bb2:            ; preds = %bb, %bb1
1141         %.rle6 = phi i32 [ %3, %bb1 ], [ %.rle, %bb ]
1142         %indvar.next = add i32 %i.05, 1
1143         %exitcond = icmp eq i32 %indvar.next, %n
1144         br i1 %exitcond, label %return, label %bb
1145
1146 DSE should sink partially dead stores to get the store out of the loop.
1147
1148 Here's another partial dead case:
1149 http://gcc.gnu.org/bugzilla/show_bug.cgi?id=12395
1150
1151 //===---------------------------------------------------------------------===//
1152
1153 Scalar PRE hoists the mul in the common block up to the else:
1154
1155 int test (int a, int b, int c, int g) {
1156   int d, e;
1157   if (a)
1158     d = b * c;
1159   else
1160     d = b - c;
1161   e = b * c + g;
1162   return d + e;
1163 }
1164
1165 It would be better to do the mul once to reduce codesize above the if.
1166 This is GCC PR38204.
1167
1168 //===---------------------------------------------------------------------===//
1169
1170 GCC PR37810 is an interesting case where we should sink load/store reload
1171 into the if block and outside the loop, so we don't reload/store it on the
1172 non-call path.
1173
1174 for () {
1175   *P += 1;
1176   if ()
1177     call();
1178   else
1179     ...
1180 ->
1181 tmp = *P
1182 for () {
1183   tmp += 1;
1184   if () {
1185     *P = tmp;
1186     call();
1187     tmp = *P;
1188   } else ...
1189 }
1190 *P = tmp;
1191
1192 We now hoist the reload after the call (Transforms/GVN/lpre-call-wrap.ll), but
1193 we don't sink the store.  We need partially dead store sinking.
1194
1195 //===---------------------------------------------------------------------===//
1196
1197 [PHI TRANSLATE GEPs]
1198
1199 GCC PR37166: Sinking of loads prevents SROA'ing the "g" struct on the stack
1200 leading to excess stack traffic. This could be handled by GVN with some crazy
1201 symbolic phi translation.  The code we get looks like (g is on the stack):
1202
1203 bb2:            ; preds = %bb1
1204 ..
1205         %9 = getelementptr %struct.f* %g, i32 0, i32 0
1206         store i32 %8, i32* %9, align  bel %bb3
1207
1208 bb3:            ; preds = %bb1, %bb2, %bb
1209         %c_addr.0 = phi %struct.f* [ %g, %bb2 ], [ %c, %bb ], [ %c, %bb1 ]
1210         %b_addr.0 = phi %struct.f* [ %b, %bb2 ], [ %g, %bb ], [ %b, %bb1 ]
1211         %10 = getelementptr %struct.f* %c_addr.0, i32 0, i32 0
1212         %11 = load i32* %10, align 4
1213
1214 %11 is fully redundant, an in BB2 it should have the value %8.
1215
1216 GCC PR33344 is a similar case.
1217
1218 //===---------------------------------------------------------------------===//
1219
1220 [PHI TRANSLATE INDEXED GEPs]  PR5313
1221
1222 Load redundancy elimination for simple loop.  This loop:
1223
1224 void append_text(const char* text,unsigned char * const  io) {
1225   while(*text)
1226     *io=*text++;
1227 }
1228
1229 Compiles to have a fully redundant load in the loop (%2):
1230
1231 define void @append_text(i8* nocapture %text, i8* nocapture %io) nounwind {
1232 entry:
1233   %0 = load i8* %text, align 1                    ; <i8> [#uses=1]
1234   %1 = icmp eq i8 %0, 0                           ; <i1> [#uses=1]
1235   br i1 %1, label %return, label %bb
1236
1237 bb:                                               ; preds = %bb, %entry
1238   %indvar = phi i32 [ 0, %entry ], [ %tmp, %bb ]  ; <i32> [#uses=2]
1239   %text_addr.04 = getelementptr i8* %text, i32 %indvar ; <i8*> [#uses=1]
1240   %2 = load i8* %text_addr.04, align 1            ; <i8> [#uses=1]
1241   store i8 %2, i8* %io, align 1
1242   %tmp = add i32 %indvar, 1                       ; <i32> [#uses=2]
1243   %scevgep = getelementptr i8* %text, i32 %tmp    ; <i8*> [#uses=1]
1244   %3 = load i8* %scevgep, align 1                 ; <i8> [#uses=1]
1245   %4 = icmp eq i8 %3, 0                           ; <i1> [#uses=1]
1246   br i1 %4, label %return, label %bb
1247
1248 return:                                           ; preds = %bb, %entry
1249   ret void
1250 }
1251
1252 //===---------------------------------------------------------------------===//
1253
1254 There are many load PRE testcases in testsuite/gcc.dg/tree-ssa/loadpre* in the
1255 GCC testsuite.  There are many pre testcases as ssa-pre-*.c
1256
1257 //===---------------------------------------------------------------------===//
1258
1259 There are some interesting cases in testsuite/gcc.dg/tree-ssa/pred-comm* in the
1260 GCC testsuite.  For example, predcom-1.c is:
1261
1262  for (i = 2; i < 1000; i++)
1263     fib[i] = (fib[i-1] + fib[i - 2]) & 0xffff;
1264
1265 which compiles into:
1266
1267 bb1:            ; preds = %bb1, %bb1.thread
1268         %indvar = phi i32 [ 0, %bb1.thread ], [ %0, %bb1 ]
1269         %i.0.reg2mem.0 = add i32 %indvar, 2
1270         %0 = add i32 %indvar, 1         ; <i32> [#uses=3]
1271         %1 = getelementptr [1000 x i32]* @fib, i32 0, i32 %0
1272         %2 = load i32* %1, align 4              ; <i32> [#uses=1]
1273         %3 = getelementptr [1000 x i32]* @fib, i32 0, i32 %indvar
1274         %4 = load i32* %3, align 4              ; <i32> [#uses=1]
1275         %5 = add i32 %4, %2             ; <i32> [#uses=1]
1276         %6 = and i32 %5, 65535          ; <i32> [#uses=1]
1277         %7 = getelementptr [1000 x i32]* @fib, i32 0, i32 %i.0.reg2mem.0
1278         store i32 %6, i32* %7, align 4
1279         %exitcond = icmp eq i32 %0, 998         ; <i1> [#uses=1]
1280         br i1 %exitcond, label %return, label %bb1
1281
1282 This is basically:
1283   LOAD fib[i+1]
1284   LOAD fib[i]
1285   STORE fib[i+2]
1286
1287 instead of handling this as a loop or other xform, all we'd need to do is teach
1288 load PRE to phi translate the %0 add (i+1) into the predecessor as (i'+1+1) =
1289 (i'+2) (where i' is the previous iteration of i).  This would find the store
1290 which feeds it.
1291
1292 predcom-2.c is apparently the same as predcom-1.c
1293 predcom-3.c is very similar but needs loads feeding each other instead of
1294 store->load.
1295 predcom-4.c seems the same as the rest.
1296
1297
1298 //===---------------------------------------------------------------------===//
1299
1300 Other simple load PRE cases:
1301 http://gcc.gnu.org/bugzilla/show_bug.cgi?id=35287 [LPRE crit edge splitting]
1302
1303 http://gcc.gnu.org/bugzilla/show_bug.cgi?id=34677 (licm does this, LPRE crit edge)
1304   llvm-gcc t2.c -S -o - -O0 -emit-llvm | llvm-as | opt -mem2reg -simplifycfg -gvn | llvm-dis
1305
1306 http://gcc.gnu.org/bugzilla/show_bug.cgi?id=16799 [BITCAST PHI TRANS]
1307
1308 //===---------------------------------------------------------------------===//
1309
1310 Type based alias analysis:
1311 http://gcc.gnu.org/bugzilla/show_bug.cgi?id=14705
1312
1313 //===---------------------------------------------------------------------===//
1314
1315 A/B get pinned to the stack because we turn an if/then into a select instead
1316 of PRE'ing the load/store.  This may be fixable in instcombine:
1317 http://gcc.gnu.org/bugzilla/show_bug.cgi?id=37892
1318
1319 struct X { int i; };
1320 int foo (int x) {
1321   struct X a;
1322   struct X b;
1323   struct X *p;
1324   a.i = 1;
1325   b.i = 2;
1326   if (x)
1327     p = &a;
1328   else
1329     p = &b;
1330   return p->i;
1331 }
1332
1333 //===---------------------------------------------------------------------===//
1334
1335 Interesting missed case because of control flow flattening (should be 2 loads):
1336 http://gcc.gnu.org/bugzilla/show_bug.cgi?id=26629
1337 With: llvm-gcc t2.c -S -o - -O0 -emit-llvm | llvm-as |
1338              opt -mem2reg -gvn -instcombine | llvm-dis
1339 we miss it because we need 1) GEP PHI TRAN, 2) CRIT EDGE 3) MULTIPLE DIFFERENT
1340 VALS PRODUCED BY ONE BLOCK OVER DIFFERENT PATHS
1341
1342 //===---------------------------------------------------------------------===//
1343
1344 http://gcc.gnu.org/bugzilla/show_bug.cgi?id=19633
1345 We could eliminate the branch condition here, loading from null is undefined:
1346
1347 struct S { int w, x, y, z; };
1348 struct T { int r; struct S s; };
1349 void bar (struct S, int);
1350 void foo (int a, struct T b)
1351 {
1352   struct S *c = 0;
1353   if (a)
1354     c = &b.s;
1355   bar (*c, a);
1356 }
1357
1358 //===---------------------------------------------------------------------===//
1359
1360 simplifylibcalls should do several optimizations for strspn/strcspn:
1361
1362 strcspn(x, "") -> strlen(x)
1363 strcspn("", x) -> 0
1364 strspn("", x) -> 0
1365 strspn(x, "") -> strlen(x)
1366 strspn(x, "a") -> strchr(x, 'a')-x
1367
1368 strcspn(x, "a") -> inlined loop for up to 3 letters (similarly for strspn):
1369
1370 size_t __strcspn_c3 (__const char *__s, int __reject1, int __reject2,
1371                      int __reject3) {
1372   register size_t __result = 0;
1373   while (__s[__result] != '\0' && __s[__result] != __reject1 &&
1374          __s[__result] != __reject2 && __s[__result] != __reject3)
1375     ++__result;
1376   return __result;
1377 }
1378
1379 This should turn into a switch on the character.  See PR3253 for some notes on
1380 codegen.
1381
1382 456.hmmer apparently uses strcspn and strspn a lot.  471.omnetpp uses strspn.
1383
1384 //===---------------------------------------------------------------------===//
1385
1386 "gas" uses this idiom:
1387   else if (strchr ("+-/*%|&^:[]()~", *intel_parser.op_string))
1388 ..
1389   else if (strchr ("<>", *intel_parser.op_string)
1390
1391 Those should be turned into a switch.
1392
1393 //===---------------------------------------------------------------------===//
1394
1395 252.eon contains this interesting code:
1396
1397         %3072 = getelementptr [100 x i8]* %tempString, i32 0, i32 0
1398         %3073 = call i8* @strcpy(i8* %3072, i8* %3071) nounwind
1399         %strlen = call i32 @strlen(i8* %3072)    ; uses = 1
1400         %endptr = getelementptr [100 x i8]* %tempString, i32 0, i32 %strlen
1401         call void @llvm.memcpy.i32(i8* %endptr,
1402           i8* getelementptr ([5 x i8]* @"\01LC42", i32 0, i32 0), i32 5, i32 1)
1403         %3074 = call i32 @strlen(i8* %endptr) nounwind readonly
1404
1405 This is interesting for a couple reasons.  First, in this:
1406
1407         %3073 = call i8* @strcpy(i8* %3072, i8* %3071) nounwind
1408         %strlen = call i32 @strlen(i8* %3072)
1409
1410 The strlen could be replaced with: %strlen = sub %3072, %3073, because the
1411 strcpy call returns a pointer to the end of the string.  Based on that, the
1412 endptr GEP just becomes equal to 3073, which eliminates a strlen call and GEP.
1413
1414 Second, the memcpy+strlen strlen can be replaced with:
1415
1416         %3074 = call i32 @strlen([5 x i8]* @"\01LC42") nounwind readonly
1417
1418 Because the destination was just copied into the specified memory buffer.  This,
1419 in turn, can be constant folded to "4".
1420
1421 In other code, it contains:
1422
1423         %endptr6978 = bitcast i8* %endptr69 to i32*
1424         store i32 7107374, i32* %endptr6978, align 1
1425         %3167 = call i32 @strlen(i8* %endptr69) nounwind readonly
1426
1427 Which could also be constant folded.  Whatever is producing this should probably
1428 be fixed to leave this as a memcpy from a string.
1429
1430 Further, eon also has an interesting partially redundant strlen call:
1431
1432 bb8:            ; preds = %_ZN18eonImageCalculatorC1Ev.exit
1433         %682 = getelementptr i8** %argv, i32 6          ; <i8**> [#uses=2]
1434         %683 = load i8** %682, align 4          ; <i8*> [#uses=4]
1435         %684 = load i8* %683, align 1           ; <i8> [#uses=1]
1436         %685 = icmp eq i8 %684, 0               ; <i1> [#uses=1]
1437         br i1 %685, label %bb10, label %bb9
1438
1439 bb9:            ; preds = %bb8
1440         %686 = call i32 @strlen(i8* %683) nounwind readonly
1441         %687 = icmp ugt i32 %686, 254           ; <i1> [#uses=1]
1442         br i1 %687, label %bb10, label %bb11
1443
1444 bb10:           ; preds = %bb9, %bb8
1445         %688 = call i32 @strlen(i8* %683) nounwind readonly
1446
1447 This could be eliminated by doing the strlen once in bb8, saving code size and
1448 improving perf on the bb8->9->10 path.
1449
1450 //===---------------------------------------------------------------------===//
1451
1452 I see an interesting fully redundant call to strlen left in 186.crafty:InputMove
1453 which looks like:
1454        %movetext11 = getelementptr [128 x i8]* %movetext, i32 0, i32 0
1455
1456
1457 bb62:           ; preds = %bb55, %bb53
1458         %promote.0 = phi i32 [ %169, %bb55 ], [ 0, %bb53 ]
1459         %171 = call i32 @strlen(i8* %movetext11) nounwind readonly align 1
1460         %172 = add i32 %171, -1         ; <i32> [#uses=1]
1461         %173 = getelementptr [128 x i8]* %movetext, i32 0, i32 %172
1462
1463 ...  no stores ...
1464        br i1 %or.cond, label %bb65, label %bb72
1465
1466 bb65:           ; preds = %bb62
1467         store i8 0, i8* %173, align 1
1468         br label %bb72
1469
1470 bb72:           ; preds = %bb65, %bb62
1471         %trank.1 = phi i32 [ %176, %bb65 ], [ -1, %bb62 ]
1472         %177 = call i32 @strlen(i8* %movetext11) nounwind readonly align 1
1473
1474 Note that on the bb62->bb72 path, that the %177 strlen call is partially
1475 redundant with the %171 call.  At worst, we could shove the %177 strlen call
1476 up into the bb65 block moving it out of the bb62->bb72 path.   However, note
1477 that bb65 stores to the string, zeroing out the last byte.  This means that on
1478 that path the value of %177 is actually just %171-1.  A sub is cheaper than a
1479 strlen!
1480
1481 This pattern repeats several times, basically doing:
1482
1483   A = strlen(P);
1484   P[A-1] = 0;
1485   B = strlen(P);
1486   where it is "obvious" that B = A-1.
1487
1488 //===---------------------------------------------------------------------===//
1489
1490 186.crafty contains this interesting pattern:
1491
1492 %77 = call i8* @strstr(i8* getelementptr ([6 x i8]* @"\01LC5", i32 0, i32 0),
1493                        i8* %30)
1494 %phitmp648 = icmp eq i8* %77, getelementptr ([6 x i8]* @"\01LC5", i32 0, i32 0)
1495 br i1 %phitmp648, label %bb70, label %bb76
1496
1497 bb70:           ; preds = %OptionMatch.exit91, %bb69
1498         %78 = call i32 @strlen(i8* %30) nounwind readonly align 1               ; <i32> [#uses=1]
1499
1500 This is basically:
1501   cststr = "abcdef";
1502   if (strstr(cststr, P) == cststr) {
1503      x = strlen(P);
1504      ...
1505
1506 The strstr call would be significantly cheaper written as:
1507
1508 cststr = "abcdef";
1509 if (memcmp(P, str, strlen(P)))
1510   x = strlen(P);
1511
1512 This is memcmp+strlen instead of strstr.  This also makes the strlen fully
1513 redundant.
1514
1515 //===---------------------------------------------------------------------===//
1516
1517 186.crafty also contains this code:
1518
1519 %1906 = call i32 @strlen(i8* getelementptr ([32 x i8]* @pgn_event, i32 0,i32 0))
1520 %1907 = getelementptr [32 x i8]* @pgn_event, i32 0, i32 %1906
1521 %1908 = call i8* @strcpy(i8* %1907, i8* %1905) nounwind align 1
1522 %1909 = call i32 @strlen(i8* getelementptr ([32 x i8]* @pgn_event, i32 0,i32 0))
1523 %1910 = getelementptr [32 x i8]* @pgn_event, i32 0, i32 %1909
1524
1525 The last strlen is computable as 1908-@pgn_event, which means 1910=1908.
1526
1527 //===---------------------------------------------------------------------===//
1528
1529 186.crafty has this interesting pattern with the "out.4543" variable:
1530
1531 call void @llvm.memcpy.i32(
1532         i8* getelementptr ([10 x i8]* @out.4543, i32 0, i32 0),
1533        i8* getelementptr ([7 x i8]* @"\01LC28700", i32 0, i32 0), i32 7, i32 1)
1534 %101 = call@printf(i8* ...   @out.4543, i32 0, i32 0)) nounwind
1535
1536 It is basically doing:
1537
1538   memcpy(globalarray, "string");
1539   printf(...,  globalarray);
1540
1541 Anyway, by knowing that printf just reads the memory and forward substituting
1542 the string directly into the printf, this eliminates reads from globalarray.
1543 Since this pattern occurs frequently in crafty (due to the "DisplayTime" and
1544 other similar functions) there are many stores to "out".  Once all the printfs
1545 stop using "out", all that is left is the memcpy's into it.  This should allow
1546 globalopt to remove the "stored only" global.
1547
1548 //===---------------------------------------------------------------------===//
1549
1550 This code:
1551
1552 define inreg i32 @foo(i8* inreg %p) nounwind {
1553   %tmp0 = load i8* %p
1554   %tmp1 = ashr i8 %tmp0, 5
1555   %tmp2 = sext i8 %tmp1 to i32
1556   ret i32 %tmp2
1557 }
1558
1559 could be dagcombine'd to a sign-extending load with a shift.
1560 For example, on x86 this currently gets this:
1561
1562         movb    (%eax), %al
1563         sarb    $5, %al
1564         movsbl  %al, %eax
1565
1566 while it could get this:
1567
1568         movsbl  (%eax), %eax
1569         sarl    $5, %eax
1570
1571 //===---------------------------------------------------------------------===//
1572
1573 GCC PR31029:
1574
1575 int test(int x) { return 1-x == x; }     // --> return false
1576 int test2(int x) { return 2-x == x; }    // --> return x == 1 ?
1577
1578 Always foldable for odd constants, what is the rule for even?
1579
1580 //===---------------------------------------------------------------------===//
1581
1582 PR 3381: GEP to field of size 0 inside a struct could be turned into GEP
1583 for next field in struct (which is at same address).
1584
1585 For example: store of float into { {{}}, float } could be turned into a store to
1586 the float directly.
1587
1588 //===---------------------------------------------------------------------===//
1589
1590 #include <math.h>
1591 double foo(double a) {    return sin(a); }
1592
1593 This compiles into this on x86-64 Linux:
1594 foo:
1595         subq    $8, %rsp
1596         call    sin
1597         addq    $8, %rsp
1598         ret
1599 vs:
1600
1601 foo:
1602         jmp sin
1603
1604 //===---------------------------------------------------------------------===//
1605
1606 The arg promotion pass should make use of nocapture to make its alias analysis
1607 stuff much more precise.
1608
1609 //===---------------------------------------------------------------------===//
1610
1611 The following functions should be optimized to use a select instead of a
1612 branch (from gcc PR40072):
1613
1614 char char_int(int m) {if(m>7) return 0; return m;}
1615 int int_char(char m) {if(m>7) return 0; return m;}
1616
1617 //===---------------------------------------------------------------------===//
1618
1619 int func(int a, int b) { if (a & 0x80) b |= 0x80; else b &= ~0x80; return b; }
1620
1621 Generates this:
1622
1623 define i32 @func(i32 %a, i32 %b) nounwind readnone ssp {
1624 entry:
1625   %0 = and i32 %a, 128                            ; <i32> [#uses=1]
1626   %1 = icmp eq i32 %0, 0                          ; <i1> [#uses=1]
1627   %2 = or i32 %b, 128                             ; <i32> [#uses=1]
1628   %3 = and i32 %b, -129                           ; <i32> [#uses=1]
1629   %b_addr.0 = select i1 %1, i32 %3, i32 %2        ; <i32> [#uses=1]
1630   ret i32 %b_addr.0
1631 }
1632
1633 However, it's functionally equivalent to:
1634
1635          b = (b & ~0x80) | (a & 0x80);
1636
1637 Which generates this:
1638
1639 define i32 @func(i32 %a, i32 %b) nounwind readnone ssp {
1640 entry:
1641   %0 = and i32 %b, -129                           ; <i32> [#uses=1]
1642   %1 = and i32 %a, 128                            ; <i32> [#uses=1]
1643   %2 = or i32 %0, %1                              ; <i32> [#uses=1]
1644   ret i32 %2
1645 }
1646
1647 This can be generalized for other forms:
1648
1649      b = (b & ~0x80) | (a & 0x40) << 1;
1650
1651 //===---------------------------------------------------------------------===//
1652
1653 These two functions produce different code. They shouldn't:
1654
1655 #include <stdint.h>
1656
1657 uint8_t p1(uint8_t b, uint8_t a) {
1658   b = (b & ~0xc0) | (a & 0xc0);
1659   return (b);
1660 }
1661
1662 uint8_t p2(uint8_t b, uint8_t a) {
1663   b = (b & ~0x40) | (a & 0x40);
1664   b = (b & ~0x80) | (a & 0x80);
1665   return (b);
1666 }
1667
1668 define zeroext i8 @p1(i8 zeroext %b, i8 zeroext %a) nounwind readnone ssp {
1669 entry:
1670   %0 = and i8 %b, 63                              ; <i8> [#uses=1]
1671   %1 = and i8 %a, -64                             ; <i8> [#uses=1]
1672   %2 = or i8 %1, %0                               ; <i8> [#uses=1]
1673   ret i8 %2
1674 }
1675
1676 define zeroext i8 @p2(i8 zeroext %b, i8 zeroext %a) nounwind readnone ssp {
1677 entry:
1678   %0 = and i8 %b, 63                              ; <i8> [#uses=1]
1679   %.masked = and i8 %a, 64                        ; <i8> [#uses=1]
1680   %1 = and i8 %a, -128                            ; <i8> [#uses=1]
1681   %2 = or i8 %1, %0                               ; <i8> [#uses=1]
1682   %3 = or i8 %2, %.masked                         ; <i8> [#uses=1]
1683   ret i8 %3
1684 }
1685
1686 //===---------------------------------------------------------------------===//
1687
1688 IPSCCP does not currently propagate argument dependent constants through
1689 functions where it does not not all of the callers.  This includes functions
1690 with normal external linkage as well as templates, C99 inline functions etc.
1691 Specifically, it does nothing to:
1692
1693 define i32 @test(i32 %x, i32 %y, i32 %z) nounwind {
1694 entry:
1695   %0 = add nsw i32 %y, %z
1696   %1 = mul i32 %0, %x
1697   %2 = mul i32 %y, %z
1698   %3 = add nsw i32 %1, %2
1699   ret i32 %3
1700 }
1701
1702 define i32 @test2() nounwind {
1703 entry:
1704   %0 = call i32 @test(i32 1, i32 2, i32 4) nounwind
1705   ret i32 %0
1706 }
1707
1708 It would be interesting extend IPSCCP to be able to handle simple cases like
1709 this, where all of the arguments to a call are constant.  Because IPSCCP runs
1710 before inlining, trivial templates and inline functions are not yet inlined.
1711 The results for a function + set of constant arguments should be memoized in a
1712 map.
1713
1714 //===---------------------------------------------------------------------===//
1715
1716 The libcall constant folding stuff should be moved out of SimplifyLibcalls into
1717 libanalysis' constantfolding logic.  This would allow IPSCCP to be able to
1718 handle simple things like this:
1719
1720 static int foo(const char *X) { return strlen(X); }
1721 int bar() { return foo("abcd"); }
1722
1723 //===---------------------------------------------------------------------===//
1724
1725 InstCombine should use SimplifyDemandedBits to remove the or instruction:
1726
1727 define i1 @test(i8 %x, i8 %y) {
1728   %A = or i8 %x, 1
1729   %B = icmp ugt i8 %A, 3
1730   ret i1 %B
1731 }
1732
1733 Currently instcombine calls SimplifyDemandedBits with either all bits or just
1734 the sign bit, if the comparison is obviously a sign test. In this case, we only
1735 need all but the bottom two bits from %A, and if we gave that mask to SDB it
1736 would delete the or instruction for us.
1737
1738 //===---------------------------------------------------------------------===//