//===---------------------------------------------------------------------===//
+Dead argument elimination should be enhanced to handle cases when an argument is
+dead to an externally visible function. Though the argument can't be removed
+from the externally visible function, the caller doesn't need to pass it in.
+For example in this testcase:
+
+ void foo(int X) __attribute__((noinline));
+ void foo(int X) { sideeffect(); }
+ void bar(int A) { foo(A+1); }
+
+We compile bar to:
+
+define void @bar(i32 %A) nounwind ssp {
+ %0 = add nsw i32 %A, 1 ; <i32> [#uses=1]
+ tail call void @foo(i32 %0) nounwind noinline ssp
+ ret void
+}
+
+The add is dead, we could pass in 'i32 undef' instead. This occurs for C++
+templates etc, which usually have linkonce_odr/weak_odr linkage, not internal
+linkage.
+
+//===---------------------------------------------------------------------===//
+
With the recent changes to make the implicit def/use set explicit in
machineinstrs, we should change the target descriptions for 'call' instructions
so that the .td files don't list all the call-clobbered registers as implicit
... which would only do one 32-bit XOR per loop iteration instead of two.
It would also be nice to recognize the reg->size doesn't alias reg->node[i], but
-alas.
+this requires TBAA.
//===---------------------------------------------------------------------===//
return count;
}
+This is a form of idiom recognition for loops, the same thing that could be
+useful for recognizing memset/memcpy.
+
//===---------------------------------------------------------------------===//
These should turn into single 16-bit (unaligned?) loads on little/big endian
//===---------------------------------------------------------------------===//
-LSR should know what GPR types a target has. This code:
+LSR should know what GPR types a target has from TargetData. This code:
volatile short X, Y; // globals
LSR should reuse the "+" IV for the exit test.
-
//===---------------------------------------------------------------------===//
Tail call elim should be more aggressive, checking to see if the call is
//===---------------------------------------------------------------------===//
-"basicaa" should know how to look through "or" instructions that act like add
-instructions. For example in this code, the x*4+1 is turned into x*4 | 1, and
-basicaa can't analyze the array subscript, leading to duplicated loads in the
-generated code:
-
-void test(int X, int Y, int a[]) {
-int i;
- for (i=2; i<1000; i+=4) {
- a[i+0] = a[i-1+0]*a[i-2+0];
- a[i+1] = a[i-1+1]*a[i-2+1];
- a[i+2] = a[i-1+2]*a[i-2+2];
- a[i+3] = a[i-1+3]*a[i-2+3];
- }
-}
-
-BasicAA also doesn't do this for add. It needs to know that &A[i+1] != &A[i].
-
-//===---------------------------------------------------------------------===//
-
We should investigate an instruction sinking pass. Consider this silly
example in pic mode:
true();
}
-I think this basically amounts to a dag combine to simplify comparisons against
-multiply hi's into a comparison against the mullo.
+This is equivalent to the following, where 2863311531 is the multiplicative
+inverse of 3, and 1431655766 is ((2^32)-1)/3+1:
+void bar(unsigned n) {
+ if (n * 2863311531U < 1431655766U)
+ true();
+}
+
+The same transformation can work with an even modulo with the addition of a
+rotate: rotate the result of the multiply to the right by the number of bits
+which need to be zero for the condition to be true, and shrink the compare RHS
+by the same amount. Unless the target supports rotates, though, that
+transformation probably isn't worthwhile.
+
+The transformation can also easily be made to work with non-zero equality
+comparisons: just transform, for example, "n % 3 == 1" to "(n-1) % 3 == 0".
//===---------------------------------------------------------------------===//
//===---------------------------------------------------------------------===//
-Instcombine will merge comparisons like (x >= 10) && (x < 20) by producing (x -
-10) u< 10, but only when the comparisons have matching sign.
-
-This could be converted with a similiar technique. (PR1941)
-
-define i1 @test(i8 %x) {
- %A = icmp uge i8 %x, 5
- %B = icmp slt i8 %x, 20
- %C = and i1 %A, %B
- ret i1 %C
-}
-
-//===---------------------------------------------------------------------===//
-
These functions perform the same computation, but produce different assembly.
define i8 @select(i8 %x) readnone nounwind {
//===---------------------------------------------------------------------===//
-From GCC Bug 15241:
-unsigned int
-foo (unsigned int a, unsigned int b)
-{
- if (a <= 7 && b <= 7)
- baz ();
-}
-Should combine to "(a|b) <= 7". Currently not optimized with "clang
--emit-llvm-bc | opt -std-compile-opts".
-
-//===---------------------------------------------------------------------===//
-
From GCC Bug 3756:
int
pn (int n)
//===---------------------------------------------------------------------===//
-From GCC Bug 28685:
-int test(int a, int b)
-{
- int lt = a < b;
- int eq = a == b;
-
- return (lt || eq);
-}
-Should combine to "a <= b". Currently not optimized with "clang
--emit-llvm-bc | opt -std-compile-opts | llc".
-
-//===---------------------------------------------------------------------===//
-
void a(int variable)
{
if (variable == 4 || variable == 6)
//===---------------------------------------------------------------------===//
-int a(unsigned char* b) {return *b > 99;}
-There's an unnecessary zext in the generated code with "clang
--emit-llvm-bc | opt -std-compile-opts".
-
-//===---------------------------------------------------------------------===//
-
int a(unsigned b) {return ((b << 31) | (b << 30)) >> 31;}
Should be combined to "((b >> 1) | b) & 1". Currently not optimized
with "clang -emit-llvm-bc | opt -std-compile-opts".
//===---------------------------------------------------------------------===//
-unsigned a(unsigned a) {return ((a | 1) & 3) | (a & -4);}
-Should combine to "a | 1". Currently not optimized with "clang
--emit-llvm-bc | opt -std-compile-opts".
-
-//===---------------------------------------------------------------------===//
-
int a(int a, int b, int c) {return (~a & c) | ((c|a) & b);}
Should fold to "(~a & c) | (a & b)". Currently not optimized with
"clang -emit-llvm-bc | opt -std-compile-opts".
//===---------------------------------------------------------------------===//
+[STORE SINKING]
+
Store sinking: This code:
void f (int n, int *cond, int *res) {
//===---------------------------------------------------------------------===//
+[STORE SINKING]
+
GCC PR37810 is an interesting case where we should sink load/store reload
into the if block and outside the loop, so we don't reload/store it on the
non-call path.
//===---------------------------------------------------------------------===//
-[PHI TRANSLATE GEPs]
+[LOAD PRE CRIT EDGE SPLITTING]
GCC PR37166: Sinking of loads prevents SROA'ing the "g" struct on the stack
leading to excess stack traffic. This could be handled by GVN with some crazy
%10 = getelementptr %struct.f* %c_addr.0, i32 0, i32 0
%11 = load i32* %10, align 4
-%11 is fully redundant, an in BB2 it should have the value %8.
+%11 is partially redundant, an in BB2 it should have the value %8.
+
+GCC PR33344 and PR35287 are similar cases.
-GCC PR33344 is a similar case.
//===---------------------------------------------------------------------===//
-[PHI TRANSLATE INDEXED GEPs] PR5313
+[LOAD PRE]
-Load redundancy elimination for simple loop. This loop:
+There are many load PRE testcases in testsuite/gcc.dg/tree-ssa/loadpre* in the
+GCC testsuite, ones we don't get yet are (checked through loadpre25):
-void append_text(const char* text,unsigned char * const io) {
- while(*text)
- *io=*text++;
-}
+[CRIT EDGE BREAKING]
+loadpre3.c predcom-4.c
-Compiles to have a fully redundant load in the loop (%2):
+[PRE OF READONLY CALL]
+loadpre5.c
-define void @append_text(i8* nocapture %text, i8* nocapture %io) nounwind {
-entry:
- %0 = load i8* %text, align 1 ; <i8> [#uses=1]
- %1 = icmp eq i8 %0, 0 ; <i1> [#uses=1]
- br i1 %1, label %return, label %bb
-
-bb: ; preds = %bb, %entry
- %indvar = phi i32 [ 0, %entry ], [ %tmp, %bb ] ; <i32> [#uses=2]
- %text_addr.04 = getelementptr i8* %text, i32 %indvar ; <i8*> [#uses=1]
- %2 = load i8* %text_addr.04, align 1 ; <i8> [#uses=1]
- store i8 %2, i8* %io, align 1
- %tmp = add i32 %indvar, 1 ; <i32> [#uses=2]
- %scevgep = getelementptr i8* %text, i32 %tmp ; <i8*> [#uses=1]
- %3 = load i8* %scevgep, align 1 ; <i8> [#uses=1]
- %4 = icmp eq i8 %3, 0 ; <i1> [#uses=1]
- br i1 %4, label %return, label %bb
-
-return: ; preds = %bb, %entry
- ret void
-}
+[TURN SELECT INTO BRANCH]
+loadpre14.c loadpre15.c
-//===---------------------------------------------------------------------===//
+actually a conditional increment: loadpre18.c loadpre19.c
-There are many load PRE testcases in testsuite/gcc.dg/tree-ssa/loadpre* in the
-GCC testsuite. There are many pre testcases as ssa-pre-*.c
//===---------------------------------------------------------------------===//
-There are some interesting cases in testsuite/gcc.dg/tree-ssa/pred-comm* in the
-GCC testsuite. For example, predcom-1.c is:
-
- for (i = 2; i < 1000; i++)
- fib[i] = (fib[i-1] + fib[i - 2]) & 0xffff;
-
-which compiles into:
-
-bb1: ; preds = %bb1, %bb1.thread
- %indvar = phi i32 [ 0, %bb1.thread ], [ %0, %bb1 ]
- %i.0.reg2mem.0 = add i32 %indvar, 2
- %0 = add i32 %indvar, 1 ; <i32> [#uses=3]
- %1 = getelementptr [1000 x i32]* @fib, i32 0, i32 %0
- %2 = load i32* %1, align 4 ; <i32> [#uses=1]
- %3 = getelementptr [1000 x i32]* @fib, i32 0, i32 %indvar
- %4 = load i32* %3, align 4 ; <i32> [#uses=1]
- %5 = add i32 %4, %2 ; <i32> [#uses=1]
- %6 = and i32 %5, 65535 ; <i32> [#uses=1]
- %7 = getelementptr [1000 x i32]* @fib, i32 0, i32 %i.0.reg2mem.0
- store i32 %6, i32* %7, align 4
- %exitcond = icmp eq i32 %0, 998 ; <i1> [#uses=1]
- br i1 %exitcond, label %return, label %bb1
+[SCALAR PRE]
+There are many PRE testcases in testsuite/gcc.dg/tree-ssa/ssa-pre-*.c in the
+GCC testsuite.
-This is basically:
- LOAD fib[i+1]
- LOAD fib[i]
- STORE fib[i+2]
+//===---------------------------------------------------------------------===//
-instead of handling this as a loop or other xform, all we'd need to do is teach
-load PRE to phi translate the %0 add (i+1) into the predecessor as (i'+1+1) =
-(i'+2) (where i' is the previous iteration of i). This would find the store
-which feeds it.
+There are some interesting cases in testsuite/gcc.dg/tree-ssa/pred-comm* in the
+GCC testsuite. For example, we get the first example in predcom-1.c, but
+miss the second one:
-predcom-2.c is apparently the same as predcom-1.c
-predcom-3.c is very similar but needs loads feeding each other instead of
-store->load.
-predcom-4.c seems the same as the rest.
+unsigned fib[1000];
+unsigned avg[1000];
+__attribute__ ((noinline))
+void count_averages(int n) {
+ int i;
+ for (i = 1; i < n; i++)
+ avg[i] = (((unsigned long) fib[i - 1] + fib[i] + fib[i + 1]) / 3) & 0xffff;
+}
-//===---------------------------------------------------------------------===//
+which compiles into two loads instead of one in the loop.
-Other simple load PRE cases:
-http://gcc.gnu.org/bugzilla/show_bug.cgi?id=35287 [LPRE crit edge splitting]
+predcom-2.c is the same as predcom-1.c
-http://gcc.gnu.org/bugzilla/show_bug.cgi?id=34677 (licm does this, LPRE crit edge)
- llvm-gcc t2.c -S -o - -O0 -emit-llvm | llvm-as | opt -mem2reg -simplifycfg -gvn | llvm-dis
+predcom-3.c is very similar but needs loads feeding each other instead of
+store->load.
-http://gcc.gnu.org/bugzilla/show_bug.cgi?id=16799 [BITCAST PHI TRANS]
//===---------------------------------------------------------------------===//
http://gcc.gnu.org/bugzilla/show_bug.cgi?id=26629
With: llvm-gcc t2.c -S -o - -O0 -emit-llvm | llvm-as |
opt -mem2reg -gvn -instcombine | llvm-dis
-we miss it because we need 1) GEP PHI TRAN, 2) CRIT EDGE 3) MULTIPLE DIFFERENT
+we miss it because we need 1) CRIT EDGE 2) MULTIPLE DIFFERENT
VALS PRODUCED BY ONE BLOCK OVER DIFFERENT PATHS
//===---------------------------------------------------------------------===//
map.
//===---------------------------------------------------------------------===//
+
+The libcall constant folding stuff should be moved out of SimplifyLibcalls into
+libanalysis' constantfolding logic. This would allow IPSCCP to be able to
+handle simple things like this:
+
+static int foo(const char *X) { return strlen(X); }
+int bar() { return foo("abcd"); }
+
+//===---------------------------------------------------------------------===//
+
+InstCombine should use SimplifyDemandedBits to remove the or instruction:
+
+define i1 @test(i8 %x, i8 %y) {
+ %A = or i8 %x, 1
+ %B = icmp ugt i8 %A, 3
+ ret i1 %B
+}
+
+Currently instcombine calls SimplifyDemandedBits with either all bits or just
+the sign bit, if the comparison is obviously a sign test. In this case, we only
+need all but the bottom two bits from %A, and if we gave that mask to SDB it
+would delete the or instruction for us.
+
+//===---------------------------------------------------------------------===//
+
+FunctionAttrs is not marking this function as readnone (just readonly):
+$ clang t.c -emit-llvm -S -o - -O0 | opt -mem2reg -S -functionattrs
+
+int t(int a, int b, int c) {
+ int *p;
+ if (a)
+ p = &a;
+ else
+ p = &c;
+ return *p;
+}
+
+This is because we codegen this to:
+
+define i32 @t(i32 %a, i32 %b, i32 %c) nounwind readonly ssp {
+entry:
+ %a.addr = alloca i32 ; <i32*> [#uses=3]
+ %c.addr = alloca i32 ; <i32*> [#uses=2]
+...
+
+if.end:
+ %p.0 = phi i32* [ %a.addr, %if.then ], [ %c.addr, %if.else ]
+ %tmp2 = load i32* %p.0 ; <i32> [#uses=1]
+ ret i32 %tmp2
+}
+
+And functionattrs doesn't realize that the p.0 load points to function local
+memory.
+
+Also, functionattrs doesn't know about memcpy/memset. This function should be
+marked readnone, since it only twiddles local memory, but functionattrs doesn't
+handle memset/memcpy/memmove aggressively:
+
+struct X { int *p; int *q; };
+int foo() {
+ int i = 0, j = 1;
+ struct X x, y;
+ int **p;
+ y.p = &i;
+ x.q = &j;
+ p = __builtin_memcpy (&x, &y, sizeof (int *));
+ return **p;
+}
+
+//===---------------------------------------------------------------------===//
+
projects / oota-llvm.git / blobdiff