[LLVMdev] identifying all dependent instructions through multi-levels of def-use relationship

[Chuck Zhao]

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

-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20110504/f9136b61/attachment.html>