[LLVMdev] identifying all dependent instructions through multi-levels of def-use relationship
Chuck Zhao
czhao at eecg.toronto.edu
Sun May 8 19:11:29 PDT 2011
John, Ether,
Thank you for the reply.
With John's help and suggestions from Ether, I can now identify the full
list of dependent instructions that I need to make a copy and insert
somewhere else (before their original location).
Here is the list:
0 %90 = load i32* @strstart, align 4
1 %91 = add i32 %90, 2
2 %88 = load i32* @ins_h, align 4
3 %92 = getelementptr inbounds [65536 x i8]* @window, i32 0, i32 %91
4 %89 = shl i32 %88, 5
5 %93 = load i8* %92, align 1
6 %.masked = and i32 %89, 32736
7 %94 = zext i8 %93 to i32
8 %95 = xor i32 %94, %.masked
9 %.sum73 = or i32 %95, 32768
10 %104 = getelementptr inbounds [65536 x i16]* @prev, i32 0, i32 %.sum73
11 %take_addr2 = getelementptr i16* %104
12 %105 = bitcast i16* %take_addr2 to i8*
13 call void @bkp_memory(i8* %105, i32 2)
But, when I try to insert them in the above order into a PREVIOUS
location, the "Instruction does not dominate all uses!" still shows up:
Here is the code I was trying to do the clone and insert:
std::vector<Instruction *>::iterator p;
Instruction * Pos = INSERT_POSITION;
for(p = coll.begin(); p != coll.end(); ++p){
Instruction * CurI = *p;
Instruction * CloneI = CurI->clone();
CloneI->InsertAfter(Pos);
Pos = CloneI;
}
i am not sure if this it the right approach to insert a list of
dependent instructions. (For delete instructions, people need to collect
them 1st before removing. Are there similar process for insertion?)
There doesn't seem to have Phi node in the list.
The instructions seem to be inside a single BasicBlock. Would it help?
Thank you very much
Chuck
P.S.
Here is the full list of errors:
Instruction does not dominate all uses!
%88 = bitcast i16* %take_addr2 to i8*
call void @bkp_memory(i8* %88, i32 2)
Instruction does not dominate all uses!
%take_addr2 = getelementptr i16* %89
%88 = bitcast i16* %take_addr2 to i8*
Instruction does not dominate all uses!
%89 = getelementptr inbounds [65536 x i16]* @prev, i32 0, i32 %.sum73
%take_addr2 = getelementptr i16* %89
Instruction does not dominate all uses!
%.sum73 = or i32 %90, 32768
%89 = getelementptr inbounds [65536 x i16]* @prev, i32 0, i32 %.sum73
Instruction does not dominate all uses!
%90 = xor i32 %91, %.masked
%.sum73 = or i32 %90, 32768
Instruction does not dominate all uses!
%91 = zext i8 %92 to i32
%90 = xor i32 %91, %.masked
Instruction does not dominate all uses!
%92 = load i8* %94, align 1
%91 = zext i8 %92 to i32
Instruction does not dominate all uses!
%93 = shl i32 %95, 5
%.masked = and i32 %93, 32736
Instruction does not dominate all uses!
%94 = getelementptr inbounds [65536 x i8]* @window, i32 0, i32 %96
%92 = load i8* %94, align 1
Instruction does not dominate all uses!
%95 = load i32* @ins_h, align 4
%93 = shl i32 %95, 5
Instruction does not dominate all uses!
%96 = add i32 %97, 2
%94 = getelementptr inbounds [65536 x i8]* @window, i32 0, i32 %96
Instruction does not dominate all uses!
%97 = load i32* @strstart, align 4
%96 = add i32 %97, 2
Instruction does not dominate all uses!
%90 = xor i32 %91, %.masked
store i32 %90, i32* @ins_h, align 4
Instruction does not dominate all uses!
%90 = xor i32 %91, %.masked
%.sum39 = or i32 %90, 32768
Instruction does not dominate all uses!
%.sum39 = or i32 %90, 32768
%100 = getelementptr inbounds [65536 x i16]* @prev, i32 0, i32 %.sum39
Instruction does not dominate all uses!
%100 = getelementptr inbounds [65536 x i16]* @prev, i32 0, i32 %.sum39
%101 = load i16* %100, align 2
Instruction does not dominate all uses!
%101 = load i16* %100, align 2
%102 = zext i16 %101 to i32
Instruction does not dominate all uses!
%101 = load i16* %100, align 2
store i16 %101, i16* %103, align 2
Instruction does not dominate all uses!
%89 = getelementptr inbounds [65536 x i16]* @prev, i32 0, i32 %.sum73
store i16 %105, i16* %89, align 2
Instruction does not dominate all uses!
%101 = load i16* %100, align 2
%108 = icmp ne i16 %101, 0
Instruction does not dominate all uses!
%108 = icmp ne i16 %101, 0
%or.cond47 = and i1 %108, %110
Instruction does not dominate all uses!
%or.cond47 = and i1 %108, %110
br i1 %or.cond47, label %bb3, label %bb9
Broken module found, compilation aborted!
On 5/4/2011 8:20 PM, John Criswell wrote:
> Dear Chuck,
>
> I haven't read all of the details, but it seems that what you need to
> do is to clone defs before you clone any uses of the def. To do that,
> you want to iterate over the instructions in dominator-tree order.
>
> To do that, you first construct the dominator tree (there is an LLVM
> analysis pass that does that). Then, you iterate over the basic
> blocks in the dominator tree from the root of the tree to the bottom;
> make sure you process each basic block before processing any of its
> children. When you process a basic block, you clone the instructions
> in that basic block.
>
> This ensures that you process all defs before uses in a def-use chain
> for everything except phi-nodes. Phi-nodes are special because they
> are not dominated by their inputs. If your phi-node copying is
> simple, you want to create a dummy phi-node whose inputs are all
> undef. After you've finished copying all instructions, you go back
> and change the operands of the phi-nodes to be what you want them to be.
>
> The above works well for simple cases in which knowing where to insert
> phi-nodes is easy (e.g., you are inserting instrumentation in such a
> way that you are adding a phi-node that mirrors an existing phi-node
> within the program). Knowing where to put phi-nodes can be difficult
> in general. For such cases, you should make alloca'ed memory
> locations for each variable you are adding in the program. You then
> use load/store instructions to read/write the data into/out of SSA
> variables, eliminating the need to add phi-nodes. Then, when your
> pass is finished, run the mem2reg pass; it will convert your alloca'ed
> variables into SSA virtual registers and insert phi-nodes for you.
>
> As an aside, knowing how the SSA construction algorithm works is what
> led me to understand how to visit defs before uses in LLVM IR. I
> recommend reading Cytron et. al.'s paper
> (http://portal.acm.org/citation.cfm?id=115320).
>
> -- John T.
>
>
> On 5/4/11 6:16 PM, Chuck Zhao wrote:
>> While working on my optimization pass (a Function Pass), I try to
>> replicate a call instruction and insert it at some earlier location
>> (similar to LICM).
>> However, the instruction I am trying to replicate has dependencies on
>> an uncertain number of instructions that are used to generate an address.
>>
>> A simple example (IR segment):
>>
>> define void @foo() nounwind {
>> entry:
>> %a = alloca i32, align 4; ; [0]
>> %b = alloca i32, align 4
>> %c = alloca i32, align 4
>> %d = alloca i32, align 4
>> %e = alloca i32, align 4
>> %f = alloca i32, align 4
>> %A = alloca [100 x i32], align 4
>> call void @start_ckpt() nounwind
>> %0 = call i32 @puts(i8* getelementptr inbounds ([8 x i8]* @.str,
>> i32 0, i32 0)) nounwind
>> %a1 = bitcast i32* %a to i8* ; [1]
>> call void @bkp_memory(i8* %a1, i32 4) nounwind ; [2] the
>> function call instruction that I am about to replicate
>>
>> I need to make a copy/clone of the call instruction [2]. However,
>> I->clone() failed on [2], because [2] has dependency chained
>> instructions that all will need to be cloned before itself can.
>> The back-trace of dependent instructions go to: [1] and [0]. Thus
>> both [1] and [2] need to be cloned in order before replicate [2].
>>
>>
>> A more interesting example is given below (IR Segment):
>>
>> bb1: ; preds = %bb29,
>> %bb30.preheader
>> %match_length.354 = phi i32 [ %match_length.2.ph, %bb29 ], [ 2,
>> %bb30.preheader ]
>> %match_available.153 = phi i32 [ %match_available.0.ph, %bb29 ], [
>> 0, %bb30.preheader ]
>> tail call void @start_ckpt() nounwind noinline
>> %88 = load i32* @ins_h, align 4 ; [0]
>> %89 = shl i32 %88, 5 ;[1]
>> %90 = load i32* @strstart, align 4 ; [2]
>> %91 = add i32 %90, 2 ; [3]
>> %92 = getelementptr inbounds [65536 x i8]* @window, i32 0, i32
>> %91 ; [4]
>> %93 = load i8* %92, align 1 ; [5]
>> %94 = zext i8 %93 to i32 ; [6]
>> %.masked = and i32 %89, 32736 ;[7]
>> %95 = xor i32 %94, %.masked ;[8]
>> %take_addr = getelementptr i32* @ins_h
>> %96 = bitcast i32* %take_addr to i8*
>> call void @bkp_memory(i8* %96, i32 4)
>> store i32 %95, i32* @ins_h, align 4
>> %97 = and i32 %90, 32767
>> %.sum39 = or i32 %95, 32768
>> %98 = getelementptr inbounds [65536 x i16]* @prev, i32 0, i32 %.sum39
>> %99 = load i16* %98, align 2
>> %100 = zext i16 %99 to i32
>> %101 = getelementptr inbounds [65536 x i16]* @prev, i32 0, i32 %97
>> %take_addr1 = getelementptr i16* %101
>> %102 = bitcast i16* %take_addr1 to i8*
>> call void @bkp_memory(i8* %102, i32 2)
>> store i16 %99, i16* %101, align 2
>> %103 = trunc i32 %90 to i16
>> %.sum73 = or i32 %95, 32768 ;[9]
>> %104 = getelementptr inbounds [65536 x i16]* @prev, i32 0, i32
>> %.sum73 ;[10]
>> %take_addr2 = getelementptr i16* %104 ; [11]
>> %105 = bitcast i16* %take_addr2 to i8* ;[12]
>> call void @bkp_memory(i8* %105, i32 2); [13]
>>
>> Again, attempting to replicate a call instruction [13]. But, this
>> time the dependency chain is much longer and goes way further back,
>> which includes [0] .. [12].
>>
>> Knowing this dependency chain could be arbitrarily long, with
>> multiple levels of use-def and def-use relationships. The termination
>> conditions could be one of:
>> (1). local variable declaration (Alloca)
>> (2). global variable
>> (3). const
>>
>> I think it will need a depth-first or breath-first search to identify
>> all related instructions before the I->clone() can possibly happen.
>>
>> I am asking if there is a known-good way of doing this, or some LLVM
>> API provided, since making a copy of an existing LLVM instruction
>> seems to be a very common task in code transformations.
>>
>>
>> Thank you very much
>>
>> Chuck
>>
>>
>> _______________________________________________
>> LLVM Developers mailing list
>> LLVMdev at cs.uiuc.edu http://llvm.cs.uiuc.edu
>> http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20110508/987ee53d/attachment.html>
More information about the llvm-dev
mailing list