Compiler Design

BubbleSort void swap(int *xp, int *yp) { int temp = *xp; *xp = *yp; *yp = temp; }

void bubbleSort(int arr[], int n) { int i, j; for (i = 0; i < n-1; i++) for (j = 0; j < n-i-1; j++) if (arr[j] > arr[j+1]) swap(&arr[j], &arr[j+1]); }

int main() { int arr[] = {64, 34, 25, 12, 22, 11, 90}; int n = sizeof(arr)/sizeof(arr[0]); bubbleSort(arr, n); return 0; }

Unoptimised LLVM IR Code define void @swap(i32* %xp, i32* %yp) #0 { %1 = alloca i32*, align 4 %2 = alloca i32*, align 4 %temp = alloca i32, align 4 store i32* %xp, i32** %1, align 4 store i32* %yp, i32** %2, align 4 %3 = load i32*, i32** %1, align 4 %4 = load i32, i32* %3, align 4 store i32 %4, i32* %temp, align 4

%5 = load i32*, i32** %2, align 4 %6 = load i32, i32* %5, align 4 %7 = load i32*, i32** %1, align 4 store i32 %6, i32* %7, align 4 %8 = load i32, i32* %temp, align 4 %9 = load i32*, i32** %2, align 4 store i32 %8, i32* %9, align 4 ret void } ; Function Attrs: nounwind define void @bubbleSort(i32* %arr, i32 %n) #0 { %1 = alloca i32*, align 4 %2 = alloca i32, align 4 %i = alloca i32, align 4 %j = alloca i32, align 4 store i32* %arr, i32** %1, align 4 store i32 %n, i32* %2, align 4 store i32 0, i32* %i, align 4 br label %3 ; :3 ; preds = %40, %0 %4 = load i32, i32* %i, align 4 %5 = load i32, i32* %2, align 4 %6 = sub nsw i32 %5, 1 %7 = icmp slt i32 %4, %6 br i1 %7, label %8, label %43 ; :8 store i32 0, i32* %j, align 4 br label %9

; preds = %3

; :9 ; preds = %36, %8 %10 = load i32, i32* %j, align 4 %11 = load i32, i32* %2, align 4 %12 = load i32, i32* %i, align 4 %13 = sub nsw i32 %11, %12 %14 = sub nsw i32 %13, 1 %15 = icmp slt i32 %10, %14 br i1 %15, label %16, label %39 ; :16 ; preds = %9 %17 = load i32, i32* %j, align 4 %18 = load i32*, i32** %1, align 4 %19 = getelementptr inbounds i32, i32* %18, i32 %17 %20 = load i32, i32* %19, align 4 %21 = load i32, i32* %j, align 4

%22 = add nsw i32 %21, 1 %23 = load i32*, i32** %1, align 4 %24 = getelementptr inbounds i32, i32* %23, i32 %22 %25 = load i32, i32* %24, align 4 %26 = icmp sgt i32 %20, %25 br i1 %26, label %27, label %35 ; :27 ; preds = %16 %28 = load i32, i32* %j, align 4 %29 = load i32*, i32** %1, align 4 %30 = getelementptr inbounds i32, i32* %29, i32 %28 %31 = load i32, i32* %j, align 4 %32 = add nsw i32 %31, 1 %33 = load i32*, i32** %1, align 4 %34 = getelementptr inbounds i32, i32* %33, i32 %32 call void @swap(i32* %30, i32* %34) br label %35 ; :35 br label %36

; preds = %27, %16

; :36 ; preds = %35 %37 = load i32, i32* %j, align 4 %38 = add nsw i32 %37, 1 store i32 %38, i32* %j, align 4 br label %9 ; :39 br label %40

; preds = %9

; :40 ; preds = %39 %41 = load i32, i32* %i, align 4 %42 = add nsw i32 %41, 1 store i32 %42, i32* %i, align 4 br label %3 ; :43 ret void }

; preds = %3

Optimised LLVM IR Code define void @swap(i32* nocapture %xp, i32* nocapture %yp) #0 { %1 = load i32, i32* %xp, align 4, !tbaa !1 %2 = load i32, i32* %yp, align 4, !tbaa !1 store i32 %2, i32* %xp, align 4, !tbaa !1

store i32 %1, i32* %yp, align 4, !tbaa !1 ret void } ; Function Attrs: argmemonly nounwind declare void @llvm.lifetime.start(i64, i8* nocapture) #1 ; Function Attrs: argmemonly nounwind declare void @llvm.lifetime.end(i64, i8* nocapture) #1 ; Function Attrs: norecurse nounwind define void @bubbleSort(i32* nocapture %arr, i32 %n) #0 { %1 = icmp sgt i32 %n, 1 br i1 %1, label %.preheader.lr.ph, label %._crit_edge3 .preheader.lr.ph: %2 = add i32 %n, -1 br label %.preheader

; preds = %0

.preheader: ; preds = %._crit_edge, %.preheader.lr.ph %indvars.iv = phi i32 [ %2, %.preheader.lr.ph ], [ %indvars.iv.next, %._crit_edge ] %i.02 = phi i32 [ 0, %.preheader.lr.ph ], [ %13, %._crit_edge ] %3 = sub i32 %2, %i.02 %4 = icmp sgt i32 %3, 0 br i1 %4, label %.lr.ph.preheader, label %._crit_edge .lr.ph.preheader: ; preds = %.preheader %.pre = load i32, i32* %arr, align 4, !tbaa !1 br label %.lr.ph .lr.ph: ; preds = %.backedge, %.lr.ph.preheader %5 = phi i32 [ %10, %.backedge ], [ %.pre, %.lr.ph.preheader ] %j.01 = phi i32 [ %6, %.backedge ], [ 0, %.lr.ph.preheader ] %6 = add nuw nsw i32 %j.01, 1 %7 = getelementptr inbounds i32, i32* %arr, i32 %6 %8 = load i32, i32* %7, align 4, !tbaa !1 %9 = icmp sgt i32 %5, %8 br i1 %9, label %11, label %.backedge .backedge: ; preds = %.lr.ph, %11 %10 = phi i32 [ %8, %.lr.ph ], [ %5, %11 ] %exitcond = icmp eq i32 %6, %indvars.iv br i1 %exitcond, label %._crit_edge.loopexit, label %.lr.ph ; :11 ; preds = %.lr.ph %12 = getelementptr inbounds i32, i32* %arr, i32 %j.01 store i32 %8, i32* %12, align 4, !tbaa !1

store i32 %5, i32* %7, align 4, !tbaa !1 br label %.backedge ._crit_edge.loopexit: br label %._crit_edge

; preds = %.backedge

._crit_edge: ; preds = %._crit_edge.loopexit, %.preheader %13 = add nuw nsw i32 %i.02, 1 %indvars.iv.next = add i32 %indvars.iv, -1 %exitcond4 = icmp eq i32 %13, %2 br i1 %exitcond4, label %._crit_edge3.loopexit, label %.preheader ._crit_edge3.loopexit: br label %._crit_edge3 ._crit_edge3: ret void }

; preds = %._crit_edge ; preds = %._crit_edge3.loopexit, %0