<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.01 Transitional//EN">
<html>
<head>
<meta http-equiv="content-type" content="text/html; charset=ISO-8859-1">
</head>
<body text="#000000" bgcolor="#ffffff">
<font size="+1">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).<br>
However, the instruction I am trying to replicate has dependencies
on an uncertain number of instructions that are used to generate
an address.<br>
<br>
A simple example (IR segment):<br>
<br>
define void @foo() nounwind {<br>
entry:<br>
<font color="#cc0000">%a = alloca i32, align 4;
; [0]</font><br>
%b = alloca i32, align 4<br>
%c = alloca i32, align 4<br>
%d = alloca i32, align 4<br>
%e = alloca i32, align 4<br>
%f = alloca i32, align 4<br>
%A = alloca [100 x i32], align 4<br>
call void @start_ckpt() nounwind<br>
%0 = call i32 @puts(i8* getelementptr inbounds ([8 x i8]* @.str,
i32 0, i32 0)) nounwind<br>
<font color="#990000"> </font><font color="#990000">%a1 =
bitcast i32* %a to i8* ; [1]</font><br>
<font color="#6600cc"> call void @bkp_memory(i8* %a1, i32 4)
nounwind ; [2] the function call instruction that I
am about to replicate</font><br>
<br>
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.<br>
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].<br>
<br>
<br>
A more interesting example is given below (IR Segment):<br>
<br>
bb1: ; preds = %bb29,
%bb30.preheader<br>
%match_length.354 = phi i32 [ %match_length.2.ph, %bb29 ], [ 2,
%bb30.preheader ]<br>
%match_available.153 = phi i32 [ %match_available.0.ph, %bb29 ],
[ 0, %bb30.preheader ]<br>
tail call void @start_ckpt() nounwind noinline<br>
<font color="#000099"> %88 = load i32* @ins_h, align 4
; [0]<br>
%89 = shl i32 %88, 5 ;[1]<br>
%90 = load i32* @strstart, align 4 ; [2]<br>
%91 = add i32 %90, 2 ; [3]<br>
%92 = getelementptr inbounds [65536 x i8]* @window, i32 0, i32
%91 ; [4]<br>
%93 = load i8* %92, align 1 ; [5]<br>
%94 = zext i8 %93 to i32 ; [6]<br>
</font><font color="#000099"> %.masked = and i32 %89, 32736
;[7]</font><br>
<font color="#000099"> %95 = xor i32 %94, %.masked
;[8]</font><br>
%take_addr = getelementptr i32* @ins_h<br>
%96 = bitcast i32* %take_addr to i8*<br>
call void @bkp_memory(i8* %96, i32 4)<br>
store i32 %95, i32* @ins_h, align 4<br>
%97 = and i32 %90, 32767<br>
%.sum39 = or i32 %95, 32768<br>
%98 = getelementptr inbounds [65536 x i16]* @prev, i32 0, i32
%.sum39<br>
%99 = load i16* %98, align 2<br>
%100 = zext i16 %99 to i32<br>
%101 = getelementptr inbounds [65536 x i16]* @prev, i32 0, i32
%97<br>
%take_addr1 = getelementptr i16* %101<br>
%102 = bitcast i16* %take_addr1 to i8*<br>
call void @bkp_memory(i8* %102, i32 2)<br>
store i16 %99, i16* %101, align 2<br>
%103 = trunc i32 %90 to i16<br>
<font color="#000099"> %.sum73 = or i32 %95, 32768
;[9]<br>
%104 = getelementptr inbounds [65536 x i16]* @prev, i32 0, i32
%.sum73 ;[10]<br>
%take_addr2 = getelementptr i16* %104 ; [11]<br>
%105 = bitcast i16* %take_addr2 to i8* ;[12]</font><br>
<font color="#6600cc"> call void @bkp_memory(i8* %105, i32 2);
[13]</font><br>
<br>
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].<br>
<br>
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:<br>
(1). local variable declaration (Alloca)<br>
(2). global variable <br>
(3). const<br>
<br>
I think it will need a depth-first or breath-first search to
identify all related instructions before the I->clone() can
possibly happen.<br>
<br>
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.<br>
<br>
<br>
Thank you very much<br>
<br>
Chuck<br>
<br>
</font>
</body>
</html>