Failure to notice that all arguments of a phi are the same

[llvmbot]

Bugzilla Link	13307
Version	trunk
OS	Linux
Reporter	LLVM Bugzilla Contributor
CC	@jrmuizel

Extended Description

We compile

void * malloc_rtree_get(void **node) {
void *ret;
unsigned i;

for (i = 0; i < 10; i++) {
void child = (void)node[0];
if (child == ((void*)0)) {
return (((void*)0));
}
node = child;
}
ret = node[0];
return (ret);
}

to

define i8* @​malloc_rtree_get(i8** nocapture %node) nounwind uwtable readonly ssp {
entry:
br label %for.cond
for.cond: ; preds = %if.end, %entry
%i.0 = phi i32 [ 0, %entry ], [ %inc, %if.end ]
%node.addr.0 = phi i8** [ %node, %entry ], [ %1, %if.end ]
%cmp = icmp ult i32 %i.0, 10
%0 = load i8** %node.addr.0, align 8, !tbaa !​0
br i1 %cmp, label %for.body, label %return
for.body: ; preds = %for.cond
%cmp1 = icmp eq i8* %0, null
br i1 %cmp1, label %return, label %if.end
if.end: ; preds = %for.body
%1 = bitcast i8* %0 to i8**
%inc = add i32 %i.0, 1
br label %for.cond
return: ; preds = %for.cond, %for.body
%retval.0 = phi i8* [ null, %for.body ], [ %0, %for.cond ]
ret i8* %retval.0
}

Note that if we jump from for.body to return then %0 is null and we could just use %0 instead of creating %retval.0.

[llvmbot]

GVN's propagateEquality should get this.

[llvmbot]

Sorry, that should have read: GVN's propagateEquality probably caused this.
Something similar happens a lot with select instructions, for example
select (x != 0) ? x : 0;

[llvmbot]

Just started looking at this a bit. Some observations on how we get here:

• In this particular example it looks we get here directly from the code, as with -O0 we have

  store i8* null, i8** %retval
  br label %return

which then gets translated to the phi.

• If we replace the "return (((void*)0));" with "return child;" we do get a
  simple "ret i8* %1" after instcombine, but lcssa and loop-rotate turn that into a phi of "first iteration, rest" and then correlated-propagation propagates the value of the first iteration case giving us the "same" phi.

And how to solve it:

• In simple cases like (x != 0 ? x : 0) we first get

define i32 @​f(i32 %x) {
entry:
%cmp = icmp eq i32 %x, 0
br i1 %cmp, label %cond.false, label %cond.true
cond.true:
br label %cond.end
cond.false:
br label %cond.end
cond.end:
%cond = phi i32 [ %x, %cond.true ], [ 0, %cond.false ]
ret i32 %cond
}

which simplifycfg can turn into

define i32 @​f(i32 %x) {
entry:
%cmp = icmp eq i32 %x, 0
%.x = select i1 %cmp, i32 0, i32 %x
ret i32 %.x
}

and instcombine then turns to just "ret i32 %x".

creating a select in the more complicated case doesn't help as it would be on %cmp and the comparison to null is %cmp1, so instsimplify will not be able to remove it.

I think the best way of looking at this is that instsimplify (or maybe gvn) should be able to handle the simple case without the help from simplifycfg. Even the simple case is not solved by any pass in -std-compile-opts if the simplifycfg runs are removed.