This is an archive of the discontinued LLVM Phabricator instance.

Differential D13218

Mark BB as annotated if its weight is > 0
ClosedPublic

Authored by danielcdh on Sep 28 2015, 10:14 AM.

Details

Reviewers
dnovillo
davidxl
Summary

Mark BB as annotated if its weight is > 0, otherwise the propagation algorithm will not be able to propagate edge weights.

Diff Detail

Event Timeline

danielcdh updated this revision to Diff 35885.Sep 28 2015, 10:14 AM
danielcdh retitled this revision from to Mark BB as annotated if its weight is > 0.
danielcdh updated this object.
danielcdh added a reviewer: dnovillo.
dnovillo edited edge metadata.Sep 28 2015, 10:39 AM

LGTM with a test case.

Thanks.

danielcdh updated this revision to Diff 35892.Sep 28 2015, 10:53 AM
danielcdh edited edge metadata.

Update reviewer

danielcdh updated this revision to Diff 35894.Sep 28 2015, 10:55 AM

Add reviewers.

danielcdh added a reviewer: davidxl.Sep 28 2015, 10:58 AM
danielcdh added a subscriber: llvm-commits.
danielcdh updated this revision to Diff 35931.Sep 28 2015, 6:19 PM

Add unittest to fix propagation. This equivalence class based method is still incorrect. I will have a separate patch to fix equivalence class bug.

davidxl added inline comments.Sep 28 2015, 8:51 PM
lib/Transforms/IPO/SampleProfile.cpp
242

I think it is clearer to rename this method 'setBlockWeight' -- what it does is to read from the samples and set the cached weight for BB and mark it as annotated.

485

Should use annotated EC's weight.

579

There seems to be a missing step to propagate weights from annotated BBs to their equivalence classes -- the later should be used in Edge propagation

danielcdh added inline comments.Sep 28 2015, 9:20 PM
lib/Transforms/IPO/SampleProfile.cpp
242

In another patch http://reviews.llvm.org/D13231, I changed getBlockWeight as a const member function and removed the caching (because there is no reuse), and move the setting of BlockWeights outside this function.

485

That's correct. I'll have a separate patch to fix the EC's propagation.

dnovillo added a comment.Sep 29 2015, 6:51 AM

Let me back up a little bit. If getBlockWeight() marks the block visited all the time, then how can propagation work? getBlockWeight is only used when computing the *initial* weight of the blocks (I agree with David, it should be renamed to setBlockWeight()).

But, in looking at the code again, it doesn't seem correct to mark the block visited there. We mark them visited when we are assigning equivalence classes.

I think I'm missing something here.

danielcdh added a comment.Sep 29 2015, 7:09 AM

computeBlockWeights assigns weights to basic blocks that has profile data and mark them as annotated. But after this step, there will still be basic blocks that are not annotated. So the propagation step works on 3 things:

  • set edge weights and mark it as annotated
  • set basic block weights for those unannotated basic blocks and mark them as annotated
  • adjust basic block weights for those annotated basic blocks which has apparently incorrect weights

Equivalence class is not the place to set the annotated flag, it just sets the equivalence class for each basic block. In later propagation algorithm, instead of checking "IsAnnotated(BB)", we should check "IsAnnotated(BB->equivalence_class)".

Dehao

dnovillo added inline comments.Sep 29 2015, 8:11 AM
lib/Transforms/IPO/SampleProfile.cpp
309

clang-format this? I think it will now fit on the same line.

danielcdh updated this revision to Diff 35995.Sep 29 2015, 10:20 AM

clang-format

danielcdh marked an inline comment as done.Sep 29 2015, 10:22 AM

rerun clang-format.

dnovillo accepted this revision.Sep 29 2015, 10:50 AM
dnovillo edited edge metadata.

LGTM

This revision is now accepted and ready to land.Sep 29 2015, 10:50 AM
danielcdh updated this revision to Diff 36060.Sep 29 2015, 6:44 PM
danielcdh edited edge metadata.

This change exposed many errors in the original test input. Thus I integrated the EC related change into this patch so that I only need to update the test input once.

Diego and David, please help take another look at the patch. With this patch, the propagation should be very robust now.

dnovillo added a comment.Sep 30 2015, 4:47 AM

Patch looks fine. Just a couple of final questions.

include/llvm/ProfileData/SampleProf.h
221 ↗(On Diff #36060)

Sadly, I don't think there is a test case for this check I had added. With your new changes, we can now distinguish 0 from missing sample all the time, right?

lib/Transforms/IPO/SampleProfile.cpp
375

Not sure why we don't process blocks post-dominated by BB1 anymore?

danielcdh added inline comments.Sep 30 2015, 7:44 AM
include/llvm/ProfileData/SampleProf.h
221 ↗(On Diff #36060)

Yes, now GetBlockCount will return std::error_code if there is no profile.

lib/Transforms/IPO/SampleProfile.cpp
375

Processing dominators should be able to cover all ECs, this is because if BB1 dominates BB2, and BB1 and BB2 are in the same EC, then BB2 also post-dominates BB1.

danielcdh closed this revision.Oct 2 2015, 10:06 AM

submitted

Revision Contents

PathSize
lib/
Transforms/
IPO/
5 lines
test/
Transforms/
SampleProfile/
Inputs/
10 lines
239 lines

Diff 35995

lib/Transforms/IPO/SampleProfile.cpp

Show First 20 Lines • Show All 233 Lines • ▼ Show 20 Lines
/// ///
/// The weight of basic block \p BB is the maximum weight of all the /// The weight of basic block \p BB is the maximum weight of all the
/// instructions in BB. The weight of \p BB is computed and cached in /// instructions in BB. The weight of \p BB is computed and cached in
/// the BlockWeights map. /// the BlockWeights map.
/// ///
/// \param BB The basic block to query. /// \param BB The basic block to query.
/// ///
/// \returns The computed weight of BB. /// \returns The computed weight of BB.
unsigned SampleProfileLoader::getBlockWeight(BasicBlock *BB) { unsigned SampleProfileLoader::getBlockWeight(BasicBlock *BB) {
davidxlUnsubmitted
Not Done
ReplyInline Actions

I think it is clearer to rename this method 'setBlockWeight' -- what it does is to read from the samples and set the cached weight for BB and mark it as annotated.

davidxl: I think it is clearer to rename this method 'setBlockWeight' -- what it does is to read from…
danielcdhAuthorUnsubmitted
Not Done
ReplyInline Actions

In another patch http://reviews.llvm.org/D13231, I changed getBlockWeight as a const member function and removed the caching (because there is no reuse), and move the setting of BlockWeights outside this function.

danielcdh: In another patch http://reviews.llvm.org/D13231, I changed getBlockWeight as a const member…
// If we've computed BB's weight before, return it. // If we've computed BB's weight before, return it.
std::pair<BlockWeightMap::iterator, bool> Entry = std::pair<BlockWeightMap::iterator, bool> Entry =
BlockWeights.insert(std::make_pair(BB, 0)); BlockWeights.insert(std::make_pair(BB, 0));
if (!Entry.second) if (!Entry.second)
return Entry.first->second; return Entry.first->second;
// Otherwise, compute and cache BB's weight. // Otherwise, compute and cache BB's weight.
unsigned Weight = 0; unsigned Weight = 0;
for (auto &I : BB->getInstList()) { for (auto &I : BB->getInstList()) {
unsigned InstWeight = getInstWeight(I); unsigned InstWeight = getInstWeight(I);
if (InstWeight > Weight) if (InstWeight > Weight)
Weight = InstWeight; Weight = InstWeight;
} }
if (Weight > 0)
VisitedBlocks.insert(BB);
Entry.first->second = Weight; Entry.first->second = Weight;
return Weight; return Weight;
} }
/// \brief Compute and store the weights of every basic block. /// \brief Compute and store the weights of every basic block.
/// ///
/// This populates the BlockWeights map by computing /// This populates the BlockWeights map by computing
/// the weights of every basic block in the CFG. /// the weights of every basic block in the CFG.
Show All 35 Lines
/// with blocks from \p BB1's dominator tree, then /// with blocks from \p BB1's dominator tree, then
/// this is the post-dominator tree, and vice versa. /// this is the post-dominator tree, and vice versa.
void SampleProfileLoader::findEquivalencesFor( void SampleProfileLoader::findEquivalencesFor(
BasicBlock *BB1, SmallVector<BasicBlock *, 8> Descendants, BasicBlock *BB1, SmallVector<BasicBlock *, 8> Descendants,
DominatorTreeBase<BasicBlock> *DomTree) { DominatorTreeBase<BasicBlock> *DomTree) {
for (auto *BB2 : Descendants) { for (auto *BB2 : Descendants) {
bool IsDomParent = DomTree->dominates(BB2, BB1); bool IsDomParent = DomTree->dominates(BB2, BB1);
bool IsInSameLoop = LI->getLoopFor(BB1) == LI->getLoopFor(BB2); bool IsInSameLoop = LI->getLoopFor(BB1) == LI->getLoopFor(BB2);
if (BB1 != BB2 && VisitedBlocks.insert(BB2).second && IsDomParent && if (BB1 != BB2 && IsDomParent && IsInSameLoop) {
dnovilloUnsubmitted
Done
ReplyInline Actions

clang-format this? I think it will now fit on the same line.

dnovillo: clang-format this? I think it will now fit on the same line.
IsInSameLoop) {
EquivalenceClass[BB2] = BB1; EquivalenceClass[BB2] = BB1;
// If BB2 is heavier than BB1, make BB2 have the same weight // If BB2 is heavier than BB1, make BB2 have the same weight
// as BB1. // as BB1.
// //
// Note that we don't worry about the opposite situation here // Note that we don't worry about the opposite situation here
// (when BB2 is lighter than BB1). We will deal with this // (when BB2 is lighter than BB1). We will deal with this
// during the propagation phase. Right now, we just want to // during the propagation phase. Right now, we just want to
▲ Show 20 Lines • Show All 50 Lines • ▼ Show 20 Lines for (auto &BB : F) {
// //
// 1- BB1 post-dominates BB2. // 1- BB1 post-dominates BB2.
// 2- BB2 dominates BB1. // 2- BB2 dominates BB1.
// 3- BB1 and BB2 are in the same loop nest. // 3- BB1 and BB2 are in the same loop nest.
// //
// If all those conditions hold, BB2's equivalence class is BB1. // If all those conditions hold, BB2's equivalence class is BB1.
DominatedBBs.clear(); DominatedBBs.clear();
PDT->getDescendants(BB1, DominatedBBs); PDT->getDescendants(BB1, DominatedBBs);
findEquivalencesFor(BB1, DominatedBBs, DT.get()); findEquivalencesFor(BB1, DominatedBBs, DT.get());
dnovilloUnsubmitted
Not Done
ReplyInline Actions

Not sure why we don't process blocks post-dominated by BB1 anymore?

dnovillo: Not sure why we don't process blocks post-dominated by BB1 anymore?
danielcdhAuthorUnsubmitted
Not Done
ReplyInline Actions

Processing dominators should be able to cover all ECs, this is because if BB1 dominates BB2, and BB1 and BB2 are in the same EC, then BB2 also post-dominates BB1.

danielcdh: Processing dominators should be able to cover all ECs, this is because if BB1 dominates BB2…
DEBUG(printBlockEquivalence(dbgs(), BB1)); DEBUG(printBlockEquivalence(dbgs(), BB1));
} }
// Assign weights to equivalence classes. // Assign weights to equivalence classes.
// //
// All the basic blocks in the same equivalence class will execute // All the basic blocks in the same equivalence class will execute
// the same number of times. Since we know that the head block in // the same number of times. Since we know that the head block in
▲ Show 20 Lines • Show All 92 Lines • ▼ Show 20 Lines for (unsigned i = 0; i < 2; i++) {
// known. In this case, this edge can be based on BB's weight. // known. In this case, this edge can be based on BB's weight.
// We add up all the other known edges and set the weight on // We add up all the other known edges and set the weight on
// the self-referential edge as we did in the previous case. // the self-referential edge as we did in the previous case.
// //
// In any other case, we must continue iterating. Eventually, // In any other case, we must continue iterating. Eventually,
// all edges will get a weight, or iteration will stop when // all edges will get a weight, or iteration will stop when
// it reaches SampleProfileMaxPropagateIterations. // it reaches SampleProfileMaxPropagateIterations.
if (NumUnknownEdges <= 1) { if (NumUnknownEdges <= 1) {
unsigned &BBWeight = BlockWeights[BB]; unsigned &BBWeight = BlockWeights[BB];
davidxlUnsubmitted
Not Done
ReplyInline Actions

Should use annotated EC's weight.

davidxl: Should use annotated EC's weight.
danielcdhAuthorUnsubmitted
Not Done
ReplyInline Actions

That's correct. I'll have a separate patch to fix the EC's propagation.

danielcdh: That's correct. I'll have a separate patch to fix the EC's propagation.
if (NumUnknownEdges == 0) { if (NumUnknownEdges == 0) {
// If we already know the weight of all edges, the weight of the // If we already know the weight of all edges, the weight of the
// basic block can be computed. It should be no larger than the sum // basic block can be computed. It should be no larger than the sum
// of all edge weights. // of all edge weights.
if (TotalWeight > BBWeight) { if (TotalWeight > BBWeight) {
BBWeight = TotalWeight; BBWeight = TotalWeight;
Changed = true; Changed = true;
DEBUG(dbgs() << "All edge weights for " << BB->getName() DEBUG(dbgs() << "All edge weights for " << BB->getName()
▲ Show 20 Lines • Show All 77 Lines • ▼ Show 20 Lines
/// ///
/// - If there is a self-referential edge, and the weight of the block is /// - If there is a self-referential edge, and the weight of the block is
/// known, the weight for that edge is set to the weight of the block /// known, the weight for that edge is set to the weight of the block
/// minus the weight of the other incoming edges to that block (if /// minus the weight of the other incoming edges to that block (if
/// known). /// known).
void SampleProfileLoader::propagateWeights(Function &F) { void SampleProfileLoader::propagateWeights(Function &F) {
bool Changed = true; bool Changed = true;
unsigned i = 0; unsigned i = 0;
davidxlUnsubmitted
Not Done
ReplyInline Actions

There seems to be a missing step to propagate weights from annotated BBs to their equivalence classes -- the later should be used in Edge propagation

davidxl: There seems to be a missing step to propagate weights from annotated BBs to their equivalence…
// Add an entry count to the function using the samples gathered // Add an entry count to the function using the samples gathered
// at the function entry. // at the function entry.
F.setEntryCount(Samples->getHeadSamples()); F.setEntryCount(Samples->getHeadSamples());
// Before propagation starts, build, for each block, a list of // Before propagation starts, build, for each block, a list of
// unique predecessors and successors. This is necessary to handle // unique predecessors and successors. This is necessary to handle
// identical edges in multiway branches. Since we visit all blocks and all // identical edges in multiway branches. Since we visit all blocks and all
// edges of the CFG, it is cleaner to build these lists once at the start // edges of the CFG, it is cleaner to build these lists once at the start
▲ Show 20 Lines • Show All 203 Lines • Show Last 20 Lines

test/Transforms/SampleProfile/Inputs/cfg.prof

  • This file was added.
main:15680:0
1: 2500
4: 1000
5: 1000
6: 800
7: 500
9: 10226
10: 2243
16: 0
18: 0

test/Transforms/SampleProfile/cfg.ll

  • This file was added.
; RUN: opt < %s -sample-profile -sample-profile-file=%S/Inputs/cfg.prof | opt -analyze -branch-prob | FileCheck %s
; Original C++ code for this test case:
;
; #include <stdio.h>
; #include <stdlib.h>
; int main(int argc, char *argv[]) {
; if (argc < 2)
; return 1;
; double result;
; int limit = atoi(argv[1]);
; if (limit > 100) {
; double s = 23.041968 * atoi(argv[2]);
; for (int u = 0; u < limit; u++) {
; double x = s;
; s = x + 3.049 + (double)u;
; s -= s + 3.94 / x * 0.32;
; }
; result = s;
; } else {
; result = atoi(argv[2]);
; }
; printf("result is %lf\n", result);
; return 0;
; }
@.str = private unnamed_addr constant [15 x i8] c"result is %lf\0A\00", align 1
; Function Attrs: uwtable
define i32 @main(i32 %argc, i8** %argv) #0 {
; CHECK: Printing analysis 'Branch Probability Analysis' for function 'main':
entry:
%retval = alloca i32, align 4
%argc.addr = alloca i32, align 4
%argv.addr = alloca i8**, align 8
%result = alloca double, align 8
%limit = alloca i32, align 4
%s = alloca double, align 8
%u = alloca i32, align 4
%x = alloca double, align 8
store i32 0, i32* %retval, align 4
store i32 %argc, i32* %argc.addr, align 4
call void @llvm.dbg.declare(metadata i32* %argc.addr, metadata !16, metadata !17), !dbg !18
store i8** %argv, i8*** %argv.addr, align 8
call void @llvm.dbg.declare(metadata i8*** %argv.addr, metadata !19, metadata !17), !dbg !20
%0 = load i32, i32* %argc.addr, align 4, !dbg !21
%cmp = icmp slt i32 %0, 2, !dbg !23
br i1 %cmp, label %if.then, label %if.end, !dbg !24
; CHECK: edge entry -> if.then probability is 0x4ccccccd / 0x80000000 = 60.00%
; CHECK: edge entry -> if.end probability is 0x33333333 / 0x80000000 = 40.00%
if.then: ; preds = %entry
store i32 1, i32* %retval, align 4, !dbg !25
br label %return, !dbg !25
if.end: ; preds = %entry
call void @llvm.dbg.declare(metadata double* %result, metadata !26, metadata !17), !dbg !27
call void @llvm.dbg.declare(metadata i32* %limit, metadata !28, metadata !17), !dbg !29
%1 = load i8**, i8*** %argv.addr, align 8, !dbg !30
%arrayidx = getelementptr inbounds i8*, i8** %1, i64 1, !dbg !30
%2 = load i8*, i8** %arrayidx, align 8, !dbg !30
%call = call i32 @atoi(i8* %2) #4, !dbg !31
store i32 %call, i32* %limit, align 4, !dbg !29
%3 = load i32, i32* %limit, align 4, !dbg !32
%cmp1 = icmp sgt i32 %3, 100, !dbg !34
br i1 %cmp1, label %if.then.2, label %if.else, !dbg !35
; CHECK: edge if.end -> if.then.2 probability is 0x66666666 / 0x80000000 = 80.00%
; CHECK: edge if.end -> if.else probability is 0x1999999a / 0x80000000 = 20.00%
if.then.2: ; preds = %if.end
call void @llvm.dbg.declare(metadata double* %s, metadata !36, metadata !17), !dbg !38
%4 = load i8**, i8*** %argv.addr, align 8, !dbg !39
%arrayidx3 = getelementptr inbounds i8*, i8** %4, i64 2, !dbg !39
%5 = load i8*, i8** %arrayidx3, align 8, !dbg !39
%call4 = call i32 @atoi(i8* %5) #4, !dbg !40
%conv = sitofp i32 %call4 to double, !dbg !40
%mul = fmul double 0x40370ABE6A337A81, %conv, !dbg !41
store double %mul, double* %s, align 8, !dbg !38
call void @llvm.dbg.declare(metadata i32* %u, metadata !42, metadata !17), !dbg !44
store i32 0, i32* %u, align 4, !dbg !44
br label %for.cond, !dbg !45
for.cond: ; preds = %for.inc, %if.then.2
%6 = load i32, i32* %u, align 4, !dbg !46
%7 = load i32, i32* %limit, align 4, !dbg !48
%cmp5 = icmp slt i32 %6, %7, !dbg !49
br i1 %cmp5, label %for.body, label %for.end, !dbg !50
for.body: ; preds = %for.cond
call void @llvm.dbg.declare(metadata double* %x, metadata !51, metadata !17), !dbg !53
%8 = load double, double* %s, align 8, !dbg !54
store double %8, double* %x, align 8, !dbg !53
%9 = load double, double* %x, align 8, !dbg !55
%add = fadd double %9, 3.049000e+00, !dbg !56
%10 = load i32, i32* %u, align 4, !dbg !57
%conv6 = sitofp i32 %10 to double, !dbg !57
%add7 = fadd double %add, %conv6, !dbg !58
store double %add7, double* %s, align 8, !dbg !59
%11 = load double, double* %s, align 8, !dbg !60
%12 = load double, double* %x, align 8, !dbg !61
%div = fdiv double 3.940000e+00, %12, !dbg !62
%mul8 = fmul double %div, 3.200000e-01, !dbg !63
%add9 = fadd double %11, %mul8, !dbg !64
%13 = load double, double* %s, align 8, !dbg !65
%sub = fsub double %13, %add9, !dbg !65
store double %sub, double* %s, align 8, !dbg !65
br label %for.inc, !dbg !66
for.inc: ; preds = %for.body
%14 = load i32, i32* %u, align 4, !dbg !67
%inc = add nsw i32 %14, 1, !dbg !67
store i32 %inc, i32* %u, align 4, !dbg !67
br label %for.cond, !dbg !68
for.end: ; preds = %for.cond
%15 = load double, double* %s, align 8, !dbg !69
store double %15, double* %result, align 8, !dbg !70
br label %if.end.13, !dbg !71
if.else: ; preds = %if.end
%16 = load i8**, i8*** %argv.addr, align 8, !dbg !72
%arrayidx10 = getelementptr inbounds i8*, i8** %16, i64 2, !dbg !72
%17 = load i8*, i8** %arrayidx10, align 8, !dbg !72
%call11 = call i32 @atoi(i8* %17) #4, !dbg !74
%conv12 = sitofp i32 %call11 to double, !dbg !74
store double %conv12, double* %result, align 8, !dbg !75
br label %if.end.13
if.end.13: ; preds = %if.else, %for.end
%18 = load double, double* %result, align 8, !dbg !76
%call14 = call i32 (i8*, ...) @printf(i8* getelementptr inbounds ([15 x i8], [15 x i8]* @.str, i32 0, i32 0), double %18), !dbg !77
store i32 0, i32* %retval, align 4, !dbg !78
br label %return, !dbg !78
return: ; preds = %if.end.13, %if.then
%19 = load i32, i32* %retval, align 4, !dbg !79
ret i32 %19, !dbg !79
}
; Function Attrs: nounwind readnone
declare void @llvm.dbg.declare(metadata, metadata, metadata) #1
; Function Attrs: nounwind readonly
declare i32 @atoi(i8*) #2
declare i32 @printf(i8*, ...) #3
attributes #0 = { uwtable "disable-tail-calls"="false" "less-precise-fpmad"="false" "no-frame-pointer-elim"="true" "no-frame-pointer-elim-non-leaf" "no-infs-fp-math"="false" "no-nans-fp-math"="false" "stack-protector-buffer-size"="8" "target-cpu"="x86-64" "target-features"="+sse,+sse2" "unsafe-fp-math"="false" "use-soft-float"="false" }
attributes #1 = { nounwind readnone }
attributes #2 = { nounwind readonly "disable-tail-calls"="false" "less-precise-fpmad"="false" "no-frame-pointer-elim"="true" "no-frame-pointer-elim-non-leaf" "no-infs-fp-math"="false" "no-nans-fp-math"="false" "stack-protector-buffer-size"="8" "target-cpu"="x86-64" "target-features"="+sse,+sse2" "unsafe-fp-math"="false" "use-soft-float"="false" }
attributes #3 = { "disable-tail-calls"="false" "less-precise-fpmad"="false" "no-frame-pointer-elim"="true" "no-frame-pointer-elim-non-leaf" "no-infs-fp-math"="false" "no-nans-fp-math"="false" "stack-protector-buffer-size"="8" "target-cpu"="x86-64" "target-features"="+sse,+sse2" "unsafe-fp-math"="false" "use-soft-float"="false" }
attributes #4 = { nounwind readonly }
!llvm.dbg.cu = !{!0}
!llvm.module.flags = !{!13, !14}
!llvm.ident = !{!15}
!0 = distinct !DICompileUnit(language: DW_LANG_C_plus_plus, file: !1, producer: "clang version 3.8.0 (trunk 248211) (llvm/trunk 248217)", isOptimized: false, runtimeVersion: 0, emissionKind: 1, enums: !2, retainedTypes: !3, subprograms: !5)
!1 = !DIFile(filename: "test.cc", directory: "/ssd/llvm_commit")
!2 = !{}
!3 = !{!4}
!4 = !DIBasicType(name: "double", size: 64, align: 64, encoding: DW_ATE_float)
!5 = !{!6}
!6 = distinct !DISubprogram(name: "main", scope: !1, file: !1, line: 4, type: !7, isLocal: false, isDefinition: true, scopeLine: 4, flags: DIFlagPrototyped, isOptimized: false, function: i32 (i32, i8**)* @main, variables: !2)
!7 = !DISubroutineType(types: !8)
!8 = !{!9, !9, !10}
!9 = !DIBasicType(name: "int", size: 32, align: 32, encoding: DW_ATE_signed)
!10 = !DIDerivedType(tag: DW_TAG_pointer_type, baseType: !11, size: 64, align: 64)
!11 = !DIDerivedType(tag: DW_TAG_pointer_type, baseType: !12, size: 64, align: 64)
!12 = !DIBasicType(name: "char", size: 8, align: 8, encoding: DW_ATE_signed_char)
!13 = !{i32 2, !"Dwarf Version", i32 4}
!14 = !{i32 2, !"Debug Info Version", i32 3}
!15 = !{!"clang version 3.8.0 (trunk 248211) (llvm/trunk 248217)"}
!16 = !DILocalVariable(name: "argc", arg: 1, scope: !6, file: !1, line: 4, type: !9)
!17 = !DIExpression()
!18 = !DILocation(line: 4, column: 15, scope: !6)
!19 = !DILocalVariable(name: "argv", arg: 2, scope: !6, file: !1, line: 4, type: !10)
!20 = !DILocation(line: 4, column: 27, scope: !6)
!21 = !DILocation(line: 5, column: 8, scope: !22)
!22 = distinct !DILexicalBlock(scope: !6, file: !1, line: 5, column: 8)
!23 = !DILocation(line: 5, column: 13, scope: !22)
!24 = !DILocation(line: 5, column: 8, scope: !6)
!25 = !DILocation(line: 6, column: 6, scope: !22)
!26 = !DILocalVariable(name: "result", scope: !6, file: !1, line: 7, type: !4)
!27 = !DILocation(line: 7, column: 11, scope: !6)
!28 = !DILocalVariable(name: "limit", scope: !6, file: !1, line: 8, type: !9)
!29 = !DILocation(line: 8, column: 8, scope: !6)
!30 = !DILocation(line: 8, column: 21, scope: !6)
!31 = !DILocation(line: 8, column: 16, scope: !6)
!32 = !DILocation(line: 9, column: 8, scope: !33)
!33 = distinct !DILexicalBlock(scope: !6, file: !1, line: 9, column: 8)
!34 = !DILocation(line: 9, column: 14, scope: !33)
!35 = !DILocation(line: 9, column: 8, scope: !6)
!36 = !DILocalVariable(name: "s", scope: !37, file: !1, line: 10, type: !4)
!37 = distinct !DILexicalBlock(scope: !33, file: !1, line: 9, column: 21)
!38 = !DILocation(line: 10, column: 13, scope: !37)
!39 = !DILocation(line: 10, column: 34, scope: !37)
!40 = !DILocation(line: 10, column: 29, scope: !37)
!41 = !DILocation(line: 10, column: 27, scope: !37)
!42 = !DILocalVariable(name: "u", scope: !43, file: !1, line: 11, type: !9)
!43 = distinct !DILexicalBlock(scope: !37, file: !1, line: 11, column: 6)
!44 = !DILocation(line: 11, column: 15, scope: !43)
!45 = !DILocation(line: 11, column: 11, scope: !43)
!46 = !DILocation(line: 11, column: 22, scope: !47)
!47 = distinct !DILexicalBlock(scope: !43, file: !1, line: 11, column: 6)
!48 = !DILocation(line: 11, column: 26, scope: !47)
!49 = !DILocation(line: 11, column: 24, scope: !47)
!50 = !DILocation(line: 11, column: 6, scope: !43)
!51 = !DILocalVariable(name: "x", scope: !52, file: !1, line: 12, type: !4)
!52 = distinct !DILexicalBlock(scope: !47, file: !1, line: 11, column: 38)
!53 = !DILocation(line: 12, column: 15, scope: !52)
!54 = !DILocation(line: 12, column: 19, scope: !52)
!55 = !DILocation(line: 13, column: 12, scope: !52)
!56 = !DILocation(line: 13, column: 14, scope: !52)
!57 = !DILocation(line: 13, column: 32, scope: !52)
!58 = !DILocation(line: 13, column: 22, scope: !52)
!59 = !DILocation(line: 13, column: 10, scope: !52)
!60 = !DILocation(line: 14, column: 13, scope: !52)
!61 = !DILocation(line: 14, column: 24, scope: !52)
!62 = !DILocation(line: 14, column: 22, scope: !52)
!63 = !DILocation(line: 14, column: 26, scope: !52)
!64 = !DILocation(line: 14, column: 15, scope: !52)
!65 = !DILocation(line: 14, column: 10, scope: !52)
!66 = !DILocation(line: 15, column: 6, scope: !52)
!67 = !DILocation(line: 11, column: 34, scope: !47)
!68 = !DILocation(line: 11, column: 6, scope: !47)
!69 = !DILocation(line: 16, column: 15, scope: !37)
!70 = !DILocation(line: 16, column: 13, scope: !37)
!71 = !DILocation(line: 17, column: 4, scope: !37)
!72 = !DILocation(line: 18, column: 20, scope: !73)
!73 = distinct !DILexicalBlock(scope: !33, file: !1, line: 17, column: 11)
!74 = !DILocation(line: 18, column: 15, scope: !73)
!75 = !DILocation(line: 18, column: 13, scope: !73)
!76 = !DILocation(line: 20, column: 30, scope: !6)
!77 = !DILocation(line: 20, column: 4, scope: !6)
!78 = !DILocation(line: 21, column: 4, scope: !6)
!79 = !DILocation(line: 22, column: 2, scope: !6)