<html xmlns:o="urn:schemas-microsoft-com:office:office" xmlns:w="urn:schemas-microsoft-com:office:word" xmlns:m="http://schemas.microsoft.com/office/2004/12/omml" xmlns="http://www.w3.org/TR/REC-html40"><head><meta name=Title content=""><meta name=Keywords content=""><meta http-equiv=Content-Type content="text/html; charset=utf-8"><meta name=Generator content="Microsoft Word 15 (filtered medium)"><style><!--
/* Font Definitions */
@font-face
{font-family:"Courier New";
panose-1:2 7 3 9 2 2 5 2 4 4;}
@font-face
{font-family:"Cambria Math";
panose-1:2 4 5 3 5 4 6 3 2 4;}
@font-face
{font-family:DengXian;
panose-1:2 1 6 0 3 1 1 1 1 1;}
@font-face
{font-family:Calibri;
panose-1:2 15 5 2 2 2 4 3 2 4;}
/* Style Definitions */
p.MsoNormal, li.MsoNormal, div.MsoNormal
{margin:0in;
margin-bottom:.0001pt;
font-size:12.0pt;
font-family:"Calibri",sans-serif;}
a:link, span.MsoHyperlink
{mso-style-priority:99;
color:#0563C1;
text-decoration:underline;}
a:visited, span.MsoHyperlinkFollowed
{mso-style-priority:99;
color:#954F72;
text-decoration:underline;}
span.EmailStyle17
{mso-style-type:personal-compose;
font-family:"Calibri",sans-serif;
color:windowtext;}
span.msoIns
{mso-style-type:export-only;
mso-style-name:"";
text-decoration:underline;
color:teal;}
.MsoChpDefault
{mso-style-type:export-only;
font-family:"Calibri",sans-serif;}
@page WordSection1
{size:8.5in 11.0in;
margin:1.0in 1.0in 1.0in 1.0in;}
div.WordSection1
{page:WordSection1;}
--></style></head><body bgcolor=white lang=EN-US link="#0563C1" vlink="#954F72"><div class=WordSection1><p class=MsoNormal><span style='font-size:11.0pt'>Hi All,<o:p></o:p></span></p><p class=MsoNormal><span style='font-size:11.0pt'><o:p> </o:p></span></p><p class=MsoNormal><span style='font-size:11.0pt'>I’m currently working on a simple task which needs to transform loops into tail-recursive functions. I found the CodeExtractor class a handy helper to use, but later encountered a problem.<o:p></o:p></span></p><p class=MsoNormal><span style='font-size:11.0pt'><o:p> </o:p></span></p><p class=MsoNormal><span style='font-size:11.0pt'>Consider the following CU<o:p></o:p></span></p><p class=MsoNormal><span style='font-size:11.0pt'><o:p> </o:p></span></p><p class=MsoNormal style='margin-left:.5in'><span style='font-size:11.0pt;font-family:"Courier New",serif'>struct S { int a, b; };<o:p></o:p></span></p><p class=MsoNormal style='margin-left:.5in'><span style='font-size:11.0pt;font-family:"Courier New",serif'><o:p> </o:p></span></p><p class=MsoNormal style='margin-left:.5in'><span style='font-size:11.0pt;font-family:"Courier New",serif'>int foo(struct S *s, unsigned n) {<o:p></o:p></span></p><p class=MsoNormal style='margin-left:.5in'><span style='font-size:11.0pt;font-family:"Courier New",serif'> struct S *next = s;<o:p></o:p></span></p><p class=MsoNormal style='margin-left:.5in'><span style='font-size:11.0pt;font-family:"Courier New",serif'><o:p> </o:p></span></p><p class=MsoNormal style='margin-left:.5in'><span style='font-size:11.0pt;font-family:"Courier New",serif'> unsigned i;<o:p></o:p></span></p><p class=MsoNormal style='margin-left:.5in'><span style='font-size:11.0pt;font-family:"Courier New",serif'> for (i = 0; i < n; ++i) {<o:p></o:p></span></p><p class=MsoNormal style='margin-left:.5in'><span style='font-size:11.0pt;font-family:"Courier New",serif'> if (!s[i].a)<o:p></o:p></span></p><p class=MsoNormal style='margin-left:.5in'><span style='font-size:11.0pt;font-family:"Courier New",serif'> break;<o:p></o:p></span></p><p class=MsoNormal style='margin-left:.5in'><span style='font-size:11.0pt;font-family:"Courier New",serif'> next = s + i;<o:p></o:p></span></p><p class=MsoNormal style='margin-left:.5in'><span style='font-size:11.0pt;font-family:"Courier New",serif'> }<o:p></o:p></span></p><p class=MsoNormal style='margin-left:.5in'><span style='font-size:11.0pt;font-family:"Courier New",serif'> return next->b;<o:p></o:p></span></p><p class=MsoNormal style='margin-left:.5in'><span style='font-size:11.0pt;font-family:"Courier New",serif'>}<o:p></o:p></span></p><p class=MsoNormal><span style='font-size:11.0pt'><o:p> </o:p></span></p><p class=MsoNormal><span style='font-size:11.0pt'>clang 5.0 gives the following IR with O1 optimizations<o:p></o:p></span></p><p class=MsoNormal><span style='font-size:11.0pt'><o:p> </o:p></span></p><p class=MsoNormal style='margin-left:.5in'><span style='font-size:11.0pt;font-family:"Courier New",serif'>%struct.S = type { i32, i32 }<o:p></o:p></span></p><p class=MsoNormal style='margin-left:.5in'><span style='font-size:11.0pt;font-family:"Courier New",serif'><o:p> </o:p></span></p><p class=MsoNormal style='margin-left:.5in'><span style='font-size:11.0pt;font-family:"Courier New",serif'>; Function Attrs: norecurse nounwind readonly uwtable<o:p></o:p></span></p><p class=MsoNormal style='margin-left:.5in'><span style='font-size:11.0pt;font-family:"Courier New",serif'>define i32 @foo(%struct.S* nocapture readonly, i32) local_unnamed_addr #0 {<o:p></o:p></span></p><p class=MsoNormal style='margin-left:.5in'><span style='font-size:11.0pt;font-family:"Courier New",serif'> %3 = icmp eq i32 %1, 0<o:p></o:p></span></p><p class=MsoNormal style='margin-left:.5in'><span style='font-size:11.0pt;font-family:"Courier New",serif'> br i1 %3, label %16, label %4<o:p></o:p></span></p><p class=MsoNormal style='margin-left:.5in'><span style='font-size:11.0pt;font-family:"Courier New",serif'><o:p> </o:p></span></p><p class=MsoNormal style='margin-left:.5in'><span style='font-size:11.0pt;font-family:"Courier New",serif'>; <label>:4: ; preds = %2<o:p></o:p></span></p><p class=MsoNormal style='margin-left:.5in'><span style='font-size:11.0pt;font-family:"Courier New",serif'> br label %7<o:p></o:p></span></p><p class=MsoNormal style='margin-left:.5in'><span style='font-size:11.0pt;font-family:"Courier New",serif'><o:p> </o:p></span></p><p class=MsoNormal style='margin-left:.5in'><span style='font-size:11.0pt;font-family:"Courier New",serif'>; <label>:5: ; preds = %7<o:p></o:p></span></p><p class=MsoNormal style='margin-left:.5in'><span style='font-size:11.0pt;font-family:"Courier New",serif'> %6 = icmp ult i32 %15, %1<o:p></o:p></span></p><p class=MsoNormal style='margin-left:.5in'><span style='font-size:11.0pt;font-family:"Courier New",serif'> br i1 %6, label %7, label %16<o:p></o:p></span></p><p class=MsoNormal style='margin-left:.5in'><span style='font-size:11.0pt;font-family:"Courier New",serif'><o:p> </o:p></span></p><p class=MsoNormal style='margin-left:.5in'><span style='font-size:11.0pt;font-family:"Courier New",serif'>; <label>:7: ; preds = %4, %5<o:p></o:p></span></p><p class=MsoNormal style='margin-left:.5in'><span style='font-size:11.0pt;font-family:"Courier New",serif'> %8 = phi i32 [ %15, %5 ], [ 0, %4 ]<o:p></o:p></span></p><p class=MsoNormal style='margin-left:.5in'><span style='font-size:11.0pt;font-family:"Courier New",serif'> %9 = phi %struct.S* [ %11, %5 ], [ %0, %4 ]<o:p></o:p></span></p><p class=MsoNormal style='margin-left:.5in'><span style='font-size:11.0pt;font-family:"Courier New",serif'> %10 = zext i32 %8 to i64<o:p></o:p></span></p><p class=MsoNormal style='margin-left:.5in'><span style='font-size:11.0pt;font-family:"Courier New",serif'> %11 = getelementptr inbounds %struct.S, %struct.S* %0, i64 %10<o:p></o:p></span></p><p class=MsoNormal style='margin-left:.5in'><span style='font-size:11.0pt;font-family:"Courier New",serif'> %12 = getelementptr inbounds %struct.S, %struct.S* %11, i64 0, i32 0<o:p></o:p></span></p><p class=MsoNormal style='margin-left:.5in'><span style='font-size:11.0pt;font-family:"Courier New",serif'> %13 = load i32, i32* %12, align 4, !tbaa !2<o:p></o:p></span></p><p class=MsoNormal style='margin-left:.5in'><span style='font-size:11.0pt;font-family:"Courier New",serif'> %14 = icmp eq i32 %13, 0<o:p></o:p></span></p><p class=MsoNormal style='margin-left:.5in'><span style='font-size:11.0pt;font-family:"Courier New",serif'> %15 = add i32 %8, 1<o:p></o:p></span></p><p class=MsoNormal style='margin-left:.5in'><span style='font-size:11.0pt;font-family:"Courier New",serif'> br i1 %14, label %16, label %5<o:p></o:p></span></p><p class=MsoNormal style='margin-left:.5in'><span style='font-size:11.0pt;font-family:"Courier New",serif'><o:p> </o:p></span></p><p class=MsoNormal style='margin-left:.5in'><span style='font-size:11.0pt;font-family:"Courier New",serif'>; <label>:16: ; preds = %5, %7, %2<o:p></o:p></span></p><p class=MsoNormal style='margin-left:.5in'><span style='font-size:11.0pt;font-family:"Courier New",serif'> %17 = phi %struct.S* [ %0, %2 ], [ %9, %7 ], [ %11, %5 ]<o:p></o:p></span></p><p class=MsoNormal style='margin-left:.5in'><span style='font-size:11.0pt;font-family:"Courier New",serif'> %18 = getelementptr inbounds %struct.S, %struct.S* %17, i64 0, i32 1<o:p></o:p></span></p><p class=MsoNormal style='margin-left:.5in'><span style='font-size:11.0pt;font-family:"Courier New",serif'> %19 = load i32, i32* %18, align 4, !tbaa !7<o:p></o:p></span></p><p class=MsoNormal style='margin-left:.5in'><span style='font-size:11.0pt;font-family:"Courier New",serif'> ret i32 %19<o:p></o:p></span></p><p class=MsoNormal style='margin-left:.5in'><span style='font-size:11.0pt;font-family:"Courier New",serif'>}<o:p></o:p></span></p><p class=MsoNormal><span style='font-size:11.0pt'><o:p> </o:p></span></p><p class=MsoNormal><span style='font-size:11.0pt'>Here %17 should be noted, which is a phi with 3 incoming blocks, with two of them being part of the loop.<o:p></o:p></span></p><p class=MsoNormal><span style='font-size:11.0pt'><o:p> </o:p></span></p><p class=MsoNormal><span style='font-size:11.0pt'>After using CodeExtractor to extract the loop into a new function, I got<o:p></o:p></span></p><p class=MsoNormal><span style='font-size:11.0pt'><o:p> </o:p></span></p><p class=MsoNormal style='margin-left:.5in'><span style='font-size:11.0pt;font-family:"Courier New",serif'>%struct.S = type { i32, i32 }<o:p></o:p></span></p><p class=MsoNormal style='margin-left:.5in'><span style='font-size:11.0pt;font-family:"Courier New",serif'><o:p> </o:p></span></p><p class=MsoNormal style='margin-left:.5in'><span style='font-size:11.0pt;font-family:"Courier New",serif'>; Function Attrs: norecurse nounwind readonly uwtable<o:p></o:p></span></p><p class=MsoNormal style='margin-left:.5in'><span style='font-size:11.0pt;font-family:"Courier New",serif'>define i32 @foo(%struct.S* nocapture readonly, i32) local_unnamed_addr #0 {<o:p></o:p></span></p><p class=MsoNormal style='margin-left:.5in'><span style='font-size:11.0pt;font-family:"Courier New",serif'> %.loc1 = alloca %struct.S*<o:p></o:p></span></p><p class=MsoNormal style='margin-left:.5in'><span style='font-size:11.0pt;font-family:"Courier New",serif'> %.loc = alloca %struct.S*<o:p></o:p></span></p><p class=MsoNormal style='margin-left:.5in'><span style='font-size:11.0pt;font-family:"Courier New",serif'> %3 = icmp eq i32 %1, 0<o:p></o:p></span></p><p class=MsoNormal style='margin-left:.5in'><span style='font-size:11.0pt;font-family:"Courier New",serif'> br i1 %3, label %5, label %4<o:p></o:p></span></p><p class=MsoNormal style='margin-left:.5in'><span style='font-size:11.0pt;font-family:"Courier New",serif'><o:p> </o:p></span></p><p class=MsoNormal style='margin-left:.5in'><span style='font-size:11.0pt;font-family:"Courier New",serif'>; <label>:4: ; preds = %2<o:p></o:p></span></p><p class=MsoNormal style='margin-left:.5in'><span style='font-size:11.0pt;font-family:"Courier New",serif'> br label %codeRepl<o:p></o:p></span></p><p class=MsoNormal style='margin-left:.5in'><span style='font-size:11.0pt;font-family:"Courier New",serif'><o:p> </o:p></span></p><p class=MsoNormal style='margin-left:.5in'><span style='font-size:11.0pt;font-family:"Courier New",serif'>codeRepl: ; preds = %4<o:p></o:p></span></p><p class=MsoNormal style='margin-left:.5in'><span style='font-size:11.0pt;font-family:"Courier New",serif'> call void @foo_(%struct.S* %0, i32 %1, %struct.S** %.loc, %struct.S** %.loc1)<o:p></o:p></span></p><p class=MsoNormal style='margin-left:.5in'><span style='font-size:11.0pt;font-family:"Courier New",serif'> %.reload = load %struct.S*, %struct.S** %.loc<o:p></o:p></span></p><p class=MsoNormal style='margin-left:.5in'><span style='font-size:11.0pt;font-family:"Courier New",serif'> %.reload2 = load %struct.S*, %struct.S** %.loc1<o:p></o:p></span></p><p class=MsoNormal style='margin-left:.5in'><span style='font-size:11.0pt;font-family:"Courier New",serif'> br label %.loopexit<o:p></o:p></span></p><p class=MsoNormal style='margin-left:.5in'><span style='font-size:11.0pt;font-family:"Courier New",serif'><o:p> </o:p></span></p><p class=MsoNormal style='margin-left:.5in'><span style='font-size:11.0pt;font-family:"Courier New",serif'>.loopexit: ; preds = %codeRepl<o:p></o:p></span></p><p class=MsoNormal style='margin-left:.5in'><span style='font-size:11.0pt;font-family:"Courier New",serif'> %.ph = phi %struct.S* [ %.reload2, %codeRepl ], [ %.reload, %codeRepl ]<o:p></o:p></span></p><p class=MsoNormal style='margin-left:.5in'><span style='font-size:11.0pt;font-family:"Courier New",serif'> br label %5<o:p></o:p></span></p><p class=MsoNormal style='margin-left:.5in'><span style='font-size:11.0pt;font-family:"Courier New",serif'><o:p> </o:p></span></p><p class=MsoNormal style='margin-left:.5in'><span style='font-size:11.0pt;font-family:"Courier New",serif'>; <label>:5: ; preds = %.loopexit, %2<o:p></o:p></span></p><p class=MsoNormal style='margin-left:.5in'><span style='font-size:11.0pt;font-family:"Courier New",serif'> %6 = phi %struct.S* [ %0, %2 ], [ %.ph, %.loopexit ]<o:p></o:p></span></p><p class=MsoNormal style='margin-left:.5in'><span style='font-size:11.0pt;font-family:"Courier New",serif'> %7 = getelementptr inbounds %struct.S, %struct.S* %6, i64 0, i32 1<o:p></o:p></span></p><p class=MsoNormal style='margin-left:.5in'><span style='font-size:11.0pt;font-family:"Courier New",serif'> %8 = load i32, i32* %7, align 4, !tbaa !2<o:p></o:p></span></p><p class=MsoNormal style='margin-left:.5in'><span style='font-size:11.0pt;font-family:"Courier New",serif'> ret i32 %8<o:p></o:p></span></p><p class=MsoNormal style='margin-left:.5in'><span style='font-size:11.0pt;font-family:"Courier New",serif'>}<o:p></o:p></span></p><p class=MsoNormal style='margin-left:.5in'><span style='font-size:11.0pt;font-family:"Courier New",serif'><o:p> </o:p></span></p><p class=MsoNormal style='margin-left:.5in'><span style='font-size:11.0pt;font-family:"Courier New",serif'>; Function Attrs: nounwind uwtable<o:p></o:p></span></p><p class=MsoNormal style='margin-left:.5in'><span style='font-size:11.0pt;font-family:"Courier New",serif'>define internal void @foo_(%struct.S*, i32, %struct.S** %.out, %struct.S** %.out1) #1 {<o:p></o:p></span></p><p class=MsoNormal style='margin-left:.5in'><span style='font-size:11.0pt;font-family:"Courier New",serif'>newFuncRoot:<o:p></o:p></span></p><p class=MsoNormal style='margin-left:.5in'><span style='font-size:11.0pt;font-family:"Courier New",serif'> br label %2<o:p></o:p></span></p><p class=MsoNormal style='margin-left:.5in'><span style='font-size:11.0pt;font-family:"Courier New",serif'><o:p> </o:p></span></p><p class=MsoNormal style='margin-left:.5in'><span style='font-size:11.0pt;font-family:"Courier New",serif'>.loopexit.exitStub: ; preds = %11, %2<o:p></o:p></span></p><p class=MsoNormal style='margin-left:.5in'><span style='font-size:11.0pt;font-family:"Courier New",serif'> store %struct.S* %4, %struct.S** %.out<o:p></o:p></span></p><p class=MsoNormal style='margin-left:.5in'><span style='font-size:11.0pt;font-family:"Courier New",serif'> store %struct.S* %6, %struct.S** %.out1<o:p></o:p></span></p><p class=MsoNormal style='margin-left:.5in'><span style='font-size:11.0pt;font-family:"Courier New",serif'> ret void<o:p></o:p></span></p><p class=MsoNormal style='margin-left:.5in'><span style='font-size:11.0pt;font-family:"Courier New",serif'><o:p> </o:p></span></p><p class=MsoNormal style='margin-left:.5in'><span style='font-size:11.0pt;font-family:"Courier New",serif'>; <label>:2: ; preds = %newFuncRoot, %11<o:p></o:p></span></p><p class=MsoNormal style='margin-left:.5in'><span style='font-size:11.0pt;font-family:"Courier New",serif'> %3 = phi i32 [ %10, %11 ], [ 0, %newFuncRoot ]<o:p></o:p></span></p><p class=MsoNormal style='margin-left:.5in'><span style='font-size:11.0pt;font-family:"Courier New",serif'> %4 = phi %struct.S* [ %6, %11 ], [ %0, %newFuncRoot ]<o:p></o:p></span></p><p class=MsoNormal style='margin-left:.5in'><span style='font-size:11.0pt;font-family:"Courier New",serif'> %5 = zext i32 %3 to i64<o:p></o:p></span></p><p class=MsoNormal style='margin-left:.5in'><span style='font-size:11.0pt;font-family:"Courier New",serif'> %6 = getelementptr inbounds %struct.S, %struct.S* %0, i64 %5<o:p></o:p></span></p><p class=MsoNormal style='margin-left:.5in'><span style='font-size:11.0pt;font-family:"Courier New",serif'> %7 = getelementptr inbounds %struct.S, %struct.S* %6, i64 0, i32 0<o:p></o:p></span></p><p class=MsoNormal style='margin-left:.5in'><span style='font-size:11.0pt;font-family:"Courier New",serif'> %8 = load i32, i32* %7, align 4, !tbaa !7<o:p></o:p></span></p><p class=MsoNormal style='margin-left:.5in'><span style='font-size:11.0pt;font-family:"Courier New",serif'> %9 = icmp eq i32 %8, 0<o:p></o:p></span></p><p class=MsoNormal style='margin-left:.5in'><span style='font-size:11.0pt;font-family:"Courier New",serif'> %10 = add i32 %3, 1<o:p></o:p></span></p><p class=MsoNormal style='margin-left:.5in'><span style='font-size:11.0pt;font-family:"Courier New",serif'> br i1 %9, label %.loopexit.exitStub, label %11<o:p></o:p></span></p><p class=MsoNormal style='margin-left:.5in'><span style='font-size:11.0pt;font-family:"Courier New",serif'><o:p> </o:p></span></p><p class=MsoNormal style='margin-left:.5in'><span style='font-size:11.0pt;font-family:"Courier New",serif'>; <label>:11: ; preds = %2<o:p></o:p></span></p><p class=MsoNormal style='margin-left:.5in'><span style='font-size:11.0pt;font-family:"Courier New",serif'> %12 = icmp ult i32 %10, %1<o:p></o:p></span></p><p class=MsoNormal style='margin-left:.5in'><span style='font-size:11.0pt;font-family:"Courier New",serif'> br i1 %12, label %2, label %.loopexit.exitStub<o:p></o:p></span></p><p class=MsoNormal style='margin-left:.5in'><span style='font-size:11.0pt;font-family:"Courier New",serif'>}<o:p></o:p></span></p><p class=MsoNormal><span style='font-size:11.0pt'><o:p> </o:p></span></p><p class=MsoNormal><span style='font-size:11.0pt'>Now, because the loop is coalesced into a function, the definition of %.ph (derived from %17 in the previous version of IR) in .loopexit becomes funny: two different incoming values for the same incoming block. I was wondering if this is a bug of CodeExtractor or the extractor makes assumptions about the code to be extracted which I’m not aware of. <o:p></o:p></span></p><p class=MsoNormal><span style='font-size:11.0pt'><o:p> </o:p></span></p><p class=MsoNormal><span style='font-size:11.0pt'>Thanks,<o:p></o:p></span></p><p class=MsoNormal><span style='font-size:11.0pt'>Pei Wang<o:p></o:p></span></p></div></body></html>