Optimizations like LoadPRE in GVN will insert new instructions. If the insertion point is in a already processed BB, they should get a value number explicitly. If the insertion point is after current instruction, then just leave it. However, current GVN framework has no support for it.
In this patch, we just bail out if a VN can't be found.
Details
Details
- Reviewers
• dberlin
Diff Detail
Diff Detail
Event Timeline
Comment Actions
This patch adds a reduced test from SPASS.
we need the check:
if (Num >= NextNum)
addToLeaderTable(Num, I, I->getParent());Otherwise, BB %wile.end (see line 91) will become :
while.end: ; preds = %while.cond.16
%add.ptr = getelementptr inbounds i8, i8* %v2, i32 undef store i8* %add.ptr, i8** @dfg_text, align 4 %sub.ptr.sub26 = sub i32 0, %0 ==> use here %0 = ptrtoint i8* %add.ptr to i32 ==> def here switch i32 undef, label %sw.default [ i32 65, label %while.bodythread-pre-split
Comment Actions
Err, then the algorithm is broken somewhere.
This is definitely not the right fix from what i've seen so far.
Can you see what decides to insert this?
I suspect, based on your failure mode, that the leader table is not ordered
locally by dominance, only by bb, and so when it calls findLeader, it grabs
the first thing it finds, and does a broken thing.
It would only work in the processInstruction case because processInstrucion
goes in dominance order.
If so, that would be bad (and hard to fix well without serious surgery),
and we should probably declare it broken, revert your set of patches, and
just abort PRE (IE the other option i suggested where we set success=false
and bailing)
Comment Actions
Hi Berlin,
Here is what’s happening:
When it sees the load in BB if.then.14:
%v1 = load i32, i32* bitcast (i8** @dfg_text to i32*), align 4
Then, it tries to do PRE.
So it finds the store in BB while.end:
store i8* %add.ptr, i8** @dfg_text, align 4
So, in GetStoreValueForLoad, it inserts a PtrToInt (line 1153)
Now, the BB becomes
while.end: ; preds = %while.cond.16
%add.ptr = getelementptr inbo %sub.ptr.rhs.cast25 unds i8, i8* %v2, i32 undef store i8* %add.ptr, i8** @dfg_text, align 4 %sub.ptr.rhs.cast25 = ptrtoint i8* %add.ptr to i32 *** original ptrtoint *** %sub.ptr.sub26 = sub i32 0, %sub.ptr.rhs.cast25 %0 = ptrtoint i8* %add.ptr to i32 *** newly created *** switch i32 undef, label %sw.default [
This new instruction happens to have the same GVN as %sub.ptr.rhs.cast25
So, when GVN process BB while.end, if finds that %sub.ptr.rhs.cast25 already have a GVN, so deleted it and replaces the use with %0, which is wrong.
So it seems we do need to check if a VN exists before adding to LaderTable in addNewInstruction().
Comment Actions
This is actually exactly what i feared.
"So it seems we do need to check if a VN exists before adding to LaderTable
in addNewInstruction().
"
No, it means the leader table is messed up.
THe check you are trying to add is equivalent to this:
02382 If the number we were assigned was a brand new VN, then we
don't02383 need to do a lookup to see if the number already
exists02384 // somewhere in the domtree: it can't!02385 if (Num >=
NextNum) {02386 addToLeaderTable(Num, I, I->getParent
http://llvm.org/docs/doxygen/html/classllvm_1_1Instruction.html#a9cd49851904f15060edb782ef4dd1b2d());02387
return false;02388 }
As i mentioned, it's doing this because it's not sensible to call
findLeader on a new value number.
Replicating this in the new instruction code fixes nothing. It's just plain
wrong ;-)
In fact, your code does this:
unsigned Num = VN.lookup_or_add(I); uint32_t NextNum = VN.getNextUnusedValueNumber();
This is the wrong order to call these in ;-)
You want to get the next unused number before lookup/add it.
In any case, the bug you have found is that findLeader(VN for ptrtoint,
BB) is returning the wrong answer, as I suspect.
It should return %sub.ptr.rhs.cast25 in that BB, but it's returning %0.
This is because the leader table management is a bit broken, and expects to
only have a single value per bb (which makes little to no sense if you
handle loads, but GVN doesn't so it can get away with it).
One possible fix i can think of:
Right now you have:
// Assign VNs for instructions newly created during GVN optimization.
void addNewInstruction(Value *Val) {
if (Instruction *I = dyn_cast<Instruction>(Val)) {
unsigned Num = VN.lookup_or_add(I);
uint32_t NextNum = VN.getNextUnusedValueNumber();
if (Num >= NextNum)
addToLeaderTable(Num, I, I->getParent());
}
}change it to
// Assign VNs for instructions newly created during GVN optimization.
Value *findOrAddNewInstruction(Value *Val) {
if (Instruction *I = dyn_cast<Instruction>(Val)) {// Note: I reversed the order to be correct
uint32_t NextNum = VN.getNextUnusedValueNumber();
unsigned Num = VN.lookup_or_add(I);
if (Num >= NextNum) {
addToLeaderTable(Num, I, I->getParent());
return nullptr;
} else if (Value *Existing = findLeader(I->getParent(), Num)) {
return Existing;
} else {
addToLeaderTable(Num, I, I->getParent());
}
}
}Call add new instruction, and if it returns non null, replace the
instruction you created with the return value (or GVN will do it later for
you if you like).
If you'd rather have GVN do that part, change it to:
void addNewInstruction(Value *Val) {
if (Instruction *I = dyn_cast<Instruction>(Val)) {
// Note: I reversed the order to be correct
uint32_t NextNum = VN.getNextUnusedValueNumber();
unsigned Num = VN.lookup_or_add(I);
if (Num >= NextNum) {
addToLeaderTable(Num, I, I->getParent());
} else if (findLeader(I->getParent(), Num) != nullptr) {
return;
} else {
addToLeaderTable(Num, I, I->getParent());
}
}
}GVN will do the propagation for you, at the expense of extra findLeader
calls
Comment Actions
(this patch is mainly for discussion)
Hi Berlin,
Very appreciate for the explanation.
My previous order about NextNum was indeed wrong, and thus addToLeaderTable was never executed, which masked the another problem:
the newly created inst (%0) will get the VN before %sub.ptr.rhs.cast25. The NextNum check won’t prevent this.
Looks like we should only assign numbers for new instrs that would have been visited (we only do make ups). For new instrs inserted in future points, we just leave it and wait for it to be processed naturally.
But I can't find such support from existing GVN framework. I have an approximated solution in the patch.
Any suggestions?
Comment Actions
I think this is going to be pretty much impossible to solve sanely in the
current infrastructure.
Rather than try to make this more and more complicated, i would suggest we
just step back and go with a variant on your original patch.
The attached should work (untested though, not on a computer with actual up
to date llvm source ;P)
Comment Actions
I agree. There is no easy fix. I applied your patch, run clang-format and verified that it passed the tests.
creates PtrToInt here, but has the same VN as %sub.ptr.rhs.cast25