Problem with "Does not dominate all uses"

Hi!

I'm having some trouble with a pass I'm writing.

I'm using DemotePHIToStack to remove all phi node in my code with this code (this is the first thing I do in my pass):

    // Erase phi node
    vector<PHINode*> phis;
    for (Function::iterator i=f->begin();i!=f->end();++i) {
        for(BasicBlock::iterator b=i->begin();b!=i->end();++b) {
            if(isa<PHINode>(b)) {
                PHINode *phi= cast<PHINode>(b);
                phis.push_back(phi);
            }
        }
    }

    for(vector<PHINode*>::iterator i=phis.begin();i!=phis.end();++i) {
        PHINode *phi = *i;
        DemotePHIToStack(phi,NULL);
    }

If I only run this code, I obtain this code (see safer.phi.ll).
If I run the rest of my pass, I obtain this code (see safer.phi.obfu.ll)

And I got this error for the file safer.phi.obfu.ll:

Instruction does not dominate all uses!
  %18 = load i8** %key.addr, align 8, !dbg !322
  call void @Safer_Expand_Userkey(i8* %18, i8* %19, i32 %cond.reload, i32 0, i8* %arraydecay), !dbg !322
Instruction does not dominate all uses!
  %19 = load i8** %key.addr, align 8, !dbg !322
  call void @Safer_Expand_Userkey(i8* %18, i8* %19, i32 %cond.reload, i32 0, i8* %arraydecay), !dbg !322
Broken module found, compilation aborted!
0 opt 0x0000000000946d3f
1 opt 0x0000000000947229
2 libpthread.so.0 0x00007fcba9ff2170
3 libc.so.6 0x00007fcba925dfa5 gsignal + 53
4 libc.so.6 0x00007fcba925f428 abort + 328
5 opt 0x000000000090951d
6 opt 0x00000000008e609f llvm::FPPassManager::runOnFunction(llvm::Function&) + 607
7 opt 0x00000000008e60f3 llvm::FPPassManager::runOnModule(llvm::Module&) + 51
8 opt 0x00000000008e5c6c llvm::MPPassManager::runOnModule(llvm::Module&) + 524
9 opt 0x00000000008e5d77 llvm::PassManagerImpl::run(llvm::Module&) + 151
10 opt 0x00000000004a1d99 main + 3385
11 libc.so.6 0x00007fcba924a725 __libc_start_main + 245
12 opt 0x00000000004a6135
Stack dump:
0. Program arguments: opt -load ../../../build/Release+Asserts/lib/LLVMobfuscation.so -flattening src/ciphers/safer/safer.bc -o src/ciphers/safer/safer.bc -stats
1. Running pass 'Function Pass Manager' on module 'src/ciphers/safer/safer.bc'.
2. Running pass 'Module Verifier' on function '@safer_k64_setup'
make: *** [src/ciphers/safer/safer.o] Aborted

So the problem come from the bloc if.end11 and cond.end. I understand the dominate problem, but the thing is that these instruction (in first file):

if.end11: ; preds = %if.end8
  %6 = load i8** %key.addr, align 8, !dbg !322
  %7 = load i8** %key.addr, align 8, !dbg !322
  ...

cond.end: ; preds = %cond.false, %cond.true
  %cond.reload = load i32* %cond.reg2mem
  %10 = load %union.Symmetric_key** %skey.addr, align 8, !dbg !322
  %safer = bitcast %union.Symmetric_key* %10 to %struct.safer_key*, !dbg !322
  %key13 = getelementptr inbounds %struct.safer_key* %safer, i32 0, i32 0, !dbg !322
  %arraydecay = getelementptr inbounds [217 x i8]* %key13, i32 0, i32 0, !dbg !322
  call void @Safer_Expand_Userkey(i8* %6, i8* %7, i32 %cond.reload, i32 0, i8* %arraydecay), !dbg !322
  store i32 0, i32* %retval, !dbg !323
  br label %return, !dbg !323

are the same in the second file:

if.end11: ; preds = %loopEntry
  %18 = load i8** %key.addr, align 8, !dbg !322
  %19 = load i8** %key.addr, align 8, !dbg !322
  ...

cond.end: ; preds = %loopEntry
  %cond.reload = load i32* %cond.reg2mem
  %24 = load %union.Symmetric_key** %skey.addr, align 8, !dbg !322
  %safer = bitcast %union.Symmetric_key* %24 to %struct.safer_key*, !dbg !322
  %key13 = getelementptr inbounds %struct.safer_key* %safer, i32 0, i32 0, !dbg !322
  %arraydecay = getelementptr inbounds [217 x i8]* %key13, i32 0, i32 0, !dbg !322
  call void @Safer_Expand_Userkey(i8* %18, i8* %19, i32 %cond.reload, i32 0, i8* %arraydecay), !dbg !322
  store i32 0, i32* %retval, !dbg !323
  store i32 14, i32* %switchVar
  br label %loopEnd

I don't understant why the first time I don't have a dominate problem, but the second time I do (I'm pretty sure it's because of the rest of my pass but I can't figure where because the code that cause problem it's the same in the both version).

Any idea?

Thx,
Cheers

safer.phi.ll (4.41 KB)

safer.phi.obfu.ll (5.87 KB)

In your original file, %6 is defined in if.end11 and is used in cond.end. if.end11 branches to cond.true and cond.false, both of which branch unconditionally to cond.end. Therefore %6 dominates its use.

In your second file %18 is defined in end.11 and used in cond.end. However, end.11 no longer dominates cond.end because you have rewritten all branches to go through the switch statement in loopEntry, and it is possible to take the path from entry to loopEntry to cond.end without going through end.11.

Cameron

Oh ok I see the problem...

Thank you very much

Cheers

I have another question.

DemotePHIToStack is not supposed to get rid of this problem, by replacing the instruction with a pointer and so there is no more dominance problem ?

Cheers

ps: sorry for double post