lib/Target/README.txt

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