<html xmlns:v="urn:schemas-microsoft-com:vml" 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 http-equiv=Content-Type content="text/html; charset=us-ascii"><meta name=Generator content="Microsoft Word 15 (filtered medium)"><style><!--
/* Font Definitions */
@font-face
{font-family:"Cambria Math";
panose-1:2 4 5 3 5 4 6 3 2 4;}
@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:11.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;}
p.MsoListParagraph, li.MsoListParagraph, div.MsoListParagraph
{mso-style-priority:34;
margin-top:0in;
margin-right:0in;
margin-bottom:0in;
margin-left:.5in;
margin-bottom:.0001pt;
font-size:11.0pt;
font-family:"Calibri",sans-serif;}
span.EmailStyle17
{mso-style-type:personal-compose;
font-family:"Calibri",sans-serif;
color:windowtext;}
.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;}
/* List Definitions */
@list l0
{mso-list-id:1592855385;
mso-list-type:hybrid;
mso-list-template-ids:575183982 67698705 67698713 67698715 67698703 67698713 67698715 67698703 67698713 67698715;}
@list l0:level1
{mso-level-text:"%1\)";
mso-level-tab-stop:none;
mso-level-number-position:left;
text-indent:-.25in;}
@list l0:level2
{mso-level-number-format:alpha-lower;
mso-level-tab-stop:none;
mso-level-number-position:left;
text-indent:-.25in;}
@list l0:level3
{mso-level-number-format:roman-lower;
mso-level-tab-stop:none;
mso-level-number-position:right;
text-indent:-9.0pt;}
@list l0:level4
{mso-level-tab-stop:none;
mso-level-number-position:left;
text-indent:-.25in;}
@list l0:level5
{mso-level-number-format:alpha-lower;
mso-level-tab-stop:none;
mso-level-number-position:left;
text-indent:-.25in;}
@list l0:level6
{mso-level-number-format:roman-lower;
mso-level-tab-stop:none;
mso-level-number-position:right;
text-indent:-9.0pt;}
@list l0:level7
{mso-level-tab-stop:none;
mso-level-number-position:left;
text-indent:-.25in;}
@list l0:level8
{mso-level-number-format:alpha-lower;
mso-level-tab-stop:none;
mso-level-number-position:left;
text-indent:-.25in;}
@list l0:level9
{mso-level-number-format:roman-lower;
mso-level-tab-stop:none;
mso-level-number-position:right;
text-indent:-9.0pt;}
@list l1
{mso-list-id:1607275671;
mso-list-type:hybrid;
mso-list-template-ids:669547366 67698705 67698713 67698715 67698703 67698713 67698715 67698703 67698713 67698715;}
@list l1:level1
{mso-level-text:"%1\)";
mso-level-tab-stop:none;
mso-level-number-position:left;
margin-left:.75in;
text-indent:-.25in;}
@list l1:level2
{mso-level-number-format:alpha-lower;
mso-level-tab-stop:none;
mso-level-number-position:left;
margin-left:1.25in;
text-indent:-.25in;}
@list l1:level3
{mso-level-number-format:roman-lower;
mso-level-tab-stop:none;
mso-level-number-position:right;
margin-left:1.75in;
text-indent:-9.0pt;}
@list l1:level4
{mso-level-tab-stop:none;
mso-level-number-position:left;
margin-left:2.25in;
text-indent:-.25in;}
@list l1:level5
{mso-level-number-format:alpha-lower;
mso-level-tab-stop:none;
mso-level-number-position:left;
margin-left:2.75in;
text-indent:-.25in;}
@list l1:level6
{mso-level-number-format:roman-lower;
mso-level-tab-stop:none;
mso-level-number-position:right;
margin-left:3.25in;
text-indent:-9.0pt;}
@list l1:level7
{mso-level-tab-stop:none;
mso-level-number-position:left;
margin-left:3.75in;
text-indent:-.25in;}
@list l1:level8
{mso-level-number-format:alpha-lower;
mso-level-tab-stop:none;
mso-level-number-position:left;
margin-left:4.25in;
text-indent:-.25in;}
@list l1:level9
{mso-level-number-format:roman-lower;
mso-level-tab-stop:none;
mso-level-number-position:right;
margin-left:4.75in;
text-indent:-9.0pt;}
@list l2
{mso-list-id:1901019370;
mso-list-type:hybrid;
mso-list-template-ids:-2124128254 67698705 67698713 67698715 67698703 67698713 67698715 67698703 67698713 67698715;}
@list l2:level1
{mso-level-text:"%1\)";
mso-level-tab-stop:none;
mso-level-number-position:left;
text-indent:-.25in;}
@list l2:level2
{mso-level-number-format:alpha-lower;
mso-level-tab-stop:none;
mso-level-number-position:left;
text-indent:-.25in;}
@list l2:level3
{mso-level-number-format:roman-lower;
mso-level-tab-stop:none;
mso-level-number-position:right;
text-indent:-9.0pt;}
@list l2:level4
{mso-level-tab-stop:none;
mso-level-number-position:left;
text-indent:-.25in;}
@list l2:level5
{mso-level-number-format:alpha-lower;
mso-level-tab-stop:none;
mso-level-number-position:left;
text-indent:-.25in;}
@list l2:level6
{mso-level-number-format:roman-lower;
mso-level-tab-stop:none;
mso-level-number-position:right;
text-indent:-9.0pt;}
@list l2:level7
{mso-level-tab-stop:none;
mso-level-number-position:left;
text-indent:-.25in;}
@list l2:level8
{mso-level-number-format:alpha-lower;
mso-level-tab-stop:none;
mso-level-number-position:left;
text-indent:-.25in;}
@list l2:level9
{mso-level-number-format:roman-lower;
mso-level-tab-stop:none;
mso-level-number-position:right;
text-indent:-9.0pt;}
ol
{margin-bottom:0in;}
ul
{margin-bottom:0in;}
--></style><!--[if gte mso 9]><xml>
<o:shapedefaults v:ext="edit" spidmax="1026" />
</xml><![endif]--><!--[if gte mso 9]><xml>
<o:shapelayout v:ext="edit">
<o:idmap v:ext="edit" data="1" />
</o:shapelayout></xml><![endif]--></head><body lang=EN-US link="#0563C1" vlink="#954F72"><div class=WordSection1><p class=MsoNormal>Hi all,<o:p></o:p></p><p class=MsoNormal><o:p> </o:p></p><p class=MsoNormal>I am trying to create a MachineFunctionPass that analyzes the call graph of a module. (The analysis specifically needs to look at X86 operations, so unfortunately I cannot do this at the IR level, even though that would be substantially easier, given that there is no direct machine-level equivalent to a ModulePass.) Traversing the control-flow graph of basic blocks <i>within</i> a machine function is easy enough; the challenge I am facing is how to match call instructions to their targets, i.e., determine the function being called.<o:p></o:p></p><p class=MsoNormal><o:p> </o:p></p><p class=MsoNormal>At the IR level, I can create a CallGraph object from the Module, and iterate down to individual Instructions, where I can check if an instruction casts to a CallInst, and if it does, use CallInst::getCalledFunction() to find the target. At the MachineInstr level, however, a call instruction is simply an opcode with value arguments, and much of the semantics appear to be stripped away. Where MI is a pointer to a MachineInstr, I can use MI->getDesc().isCall() to determine if the instruction is a call; but there’s no indication of<i> what</i> is being called.<o:p></o:p></p><p class=MsoNormal><o:p> </o:p></p><p class=MsoNormal>My first “rough” attempt at solving this was to first traverse the IR-level Module in the MachineFunctionPass’s doInitialization(). For each function, I’m iterating down to individual Instructions, finding ones that can be dyn_casted to CallInst, and pushing the result of getCalledFunction() onto a std::queue (FIFO). Down in runOnMachineFunction(), I’m performing the “same” iteration, over MachineBasicBlocks and then MachineInstrs, and each time I find a call instruction (with getDesc().isCall()), I dequeue the next Function pointer saved from the IR level. This is then considered the “matched” target for the function call. (Since there is a 1-1 correspondence between Functions and MachineFunctions, this is enough to determine the target.)<o:p></o:p></p><p class=MsoNormal><o:p> </o:p></p><p class=MsoNormal>Testing this approach with llc on the bitcode representation of a simple C program, it seems to <i>mostly</i> work; but for some functions, it appears that calls present in IR are no longer present in the corresponding MachineFunction. That is, there are call targets “left over” in the queue after the pass is finished. This prompts a few questions:<o:p></o:p></p><p class=MsoNormal><o:p> </o:p></p><p class=MsoListParagraph style='text-indent:-.25in;mso-list:l2 level1 lfo1'><![if !supportLists]><span style='mso-list:Ignore'>1)<span style='font:7.0pt "Times New Roman"'> </span></span><![endif]>Is the order of function calls stable between the IR and MachineInstr layers?<o:p></o:p></p><p class=MsoListParagraph style='text-indent:-.25in;mso-list:l2 level1 lfo1'><![if !supportLists]><span style='mso-list:Ignore'>2)<span style='font:7.0pt "Times New Roman"'> </span></span><![endif]>Can inlining (which would remove function calls) occur between the IR and MachineInstr layers? (specifically, between the Module processed by doInitialization(), and the MachineFunction processed by runOnMachineFunction()?)<o:p></o:p></p><p class=MsoListParagraph style='text-indent:-.25in;mso-list:l2 level1 lfo1'><![if !supportLists]><span style='mso-list:Ignore'>3)<span style='font:7.0pt "Times New Roman"'> </span></span><![endif]>Do:<o:p></o:p></p><p class=MsoListParagraph style='margin-left:1.0in;text-indent:-.25in;mso-list:l2 level2 lfo1'><![if !supportLists]><span style='mso-list:Ignore'>a.<span style='font:7.0pt "Times New Roman"'> </span></span><![endif]>dyn_casting an Instruction to a CallInst at the IR level, and<o:p></o:p></p><p class=MsoListParagraph style='margin-left:1.0in;text-indent:-.25in;mso-list:l2 level2 lfo1'><![if !supportLists]><span style='mso-list:Ignore'>b.<span style='font:7.0pt "Times New Roman"'> </span></span><![endif]>checking MI->getDesc().isCall() at the MachinIstr level<o:p></o:p></p><p class=MsoNormal style='margin-left:.5in'>both comprehensively account for all possible ways an instruction (in IR or X86, respectively) can make a call – direct or indirect calls, etc.? (i.e., could one of these methods “miss” a call that the other would identify, assuming that no function calls have been removed or reordered between them?)<o:p></o:p></p><p class=MsoListParagraph style='text-indent:-.25in;mso-list:l2 level1 lfo1'><![if !supportLists]><span style='mso-list:Ignore'>4)<span style='font:7.0pt "Times New Roman"'> </span></span><![endif]>Does anyone know of a better way to do this? :-)<o:p></o:p></p><p class=MsoNormal style='text-indent:.25in'><o:p> </o:p></p><p class=MsoNormal>Any suggestions or answers are greatly appreciated.<o:p></o:p></p><p class=MsoNormal><o:p> </o:p></p><p class=MsoNormal>Sincerely,<o:p></o:p></p><p class=MsoNormal>Ethan Johnson<o:p></o:p></p><p class=MsoNormal><o:p> </o:p></p><p class=MsoNormal><i>Ethan J. Johnson<o:p></o:p></i></p><p class=MsoNormal><i>Computer Science PhD student, Systems group, University of Rochester<o:p></o:p></i></p><p class=MsoNormal><a href="mailto:ejohns48@cs.rochester.edu"><i><span style='color:#0563C1'>ejohns48@cs.rochester.edu</span></i></a><i><o:p></o:p></i></p><p class=MsoNormal><a href="mailto:ethanjohnson@acm.org"><i><span style='color:#0563C1'>ethanjohnson@acm.org</span></i></a><i><o:p></o:p></i></p><p class=MsoNormal><i>PGP pubkey available from public directory or on request<o:p></o:p></i></p><p class=MsoNormal><o:p> </o:p></p></div></body></html>