Fix OpenSSL multiple vulnerabilities. [13:03]

Fix BIND remote denial of service. [13:04] Security: CVE-2013-0166, CVE-2013-0169 Security: FreeBSD-SA-13:03.openssl Security: CVE-2013-2266 Security: FreeBSD-SA-13:04.bind Approved by: so
Fix Denial of Service vulnerability in named(8) with DNS64. [13:01]
2026-10-28 19:34:43 +01:00 · 2013-04-02 17:34:42 +00:00 · 2013-02-19 13:27:20 +00:00 · 2012-11-22 22:52:15 +00:00 · 2012-08-06 21:33:11 +00:00 · 2012-06-12 12:10:10 +00:00
2623 changed files with 195986 additions and 131657 deletions
@@ -4,7 +4,7 @@
 The compilation of software known as FreeBSD is distributed under the
 following terms:

-Copyright (c) 1992-2011 The FreeBSD Project. All rights reserved.
+Copyright (c) 1992-2012 The FreeBSD Project. All rights reserved.

 Redistribution and use in source and binary forms, with or without
 modification, are permitted provided that the following conditions
@@ -182,10 +182,12 @@ buildworld: upgrade_checks
 #
 # In the following, the first 'rm' in a series will usually remove all
 # files and directories.  If it does not, then there are probably some
-# files with chflags set, so this unsets them and tries the 'rm' a
+# files with file flags set, so this unsets them and tries the 'rm' a
 # second time.  There are situations where this target will be cleaning
 # some directories via more than one method, but that duplication is
-# needed to correctly handle all the possible situations.
+# needed to correctly handle all the possible situations.  Removing all
+# files without file flags set in the first 'rm' instance saves time,
+# because 'chflags' will need to operate on fewer files afterwards.
 #
 BW_CANONICALOBJDIR:=${MAKEOBJDIRPREFIX}${.CURDIR}
 cleanworld:
@@ -107,7 +107,7 @@ CLEANDIR=	cleandir
 .endif

 CVS?=		cvs
-CVSFLAGS?=	-A -P -d -I!
+CVSFLAGS?=	-r RELENG_9_0 -P -d -I!
 SVN?=		svn
 SVNFLAGS?=	-r HEAD
 SUP?=		/usr/bin/csup
@@ -1030,7 +1030,9 @@ _crunchgen=	usr.sbin/crunch/crunchgen
 .if ${MK_CLANG} != "no"
 _clang_tblgen= \
 	lib/clang/libllvmsupport \
-	usr.bin/clang/tblgen
+	lib/clang/libllvmtablegen \
+	usr.bin/clang/tblgen \
+	usr.bin/clang/clang-tblgen
 .endif

 .if ${MK_CDDL} != "no" && \
@@ -1218,7 +1220,8 @@ _startup_libs+=	lib/libc

 gnu/lib/libgcc__L: lib/libc__L

-_prebuild_libs=	${_kerberos5_lib_libasn1} ${_kerberos5_lib_libheimntlm} \
+_prebuild_libs=	${_kerberos5_lib_libasn1} ${_kerberos5_lib_libhdb} \
+		${_kerberos5_lib_libheimntlm} \
 		${_kerberos5_lib_libhx509} ${_kerberos5_lib_libkrb5} \
 		${_kerberos5_lib_libroken} \
 		lib/libbz2 lib/libcom_err lib/libcrypt \
@@ -1268,6 +1271,19 @@ secure/lib/libssh__L: lib/libgssapi__L kerberos5/lib/libkrb5__L \
 _secure_lib=	secure/lib
 .endif

+.if ${MK_KERBEROS} != "no"
+kerberos5/lib/libasn1__L: lib/libcom_err__L kerberos5/lib/libroken__L
+kerberos5/lib/libhdb__L: kerberos5/lib/libasn1__L lib/libcom_err__L \
+    kerberos5/lib/libkrb5__L kerberos5/lib/libroken__L
+kerberos5/lib/libheimntlm__L: secure/lib/libcrypto__L kerberos5/lib/libkrb5__L
+kerberos5/lib/libhx509__L: kerberos5/lib/libasn1__L lib/libcom_err__L \
+    secure/lib/libcrypto__L kerberos5/lib/libroken__L
+kerberos5/lib/libkrb5__L: kerberos5/lib/libasn1__L lib/libcom_err__L \
+    lib/libcrypt__L secure/lib/libcrypto__L kerberos5/lib/libhx509__L \
+    kerberos5/lib/libroken__L
+kerberos5/lib/libroken__L: lib/libcrypt__L
+.endif
+
 .if ${MK_GSSAPI} != "no"
 _lib_libgssapi=	lib/libgssapi
 .endif
@@ -1279,6 +1295,7 @@ _lib_libipx=	lib/libipx
 .if ${MK_KERBEROS} != "no"
 _kerberos5_lib=	kerberos5/lib
 _kerberos5_lib_libasn1= kerberos5/lib/libasn1
+_kerberos5_lib_libhdb= kerberos5/lib/libhdb
 _kerberos5_lib_libkrb5= kerberos5/lib/libkrb5
 _kerberos5_lib_libhx509= kerberos5/lib/libhx509
 _kerberos5_lib_libroken= kerberos5/lib/libroken
@@ -9,18 +9,53 @@ handbook.
 Items affecting the ports and packages system can be found in
 /usr/ports/UPDATING.  Please read that file before running portupgrade.

-NOTE TO PEOPLE WHO THINK THAT FreeBSD 9.x IS SLOW:
-	FreeBSD 9.x has many debugging features turned on, in both the kernel
-	and userland.  These features attempt to detect incorrect use of
-	system primitives, and encourage loud failure through extra sanity
-	checking and fail stop semantics.  They also substantially impact
-	system performance.  If you want to do performance measurement,
-	benchmarking, and optimization, you'll want to turn them off.  This
-	includes various WITNESS- related kernel options, INVARIANTS, malloc
-	debugging flags in userland, and various verbose features in the
-	kernel.  Many developers choose to disable these features on build
-	machines to maximize performance.  (To disable malloc debugging, run
-	ln -s aj /etc/malloc.conf.)
+20130402:	p7	FreeBSD-SA-13:03.openssl FreeBSD-SA-13:04.bind
+	Fix multiple vulnerabilities in OpenSSL.
+
+	Fix Denial of Service vulnerability in named(8).
+
+20130218:	p6	FreeBSD-SA-13:01.bind FreeBSD-SA-13:02.libc
+	Fix Denial of Service vulnerability in named(8) with DNS64.
+
+	Fix Denial of Service vulnerability in libc's glob(3) functionality.
+
+20121122:	p5	FreeBSD-SA-12:06.bind FreeBSD-SA-12:07.hostapd
+			FreeBSD-SA-12:08.linux
+	Fix multiple Denial of Service vulnerabilities with named(8).
+
+	Fix insufficient message length validation for EAP-TLS messages.
+
+	Fix Linux compatibility layer input validation error.
+
+20120806:	p4	FreeBSD-SA-12:05.bind
+	Fix named(8) DNSSEC validation Denial of Service.
+
+20120612:	p3	FreeBSD-SA-12:03.bind
+			FreeBSD-SA-12:04.sysret
+			FreeBSD-EN-12:02.ipv6refcount
+	Fix a problem where zero-length RDATA fields can cause named to crash.
+	[12:03]
+
+	Correct a privilege escalation when returning from kernel if
+	running FreeBSD/amd64 on non-AMD processors. [12:04]
+
+	Fix reference count errors in IPv6 code. [EN-12:02]
+
+20120530:	p2	FreeBSD-SA-12:01.openssl (revised),
+			FreeBSD-SA-12:02.crypt
+	Update the previous openssl fix. [12:01]
+
+	Fix a bug in crypt(3) ignoring characters of a passphrase. [12:02]
+
+20120503:	p1	FreeBSD-SA-12:01.openssl
+	Fix multiple OpenSSL vulnerabilities.
+
+20120106:
+	9.0-RELEASE.
+
+20111101:
+	The broken amd(4) driver has been replaced with esp(4) in the amd64,
+	i386 and pc98 GENERIC kernel configuration files.

 20110913:
 	This commit modifies vfs_register() so that it uses a hash
@@ -29,7 +29,7 @@
 .\"     @(#)ps.1	8.3 (Berkeley) 4/18/94
 .\" $FreeBSD$
 .\"
-.Dd July 1, 2011
+.Dd October 1, 2011
 .Dt PS 1
 .Os
 .Sh NAME
@@ -54,6 +54,11 @@ utility
 displays a header line, followed by lines containing information about
 all of your
 processes that have controlling terminals.
+If the
+.Fl x
+options is specified,
+.Nm
+will also display processes that do not have controlling terminals.
 .Pp
 A different set of processes can be selected for display by using any
 combination of the
@@ -90,8 +95,8 @@ and
 .Fl o
 options).
 The default output format includes, for each process, the process' ID,
-controlling terminal, CPU time (including both user and system time),
-state, and associated command.
+controlling terminal, state, CPU time (including both user and system time)
+and associated command.
 .Pp
 The process file system (see
 .Xr procfs 5 )
@@ -103,13 +108,9 @@ The options are as follows:
 .Bl -tag -width indent
 .It Fl a
 Display information about other users' processes as well as your own.
-This will skip any processes which do not have a controlling terminal,
-unless the
-.Fl x
-option is also specified.
-This can be disabled by setting the
+If the
 .Va security.bsd.see_other_uids
-sysctl to zero.
+sysctl is set to zero, this option is honored only if the UID of the user is 0.
 .It Fl c
 Change the
 .Dq command
@@ -216,6 +217,9 @@ with the standard input.
 .It Fl t
 Display information about processes attached to the specified terminal
 devices.
+Full pathnames, as well as abbreviations (see explanation of the
+.Cm tt
+keyword) can be specified.
 .It Fl U
 Display the processes belonging to the specified usernames.
 .It Fl u
@@ -427,12 +431,15 @@ The process is being traced or debugged.
 An abbreviation for the pathname of the controlling terminal, if any.
 The abbreviation consists of the three letters following
 .Pa /dev/tty ,
-or, for the console,
-.Dq Li con .
+or, for pseudo-terminals, the corresponding entry in
+.Pa /dev/pts .
 This is followed by a
 .Ql -
 if the process can no longer reach that
 controlling terminal (i.e., it has been revoked).
+The full pathname of the controlling terminal is available via the
+.Cm tty
+keyword.
 .It Cm wchan
 The event (an address in the system) on which a process waits.
 When printed numerically, the initial part of the address is
@@ -2190,8 +2190,10 @@ dump_block_stats(spa_t *spa)
 	 */
 	(void) bpobj_iterate_nofree(&spa->spa_deferred_bpobj,
 	    count_block_cb, &zcb, NULL);
-	(void) bpobj_iterate_nofree(&spa->spa_dsl_pool->dp_free_bpobj,
-	    count_block_cb, &zcb, NULL);
+	if (spa_version(spa) >= SPA_VERSION_DEADLISTS) {
+		(void) bpobj_iterate_nofree(&spa->spa_dsl_pool->dp_free_bpobj,
+		    count_block_cb, &zcb, NULL);
+	}

 	if (dump_opt['c'] > 1)
 		flags |= TRAVERSE_PREFETCH_DATA;
@@ -76,6 +76,7 @@ static __inline int
 thr_create(void *stack_base, size_t stack_size, void *(*start_func) (void*),
    void *arg, long flags, thread_t *new_thread_ID)
 {
+	pthread_t dummy;
 	int ret;

 	assert(stack_base == NULL);
@@ -85,9 +86,12 @@ thr_create(void *stack_base, size_t stack_size, void *(*start_func) (void*),
 	pthread_attr_t attr;
 	pthread_attr_init(&attr);

-	if(flags & THR_DETACHED)
+	if (flags & THR_DETACHED)
 		pthread_attr_setdetachstate(&attr, PTHREAD_CREATE_DETACHED);

+	if (new_thread_ID == NULL)
+		new_thread_ID = &dummy;
+
 	/* This function ignores the THR_BOUND flag, since NPTL doesn't seem to support PTHREAD_SCOPE_PROCESS */

 	ret = pthread_create(new_thread_ID, &attr, start_func, arg);
@@ -467,7 +467,6 @@ change_one(zfs_handle_t *zhp, void *data)
 			 * This is necessary when the original mountpoint
 			 * is legacy or none.
 			 */
-			ASSERT(!clp->cl_alldependents);
 			verify(uu_list_insert_before(clp->cl_list,
 			    uu_list_first(clp->cl_list), cn) == 0);
 		}
@@ -87,7 +87,7 @@ again:	if ((t = tq->tq_freelist) != NULL && tq->tq_nalloc >= tq->tq_minalloc) {
 		}
 		mutex_exit(&tq->tq_lock);

-		t = kmem_alloc(sizeof (task_t), tqflags);
+		t = kmem_alloc(sizeof (task_t), tqflags & KM_SLEEP);

 		mutex_enter(&tq->tq_lock);
 		if (t != NULL)
@@ -18,4 +18,4 @@ CFLAGS+=	-I${.CURDIR}/../../../sys/cddl/compat/opensolaris \
 		-I${OPENSOLARIS_SYS_DISTDIR}/uts/common \
 		-DPIC ${PICFLAG}

-.include <bsd.prog.mk>
+.include <bsd.lib.mk>
@@ -1,3 +1,9 @@
+	--- 9.8.1-P1 released ---
+
+3218.	[security]	Cache lookup could return RRSIG data associated with
+			nonexistent records, leading to an assertion
+			failure. [RT #26590]
+
 	--- 9.8.1 released ---

 	--- 9.8.1rc1 released ---
@@ -15,7 +15,7 @@
 * PERFORMANCE OF THIS SOFTWARE.
 */

-/* $Id: query.c,v 1.353.8.11 2011-06-09 03:14:03 marka Exp $ */
+/* $Id: query.c,v 1.353.8.11.4.1 2011-11-16 09:32:08 marka Exp $ */

 /*! \file */

@@ -1137,13 +1137,6 @@ query_isduplicate(ns_client_t *client, dns_name_t *name,
 		mname = NULL;
 	}

-	/*
-	 * If the dns_name_t we're looking up is already in the message,
-	 * we don't want to trigger the caller's name replacement logic.
-	 */
-	if (name == mname)
-		mname = NULL;
-
 	*mnamep = mname;

 	CTRACE("query_isduplicate: false: done");
@@ -1341,6 +1334,7 @@ query_addadditional(void *arg, dns_name_t *name, dns_rdatatype_t qtype) {
 	if (dns_rdataset_isassociated(rdataset) &&
 	    !query_isduplicate(client, fname, type, &mname)) {
 		if (mname != NULL) {
+			INSIST(mname != fname);
 			query_releasename(client, &fname);
 			fname = mname;
 		} else
@@ -1393,21 +1387,21 @@ query_addadditional(void *arg, dns_name_t *name, dns_rdatatype_t qtype) {
 			goto addname;
 		if (result == DNS_R_NCACHENXRRSET) {
 			dns_rdataset_disassociate(rdataset);
-			/*
-			 * Negative cache entries don't have sigrdatasets.
-			 */
-			INSIST(sigrdataset == NULL ||
-			       ! dns_rdataset_isassociated(sigrdataset));
+			if (sigrdataset != NULL &&
+			    dns_rdataset_isassociated(sigrdataset))
+				dns_rdataset_disassociate(sigrdataset);
 		}
 		if (result == ISC_R_SUCCESS) {
 			mname = NULL;
 			if (!query_isduplicate(client, fname,
 					       dns_rdatatype_a, &mname)) {
+				if (mname != fname) {
 				if (mname != NULL) {
 					query_releasename(client, &fname);
 					fname = mname;
 				} else
 					need_addname = ISC_TRUE;
+				}
 				ISC_LIST_APPEND(fname->list, rdataset, link);
 				added_something = ISC_TRUE;
 				if (sigrdataset != NULL &&
@@ -1438,18 +1432,21 @@ query_addadditional(void *arg, dns_name_t *name, dns_rdatatype_t qtype) {
 			goto addname;
 		if (result == DNS_R_NCACHENXRRSET) {
 			dns_rdataset_disassociate(rdataset);
-			INSIST(sigrdataset == NULL ||
-			       ! dns_rdataset_isassociated(sigrdataset));
+			if (sigrdataset != NULL &&
+			    dns_rdataset_isassociated(sigrdataset))
+				dns_rdataset_disassociate(sigrdataset);
 		}
 		if (result == ISC_R_SUCCESS) {
 			mname = NULL;
 			if (!query_isduplicate(client, fname,
 					       dns_rdatatype_aaaa, &mname)) {
+				if (mname != fname) {
 				if (mname != NULL) {
 					query_releasename(client, &fname);
 					fname = mname;
 				} else
 					need_addname = ISC_TRUE;
+				}
 				ISC_LIST_APPEND(fname->list, rdataset, link);
 				added_something = ISC_TRUE;
 				if (sigrdataset != NULL &&
@@ -1889,10 +1886,8 @@ query_addadditional2(void *arg, dns_name_t *name, dns_rdatatype_t qtype) {
 		goto setcache;
 	if (result == DNS_R_NCACHENXRRSET) {
 		dns_rdataset_disassociate(rdataset);
-		/*
-		 * Negative cache entries don't have sigrdatasets.
-		 */
-		INSIST(! dns_rdataset_isassociated(sigrdataset));
+		if (dns_rdataset_isassociated(sigrdataset))
+			dns_rdataset_disassociate(sigrdataset);
 	}
 	if (result == ISC_R_SUCCESS) {
 		/* Remember the result as a cache */
@@ -1963,6 +1958,7 @@ query_addadditional2(void *arg, dns_name_t *name, dns_rdatatype_t qtype) {
 		    crdataset->type == dns_rdatatype_aaaa) {
 			if (!query_isduplicate(client, fname, crdataset->type,
 					       &mname)) {
+				if (mname != fname) {
 				if (mname != NULL) {
 					/*
 					 * A different type of this name is
@@ -1979,6 +1975,7 @@ query_addadditional2(void *arg, dns_name_t *name, dns_rdatatype_t qtype) {
 					mname0 = mname;
 				} else
 					need_addname = ISC_TRUE;
+				}
 				ISC_LIST_UNLINK(cfname.list, crdataset, link);
 				ISC_LIST_APPEND(fname->list, crdataset, link);
 				added_something = ISC_TRUE;
@@ -4863,10 +4860,12 @@ dns64_ttl(dns_db_t *db, dns_dbversion_t *version) {
 	isc_result_t result;
 	isc_uint32_t ttl = ISC_UINT32_MAX;

+	dns_rdataset_init(&rdataset);
+
 	result = dns_db_getoriginnode(db, &node);
 	if (result != ISC_R_SUCCESS)
 		goto cleanup;
-	dns_rdataset_init(&rdataset);
+
 	result = dns_db_findrdataset(db, node, version, dns_rdatatype_soa,
 				     0, 0, &rdataset, NULL);
 	if (result != ISC_R_SUCCESS)
@@ -146,6 +146,17 @@ struct dns_rdata {
 #define DNS_RDATA_VALIDFLAGS(rdata) \
 	(((rdata)->flags & ~(DNS_RDATA_UPDATE|DNS_RDATA_OFFLINE)) == 0)

+/*
+ * The maximum length of a RDATA that can be sent on the wire.
+ * Max packet size (65535) less header (12), less name (1), type (2),
+ * class (2), ttl(4), length (2).
+ *
+ * None of the defined types that support name compression can exceed
+ * this and all new types are to be sent uncompressed.
+ */
+
+#define DNS_RDATA_MAXLENGTH	65512U
+
 /*
 * Flags affecting rdata formatting style.  Flags 0xFFFF0000
 * are used by masterfile-level formatting and defined elsewhere.
@@ -75,7 +75,7 @@
 /*%
 * max message size - header - root - type - class - ttl - rdlen
 */
-#define MINTSIZ (65535 - 12 - 1 - 2 - 2 - 4 - 2)
+#define MINTSIZ DNS_RDATA_MAXLENGTH
 /*%
 * Size for tokens in the presentation format,
 * The largest tokens are the base64 blocks in KEY and CERT records,
@@ -15,7 +15,7 @@
 * PERFORMANCE OF THIS SOFTWARE.
 */

-/* $Id: rbtdb.c,v 1.310.8.5 2011-06-08 23:02:42 each Exp $ */
+/* $Id: rbtdb.c,v 1.310.8.5.4.1 2011-11-16 09:32:08 marka Exp $ */

 /*! \file */

@@ -5053,7 +5053,7 @@ cache_find(dns_db_t *db, dns_name_t *name, dns_dbversion_t *version,
 			      rdataset);
 		if (need_headerupdate(found, search.now))
 			update = found;
-		if (foundsig != NULL) {
+		if (!NEGATIVE(found) && foundsig != NULL) {
 			bind_rdataset(search.rbtdb, node, foundsig, search.now,
 				      sigrdataset);
 			if (need_headerupdate(foundsig, search.now))
@@ -5685,7 +5685,7 @@ cache_findrdataset(dns_db_t *db, dns_dbnode_t *node, dns_dbversion_t *version,
 	}
 	if (found != NULL) {
 		bind_rdataset(rbtdb, rbtnode, found, now, rdataset);
-		if (foundsig != NULL)
+		if (!NEGATIVE(found) && foundsig != NULL)
 			bind_rdataset(rbtdb, rbtnode, foundsig, now,
 				      sigrdataset);
 	}
@@ -325,8 +325,8 @@ dns_rdata_compare(const dns_rdata_t *rdata1, const dns_rdata_t *rdata2) {

 	REQUIRE(rdata1 != NULL);
 	REQUIRE(rdata2 != NULL);
-	REQUIRE(rdata1->data != NULL);
-	REQUIRE(rdata2->data != NULL);
+	REQUIRE(rdata1->length == 0 || rdata1->data != NULL);
+	REQUIRE(rdata2->length == 0 || rdata2->data != NULL);
 	REQUIRE(DNS_RDATA_VALIDFLAGS(rdata1));
 	REQUIRE(DNS_RDATA_VALIDFLAGS(rdata2));

@@ -356,8 +356,8 @@ dns_rdata_casecompare(const dns_rdata_t *rdata1, const dns_rdata_t *rdata2) {

 	REQUIRE(rdata1 != NULL);
 	REQUIRE(rdata2 != NULL);
-	REQUIRE(rdata1->data != NULL);
-	REQUIRE(rdata2->data != NULL);
+	REQUIRE(rdata1->length == 0 || rdata1->data != NULL);
+	REQUIRE(rdata2->length == 0 || rdata2->data != NULL);
 	REQUIRE(DNS_RDATA_VALIDFLAGS(rdata1));
 	REQUIRE(DNS_RDATA_VALIDFLAGS(rdata2));

@@ -425,6 +425,7 @@ dns_rdata_fromwire(dns_rdata_t *rdata, dns_rdataclass_t rdclass,
 	isc_buffer_t st;
 	isc_boolean_t use_default = ISC_FALSE;
 	isc_uint32_t activelength;
+	size_t length;

 	REQUIRE(dctx != NULL);
 	if (rdata != NULL) {
@@ -454,6 +455,14 @@ dns_rdata_fromwire(dns_rdata_t *rdata, dns_rdataclass_t rdclass,
 		}
 	}

+	/*
+	 * Reject any rdata that expands out to more than DNS_RDATA_MAXLENGTH
+	 * as we cannot transmit it.
+	 */
+	length = isc_buffer_usedlength(target) - isc_buffer_usedlength(&st);
+	if (result == ISC_R_SUCCESS && length > DNS_RDATA_MAXLENGTH)
+		result = DNS_R_FORMERR;
+
 	/*
 	 * We should have consumed all of our buffer.
 	 */
@@ -462,8 +471,7 @@ dns_rdata_fromwire(dns_rdata_t *rdata, dns_rdataclass_t rdclass,

 	if (rdata != NULL && result == ISC_R_SUCCESS) {
 		region.base = isc_buffer_used(&st);
-		region.length = isc_buffer_usedlength(target) -
-				isc_buffer_usedlength(&st);
+		region.length = length;
 		dns_rdata_fromregion(rdata, rdclass, type, &region);
 	}

@@ -598,6 +606,7 @@ dns_rdata_fromtext(dns_rdata_t *rdata, dns_rdataclass_t rdclass,
 	unsigned long line;
 	void (*callback)(dns_rdatacallbacks_t *, const char *, ...);
 	isc_result_t tresult;
+	size_t length;

 	REQUIRE(origin == NULL || dns_name_isabsolute(origin) == ISC_TRUE);
 	if (rdata != NULL) {
@@ -670,10 +679,13 @@ dns_rdata_fromtext(dns_rdata_t *rdata, dns_rdataclass_t rdclass,
 		}
 	} while (1);

+	length = isc_buffer_usedlength(target) - isc_buffer_usedlength(&st);
+	if (result == ISC_R_SUCCESS && length > DNS_RDATA_MAXLENGTH)
+		result = ISC_R_NOSPACE;
+
 	if (rdata != NULL && result == ISC_R_SUCCESS) {
 		region.base = isc_buffer_used(&st);
-		region.length = isc_buffer_usedlength(target) -
-				isc_buffer_usedlength(&st);
+		region.length = length;
 		dns_rdata_fromregion(rdata, rdclass, type, &region);
 	}
 	if (result != ISC_R_SUCCESS) {
@@ -781,6 +793,7 @@ dns_rdata_fromstruct(dns_rdata_t *rdata, dns_rdataclass_t rdclass,
 	isc_buffer_t st;
 	isc_region_t region;
 	isc_boolean_t use_default = ISC_FALSE;
+	size_t length;

 	REQUIRE(source != NULL);
 	if (rdata != NULL) {
@@ -795,10 +808,13 @@ dns_rdata_fromstruct(dns_rdata_t *rdata, dns_rdataclass_t rdclass,
 	if (use_default)
 		(void)NULL;

+	length = isc_buffer_usedlength(target) - isc_buffer_usedlength(&st);
+	if (result == ISC_R_SUCCESS && length > DNS_RDATA_MAXLENGTH)
+		result = ISC_R_NOSPACE;
+
 	if (rdata != NULL && result == ISC_R_SUCCESS) {
 		region.base = isc_buffer_used(&st);
-		region.length = isc_buffer_usedlength(target) -
-				isc_buffer_usedlength(&st);
+		region.length = length;
 		dns_rdata_fromregion(rdata, rdclass, type, &region);
 	}
 	if (result != ISC_R_SUCCESS)
@@ -125,6 +125,11 @@ isc_result_t
 dns_rdataslab_fromrdataset(dns_rdataset_t *rdataset, isc_mem_t *mctx,
 			   isc_region_t *region, unsigned int reservelen)
 {
+	/*
+	 * Use &removed as a sentinal pointer for duplicate
+	 * rdata as rdata.data == NULL is valid.
+	 */
+	static unsigned char removed;
 	struct xrdata  *x;
 	unsigned char  *rawbuf;
 #if DNS_RDATASET_FIXED
@@ -168,6 +173,7 @@ dns_rdataslab_fromrdataset(dns_rdataset_t *rdataset, isc_mem_t *mctx,
 		INSIST(result == ISC_R_SUCCESS);
 		dns_rdata_init(&x[i].rdata);
 		dns_rdataset_current(rdataset, &x[i].rdata);
+		INSIST(x[i].rdata.data != &removed);
 #if DNS_RDATASET_FIXED
 		x[i].order = i;
 #endif
@@ -200,8 +206,7 @@ dns_rdataslab_fromrdataset(dns_rdataset_t *rdataset, isc_mem_t *mctx,
 	 */
 	for (i = 1; i < nalloc; i++) {
 		if (compare_rdata(&x[i-1].rdata, &x[i].rdata) == 0) {
-			x[i-1].rdata.data = NULL;
-			x[i-1].rdata.length = 0;
+			x[i-1].rdata.data = &removed;
 #if DNS_RDATASET_FIXED
 			/*
 			 * Preserve the least order so A, B, A -> A, B
@@ -291,7 +296,7 @@ dns_rdataslab_fromrdataset(dns_rdataset_t *rdataset, isc_mem_t *mctx,
 #endif

 	for (i = 0; i < nalloc; i++) {
-		if (x[i].rdata.data == NULL)
+		if (x[i].rdata.data == &removed)
 			continue;
 #if DNS_RDATASET_FIXED
 		offsettable[x[i].order] = rawbuf - offsetbase;
@@ -8318,6 +8318,7 @@ dns_resolver_addbadcache(dns_resolver_t *resolver, dns_name_t *name,
 			goto cleanup;
 		bad->type = type;
 		bad->hashval = hashval;
+		bad->expire = *expire;
 		isc_buffer_init(&buffer, bad + 1, name->length);
 		dns_name_init(&bad->name, NULL);
 		dns_name_copy(name, &bad->name, &buffer);
@@ -8329,8 +8330,8 @@ dns_resolver_addbadcache(dns_resolver_t *resolver, dns_name_t *name,
 		if (resolver->badcount < resolver->badhash * 2 &&
 		    resolver->badhash > DNS_BADCACHE_SIZE)
 			resizehash(resolver, &now, ISC_FALSE);
-	}
-	bad->expire = *expire;
+	} else
+		bad->expire = *expire;
 cleanup:
 	UNLOCK(&resolver->lock);
 }
@@ -1,4 +1,4 @@
-# $Id: version,v 1.53.8.9 2011-08-24 02:08:26 marka Exp $
+# $Id: version,v 1.53.8.9.6.1 2011-11-16 09:32:07 marka Exp $
 # 
 # This file must follow /bin/sh rules.  It is imported directly via
 # configure.
@@ -6,5 +6,5 @@
 MAJORVER=9
 MINORVER=8
 PATCHVER=1
-RELEASETYPE=
-RELEASEVER=
+RELEASETYPE=-P
+RELEASEVER=1
@@ -1 +1 @@
-4.2.2
+4.2.1
@@ -1 +1 @@
-prerelease
+patched
@@ -3217,7 +3217,8 @@ legitimize_pic_address (rtx orig, enum machine_mode mode, rtx reg)
 	  gcc_assert (!no_new_pseudos);
 	  if (arm_pic_register != INVALID_REGNUM)
 	    {
-	      cfun->machine->pic_reg = gen_rtx_REG (Pmode, arm_pic_register);
+	      if (!cfun->machine->pic_reg)
+		cfun->machine->pic_reg = gen_rtx_REG (Pmode, arm_pic_register);

 	      /* Play games to avoid marking the function as needing pic
 		 if we are being called as part of the cost-estimation
@@ -3229,7 +3230,8 @@ legitimize_pic_address (rtx orig, enum machine_mode mode, rtx reg)
 	    {
 	      rtx seq;

-	      cfun->machine->pic_reg = gen_reg_rtx (Pmode);
+	      if (!cfun->machine->pic_reg)
+		  cfun->machine->pic_reg = gen_reg_rtx (Pmode);

 	      /* Play games to avoid marking the function as needing pic
 		 if we are being called as part of the cost-estimation
@@ -0,0 +1,69 @@
+==============================================================================
+LLVM Release License
+==============================================================================
+University of Illinois/NCSA
+Open Source License
+
+Copyright (c) 2003-2011 University of Illinois at Urbana-Champaign.
+All rights reserved.
+
+Developed by:
+
+    LLVM Team
+
+    University of Illinois at Urbana-Champaign
+
+    http://llvm.org
+
+Permission is hereby granted, free of charge, to any person obtaining a copy of
+this software and associated documentation files (the "Software"), to deal with
+the Software without restriction, including without limitation the rights to
+use, copy, modify, merge, publish, distribute, sublicense, and/or sell copies
+of the Software, and to permit persons to whom the Software is furnished to do
+so, subject to the following conditions:
+
+    * Redistributions of source code must retain the above copyright notice,
+      this list of conditions and the following disclaimers.
+
+    * Redistributions in binary form must reproduce the above copyright notice,
+      this list of conditions and the following disclaimers in the
+      documentation and/or other materials provided with the distribution.
+
+    * Neither the names of the LLVM Team, University of Illinois at
+      Urbana-Champaign, nor the names of its contributors may be used to
+      endorse or promote products derived from this Software without specific
+      prior written permission.
+
+THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
+IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, FITNESS
+FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.  IN NO EVENT SHALL THE
+CONTRIBUTORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
+LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
+OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS WITH THE
+SOFTWARE.
+
+==============================================================================
+Copyrights and Licenses for Third Party Software Distributed with LLVM:
+==============================================================================
+The LLVM software contains code written by third parties.  Such software will
+have its own individual LICENSE.TXT file in the directory in which it appears.
+This file will describe the copyrights, license, and restrictions which apply
+to that code.
+
+The disclaimer of warranty in the University of Illinois Open Source License
+applies to all code in the LLVM Distribution, and nothing in any of the
+other licenses gives permission to use the names of the LLVM Team or the
+University of Illinois to endorse or promote products derived from this
+Software.
+
+The following pieces of software have additional or alternate copyrights,
+licenses, and/or restrictions:
+
+Program             Directory
+-------             ---------
+Autoconf            llvm/autoconf
+                    llvm/projects/ModuleMaker/autoconf
+                    llvm/projects/sample/autoconf
+CellSPU backend     llvm/lib/Target/CellSPU/README.txt
+Google Test         llvm/utils/unittest/googletest
+OpenBSD regex       llvm/lib/Support/{reg*, COPYRIGHT.regex}
@@ -115,7 +115,10 @@ typedef enum {
    LLVMNoImplicitFloatAttribute = 1<<23,
    LLVMNakedAttribute      = 1<<24,
    LLVMInlineHintAttribute = 1<<25,
-    LLVMStackAlignment = 7<<26
+    LLVMStackAlignment = 7<<26,
+    LLVMReturnsTwice = 1 << 29,
+    LLVMUWTable = 1 << 30,
+    LLVMNonLazyBind = 1 << 31
 } LLVMAttribute;

 typedef enum {
@@ -125,7 +128,7 @@ typedef enum {
  LLVMSwitch         = 3,
  LLVMIndirectBr     = 4,
  LLVMInvoke         = 5,
-  LLVMUnwind         = 6,
+  /* removed 6 due to API changes */
  LLVMUnreachable    = 7,

  /* Standard Binary Operators */
@@ -176,14 +179,26 @@ typedef enum {
  LLVMPHI            = 44,
  LLVMCall           = 45,
  LLVMSelect         = 46,
-  /* UserOp1 */
-  /* UserOp2 */
+  LLVMUserOp1        = 47,
+  LLVMUserOp2        = 48,
  LLVMVAArg          = 49,
  LLVMExtractElement = 50,
  LLVMInsertElement  = 51,
  LLVMShuffleVector  = 52,
  LLVMExtractValue   = 53,
-  LLVMInsertValue    = 54
+  LLVMInsertValue    = 54,
+
+  /* Atomic operators */
+  LLVMFence          = 55,
+  LLVMAtomicCmpXchg  = 56,
+  LLVMAtomicRMW      = 57,
+
+  /* Exception Handling Operators */
+  LLVMResume         = 58,
+  LLVMLandingPad     = 59,
+  LLVMUnwind         = 60
+
+
 } LLVMOpcode;

 typedef enum {
@@ -274,6 +289,11 @@ typedef enum {
  LLVMRealPredicateTrue   /**< Always true (always folded) */
 } LLVMRealPredicate;

+typedef enum {
+  LLVMLandingPadCatch,    /**< A catch clause   */
+  LLVMLandingPadFilter    /**< A filter clause  */
+} LLVMLandingPadClauseTy;
+
 void LLVMInitializeCore(LLVMPassRegistryRef R);


@@ -340,6 +360,7 @@ LLVMContextRef LLVMGetModuleContext(LLVMModuleRef M);

 /** See llvm::LLVMTypeKind::getTypeID. */
 LLVMTypeKind LLVMGetTypeKind(LLVMTypeRef Ty);
+LLVMBool LLVMTypeIsSized(LLVMTypeRef Ty);

 /** See llvm::LLVMType::getContext. */
 LLVMContextRef LLVMGetTypeContext(LLVMTypeRef Ty);
@@ -388,6 +409,7 @@ LLVMTypeRef LLVMStructTypeInContext(LLVMContextRef C, LLVMTypeRef *ElementTypes,
 LLVMTypeRef LLVMStructType(LLVMTypeRef *ElementTypes, unsigned ElementCount,
                           LLVMBool Packed);
 LLVMTypeRef LLVMStructCreateNamed(LLVMContextRef C, const char *Name);
+const char *LLVMGetStructName(LLVMTypeRef Ty);
 void LLVMStructSetBody(LLVMTypeRef StructTy, LLVMTypeRef *ElementTypes,
                       unsigned ElementCount, LLVMBool Packed);

@@ -427,8 +449,11 @@ LLVMTypeRef LLVMX86MMXType(void);
  macro(Argument)                           \
  macro(BasicBlock)                         \
  macro(InlineAsm)                          \
+  macro(MDNode)                             \
+  macro(MDString)                           \
  macro(User)                               \
    macro(Constant)                         \
+      macro(BlockAddress)                   \
      macro(ConstantAggregateZero)          \
      macro(ConstantArray)                  \
      macro(ConstantExpr)                   \
@@ -448,29 +473,32 @@ LLVMTypeRef LLVMX86MMXType(void);
        macro(IntrinsicInst)                \
          macro(DbgInfoIntrinsic)           \
            macro(DbgDeclareInst)           \
+          macro(EHExceptionInst)            \
          macro(EHSelectorInst)             \
          macro(MemIntrinsic)               \
            macro(MemCpyInst)               \
            macro(MemMoveInst)              \
            macro(MemSetInst)               \
      macro(CmpInst)                        \
-      macro(FCmpInst)                       \
-      macro(ICmpInst)                       \
+        macro(FCmpInst)                     \
+        macro(ICmpInst)                     \
      macro(ExtractElementInst)             \
      macro(GetElementPtrInst)              \
      macro(InsertElementInst)              \
      macro(InsertValueInst)                \
+      macro(LandingPadInst)                 \
      macro(PHINode)                        \
      macro(SelectInst)                     \
      macro(ShuffleVectorInst)              \
      macro(StoreInst)                      \
      macro(TerminatorInst)                 \
        macro(BranchInst)                   \
+        macro(IndirectBrInst)               \
        macro(InvokeInst)                   \
        macro(ReturnInst)                   \
        macro(SwitchInst)                   \
        macro(UnreachableInst)              \
-        macro(UnwindInst)                   \
+        macro(ResumeInst)                   \
    macro(UnaryInstruction)                 \
      macro(AllocaInst)                     \
      macro(CastInst)                       \
@@ -533,6 +561,11 @@ LLVMValueRef LLVMMDString(const char *Str, unsigned SLen);
 LLVMValueRef LLVMMDNodeInContext(LLVMContextRef C, LLVMValueRef *Vals,
                                 unsigned Count);
 LLVMValueRef LLVMMDNode(LLVMValueRef *Vals, unsigned Count);
+const char  *LLVMGetMDString(LLVMValueRef V, unsigned* Len);
+int LLVMGetMDNodeNumOperands(LLVMValueRef V);
+LLVMValueRef *LLVMGetMDNodeOperand(LLVMValueRef V, unsigned i);
+unsigned LLVMGetNamedMetadataNumOperands(LLVMModuleRef M, const char* name);
+void LLVMGetNamedMetadataOperands(LLVMModuleRef M, const char* name, LLVMValueRef *Dest);

 /* Operations on scalar constants */
 LLVMValueRef LLVMConstInt(LLVMTypeRef IntTy, unsigned long long N,
@@ -728,6 +761,7 @@ LLVMValueRef LLVMBasicBlockAsValue(LLVMBasicBlockRef BB);
 LLVMBool LLVMValueIsBasicBlock(LLVMValueRef Val);
 LLVMBasicBlockRef LLVMValueAsBasicBlock(LLVMValueRef Val);
 LLVMValueRef LLVMGetBasicBlockParent(LLVMBasicBlockRef BB);
+LLVMValueRef LLVMGetBasicBlockTerminator(LLVMBasicBlockRef BB);
 unsigned LLVMCountBasicBlocks(LLVMValueRef Fn);
 void LLVMGetBasicBlocks(LLVMValueRef Fn, LLVMBasicBlockRef *BasicBlocks);
 LLVMBasicBlockRef LLVMGetFirstBasicBlock(LLVMValueRef Fn);
@@ -747,16 +781,21 @@ LLVMBasicBlockRef LLVMAppendBasicBlock(LLVMValueRef Fn, const char *Name);
 LLVMBasicBlockRef LLVMInsertBasicBlock(LLVMBasicBlockRef InsertBeforeBB,
                                       const char *Name);
 void LLVMDeleteBasicBlock(LLVMBasicBlockRef BB);
+void LLVMRemoveBasicBlockFromParent(LLVMBasicBlockRef BB);

 void LLVMMoveBasicBlockBefore(LLVMBasicBlockRef BB, LLVMBasicBlockRef MovePos);
 void LLVMMoveBasicBlockAfter(LLVMBasicBlockRef BB, LLVMBasicBlockRef MovePos);

-/* Operations on instructions */
-LLVMBasicBlockRef LLVMGetInstructionParent(LLVMValueRef Inst);
 LLVMValueRef LLVMGetFirstInstruction(LLVMBasicBlockRef BB);
 LLVMValueRef LLVMGetLastInstruction(LLVMBasicBlockRef BB);
+
+/* Operations on instructions */
+LLVMBasicBlockRef LLVMGetInstructionParent(LLVMValueRef Inst);
 LLVMValueRef LLVMGetNextInstruction(LLVMValueRef Inst);
 LLVMValueRef LLVMGetPreviousInstruction(LLVMValueRef Inst);
+void LLVMInstructionEraseFromParent(LLVMValueRef Inst);
+LLVMOpcode   LLVMGetInstructionOpcode(LLVMValueRef Inst);
+LLVMIntPredicate LLVMGetICmpPredicate(LLVMValueRef Inst);

 /* Operations on call sites */
 void LLVMSetInstructionCallConv(LLVMValueRef Instr, unsigned CC);
@@ -771,6 +810,9 @@ void LLVMSetInstrParamAlignment(LLVMValueRef Instr, unsigned index,
 LLVMBool LLVMIsTailCall(LLVMValueRef CallInst);
 void LLVMSetTailCall(LLVMValueRef CallInst, LLVMBool IsTailCall);

+/* Operations on switch instructions (only) */
+LLVMBasicBlockRef LLVMGetSwitchDefaultDest(LLVMValueRef SwitchInstr);
+
 /* Operations on phi nodes */
 void LLVMAddIncoming(LLVMValueRef PhiNode, LLVMValueRef *IncomingValues,
                     LLVMBasicBlockRef *IncomingBlocks, unsigned Count);
@@ -818,7 +860,10 @@ LLVMValueRef LLVMBuildInvoke(LLVMBuilderRef, LLVMValueRef Fn,
                             LLVMValueRef *Args, unsigned NumArgs,
                             LLVMBasicBlockRef Then, LLVMBasicBlockRef Catch,
                             const char *Name);
-LLVMValueRef LLVMBuildUnwind(LLVMBuilderRef);
+LLVMValueRef LLVMBuildLandingPad(LLVMBuilderRef B, LLVMTypeRef Ty,
+                                 LLVMValueRef PersFn, unsigned NumClauses,
+                                 const char *Name);
+LLVMValueRef LLVMBuildResume(LLVMBuilderRef B, LLVMValueRef Exn);
 LLVMValueRef LLVMBuildUnreachable(LLVMBuilderRef);

 /* Add a case to the switch instruction */
@@ -828,6 +873,12 @@ void LLVMAddCase(LLVMValueRef Switch, LLVMValueRef OnVal,
 /* Add a destination to the indirectbr instruction */
 void LLVMAddDestination(LLVMValueRef IndirectBr, LLVMBasicBlockRef Dest);

+/* Add a catch or filter clause to the landingpad instruction */
+void LLVMAddClause(LLVMValueRef LandingPad, LLVMValueRef ClauseVal);
+
+/* Set the 'cleanup' flag in the landingpad instruction */
+void LLVMSetCleanup(LLVMValueRef LandingPad, LLVMBool Val);
+
 /* Arithmetic */
 LLVMValueRef LLVMBuildAdd(LLVMBuilderRef, LLVMValueRef LHS, LLVMValueRef RHS,
                          const char *Name);
@@ -1136,7 +1187,7 @@ namespace llvm {
    return reinterpret_cast<Type**>(Tys);
  }
  
-  inline LLVMTypeRef *wrap(const Type **Tys) {
+  inline LLVMTypeRef *wrap(Type **Tys) {
    return reinterpret_cast<LLVMTypeRef*>(const_cast<Type**>(Tys));
  }
  
@@ -66,7 +66,7 @@ typedef int (*LLVMOpInfoCallback)(void *DisInfo, uint64_t PC,
 */
 struct LLVMOpInfoSymbol1 {
  uint64_t Present;  /* 1 if this symbol is present */
-  char *Name;        /* symbol name if not NULL */
+  const char *Name;  /* symbol name if not NULL */
  uint64_t Value;    /* symbol value if name is NULL */
 };

@@ -93,11 +93,35 @@ struct LLVMOpInfo1 {
 * disassembler for things like adding a comment for a PC plus a constant
 * offset load instruction to use a symbol name instead of a load address value.
 * It is passed the block information is saved when the disassembler context is
- * created and a value of a symbol to look up.  If no symbol is found NULL is
- * returned.
+ * created and the ReferenceValue to look up as a symbol.  If no symbol is found
+ * for the ReferenceValue NULL is returned.  The ReferenceType of the
+ * instruction is passed indirectly as is the PC of the instruction in
+ * ReferencePC.  If the output reference can be determined its type is returned
+ * indirectly in ReferenceType along with ReferenceName if any, or that is set
+ * to NULL.
 */
 typedef const char *(*LLVMSymbolLookupCallback)(void *DisInfo,
-                                                uint64_t SymbolValue);
+                                                uint64_t ReferenceValue,
+						uint64_t *ReferenceType,
+						uint64_t ReferencePC,
+						const char **ReferenceName);
+/**
+ * The reference types on input and output.
+ */
+/* No input reference type or no output reference type. */
+#define LLVMDisassembler_ReferenceType_InOut_None 0
+
+/* The input reference is from a branch instruction. */
+#define LLVMDisassembler_ReferenceType_In_Branch 1
+/* The input reference is from a PC relative load instruction. */
+#define LLVMDisassembler_ReferenceType_In_PCrel_Load 2
+
+/* The output reference is to as symbol stub. */
+#define LLVMDisassembler_ReferenceType_Out_SymbolStub 1
+/* The output reference is to a symbol address in a literal pool. */
+#define LLVMDisassembler_ReferenceType_Out_LitPool_SymAddr 2
+/* The output reference is to a cstring address in a literal pool. */
+#define LLVMDisassembler_ReferenceType_Out_LitPool_CstrAddr 3

 #ifdef __cplusplus
 extern "C" {
@@ -59,14 +59,14 @@ namespace llvm {
      return reinterpret_cast<LLVMObjectFileRef>(const_cast<ObjectFile*>(OF));
    }

-    inline ObjectFile::section_iterator *unwrap(LLVMSectionIteratorRef SI) {
-      return reinterpret_cast<ObjectFile::section_iterator*>(SI);
+    inline section_iterator *unwrap(LLVMSectionIteratorRef SI) {
+      return reinterpret_cast<section_iterator*>(SI);
    }

    inline LLVMSectionIteratorRef
-    wrap(const ObjectFile::section_iterator *SI) {
+    wrap(const section_iterator *SI) {
      return reinterpret_cast<LLVMSectionIteratorRef>
-        (const_cast<ObjectFile::section_iterator*>(SI));
+        (const_cast<section_iterator*>(SI));
    }
  }
 }
@@ -29,6 +29,7 @@ extern "C" {
 enum LLVMByteOrdering { LLVMBigEndian, LLVMLittleEndian };

 typedef struct LLVMOpaqueTargetData *LLVMTargetDataRef;
+typedef struct LLVMOpaqueTargetLibraryInfotData *LLVMTargetLibraryInfoRef;
 typedef struct LLVMStructLayout *LLVMStructLayoutRef;

 /* Declare all of the target-initialization functions that are available. */
@@ -42,7 +43,7 @@ typedef struct LLVMStructLayout *LLVMStructLayoutRef;
 #undef LLVM_TARGET  /* Explicit undef to make SWIG happier */

 #define LLVM_TARGET(TargetName) \
-  void LLVMInitialize##TargetName##MCAsmInfo(void);
+  void LLVMInitialize##TargetName##TargetMC(void);
 #include "llvm/Config/Targets.def"
 #undef LLVM_TARGET  /* Explicit undef to make SWIG happier */
  
@@ -72,7 +73,7 @@ static inline LLVMBool LLVMInitializeNativeTarget(void) {
 #ifdef LLVM_NATIVE_TARGET
  LLVM_NATIVE_TARGETINFO();
  LLVM_NATIVE_TARGET();
-  LLVM_NATIVE_MCASMINFO();
+  LLVM_NATIVE_TARGETMC();
  return 0;
 #else
  return 1;
@@ -90,6 +91,11 @@ LLVMTargetDataRef LLVMCreateTargetData(const char *StringRep);
    See the method llvm::PassManagerBase::add. */
 void LLVMAddTargetData(LLVMTargetDataRef, LLVMPassManagerRef);

+/** Adds target library information to a pass manager. This does not take
+    ownership of the target library info.
+    See the method llvm::PassManagerBase::add. */
+void LLVMAddTargetLibraryInfo(LLVMTargetLibraryInfoRef, LLVMPassManagerRef);
+
 /** Converts target data to a target layout string. The string must be disposed
    with LLVMDisposeMessage.
    See the constructor llvm::TargetData::TargetData. */
@@ -157,6 +163,7 @@ void LLVMDisposeTargetData(LLVMTargetDataRef);

 namespace llvm {
  class TargetData;
+  class TargetLibraryInfo;

  inline TargetData *unwrap(LLVMTargetDataRef P) {
    return reinterpret_cast<TargetData*>(P);
@@ -165,6 +172,15 @@ namespace llvm {
  inline LLVMTargetDataRef wrap(const TargetData *P) {
    return reinterpret_cast<LLVMTargetDataRef>(const_cast<TargetData*>(P));
  }
+
+  inline TargetLibraryInfo *unwrap(LLVMTargetLibraryInfoRef P) {
+    return reinterpret_cast<TargetLibraryInfo*>(P);
+  }
+
+  inline LLVMTargetLibraryInfoRef wrap(const TargetLibraryInfo *P) {
+    TargetLibraryInfo *X = const_cast<TargetLibraryInfo*>(P);
+    return reinterpret_cast<LLVMTargetLibraryInfoRef>(X);
+  }
 }

 #endif /* defined(__cplusplus) */
@@ -36,6 +36,9 @@ void LLVMAddFunctionAttrsPass(LLVMPassManagerRef PM);
 /** See llvm::createFunctionInliningPass function. */
 void LLVMAddFunctionInliningPass(LLVMPassManagerRef PM);

+/** See llvm::createAlwaysInlinerPass function. */
+void LLVMAddAlwaysInlinerPass(LLVMPassManagerRef PM);
+
 /** See llvm::createGlobalDCEPass function. */
 void LLVMAddGlobalDCEPass(LLVMPassManagerRef PM);

@@ -45,9 +48,6 @@ void LLVMAddGlobalOptimizerPass(LLVMPassManagerRef PM);
 /** See llvm::createIPConstantPropagationPass function. */
 void LLVMAddIPConstantPropagationPass(LLVMPassManagerRef PM);

-/** See llvm::createLowerSetJmpPass function. */
-void LLVMAddLowerSetJmpPass(LLVMPassManagerRef PM);
-
 /** See llvm::createPruneEHPass function. */
 void LLVMAddPruneEHPass(LLVMPassManagerRef PM);

@@ -57,9 +57,6 @@ void LLVMAddIPSCCPPass(LLVMPassManagerRef PM);
 /** See llvm::createInternalizePass function. */
 void LLVMAddInternalizePass(LLVMPassManagerRef, unsigned AllButMain);

-// FIXME: Remove in LLVM 3.0.
-void LLVMAddRaiseAllocationsPass(LLVMPassManagerRef PM);
-
 /** See llvm::createStripDeadPrototypesPass function. */
 void LLVMAddStripDeadPrototypesPass(LLVMPassManagerRef PM);

@@ -0,0 +1,90 @@
+/*===-- llvm-c/Transform/PassManagerBuilder.h - PMB C Interface ---*- C -*-===*\
+|*                                                                            *|
+|*                     The LLVM Compiler Infrastructure                       *|
+|*                                                                            *|
+|* This file is distributed under the University of Illinois Open Source      *|
+|* License. See LICENSE.TXT for details.                                      *|
+|*                                                                            *|
+|*===----------------------------------------------------------------------===*|
+|*                                                                            *|
+|* This header declares the C interface to the PassManagerBuilder class.      *|
+|*                                                                            *|
+\*===----------------------------------------------------------------------===*/
+
+#ifndef LLVM_C_PASSMANAGERBUILDER
+#define LLVM_C_PASSMANAGERBUILDER
+
+#include "llvm-c/Core.h"
+
+typedef struct LLVMOpaquePassManagerBuilder *LLVMPassManagerBuilderRef;
+
+#ifdef __cplusplus
+#include "llvm/Transforms/IPO/PassManagerBuilder.h"
+extern "C" {
+#endif
+
+/** See llvm::PassManagerBuilder. */
+LLVMPassManagerBuilderRef LLVMPassManagerBuilderCreate(void);
+void LLVMPassManagerBuilderDispose(LLVMPassManagerBuilderRef PMB);
+
+/** See llvm::PassManagerBuilder::OptLevel. */
+void
+LLVMPassManagerBuilderSetOptLevel(LLVMPassManagerBuilderRef PMB,
+                                  unsigned OptLevel);
+
+/** See llvm::PassManagerBuilder::SizeLevel. */
+void
+LLVMPassManagerBuilderSetSizeLevel(LLVMPassManagerBuilderRef PMB,
+                                   unsigned SizeLevel);
+
+/** See llvm::PassManagerBuilder::DisableUnitAtATime. */
+void
+LLVMPassManagerBuilderSetDisableUnitAtATime(LLVMPassManagerBuilderRef PMB,
+                                            LLVMBool Value);
+
+/** See llvm::PassManagerBuilder::DisableUnrollLoops. */
+void
+LLVMPassManagerBuilderSetDisableUnrollLoops(LLVMPassManagerBuilderRef PMB,
+                                            LLVMBool Value);
+
+/** See llvm::PassManagerBuilder::DisableSimplifyLibCalls */
+void
+LLVMPassManagerBuilderSetDisableSimplifyLibCalls(LLVMPassManagerBuilderRef PMB,
+                                                 LLVMBool Value);
+
+/** See llvm::PassManagerBuilder::Inliner. */
+void
+LLVMPassManagerBuilderUseInlinerWithThreshold(LLVMPassManagerBuilderRef PMB,
+                                              unsigned Threshold);
+
+/** See llvm::PassManagerBuilder::populateFunctionPassManager. */
+void
+LLVMPassManagerBuilderPopulateFunctionPassManager(LLVMPassManagerBuilderRef PMB,
+                                                  LLVMPassManagerRef PM);
+
+/** See llvm::PassManagerBuilder::populateModulePassManager. */
+void
+LLVMPassManagerBuilderPopulateModulePassManager(LLVMPassManagerBuilderRef PMB,
+                                                LLVMPassManagerRef PM);
+
+/** See llvm::PassManagerBuilder::populateLTOPassManager. */
+void LLVMPassManagerBuilderPopulateLTOPassManager(LLVMPassManagerBuilderRef PMB,
+                                                  LLVMPassManagerRef PM,
+                                                  bool Internalize,
+                                                  bool RunInliner);
+
+#ifdef __cplusplus
+}
+
+namespace llvm {
+  inline PassManagerBuilder *unwrap(LLVMPassManagerBuilderRef P) {
+    return reinterpret_cast<PassManagerBuilder*>(P);
+  }
+
+  inline LLVMPassManagerBuilderRef wrap(PassManagerBuilder *P) {
+    return reinterpret_cast<LLVMPassManagerBuilderRef>(P);
+  }
+}
+#endif
+
+#endif
@@ -107,6 +107,9 @@ void LLVMAddCorrelatedValuePropagationPass(LLVMPassManagerRef PM);
 /** See llvm::createEarlyCSEPass function */
 void LLVMAddEarlyCSEPass(LLVMPassManagerRef PM);

+/** See llvm::createLowerExpectIntrinsicPass function */
+void LLVMAddLowerExpectIntrinsicPass(LLVMPassManagerRef PM);
+
 /** See llvm::createTypeBasedAliasAnalysisPass function */
 void LLVMAddTypeBasedAliasAnalysisPass(LLVMPassManagerRef PM);

@@ -15,6 +15,7 @@
 #ifndef LLVM_APINT_H
 #define LLVM_APINT_H

+#include "llvm/ADT/ArrayRef.h"
 #include "llvm/Support/MathExtras.h"
 #include <cassert>
 #include <climits>
@@ -160,7 +161,7 @@ class APInt {
  /// not assume that the string is well-formed and (2) grows the
  /// result to hold the input.
  ///
-  /// @param radix 2, 8, 10, or 16
+  /// @param radix 2, 8, 10, 16, or 36
  /// @brief Convert a char array into an APInt
  void fromString(unsigned numBits, StringRef str, uint8_t radix);

@@ -176,6 +177,9 @@ class APInt {
  /// out-of-line slow case for inline constructor
  void initSlowCase(unsigned numBits, uint64_t val, bool isSigned);

+  /// shared code between two array constructors
+  void initFromArray(ArrayRef<uint64_t> array);
+
  /// out-of-line slow case for inline copy constructor
  void initSlowCase(const APInt& that);

@@ -230,19 +234,26 @@ public:
    clearUnusedBits();
  }

-  /// Note that numWords can be smaller or larger than the corresponding bit
-  /// width but any extraneous bits will be dropped.
+  /// Note that bigVal.size() can be smaller or larger than the corresponding
+  /// bit width but any extraneous bits will be dropped.
  /// @param numBits the bit width of the constructed APInt
-  /// @param numWords the number of words in bigVal
  /// @param bigVal a sequence of words to form the initial value of the APInt
  /// @brief Construct an APInt of numBits width, initialized as bigVal[].
+  APInt(unsigned numBits, ArrayRef<uint64_t> bigVal);
+  /// Equivalent to APInt(numBits, ArrayRef<uint64_t>(bigVal, numWords)), but
+  /// deprecated because this constructor is prone to ambiguity with the
+  /// APInt(unsigned, uint64_t, bool) constructor.
+  ///
+  /// If this overload is ever deleted, care should be taken to prevent calls
+  /// from being incorrectly captured by the APInt(unsigned, uint64_t, bool)
+  /// constructor.
  APInt(unsigned numBits, unsigned numWords, const uint64_t bigVal[]);

  /// This constructor interprets the string \arg str in the given radix. The
  /// interpretation stops when the first character that is not suitable for the
  /// radix is encountered, or the end of the string. Acceptable radix values
-  /// are 2, 8, 10 and 16. It is an error for the value implied by the string to
-  /// require more bits than numBits.
+  /// are 2, 8, 10, 16, and 36. It is an error for the value implied by the 
+  /// string to require more bits than numBits.
  ///
  /// @param numBits the bit width of the constructed APInt
  /// @param str the string to be interpreted
@@ -342,7 +353,8 @@ public:

    if (isSingleWord())
      return isUIntN(N, VAL);
-    return APInt(N, getNumWords(), pVal).zext(getBitWidth()) == (*this);
+    return APInt(N, makeArrayRef(pVal, getNumWords())).zext(getBitWidth())
+      == (*this);
  }

  /// @brief Check if this APInt has an N-bits signed integer value.
@@ -1245,13 +1257,13 @@ public:
                bool formatAsCLiteral = false) const;

  /// Considers the APInt to be unsigned and converts it into a string in the
-  /// radix given. The radix can be 2, 8, 10 or 16.
+  /// radix given. The radix can be 2, 8, 10 16, or 36.
  void toStringUnsigned(SmallVectorImpl<char> &Str, unsigned Radix = 10) const {
    toString(Str, Radix, false, false);
  }

  /// Considers the APInt to be signed and converts it into a string in the
-  /// radix given. The radix can be 2, 8, 10 or 16.
+  /// radix given. The radix can be 2, 8, 10, 16, or 36.
  void toStringSigned(SmallVectorImpl<char> &Str, unsigned Radix = 10) const {
    toString(Str, Radix, true, false);
  }
@@ -147,7 +147,53 @@ namespace llvm {
    
    /// @}
  };
-  
+
+  /// @name ArrayRef Convenience constructors
+  /// @{
+
+  /// Construct an ArrayRef from a single element.
+  template<typename T>
+  ArrayRef<T> makeArrayRef(const T &OneElt) {
+    return OneElt;
+  }
+
+  /// Construct an ArrayRef from a pointer and length.
+  template<typename T>
+  ArrayRef<T> makeArrayRef(const T *data, size_t length) {
+    return ArrayRef<T>(data, length);
+  }
+
+  /// Construct an ArrayRef from a range.
+  template<typename T>
+  ArrayRef<T> makeArrayRef(const T *begin, const T *end) {
+    return ArrayRef<T>(begin, end);
+  }
+
+  /// Construct an ArrayRef from a SmallVector.
+  template <typename T>
+  ArrayRef<T> makeArrayRef(const SmallVectorImpl<T> &Vec) {
+    return Vec;
+  }
+
+  /// Construct an ArrayRef from a SmallVector.
+  template <typename T, unsigned N>
+  ArrayRef<T> makeArrayRef(const SmallVector<T, N> &Vec) {
+    return Vec;
+  }
+
+  /// Construct an ArrayRef from a std::vector.
+  template<typename T>
+  ArrayRef<T> makeArrayRef(const std::vector<T> &Vec) {
+    return Vec;
+  }
+
+  /// Construct an ArrayRef from a C array.
+  template<typename T, size_t N>
+  ArrayRef<T> makeArrayRef(const T (&Arr)[N]) {
+    return ArrayRef<T>(Arr);
+  }
+
+  /// @}
  /// @name ArrayRef Comparison Operators
  /// @{

@@ -540,6 +540,12 @@ private:
      ++Ptr;
  }
 };
+  
+template<typename KeyT, typename ValueT, typename KeyInfoT, typename ValueInfoT>
+static inline size_t
+capacity_in_bytes(const DenseMap<KeyT, ValueT, KeyInfoT, ValueInfoT> &X) {
+  return X.getMemorySize();
+}

 } // end namespace llvm

@@ -51,7 +51,7 @@ struct DenseMapInfo<T*> {
 template<> struct DenseMapInfo<char> {
  static inline char getEmptyKey() { return ~0; }
  static inline char getTombstoneKey() { return ~0 - 1; }
-  static unsigned getHashValue(const char& Val) { return Val * 37; }
+  static unsigned getHashValue(const char& Val) { return Val * 37U; }
  static bool isEqual(const char &LHS, const char &RHS) {
    return LHS == RHS;
  }
@@ -61,7 +61,7 @@ template<> struct DenseMapInfo<char> {
 template<> struct DenseMapInfo<unsigned> {
  static inline unsigned getEmptyKey() { return ~0; }
  static inline unsigned getTombstoneKey() { return ~0U - 1; }
-  static unsigned getHashValue(const unsigned& Val) { return Val * 37; }
+  static unsigned getHashValue(const unsigned& Val) { return Val * 37U; }
  static bool isEqual(const unsigned& LHS, const unsigned& RHS) {
    return LHS == RHS;
  }
@@ -96,7 +96,7 @@ template<> struct DenseMapInfo<unsigned long long> {
 template<> struct DenseMapInfo<int> {
  static inline int getEmptyKey() { return 0x7fffffff; }
  static inline int getTombstoneKey() { return -0x7fffffff - 1; }
-  static unsigned getHashValue(const int& Val) { return (unsigned)(Val * 37); }
+  static unsigned getHashValue(const int& Val) { return (unsigned)(Val * 37U); }
  static bool isEqual(const int& LHS, const int& RHS) {
    return LHS == RHS;
  }
@@ -109,7 +109,7 @@ template<> struct DenseMapInfo<long> {
  }
  static inline long getTombstoneKey() { return getEmptyKey() - 1L; }
  static unsigned getHashValue(const long& Val) {
-    return (unsigned)(Val * 37L);
+    return (unsigned)(Val * 37UL);
  }
  static bool isEqual(const long& LHS, const long& RHS) {
    return LHS == RHS;
@@ -121,7 +121,7 @@ template<> struct DenseMapInfo<long long> {
  static inline long long getEmptyKey() { return 0x7fffffffffffffffLL; }
  static inline long long getTombstoneKey() { return -0x7fffffffffffffffLL-1; }
  static unsigned getHashValue(const long long& Val) {
-    return (unsigned)(Val * 37LL);
+    return (unsigned)(Val * 37ULL);
  }
  static bool isEqual(const long long& LHS,
                      const long long& RHS) {
@@ -142,7 +142,7 @@ struct DenseMapInfo<std::pair<T, U> > {
  }
  static inline Pair getTombstoneKey() {
    return std::make_pair(FirstInfo::getTombstoneKey(),
-                            SecondInfo::getEmptyKey());
+                          SecondInfo::getTombstoneKey());
  }
  static unsigned getHashValue(const Pair& PairVal) {
    uint64_t key = (uint64_t)FirstInfo::getHashValue(PairVal.first) << 32
@@ -158,7 +158,7 @@ struct DenseMapInfo<std::pair<T, U> > {
    return (unsigned)key;
  }
  static bool isEqual(const Pair &LHS, const Pair &RHS) {
-    return FirstInfo::isEqual(LHS.first, RHS.first) && 
+    return FirstInfo::isEqual(LHS.first, RHS.first) &&
           SecondInfo::isEqual(LHS.second, RHS.second);
  }
 };
@@ -28,7 +28,7 @@ class DenseSet {
  MapTy TheMap;
 public:
  DenseSet(const DenseSet &Other) : TheMap(Other.TheMap) {}
-  explicit DenseSet(unsigned NumInitBuckets = 64) : TheMap(NumInitBuckets) {}
+  explicit DenseSet(unsigned NumInitBuckets = 0) : TheMap(NumInitBuckets) {}

  bool empty() const { return TheMap.empty(); }
  unsigned size() const { return TheMap.size(); }
@@ -117,6 +117,10 @@ public:
      return ImmutableMap(Canonicalize ? F.getCanonicalTree(T): T);
    }

+    typename TreeTy::Factory *getTreeFactory() const {
+      return const_cast<typename TreeTy::Factory *>(&F);
+    }
+
  private:
    Factory(const Factory& RHS); // DO NOT IMPLEMENT
    void operator=(const Factory& RHS); // DO NOT IMPLEMENT
@@ -256,6 +260,159 @@ public:
  }
 };

+// NOTE: This will possibly become the new implementation of ImmutableMap some day.
+template <typename KeyT, typename ValT,
+typename ValInfo = ImutKeyValueInfo<KeyT,ValT> >
+class ImmutableMapRef {
+public:
+  typedef typename ValInfo::value_type      value_type;
+  typedef typename ValInfo::value_type_ref  value_type_ref;
+  typedef typename ValInfo::key_type        key_type;
+  typedef typename ValInfo::key_type_ref    key_type_ref;
+  typedef typename ValInfo::data_type       data_type;
+  typedef typename ValInfo::data_type_ref   data_type_ref;
+  typedef ImutAVLTree<ValInfo>              TreeTy;
+  typedef typename TreeTy::Factory          FactoryTy;
+  
+protected:
+  TreeTy *Root;
+  FactoryTy *Factory;
+  
+public:
+  /// Constructs a map from a pointer to a tree root.  In general one
+  /// should use a Factory object to create maps instead of directly
+  /// invoking the constructor, but there are cases where make this
+  /// constructor public is useful.
+  explicit ImmutableMapRef(const TreeTy* R, FactoryTy *F) 
+    : Root(const_cast<TreeTy*>(R)),
+      Factory(F) {
+    if (Root) { Root->retain(); }
+  }
+  
+  ImmutableMapRef(const ImmutableMapRef &X)
+    : Root(X.Root),
+      Factory(X.Factory) {
+    if (Root) { Root->retain(); }
+  }
+
+  ImmutableMapRef &operator=(const ImmutableMapRef &X) {
+    if (Root != X.Root) {
+      if (X.Root)
+        X.Root->retain();
+      
+      if (Root)
+        Root->release();
+      
+      Root = X.Root;
+      Factory = X.Factory;
+    }
+    return *this;
+  }
+
+  ~ImmutableMapRef() {
+    if (Root)
+      Root->release();
+  }
+  
+  static inline ImmutableMapRef getEmptyMap(FactoryTy *F) {
+    return ImmutableMapRef(0, F);
+  }
+
+  ImmutableMapRef add(key_type_ref K, data_type_ref D) {
+    TreeTy *NewT = Factory->add(Root, std::pair<key_type, data_type>(K, D));
+    return ImmutableMapRef(NewT, Factory);
+  }
+
+  ImmutableMapRef remove(key_type_ref K) {
+    TreeTy *NewT = Factory->remove(Root, K);
+    return ImmutableMapRef(NewT, Factory);
+  }
+  
+  bool contains(key_type_ref K) const {
+    return Root ? Root->contains(K) : false;
+  }
+  
+  ImmutableMap<KeyT, ValT> asImmutableMap() const {
+    return ImmutableMap<KeyT, ValT>(Factory->getCanonicalTree(Root));
+  }
+  
+  bool operator==(const ImmutableMapRef &RHS) const {
+    return Root && RHS.Root ? Root->isEqual(*RHS.Root) : Root == RHS.Root;
+  }
+  
+  bool operator!=(const ImmutableMapRef &RHS) const {
+    return Root && RHS.Root ? Root->isNotEqual(*RHS.Root) : Root != RHS.Root;
+  }
+    
+  bool isEmpty() const { return !Root; }
+    
+  //===--------------------------------------------------===//
+  // For testing.
+  //===--------------------------------------------------===//
+  
+  void verify() const { if (Root) Root->verify(); }
+  
+  //===--------------------------------------------------===//
+  // Iterators.
+  //===--------------------------------------------------===//
+  
+  class iterator {
+    typename TreeTy::iterator itr;
+    
+    iterator() {}
+    iterator(TreeTy* t) : itr(t) {}
+    friend class ImmutableMapRef;
+    
+  public:
+    value_type_ref operator*() const { return itr->getValue(); }
+    value_type*    operator->() const { return &itr->getValue(); }
+    
+    key_type_ref getKey() const { return itr->getValue().first; }
+    data_type_ref getData() const { return itr->getValue().second; }
+    
+    
+    iterator& operator++() { ++itr; return *this; }
+    iterator  operator++(int) { iterator tmp(*this); ++itr; return tmp; }
+    iterator& operator--() { --itr; return *this; }
+    iterator  operator--(int) { iterator tmp(*this); --itr; return tmp; }
+    bool operator==(const iterator& RHS) const { return RHS.itr == itr; }
+    bool operator!=(const iterator& RHS) const { return RHS.itr != itr; }
+  };
+  
+  iterator begin() const { return iterator(Root); }
+  iterator end() const { return iterator(); }
+  
+  data_type* lookup(key_type_ref K) const {
+    if (Root) {
+      TreeTy* T = Root->find(K);
+      if (T) return &T->getValue().second;
+    }
+    
+    return 0;
+  }
+  
+  /// getMaxElement - Returns the <key,value> pair in the ImmutableMap for
+  ///  which key is the highest in the ordering of keys in the map.  This
+  ///  method returns NULL if the map is empty.
+  value_type* getMaxElement() const {
+    return Root ? &(Root->getMaxElement()->getValue()) : 0;
+  }
+  
+  //===--------------------------------------------------===//
+  // Utility methods.
+  //===--------------------------------------------------===//
+  
+  unsigned getHeight() const { return Root ? Root->getHeight() : 0; }
+  
+  static inline void Profile(FoldingSetNodeID& ID, const ImmutableMapRef &M) {
+    ID.AddPointer(M.Root);
+  }
+  
+  inline void Profile(FoldingSetNodeID& ID) const {
+    return Profile(ID, *this);
+  }
+};
+  
 } // end namespace llvm

 #endif
@@ -997,6 +997,10 @@ public:

    BumpPtrAllocator& getAllocator() { return F.getAllocator(); }

+    typename TreeTy::Factory *getTreeFactory() const {
+      return const_cast<typename TreeTy::Factory *>(&F);
+    }
+    
  private:
    Factory(const Factory& RHS); // DO NOT IMPLEMENT
    void operator=(const Factory& RHS); // DO NOT IMPLEMENT
@@ -1021,6 +1025,10 @@ public:
    if (Root) { Root->retain(); }
    return Root;
  }
+  
+  TreeTy *getRootWithoutRetain() const {
+    return Root;
+  }

  /// isEmpty - Return true if the set contains no elements.
  bool isEmpty() const { return !Root; }
@@ -1078,6 +1086,132 @@ public:

  void validateTree() const { if (Root) Root->validateTree(); }
 };
+  
+// NOTE: This may some day replace the current ImmutableSet.
+template <typename ValT, typename ValInfo = ImutContainerInfo<ValT> >
+class ImmutableSetRef {
+public:
+  typedef typename ValInfo::value_type      value_type;
+  typedef typename ValInfo::value_type_ref  value_type_ref;
+  typedef ImutAVLTree<ValInfo> TreeTy;
+  typedef typename TreeTy::Factory          FactoryTy;
+  
+private:
+  TreeTy *Root;
+  FactoryTy *Factory;
+  
+public:
+  /// Constructs a set from a pointer to a tree root.  In general one
+  /// should use a Factory object to create sets instead of directly
+  /// invoking the constructor, but there are cases where make this
+  /// constructor public is useful.
+  explicit ImmutableSetRef(TreeTy* R, FactoryTy *F)
+    : Root(R),
+      Factory(F) {
+    if (Root) { Root->retain(); }
+  }
+  ImmutableSetRef(const ImmutableSetRef &X)
+    : Root(X.Root),
+      Factory(X.Factory) {
+    if (Root) { Root->retain(); }
+  }
+  ImmutableSetRef &operator=(const ImmutableSetRef &X) {
+    if (Root != X.Root) {
+      if (X.Root) { X.Root->retain(); }
+      if (Root) { Root->release(); }
+      Root = X.Root;
+      Factory = X.Factory;
+    }
+    return *this;
+  }
+  ~ImmutableSetRef() {
+    if (Root) { Root->release(); }
+  }
+  
+  static inline ImmutableSetRef getEmptySet(FactoryTy *F) {
+    return ImmutableSetRef(0, F);
+  }
+  
+  ImmutableSetRef add(value_type_ref V) {
+    return ImmutableSetRef(Factory->add(Root, V), Factory);
+  }
+  
+  ImmutableSetRef remove(value_type_ref V) {
+    return ImmutableSetRef(Factory->remove(Root, V), Factory);
+  }
+    
+  /// Returns true if the set contains the specified value.
+  bool contains(value_type_ref V) const {
+    return Root ? Root->contains(V) : false;
+  }
+  
+  ImmutableSet<ValT> asImmutableSet(bool canonicalize = true) const {
+    return ImmutableSet<ValT>(canonicalize ?
+                              Factory->getCanonicalTree(Root) : Root);
+  }
+  
+  TreeTy *getRootWithoutRetain() const {
+    return Root;
+  }
+  
+  bool operator==(const ImmutableSetRef &RHS) const {
+    return Root && RHS.Root ? Root->isEqual(*RHS.Root) : Root == RHS.Root;
+  }
+  
+  bool operator!=(const ImmutableSetRef &RHS) const {
+    return Root && RHS.Root ? Root->isNotEqual(*RHS.Root) : Root != RHS.Root;
+  }
+
+  /// isEmpty - Return true if the set contains no elements.
+  bool isEmpty() const { return !Root; }
+  
+  /// isSingleton - Return true if the set contains exactly one element.
+  ///   This method runs in constant time.
+  bool isSingleton() const { return getHeight() == 1; }
+
+  //===--------------------------------------------------===//
+  // Iterators.
+  //===--------------------------------------------------===//
+  
+  class iterator {
+    typename TreeTy::iterator itr;
+    iterator(TreeTy* t) : itr(t) {}
+    friend class ImmutableSetRef<ValT,ValInfo>;
+  public:
+    iterator() {}
+    inline value_type_ref operator*() const { return itr->getValue(); }
+    inline iterator& operator++() { ++itr; return *this; }
+    inline iterator  operator++(int) { iterator tmp(*this); ++itr; return tmp; }
+    inline iterator& operator--() { --itr; return *this; }
+    inline iterator  operator--(int) { iterator tmp(*this); --itr; return tmp; }
+    inline bool operator==(const iterator& RHS) const { return RHS.itr == itr; }
+    inline bool operator!=(const iterator& RHS) const { return RHS.itr != itr; }
+    inline value_type *operator->() const { return &(operator*()); }
+  };
+  
+  iterator begin() const { return iterator(Root); }
+  iterator end() const { return iterator(); }
+  
+  //===--------------------------------------------------===//
+  // Utility methods.
+  //===--------------------------------------------------===//
+  
+  unsigned getHeight() const { return Root ? Root->getHeight() : 0; }
+  
+  static inline void Profile(FoldingSetNodeID& ID, const ImmutableSetRef& S) {
+    ID.AddPointer(S.Root);
+  }
+  
+  inline void Profile(FoldingSetNodeID& ID) const {
+    return Profile(ID,*this);
+  }
+  
+  //===--------------------------------------------------===//
+  // For testing.
+  //===--------------------------------------------------===//
+  
+  void validateTree() const { if (Root) Root->validateTree(); }
+};

 } // end namespace llvm

@@ -1335,6 +1335,9 @@ public:
  /// valid - Return true if the current position is valid, false for end().
  bool valid() const { return path.valid(); }

+  /// atBegin - Return true if the current position is the first map entry.
+  bool atBegin() const { return path.atBegin(); }
+
  /// start - Return the beginning of the current interval.
  const KeyT &start() const { return unsafeStart(); }

@@ -108,7 +108,11 @@ namespace llvm {
    
    /// isNull - Return true if the pointer held in the union is null,
    /// regardless of which type it is.
-    bool isNull() const { return Val.getPointer() == 0; }
+    bool isNull() const {
+      // Convert from the void* to one of the pointer types, to make sure that
+      // we recursively strip off low bits if we have a nested PointerUnion.
+      return !PointerLikeTypeTraits<PT1>::getFromVoidPointer(Val.getPointer());
+    }
    operator bool() const { return !isNull(); }

    /// is<T>() return true if the Union currently holds the type matching T.
@@ -29,6 +29,14 @@ public:
  SetType Visited;
 };

+/// DFSetTraits - Allow the SetType used to record depth-first search results to
+/// optionally record node postorder.
+template<class SetType>
+struct DFSetTraits {
+  static void finishPostorder(
+    typename SetType::iterator::value_type, SetType &) {}
+};
+
 template<class SetType>
 class po_iterator_storage<SetType, true> {
 public:
@@ -109,6 +117,8 @@ public:
  inline NodeType *operator->() const { return operator*(); }

  inline _Self& operator++() {   // Preincrement
+    DFSetTraits<SetType>::finishPostorder(VisitStack.back().first,
+                                          this->Visited);
    VisitStack.pop_back();
    if (!VisitStack.empty())
      traverseChild();
@@ -1,4 +1,4 @@
-//===-- Support/SCCIterator.h - Strongly Connected Comp. Iter. --*- C++ -*-===//
+//===---- ADT/SCCIterator.h - Strongly Connected Comp. Iter. ----*- C++ -*-===//
 //
 //                     The LLVM Compiler Infrastructure
 //
@@ -87,7 +87,7 @@ class scc_iterator
        DFSVisitOne(childN);
        continue;
      }
-      
+
      unsigned childNum = nodeVisitNumbers[childN];
      if (MinVisitNumStack.back() > childNum)
        MinVisitNumStack.back() = childNum;
@@ -114,7 +114,7 @@ class scc_iterator

      if (minVisitNum != nodeVisitNumbers[visitingN])
        continue;
-      
+
      // A full SCC is on the SCCNodeStack!  It includes all nodes below
      // visitingN on the stack.  Copy those nodes to CurrentSCC,
      // reset their minVisit values, and return (this suspends
@@ -139,7 +139,7 @@ public:

  // Provide static "constructors"...
  static inline _Self begin(const GraphT &G){return _Self(GT::getEntryNode(G));}
-  static inline _Self end  (const GraphT &G) { return _Self(); }
+  static inline _Self end  (const GraphT &) { return _Self(); }

  // Direct loop termination test: I.isAtEnd() is more efficient than I == end()
  inline bool isAtEnd() const {
@@ -183,7 +183,7 @@ public:
        return true;
    return false;
  }
-                           
+
  /// ReplaceNode - This informs the scc_iterator that the specified Old node
  /// has been deleted, and New is to be used in its place.
  void ReplaceNode(NodeType *Old, NodeType *New) {
@@ -186,25 +186,21 @@ inline ItTy prior(ItTy it)
 //   // do stuff
 // else
 //   // do other stuff
+template <typename T1, typename T2>
+struct tier {
+  typedef T1 &first_type;
+  typedef T2 &second_type;

-namespace
-{
-  template <typename T1, typename T2>
-  struct tier {
-    typedef T1 &first_type;
-    typedef T2 &second_type;
+  first_type first;
+  second_type second;

-    first_type first;
-    second_type second;
-
-    tier(first_type f, second_type s) : first(f), second(s) { }
-    tier& operator=(const std::pair<T1, T2>& p) {
-      first = p.first;
-      second = p.second;
-      return *this;
-    }
-  };
-}
+  tier(first_type f, second_type s) : first(f), second(s) { }
+  tier& operator=(const std::pair<T1, T2>& p) {
+    first = p.first;
+    second = p.second;
+    return *this;
+  }
+};

 template <typename T1, typename T2>
 inline tier<T1, T2> tie(T1& f, T2& s) {
@@ -78,21 +78,21 @@ protected:
    return BeginX == static_cast<const void*>(&FirstEl);
  }

-  /// size_in_bytes - This returns size()*sizeof(T).
-  size_t size_in_bytes() const {
-    return size_t((char*)EndX - (char*)BeginX);
-  }
-
-  /// capacity_in_bytes - This returns capacity()*sizeof(T).
-  size_t capacity_in_bytes() const {
-    return size_t((char*)CapacityX - (char*)BeginX);
-  }
-
  /// grow_pod - This is an implementation of the grow() method which only works
  /// on POD-like data types and is out of line to reduce code duplication.
  void grow_pod(size_t MinSizeInBytes, size_t TSize);

 public:
+  /// size_in_bytes - This returns size()*sizeof(T).
+  size_t size_in_bytes() const {
+    return size_t((char*)EndX - (char*)BeginX);
+  }
+  
+  /// capacity_in_bytes - This returns capacity()*sizeof(T).
+  size_t capacity_in_bytes() const {
+    return size_t((char*)CapacityX - (char*)BeginX);
+  }
+
  bool empty() const { return BeginX == EndX; }
 };

@@ -738,6 +738,11 @@ public:

 };

+template<typename T, unsigned N>
+static inline size_t capacity_in_bytes(const SmallVector<T, N> &X) {
+  return X.capacity_in_bytes();
+}
+
 } // End llvm namespace

 namespace std {
@@ -54,7 +54,7 @@ public:
    Value = Val;
    return init();
  }
-  
+
  const Statistic &operator++() {
    // FIXME: This function and all those that follow carefully use an
    // atomic operation to update the value safely in the presence of
@@ -63,41 +63,43 @@ public:
    sys::AtomicIncrement(&Value);
    return init();
  }
-  
+
  unsigned operator++(int) {
    init();
    unsigned OldValue = Value;
    sys::AtomicIncrement(&Value);
    return OldValue;
  }
-  
+
  const Statistic &operator--() {
    sys::AtomicDecrement(&Value);
    return init();
  }
-  
+
  unsigned operator--(int) {
    init();
    unsigned OldValue = Value;
    sys::AtomicDecrement(&Value);
    return OldValue;
  }
-  
+
  const Statistic &operator+=(const unsigned &V) {
+    if (!V) return *this;
    sys::AtomicAdd(&Value, V);
    return init();
  }
-  
+
  const Statistic &operator-=(const unsigned &V) {
+    if (!V) return *this;
    sys::AtomicAdd(&Value, -V);
    return init();
  }
-  
+
  const Statistic &operator*=(const unsigned &V) {
    sys::AtomicMul(&Value, V);
    return init();
  }
-  
+
  const Statistic &operator/=(const unsigned &V) {
    sys::AtomicDiv(&Value, V);
    return init();
@@ -16,6 +16,7 @@

 #include "llvm/Support/DataTypes.h"
 #include "llvm/ADT/APFloat.h"
+#include "llvm/ADT/DenseMapInfo.h"
 #include "llvm/ADT/StringRef.h"
 #include <cctype>
 #include <cstdio>
@@ -0,0 +1,133 @@
+//===- llvm/ADT/TinyPtrVector.h - 'Normally tiny' vectors -------*- C++ -*-===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef LLVM_ADT_TINYPTRVECTOR_H
+#define LLVM_ADT_TINYPTRVECTOR_H
+
+#include "llvm/ADT/SmallVector.h"
+#include "llvm/ADT/PointerUnion.h"
+
+namespace llvm {
+  
+/// TinyPtrVector - This class is specialized for cases where there are
+/// normally 0 or 1 element in a vector, but is general enough to go beyond that
+/// when required.
+///
+/// NOTE: This container doesn't allow you to store a null pointer into it.
+///
+template <typename EltTy>
+class TinyPtrVector {
+public:
+  typedef llvm::SmallVector<EltTy, 4> VecTy;
+  llvm::PointerUnion<EltTy, VecTy*> Val;
+  
+  TinyPtrVector() {}
+  TinyPtrVector(const TinyPtrVector &RHS) : Val(RHS.Val) {
+    if (VecTy *V = Val.template dyn_cast<VecTy*>())
+      Val = new VecTy(*V);
+  }
+  ~TinyPtrVector() {
+    if (VecTy *V = Val.template dyn_cast<VecTy*>())
+      delete V;
+  }
+  
+  bool empty() const {
+    // This vector can be empty if it contains no element, or if it
+    // contains a pointer to an empty vector.
+    if (Val.isNull()) return true;
+    if (VecTy *Vec = Val.template dyn_cast<VecTy*>())
+      return Vec->empty();
+    return false;
+  }
+  
+  unsigned size() const {
+    if (empty())
+      return 0;
+    if (Val.template is<EltTy>())
+      return 1;
+    return Val.template get<VecTy*>()->size();
+  }
+  
+  typedef const EltTy *iterator;
+  iterator begin() const {
+    if (empty())
+      return 0;
+    
+    if (Val.template is<EltTy>())
+      return Val.template getAddrOf<EltTy>();
+    
+    return Val.template get<VecTy *>()->begin();
+
+  }
+  iterator end() const {
+    if (empty())
+      return 0;
+    
+    if (Val.template is<EltTy>())
+      return begin() + 1;
+    
+    return Val.template get<VecTy *>()->end();
+  }
+
+  
+  EltTy operator[](unsigned i) const {
+    assert(!Val.isNull() && "can't index into an empty vector");
+    if (EltTy V = Val.template dyn_cast<EltTy>()) {
+      assert(i == 0 && "tinyvector index out of range");
+      return V;
+    }
+    
+    assert(i < Val.template get<VecTy*>()->size() && 
+           "tinyvector index out of range");
+    return (*Val.template get<VecTy*>())[i];
+  }
+  
+  EltTy front() const {
+    assert(!empty() && "vector empty");
+    if (EltTy V = Val.template dyn_cast<EltTy>())
+      return V;
+    return Val.template get<VecTy*>()->front();
+  }
+  
+  void push_back(EltTy NewVal) {
+    assert(NewVal != 0 && "Can't add a null value");
+    
+    // If we have nothing, add something.
+    if (Val.isNull()) {
+      Val = NewVal;
+      return;
+    }
+    
+    // If we have a single value, convert to a vector.
+    if (EltTy V = Val.template dyn_cast<EltTy>()) {
+      Val = new VecTy();
+      Val.template get<VecTy*>()->push_back(V);
+    }
+    
+    // Add the new value, we know we have a vector.
+    Val.template get<VecTy*>()->push_back(NewVal);
+  }
+  
+  void clear() {
+    // If we have a single value, convert to empty.
+    if (Val.template is<EltTy>()) {
+      Val = (EltTy)0;
+    } else if (VecTy *Vec = Val.template dyn_cast<VecTy*>()) {
+      // If we have a vector form, just clear it.
+      Vec->clear();
+    }
+    // Otherwise, we're already empty.
+  }
+  
+private:
+  void operator=(const TinyPtrVector&); // NOT IMPLEMENTED YET.
+};
+} // end namespace llvm
+
+#endif
@@ -10,8 +10,7 @@
 #ifndef LLVM_ADT_TRIPLE_H
 #define LLVM_ADT_TRIPLE_H

-#include "llvm/ADT/StringRef.h"
-#include <string>
+#include "llvm/ADT/Twine.h"

 // Some system headers or GCC predefined macros conflict with identifiers in
 // this file.  Undefine them here.
@@ -19,8 +18,6 @@
 #undef sparc

 namespace llvm {
-class StringRef;
-class Twine;

 /// Triple - Helper class for working with target triples.
 ///
@@ -52,6 +49,8 @@ public:
    cellspu, // CellSPU: spu, cellspu
    mips,    // MIPS: mips, mipsallegrex
    mipsel,  // MIPSEL: mipsel, mipsallegrexel, psp
+    mips64,  // MIPS64: mips64
+    mips64el,// MIPS64EL: mips64el
    msp430,  // MSP430: msp430
    ppc,     // PPC: powerpc
    ppc64,   // PPC64: powerpc64, ppu
@@ -66,6 +65,8 @@ public:
    mblaze,  // MBlaze: mblaze
    ptx32,   // PTX: ptx (32-bit)
    ptx64,   // PTX: ptx (64-bit)
+    le32,    // le32: generic little-endian 32-bit CPU (PNaCl / Emscripten)
+    amdil,   // amdil: amd IL

    InvalidArch
  };
@@ -85,6 +86,7 @@ public:
    DragonFly,
    FreeBSD,
    IOS,
+    KFreeBSD,
    Linux,
    Lv2,        // PS3
    MacOSX,
@@ -96,7 +98,8 @@ public:
    Win32,
    Haiku,
    Minix,
-    RTEMS
+    RTEMS,
+    NativeClient
  };
  enum EnvironmentType {
    UnknownEnvironment,
@@ -134,24 +137,16 @@ public:
  /// @{

  Triple() : Data(), Arch(InvalidArch) {}
-  explicit Triple(StringRef Str) : Data(Str), Arch(InvalidArch) {}
-  explicit Triple(StringRef ArchStr, StringRef VendorStr, StringRef OSStr)
-    : Data(ArchStr), Arch(InvalidArch) {
-    Data += '-';
-    Data += VendorStr;
-    Data += '-';
-    Data += OSStr;
+  explicit Triple(const Twine &Str) : Data(Str.str()), Arch(InvalidArch) {}
+  Triple(const Twine &ArchStr, const Twine &VendorStr, const Twine &OSStr)
+    : Data((ArchStr + Twine('-') + VendorStr + Twine('-') + OSStr).str()),
+      Arch(InvalidArch) {
  }

-  explicit Triple(StringRef ArchStr, StringRef VendorStr, StringRef OSStr,
-    StringRef EnvironmentStr)
-    : Data(ArchStr), Arch(InvalidArch) {
-    Data += '-';
-    Data += VendorStr;
-    Data += '-';
-    Data += OSStr;
-    Data += '-';
-    Data += EnvironmentStr;
+  Triple(const Twine &ArchStr, const Twine &VendorStr, const Twine &OSStr,
+         const Twine &EnvironmentStr)
+    : Data((ArchStr + Twine('-') + VendorStr + Twine('-') + OSStr + Twine('-') +
+            EnvironmentStr).str()), Arch(InvalidArch) {
  }

  /// @}
@@ -99,6 +99,9 @@ namespace llvm {
      /// A pointer to a StringRef instance.
      StringRefKind,

+      /// A char value reinterpreted as a pointer, to render as a character.
+      CharKind,
+
      /// An unsigned int value reinterpreted as a pointer, to render as an
      /// unsigned decimal integer.
      DecUIKind,
@@ -126,13 +129,31 @@ namespace llvm {
      UHexKind
    };

+    union Child
+    {
+      const Twine *twine;
+      const char *cString;
+      const std::string *stdString;
+      const StringRef *stringRef;
+      char character;
+      unsigned int decUI;
+      int decI;
+      const unsigned long *decUL;
+      const long *decL;
+      const unsigned long long *decULL;
+      const long long *decLL;
+      const uint64_t *uHex;
+    };
+
  private:
    /// LHS - The prefix in the concatenation, which may be uninitialized for
    /// Null or Empty kinds.
-    const void *LHS;
+    Child LHS;
    /// RHS - The suffix in the concatenation, which may be uninitialized for
    /// Null or Empty kinds.
-    const void *RHS;
+    Child RHS;
+    // enums stored as unsigned chars to save on space while some compilers
+    // don't support specifying the backing type for an enum
    /// LHSKind - The NodeKind of the left hand side, \see getLHSKind().
    unsigned char LHSKind;
    /// RHSKind - The NodeKind of the left hand side, \see getLHSKind().
@@ -147,13 +168,15 @@ namespace llvm {

    /// Construct a binary twine.
    explicit Twine(const Twine &_LHS, const Twine &_RHS)
-      : LHS(&_LHS), RHS(&_RHS), LHSKind(TwineKind), RHSKind(TwineKind) {
+      : LHSKind(TwineKind), RHSKind(TwineKind) {
+      LHS.twine = &_LHS;
+      RHS.twine = &_RHS;
      assert(isValid() && "Invalid twine!");
    }

    /// Construct a twine from explicit values.
-    explicit Twine(const void *_LHS, NodeKind _LHSKind,
-                   const void *_RHS, NodeKind _RHSKind)
+    explicit Twine(Child _LHS, NodeKind _LHSKind,
+                   Child _RHS, NodeKind _RHSKind)
      : LHS(_LHS), RHS(_RHS), LHSKind(_LHSKind), RHSKind(_RHSKind) {
      assert(isValid() && "Invalid twine!");
    }
@@ -200,10 +223,10 @@ namespace llvm {

      // A twine child should always be binary.
      if (getLHSKind() == TwineKind &&
-          !static_cast<const Twine*>(LHS)->isBinary())
+          !LHS.twine->isBinary())
        return false;
      if (getRHSKind() == TwineKind &&
-          !static_cast<const Twine*>(RHS)->isBinary())
+          !RHS.twine->isBinary())
        return false;

      return true;
@@ -216,10 +239,10 @@ namespace llvm {
    NodeKind getRHSKind() const { return (NodeKind) RHSKind; }

    /// printOneChild - Print one child from a twine.
-    void printOneChild(raw_ostream &OS, const void *Ptr, NodeKind Kind) const;
+    void printOneChild(raw_ostream &OS, Child Ptr, NodeKind Kind) const;

    /// printOneChildRepr - Print the representation of one child from a twine.
-    void printOneChildRepr(raw_ostream &OS, const void *Ptr,
+    void printOneChildRepr(raw_ostream &OS, Child Ptr,
                           NodeKind Kind) const;

  public:
@@ -239,7 +262,7 @@ namespace llvm {
    /*implicit*/ Twine(const char *Str)
      : RHSKind(EmptyKind) {
      if (Str[0] != '\0') {
-        LHS = Str;
+        LHS.cString = Str;
        LHSKind = CStringKind;
      } else
        LHSKind = EmptyKind;
@@ -249,44 +272,70 @@ namespace llvm {

    /// Construct from an std::string.
    /*implicit*/ Twine(const std::string &Str)
-      : LHS(&Str), LHSKind(StdStringKind), RHSKind(EmptyKind) {
+      : LHSKind(StdStringKind), RHSKind(EmptyKind) {
+      LHS.stdString = &Str;
      assert(isValid() && "Invalid twine!");
    }

    /// Construct from a StringRef.
    /*implicit*/ Twine(const StringRef &Str)
-      : LHS(&Str), LHSKind(StringRefKind), RHSKind(EmptyKind) {
+      : LHSKind(StringRefKind), RHSKind(EmptyKind) {
+      LHS.stringRef = &Str;
      assert(isValid() && "Invalid twine!");
    }

+    /// Construct from a char.
+    explicit Twine(char Val)
+      : LHSKind(CharKind), RHSKind(EmptyKind) {
+      LHS.character = Val;
+    }
+
+    /// Construct from a signed char.
+    explicit Twine(signed char Val)
+      : LHSKind(CharKind), RHSKind(EmptyKind) {
+      LHS.character = static_cast<char>(Val);
+    }
+
+    /// Construct from an unsigned char.
+    explicit Twine(unsigned char Val)
+      : LHSKind(CharKind), RHSKind(EmptyKind) {
+      LHS.character = static_cast<char>(Val);
+    }
+
    /// Construct a twine to print \arg Val as an unsigned decimal integer.
    explicit Twine(unsigned Val)
-      : LHS((void*)(intptr_t)Val), LHSKind(DecUIKind), RHSKind(EmptyKind) {
+      : LHSKind(DecUIKind), RHSKind(EmptyKind) {
+      LHS.decUI = Val;
    }

    /// Construct a twine to print \arg Val as a signed decimal integer.
    explicit Twine(int Val)
-      : LHS((void*)(intptr_t)Val), LHSKind(DecIKind), RHSKind(EmptyKind) {
+      : LHSKind(DecIKind), RHSKind(EmptyKind) {
+      LHS.decI = Val;
    }

    /// Construct a twine to print \arg Val as an unsigned decimal integer.
    explicit Twine(const unsigned long &Val)
-      : LHS(&Val), LHSKind(DecULKind), RHSKind(EmptyKind) {
+      : LHSKind(DecULKind), RHSKind(EmptyKind) {
+      LHS.decUL = &Val;
    }

    /// Construct a twine to print \arg Val as a signed decimal integer.
    explicit Twine(const long &Val)
-      : LHS(&Val), LHSKind(DecLKind), RHSKind(EmptyKind) {
+      : LHSKind(DecLKind), RHSKind(EmptyKind) {
+      LHS.decL = &Val;
    }

    /// Construct a twine to print \arg Val as an unsigned decimal integer.
    explicit Twine(const unsigned long long &Val)
-      : LHS(&Val), LHSKind(DecULLKind), RHSKind(EmptyKind) {
+      : LHSKind(DecULLKind), RHSKind(EmptyKind) {
+      LHS.decULL = &Val;
    }

    /// Construct a twine to print \arg Val as a signed decimal integer.
    explicit Twine(const long long &Val)
-      : LHS(&Val), LHSKind(DecLLKind), RHSKind(EmptyKind) {
+      : LHSKind(DecLLKind), RHSKind(EmptyKind) {
+      LHS.decLL = &Val;
    }

    // FIXME: Unfortunately, to make sure this is as efficient as possible we
@@ -296,13 +345,17 @@ namespace llvm {

    /// Construct as the concatenation of a C string and a StringRef.
    /*implicit*/ Twine(const char *_LHS, const StringRef &_RHS)
-      : LHS(_LHS), RHS(&_RHS), LHSKind(CStringKind), RHSKind(StringRefKind) {
+      : LHSKind(CStringKind), RHSKind(StringRefKind) {
+      LHS.cString = _LHS;
+      RHS.stringRef = &_RHS;
      assert(isValid() && "Invalid twine!");
    }

    /// Construct as the concatenation of a StringRef and a C string.
    /*implicit*/ Twine(const StringRef &_LHS, const char *_RHS)
-      : LHS(&_LHS), RHS(_RHS), LHSKind(StringRefKind), RHSKind(CStringKind) {
+      : LHSKind(StringRefKind), RHSKind(CStringKind) {
+      LHS.stringRef = &_LHS;
+      RHS.cString = _RHS;
      assert(isValid() && "Invalid twine!");
    }

@@ -318,7 +371,10 @@ namespace llvm {

    // Construct a twine to print \arg Val as an unsigned hexadecimal integer.
    static Twine utohexstr(const uint64_t &Val) {
-      return Twine(&Val, UHexKind, 0, EmptyKind);
+      Child LHS, RHS;
+      LHS.uHex = &Val;
+      RHS.twine = 0;
+      return Twine(LHS, UHexKind, RHS, EmptyKind);
    }

    /// @}
@@ -371,9 +427,9 @@ namespace llvm {
      switch (getLHSKind()) {
      default: assert(0 && "Out of sync with isSingleStringRef");
      case EmptyKind:      return StringRef();
-      case CStringKind:    return StringRef((const char*)LHS);
-      case StdStringKind:  return StringRef(*(const std::string*)LHS);
-      case StringRefKind:  return *(const StringRef*)LHS;
+      case CStringKind:    return StringRef(LHS.cString);
+      case StdStringKind:  return StringRef(*LHS.stdString);
+      case StringRefKind:  return *LHS.stringRef;
      }
    }

@@ -422,7 +478,9 @@ namespace llvm {

    // Otherwise we need to create a new node, taking care to fold in unary
    // twines.
-    const void *NewLHS = this, *NewRHS = &Suffix;
+    Child NewLHS, NewRHS;
+    NewLHS.twine = this;
+    NewRHS.twine = &Suffix;
    NodeKind NewLHSKind = TwineKind, NewRHSKind = TwineKind;
    if (isUnary()) {
      NewLHS = LHS;
@@ -88,7 +88,7 @@ public:
  /// getTypeStoreSize - Return the TargetData store size for the given type,
  /// if known, or a conservative value otherwise.
  ///
-  uint64_t getTypeStoreSize(const Type *Ty);
+  uint64_t getTypeStoreSize(Type *Ty);

  //===--------------------------------------------------------------------===//
  /// Alias Queries...
@@ -136,6 +136,8 @@ public:
  Location getLocation(const LoadInst *LI);
  Location getLocation(const StoreInst *SI);
  Location getLocation(const VAArgInst *VI);
+  Location getLocation(const AtomicCmpXchgInst *CXI);
+  Location getLocation(const AtomicRMWInst *RMWI);
  static Location getLocationForSource(const MemTransferInst *MTI);
  static Location getLocationForDest(const MemIntrinsic *MI);

@@ -341,6 +343,11 @@ public:
    case Instruction::VAArg:  return getModRefInfo((const VAArgInst*)I, Loc);
    case Instruction::Load:   return getModRefInfo((const LoadInst*)I,  Loc);
    case Instruction::Store:  return getModRefInfo((const StoreInst*)I, Loc);
+    case Instruction::Fence:  return getModRefInfo((const FenceInst*)I, Loc);
+    case Instruction::AtomicCmpXchg:
+      return getModRefInfo((const AtomicCmpXchgInst*)I, Loc);
+    case Instruction::AtomicRMW:
+      return getModRefInfo((const AtomicRMWInst*)I, Loc);
    case Instruction::Call:   return getModRefInfo((const CallInst*)I,  Loc);
    case Instruction::Invoke: return getModRefInfo((const InvokeInst*)I,Loc);
    default:                  return NoModRef;
@@ -406,6 +413,39 @@ public:
    return getModRefInfo(S, Location(P, Size));
  }

+  /// getModRefInfo (for fences) - Return whether information about whether
+  /// a particular store modifies or reads the specified memory location.
+  ModRefResult getModRefInfo(const FenceInst *S, const Location &Loc) {
+    // Conservatively correct.  (We could possibly be a bit smarter if
+    // Loc is a alloca that doesn't escape.)
+    return ModRef;
+  }
+
+  /// getModRefInfo (for fences) - A convenience wrapper.
+  ModRefResult getModRefInfo(const FenceInst *S, const Value *P, uint64_t Size){
+    return getModRefInfo(S, Location(P, Size));
+  }
+
+  /// getModRefInfo (for cmpxchges) - Return whether information about whether
+  /// a particular cmpxchg modifies or reads the specified memory location.
+  ModRefResult getModRefInfo(const AtomicCmpXchgInst *CX, const Location &Loc);
+
+  /// getModRefInfo (for cmpxchges) - A convenience wrapper.
+  ModRefResult getModRefInfo(const AtomicCmpXchgInst *CX,
+                             const Value *P, unsigned Size) {
+    return getModRefInfo(CX, Location(P, Size));
+  }
+
+  /// getModRefInfo (for atomicrmws) - Return whether information about whether
+  /// a particular atomicrmw modifies or reads the specified memory location.
+  ModRefResult getModRefInfo(const AtomicRMWInst *RMW, const Location &Loc);
+
+  /// getModRefInfo (for atomicrmws) - A convenience wrapper.
+  ModRefResult getModRefInfo(const AtomicRMWInst *RMW,
+                             const Value *P, unsigned Size) {
+    return getModRefInfo(RMW, Location(P, Size));
+  }
+
  /// getModRefInfo (for va_args) - Return whether information about whether
  /// a particular va_arg modifies or reads the specified memory location.
  ModRefResult getModRefInfo(const VAArgInst* I, const Location &Loc);
@@ -111,8 +111,8 @@ class AliasSet : public ilist_node<AliasSet> {
  AliasSet *Forward;             // Forwarding pointer.
  AliasSet *Next, *Prev;         // Doubly linked list of AliasSets.

-  // All calls & invokes in this alias set.
-  std::vector<AssertingVH<Instruction> > CallSites;
+  // All instructions without a specific address in this alias set.
+  std::vector<AssertingVH<Instruction> > UnknownInsts;

  // RefCount - Number of nodes pointing to this AliasSet plus the number of
  // AliasSets forwarding to it.
@@ -147,9 +147,9 @@ class AliasSet : public ilist_node<AliasSet> {
      removeFromTracker(AST);
  }

-  CallSite getCallSite(unsigned i) const {
-    assert(i < CallSites.size());
-    return CallSite(CallSites[i]);
+  Instruction *getUnknownInst(unsigned i) const {
+    assert(i < UnknownInsts.size());
+    return UnknownInsts[i];
  }
  
 public:
@@ -253,12 +253,12 @@ private:
  void addPointer(AliasSetTracker &AST, PointerRec &Entry, uint64_t Size,
                  const MDNode *TBAAInfo,
                  bool KnownMustAlias = false);
-  void addCallSite(CallSite CS, AliasAnalysis &AA);
-  void removeCallSite(CallSite CS) {
-    for (size_t i = 0, e = CallSites.size(); i != e; ++i)
-      if (CallSites[i] == CS.getInstruction()) {
-        CallSites[i] = CallSites.back();
-        CallSites.pop_back();
+  void addUnknownInst(Instruction *I, AliasAnalysis &AA);
+  void removeUnknownInst(Instruction *I) {
+    for (size_t i = 0, e = UnknownInsts.size(); i != e; ++i)
+      if (UnknownInsts[i] == I) {
+        UnknownInsts[i] = UnknownInsts.back();
+        UnknownInsts.pop_back();
        --i; --e;  // Revisit the moved entry.
      }
  }
@@ -269,7 +269,7 @@ private:
  ///
  bool aliasesPointer(const Value *Ptr, uint64_t Size, const MDNode *TBAAInfo,
                      AliasAnalysis &AA) const;
-  bool aliasesCallSite(CallSite CS, AliasAnalysis &AA) const;
+  bool aliasesUnknownInst(Instruction *Inst, AliasAnalysis &AA) const;
 };

 inline raw_ostream& operator<<(raw_ostream &OS, const AliasSet &AS) {
@@ -326,12 +326,10 @@ public:
  bool add(LoadInst *LI);
  bool add(StoreInst *SI);
  bool add(VAArgInst *VAAI);
-  bool add(CallSite CS);          // Call/Invoke instructions
-  bool add(CallInst *CI)   { return add(CallSite(CI)); }
-  bool add(InvokeInst *II) { return add(CallSite(II)); }
  bool add(Instruction *I);       // Dispatch to one of the other add methods...
  void add(BasicBlock &BB);       // Add all instructions in basic block
  void add(const AliasSetTracker &AST); // Add alias relations from another AST
+  bool addUnknown(Instruction *I);

  /// remove methods - These methods are used to remove all entries that might
  /// be aliased by the specified instruction.  These methods return true if any
@@ -341,11 +339,9 @@ public:
  bool remove(LoadInst *LI);
  bool remove(StoreInst *SI);
  bool remove(VAArgInst *VAAI);
-  bool remove(CallSite CS);
-  bool remove(CallInst *CI)   { return remove(CallSite(CI)); }
-  bool remove(InvokeInst *II) { return remove(CallSite(II)); }
  bool remove(Instruction *I);
  void remove(AliasSet &AS);
+  bool removeUnknown(Instruction *I);
  
  void clear();

@@ -429,7 +425,7 @@ private:
  AliasSet *findAliasSetForPointer(const Value *Ptr, uint64_t Size,
                                   const MDNode *TBAAInfo);

-  AliasSet *findAliasSetForCallSite(CallSite CS);
+  AliasSet *findAliasSetForUnknownInst(Instruction *Inst);
 };

 inline raw_ostream& operator<<(raw_ostream &OS, const AliasSetTracker &AST) {
@@ -19,6 +19,7 @@
 #include "llvm/ADT/PostOrderIterator.h"
 #include "llvm/CodeGen/MachineBasicBlock.h"
 #include "llvm/CodeGen/MachineFunction.h"
+#include "llvm/Support/BlockFrequency.h"
 #include "llvm/Support/BranchProbability.h"
 #include "llvm/Support/Debug.h"
 #include "llvm/Support/raw_ostream.h"
@@ -29,8 +30,8 @@
 namespace llvm {


-class BlockFrequency;
-class MachineBlockFrequency;
+class BlockFrequencyInfo;
+class MachineBlockFrequencyInfo;

 /// BlockFrequencyImpl implements block frequency algorithm for IR and
 /// Machine Instructions. Algorithm starts with value 1024 (START_FREQ)
@@ -40,7 +41,7 @@ class MachineBlockFrequency;
 template<class BlockT, class FunctionT, class BlockProbInfoT>
 class BlockFrequencyImpl {

-  DenseMap<BlockT *, uint32_t> Freqs;
+  DenseMap<BlockT *, BlockFrequency> Freqs;

  BlockProbInfoT *BPI;

@@ -48,7 +49,7 @@ class BlockFrequencyImpl {

  typedef GraphTraits< Inverse<BlockT *> > GT;

-  static const uint32_t START_FREQ = 1024;
+  const uint32_t EntryFreq;

  std::string getBlockName(BasicBlock *BB) const {
    return BB->getNameStr();
@@ -64,26 +65,21 @@ class BlockFrequencyImpl {
    return ss.str();
  }

-  void setBlockFreq(BlockT *BB, uint32_t Freq) {
+  void setBlockFreq(BlockT *BB, BlockFrequency Freq) {
    Freqs[BB] = Freq;
    DEBUG(dbgs() << "Frequency(" << getBlockName(BB) << ") = " << Freq << "\n");
  }

  /// getEdgeFreq - Return edge frequency based on SRC frequency and Src -> Dst
  /// edge probability.
-  uint32_t getEdgeFreq(BlockT *Src, BlockT *Dst) const {
+  BlockFrequency getEdgeFreq(BlockT *Src, BlockT *Dst) const {
    BranchProbability Prob = BPI->getEdgeProbability(Src, Dst);
-    uint64_t N = Prob.getNumerator();
-    uint64_t D = Prob.getDenominator();
-    uint64_t Res = (N * getBlockFreq(Src)) / D;
-
-    assert(Res <= UINT32_MAX);
-    return (uint32_t) Res;
+    return getBlockFreq(Src) * Prob;
  }

  /// incBlockFreq - Increase BB block frequency by FREQ.
  ///
-  void incBlockFreq(BlockT *BB, uint32_t Freq) {
+  void incBlockFreq(BlockT *BB, BlockFrequency Freq) {
    Freqs[BB] += Freq;
    DEBUG(dbgs() << "Frequency(" << getBlockName(BB) << ") += " << Freq
                 << " --> " << Freqs[BB] << "\n");
@@ -95,13 +91,13 @@ class BlockFrequencyImpl {
    uint64_t N = Prob.getNumerator();
    assert(N && "Illegal division by zero!");
    uint64_t D = Prob.getDenominator();
-    uint64_t Freq = (Freqs[BB] * D) / N;
+    uint64_t Freq = (Freqs[BB].getFrequency() * D) / N;

    // Should we assert it?
    if (Freq > UINT32_MAX)
      Freq = UINT32_MAX;

-    Freqs[BB] = (uint32_t) Freq;
+    Freqs[BB] = BlockFrequency(Freq);
    DEBUG(dbgs() << "Frequency(" << getBlockName(BB) << ") /= (" << Prob
                 << ") --> " << Freqs[BB] << "\n");
  }
@@ -136,15 +132,6 @@ class BlockFrequencyImpl {
  }


-  /// Return a probability of getting to the DST block through SRC->DST edge.
-  ///
-  BranchProbability getBackEdgeProbability(BlockT *Src, BlockT *Dst) const {
-    uint32_t N = getEdgeFreq(Src, Dst);
-    uint32_t D = getBlockFreq(Dst);
-
-    return BranchProbability(N, D);
-  }
-
  /// isReachable - Returns if BB block is reachable from the entry.
  ///
  bool isReachable(BlockT *BB) {
@@ -160,7 +147,7 @@ class BlockFrequencyImpl {
    unsigned a = RPO[Src];
    unsigned b = RPO[Dst];

-    return a > b;
+    return a >= b;
  }

  /// getSingleBlockPred - return single BB block predecessor or NULL if
@@ -189,7 +176,7 @@ class BlockFrequencyImpl {
    setBlockFreq(BB, 0);

    if (BB == LoopHead) {
-      setBlockFreq(BB, START_FREQ);
+      setBlockFreq(BB, EntryFreq);
      return;
    }

@@ -224,10 +211,10 @@ class BlockFrequencyImpl {
    if (!isLoopHead)
      return;

-    assert(START_FREQ >= CycleProb[BB]);
+    assert(EntryFreq >= CycleProb[BB]);
    uint32_t CProb = CycleProb[BB];
-    uint32_t Numerator = START_FREQ - CProb ? START_FREQ - CProb : 1;
-    divBlockFreq(BB, BranchProbability(Numerator, START_FREQ));
+    uint32_t Numerator = EntryFreq - CProb ? EntryFreq - CProb : 1;
+    divBlockFreq(BB, BranchProbability(Numerator, EntryFreq));
  }

  /// doLoop - Propagate block frequency down throught the loop.
@@ -237,11 +224,13 @@ class BlockFrequencyImpl {

    SmallPtrSet<BlockT *, 8> BlocksInLoop;

-    for (rpot_iterator I = rpot_at(Head), E = rpot_end(); I != E; ++I) {
+    for (rpot_iterator I = rpot_at(Head), E = rpot_at(Tail); ; ++I) {
      BlockT *BB = *I;
      doBlock(BB, Head, BlocksInLoop);

      BlocksInLoop.insert(BB);
+      if (I == E)
+        break;
    }

    // Compute loop's cyclic probability using backedges probabilities.
@@ -252,19 +241,23 @@ class BlockFrequencyImpl {
      BlockT *Pred = *PI;
      assert(Pred);
      if (isReachable(Pred) && isBackedge(Pred, Head)) {
-        BranchProbability Prob = getBackEdgeProbability(Pred, Head);
-        uint64_t N = Prob.getNumerator();
-        uint64_t D = Prob.getDenominator();
-        uint64_t Res = (N * START_FREQ) / D;
+        uint64_t N = getEdgeFreq(Pred, Head).getFrequency();
+        uint64_t D = getBlockFreq(Head).getFrequency();
+        assert(N <= EntryFreq && "Backedge frequency must be <= EntryFreq!");
+        uint64_t Res = (N * EntryFreq) / D;

        assert(Res <= UINT32_MAX);
        CycleProb[Head] += (uint32_t) Res;
+        DEBUG(dbgs() << "  CycleProb[" << getBlockName(Head) << "] += " << Res
+                     << " --> " << CycleProb[Head] << "\n");
      }
    }
  }

-  friend class BlockFrequency;
-  friend class MachineBlockFrequency;
+  friend class BlockFrequencyInfo;
+  friend class MachineBlockFrequencyInfo;
+
+  BlockFrequencyImpl() : EntryFreq(BlockFrequency::getEntryFrequency()) { }

  void doFunction(FunctionT *fn, BlockProbInfoT *bpi) {
    Fn = fn;
@@ -314,13 +307,12 @@ class BlockFrequencyImpl {
  }

 public:
-  /// getBlockFreq - Return block frequency. Never return 0, value must be
-  /// positive.
-  uint32_t getBlockFreq(BlockT *BB) const {
-    typename DenseMap<BlockT *, uint32_t>::const_iterator I = Freqs.find(BB);
+  /// getBlockFreq - Return block frequency. Return 0 if we don't have it.
+  BlockFrequency getBlockFreq(BlockT *BB) const {
+    typename DenseMap<BlockT *, BlockFrequency>::const_iterator I = Freqs.find(BB);
    if (I != Freqs.end())
-      return I->second ? I->second : 1;
-    return 1;
+      return I->second;
+    return 0;
  }

  void print(raw_ostream &OS) const {
@@ -1,4 +1,4 @@
-//========-------- BlockFrequency.h - Block Frequency Analysis -------========//
+//========-------- BlockFrequencyInfo.h - Block Frequency Analysis -------========//
 //
 //                     The LLVM Compiler Infrastructure
 //
@@ -11,10 +11,11 @@
 //
 //===----------------------------------------------------------------------===//

-#ifndef LLVM_ANALYSIS_BLOCKFREQUENCY_H
-#define LLVM_ANALYSIS_BLOCKFREQUENCY_H
+#ifndef LLVM_ANALYSIS_BLOCKFREQUENCYINFO_H
+#define LLVM_ANALYSIS_BLOCKFREQUENCYINFO_H

 #include "llvm/Pass.h"
+#include "llvm/Support/BlockFrequency.h"
 #include <climits>

 namespace llvm {
@@ -23,29 +24,30 @@ class BranchProbabilityInfo;
 template<class BlockT, class FunctionT, class BranchProbInfoT>
 class BlockFrequencyImpl;

-/// BlockFrequency pass uses BlockFrequencyImpl implementation to estimate
+/// BlockFrequencyInfo pass uses BlockFrequencyImpl implementation to estimate
 /// IR basic block frequencies.
-class BlockFrequency : public FunctionPass {
+class BlockFrequencyInfo : public FunctionPass {

  BlockFrequencyImpl<BasicBlock, Function, BranchProbabilityInfo> *BFI;

 public:
  static char ID;

-  BlockFrequency();
+  BlockFrequencyInfo();

-  ~BlockFrequency();
+  ~BlockFrequencyInfo();

  void getAnalysisUsage(AnalysisUsage &AU) const;

  bool runOnFunction(Function &F);
+  void print(raw_ostream &O, const Module *M) const;

-  /// getblockFreq - Return block frequency. Never return 0, value must be
-  /// positive. Please note that initial frequency is equal to 1024. It means
+  /// getblockFreq - Return block frequency. Return 0 if we don't have the
+  /// information. Please note that initial frequency is equal to 1024. It means
  /// that we should not rely on the value itself, but only on the comparison to
-  /// the other block frequencies. We do this to avoid using of the floating
-  /// points.
-  uint32_t getBlockFreq(BasicBlock *BB);
+  /// the other block frequencies. We do this to avoid using of floating points.
+  ///
+  BlockFrequency getBlockFreq(BasicBlock *BB) const;
 };

 }
@@ -33,12 +33,12 @@ class BranchProbabilityInfo : public FunctionPass {
  // weight to just "inherit" the non-zero weight of an adjacent successor.
  static const uint32_t DEFAULT_WEIGHT = 16;

-  typedef std::pair<BasicBlock *, BasicBlock *> Edge;
+  typedef std::pair<const BasicBlock *, const BasicBlock *> Edge;

  DenseMap<Edge, uint32_t> Weights;

  // Get sum of the block successors' weights.
-  uint32_t getSumForBlock(BasicBlock *BB) const;
+  uint32_t getSumForBlock(const BasicBlock *BB) const;

 public:
  static char ID;
@@ -53,13 +53,14 @@ public:

  // Returned value is between 1 and UINT32_MAX. Look at
  // BranchProbabilityInfo.cpp for details.
-  uint32_t getEdgeWeight(BasicBlock *Src, BasicBlock *Dst) const;
+  uint32_t getEdgeWeight(const BasicBlock *Src, const BasicBlock *Dst) const;

  // Look at BranchProbabilityInfo.cpp for details. Use it with caution!
-  void setEdgeWeight(BasicBlock *Src, BasicBlock *Dst, uint32_t Weight);
+  void setEdgeWeight(const BasicBlock *Src, const BasicBlock *Dst,
+                     uint32_t Weight);

  // A 'Hot' edge is an edge which probability is >= 80%.
-  bool isEdgeHot(BasicBlock *Src, BasicBlock *Dst) const;
+  bool isEdgeHot(const BasicBlock *Src, const BasicBlock *Dst) const;

  // Return a hot successor for the block BB or null if there isn't one.
  BasicBlock *getHotSucc(BasicBlock *BB) const;
@@ -67,7 +68,8 @@ public:
  // Return a probability as a fraction between 0 (0% probability) and
  // 1 (100% probability), however the value is never equal to 0, and can be 1
  // only iff SRC block has only one successor.
-  BranchProbability getEdgeProbability(BasicBlock *Src, BasicBlock *Dst) const;
+  BranchProbability getEdgeProbability(const BasicBlock *Src,
+                                       const BasicBlock *Dst) const;

  // Print value between 0 (0% probability) and 1 (100% probability),
  // however the value is never equal to 0, and can be 1 only iff SRC block
@@ -18,6 +18,9 @@
 #include "llvm/ADT/DenseMap.h"

 namespace llvm {
+
+  class TargetData;
+
  // CodeMetrics - Calculate size and a few similar metrics for a set of
  // basic blocks.
  struct CodeMetrics {
@@ -46,7 +49,7 @@ namespace llvm {

    /// NumCalls - Keep track of the number of calls to 'big' functions.
    unsigned NumCalls;
-    
+
    /// NumInlineCandidates - Keep track of the number of calls to internal
    /// functions with only a single caller.  These are likely targets for
    /// future inlining, likely exposed by interleaved devirtualization.
@@ -61,24 +64,24 @@ namespace llvm {
    unsigned NumRets;

    CodeMetrics() : callsSetJmp(false), isRecursive(false),
-                    containsIndirectBr(false), usesDynamicAlloca(false), 
+                    containsIndirectBr(false), usesDynamicAlloca(false),
                    NumInsts(0), NumBlocks(0), NumCalls(0),
-                    NumInlineCandidates(0), NumVectorInsts(0), 
+                    NumInlineCandidates(0), NumVectorInsts(0),
                    NumRets(0) {}

    /// analyzeBasicBlock - Add information about the specified basic block
    /// to the current structure.
-    void analyzeBasicBlock(const BasicBlock *BB);
+    void analyzeBasicBlock(const BasicBlock *BB, const TargetData *TD = 0);

    /// analyzeFunction - Add information about the specified function
    /// to the current structure.
-    void analyzeFunction(Function *F);
-    
+    void analyzeFunction(Function *F, const TargetData *TD = 0);
+
    /// CountCodeReductionForConstant - Figure out an approximation for how
    /// many instructions will be constant folded if the specified value is
    /// constant.
    unsigned CountCodeReductionForConstant(Value *V);
-   
+
    /// CountBonusForConstant - Figure out an approximation for how much
    /// per-call performance boost we can expect if the specified value is
    /// constant.
@@ -27,6 +27,8 @@ namespace llvm {
  class TargetData;
  class Function;
  class Type;
+  template<typename T>
+  class ArrayRef;

 /// ConstantFoldInstruction - Try to constant fold the specified instruction.
 /// If successful, the constant result is returned, if not, null is returned.
@@ -47,8 +49,8 @@ Constant *ConstantFoldConstantExpression(const ConstantExpr *CE,
 /// fold instructions like loads and stores, which have no constant expression 
 /// form.
 ///
-Constant *ConstantFoldInstOperands(unsigned Opcode, const Type *DestTy,
-                                   Constant *const *Ops, unsigned NumOps,
+Constant *ConstantFoldInstOperands(unsigned Opcode, Type *DestTy,
+                                   ArrayRef<Constant *> Ops,
                                   const TargetData *TD = 0);

 /// ConstantFoldCompareInstOperands - Attempt to constant fold a compare
@@ -59,6 +61,12 @@ Constant *ConstantFoldCompareInstOperands(unsigned Predicate,
                                          Constant *LHS, Constant *RHS,
                                          const TargetData *TD = 0);

+/// ConstantFoldInsertValueInstruction - Attempt to constant fold an insertvalue
+/// instruction with the specified operands and indices.  The constant result is
+/// returned if successful; if not, null is returned.
+Constant *ConstantFoldInsertValueInstruction(Constant *Agg, Constant *Val,
+                                             ArrayRef<unsigned> Idxs);
+
 /// ConstantFoldLoadFromConstPtr - Return the value that a load from C would
 /// produce if it is constant and determinable.  If this is not determinable,
 /// return null.
@@ -76,7 +84,7 @@ bool canConstantFoldCallTo(const Function *F);
 /// ConstantFoldCall - Attempt to constant fold a call to the specified function
 /// with the specified arguments, returning null if unsuccessful.
 Constant *
-ConstantFoldCall(Function *F, Constant *const *Operands, unsigned NumOperands);
+ConstantFoldCall(Function *F, ArrayRef<Constant *> Operands);
 }

 #endif
@@ -37,6 +37,7 @@ namespace llvm {
  class DINameSpace;
  class DIVariable;
  class DISubrange;
+  class DILexicalBlockFile;
  class DILexicalBlock;
  class DISubprogram;
  class DITemplateTypeParameter;
@@ -48,9 +49,19 @@ namespace llvm {
    LLVMContext & VMContext;
    MDNode *TheCU;

+    MDNode *TempEnumTypes;
+    MDNode *TempRetainTypes;
+    MDNode *TempSubprograms;
+    MDNode *TempGVs;
+
    Function *DeclareFn;     // llvm.dbg.declare
    Function *ValueFn;       // llvm.dbg.value

+    SmallVector<Value *, 4> AllEnumTypes;
+    SmallVector<Value *, 4> AllRetainTypes;
+    SmallVector<Value *, 4> AllSubprograms;
+    SmallVector<Value *, 4> AllGVs;
+
    DIBuilder(const DIBuilder &);       // DO NOT IMPLEMENT
    void operator=(const DIBuilder &);  // DO NOT IMPLEMENT

@@ -59,6 +70,9 @@ namespace llvm {
    const MDNode *getCU() { return TheCU; }
    enum ComplexAddrKind { OpPlus=1, OpDeref };

+    /// finalize - Construct any deferred debug info descriptors.
+    void finalize();
+
    /// createCompileUnit - A CompileUnit provides an anchor for all debugging
    /// information generated during this instance of compilation.
    /// @param Lang     Source programming language, eg. dwarf::DW_LANG_C99
@@ -84,6 +98,9 @@ namespace llvm {
    /// createEnumerator - Create a single enumerator value.
    DIEnumerator createEnumerator(StringRef Name, uint64_t Val);

+    /// createNullPtrType - Create C++0x nullptr type.
+    DIType createNullPtrType(StringRef Name);
+
    /// createBasicType - Create debugging information entry for a basic 
    /// type.
    /// @param Name        Type name.
@@ -447,6 +464,14 @@ namespace llvm {
                                DIFile File, unsigned LineNo);


+    /// createLexicalBlockFile - This creates a descriptor for a lexical
+    /// block with a new file attached. This merely extends the existing
+    /// lexical block as it crosses a file.
+    /// @param Scope       Lexical block.
+    /// @param File        Source file.
+    DILexicalBlockFile createLexicalBlockFile(DIDescriptor Scope,
+					      DIFile File);
+    
    /// createLexicalBlock - This creates a descriptor for a lexical block
    /// with the specified parent context.
    /// @param Scope       Parent lexical scope.
@@ -40,6 +40,7 @@ namespace llvm {
  class DIFile;
  class DISubprogram;
  class DILexicalBlock;
+  class DILexicalBlockFile;
  class DIVariable;
  class DIType;

@@ -84,6 +85,7 @@ namespace llvm {
    explicit DIDescriptor(const MDNode *N) : DbgNode(N) {}
    explicit DIDescriptor(const DIFile F);
    explicit DIDescriptor(const DISubprogram F);
+    explicit DIDescriptor(const DILexicalBlockFile F);
    explicit DIDescriptor(const DILexicalBlock F);
    explicit DIDescriptor(const DIVariable F);
    explicit DIDescriptor(const DIType F);
@@ -117,6 +119,7 @@ namespace llvm {
    bool isFile() const;
    bool isCompileUnit() const;
    bool isNameSpace() const;
+    bool isLexicalBlockFile() const;
    bool isLexicalBlock() const;
    bool isSubrange() const;
    bool isEnumerator() const;
@@ -182,6 +185,11 @@ namespace llvm {
    StringRef getFlags() const       { return getStringField(8);   }
    unsigned getRunTimeVersion() const { return getUnsignedField(9); }

+    DIArray getEnumTypes() const;
+    DIArray getRetainedTypes() const;
+    DIArray getSubprograms() const;
+    DIArray getGlobalVariables() const;
+
    /// Verify - Verify that a compile unit is well formed.
    bool Verify() const;

@@ -201,7 +209,10 @@ namespace llvm {
    }
    StringRef getFilename() const  { return getStringField(1);   }
    StringRef getDirectory() const { return getStringField(2);   }
-    DICompileUnit getCompileUnit() const{ return getFieldAs<DICompileUnit>(3); }
+    DICompileUnit getCompileUnit() const{ 
+      assert (getVersion() <= LLVMDebugVersion10  && "Invalid CompileUnit!");
+      return getFieldAs<DICompileUnit>(3); 
+    }
  };

  /// DIEnumerator - A wrapper for an enumerator (e.g. X and Y in 'enum {X,Y}').
@@ -237,6 +248,7 @@ namespace llvm {
    DIScope getContext() const          { return getFieldAs<DIScope>(1); }
    StringRef getName() const           { return getStringField(2);     }
    DICompileUnit getCompileUnit() const{ 
+      assert (getVersion() <= LLVMDebugVersion10 && "Invalid getCompileUnit!");
     if (getVersion() == llvm::LLVMDebugVersion7)
       return getFieldAs<DICompileUnit>(3);
     
@@ -291,6 +303,9 @@ namespace llvm {
      return getFieldAs<DIFile>(3).getFilename();
    }

+    /// isUnsignedDIType - Return true if type encoding is unsigned.
+    bool isUnsignedDIType();
+
    /// replaceAllUsesWith - Replace all uses of debug info referenced by
    /// this descriptor.
    void replaceAllUsesWith(DIDescriptor &D);
@@ -447,6 +462,7 @@ namespace llvm {
    StringRef getDisplayName() const  { return getStringField(4); }
    StringRef getLinkageName() const  { return getStringField(5); }
    DICompileUnit getCompileUnit() const{ 
+      assert (getVersion() <= LLVMDebugVersion10 && "Invalid getCompileUnit!");
      if (getVersion() == llvm::LLVMDebugVersion7)
        return getFieldAs<DICompileUnit>(6);

@@ -545,6 +561,8 @@ namespace llvm {
    DISubprogram getFunctionDeclaration() const {
      return getFieldAs<DISubprogram>(18);
    }
+    MDNode *getVariablesNodes() const;
+    DIArray getVariables() const;
  };

  /// DIGlobalVariable - This is a wrapper for a global variable.
@@ -557,12 +575,24 @@ namespace llvm {
    StringRef getDisplayName() const  { return getStringField(4); }
    StringRef getLinkageName() const  { return getStringField(5); }
    DICompileUnit getCompileUnit() const{ 
+      assert (getVersion() <= LLVMDebugVersion10 && "Invalid getCompileUnit!");
      if (getVersion() == llvm::LLVMDebugVersion7)
        return getFieldAs<DICompileUnit>(6);

      DIFile F = getFieldAs<DIFile>(6); 
      return F.getCompileUnit();
    }
+    StringRef getFilename() const {
+      if (getVersion() <= llvm::LLVMDebugVersion10)
+        return getContext().getFilename();
+      return getFieldAs<DIFile>(6).getFilename();
+    } 
+    StringRef getDirectory() const {
+      if (getVersion() <= llvm::LLVMDebugVersion10)
+        return getContext().getDirectory();
+      return getFieldAs<DIFile>(6).getDirectory();
+
+    } 

    unsigned getLineNumber() const      { return getUnsignedField(7); }
    DIType getType() const              { return getFieldAs<DIType>(8); }
@@ -592,6 +622,7 @@ namespace llvm {
    DIScope getContext() const          { return getFieldAs<DIScope>(1); }
    StringRef getName() const           { return getStringField(2);     }
    DICompileUnit getCompileUnit() const{ 
+      assert (getVersion() <= LLVMDebugVersion10 && "Invalid getCompileUnit!");
      if (getVersion() == llvm::LLVMDebugVersion7)
        return getFieldAs<DICompileUnit>(3);

@@ -614,6 +645,8 @@ namespace llvm {
      return (getUnsignedField(6) & FlagArtificial) != 0;
    }

+    /// getInlinedAt - If this variable is inlined then return inline location.
+    MDNode *getInlinedAt() const;

    /// Verify - Verify that a variable descriptor is well formed.
    bool Verify() const;
@@ -628,7 +661,9 @@ namespace llvm {
    uint64_t getAddrElement(unsigned Idx) const {
      if (getVersion() <= llvm::LLVMDebugVersion8)
        return getUInt64Field(Idx+6);
-      return getUInt64Field(Idx+7);
+      if (getVersion() == llvm::LLVMDebugVersion9)
+        return getUInt64Field(Idx+7);
+      return getUInt64Field(Idx+8);
    }

    /// isBlockByrefVariable - Return true if the variable was declared as
@@ -644,6 +679,8 @@ namespace llvm {
    /// print - print variable.
    void print(raw_ostream &OS) const;

+    void printExtendedName(raw_ostream &OS) const;
+
    /// dump - print variable to dbgs() with a newline.
    void dump() const;
  };
@@ -665,6 +702,26 @@ namespace llvm {
    }
  };

+  /// DILexicalBlockFile - This is a wrapper for a lexical block with
+  /// a filename change.
+  class DILexicalBlockFile : public DIScope {
+  public:
+    explicit DILexicalBlockFile(const MDNode *N = 0) : DIScope(N) {}
+    DIScope getContext() const { return getScope().getContext(); }
+    unsigned getLineNumber() const { return getScope().getLineNumber(); }
+    unsigned getColumnNumber() const { return getScope().getColumnNumber(); }
+    StringRef getDirectory() const {
+      StringRef dir = getFieldAs<DIFile>(2).getDirectory();
+      return !dir.empty() ? dir : getContext().getDirectory();
+    }
+    StringRef getFilename() const {
+      StringRef filename = getFieldAs<DIFile>(2).getFilename();
+      assert(!filename.empty() && "Why'd you create this then?");
+      return filename;
+    }
+    DILexicalBlock getScope() const { return getFieldAs<DILexicalBlock>(1); }
+  };
+
  /// DINameSpace - A wrapper for a C++ style name space.
  class DINameSpace : public DIScope { 
  public:
@@ -678,6 +735,7 @@ namespace llvm {
      return getFieldAs<DIFile>(3).getFilename();
    }
    DICompileUnit getCompileUnit() const{ 
+      assert (getVersion() <= LLVMDebugVersion10 && "Invalid getCompileUnit!");
      if (getVersion() == llvm::LLVMDebugVersion7)
        return getFieldAs<DICompileUnit>(3);

@@ -708,13 +766,27 @@ namespace llvm {
  /// getDICompositeType - Find underlying composite type.
  DICompositeType getDICompositeType(DIType T);

+  /// isSubprogramContext - Return true if Context is either a subprogram
+  /// or another context nested inside a subprogram.
+  bool isSubprogramContext(const MDNode *Context);
+
  /// getOrInsertFnSpecificMDNode - Return a NameMDNode that is suitable
  /// to hold function specific information.
-  NamedMDNode *getOrInsertFnSpecificMDNode(Module &M, StringRef Name);
+  NamedMDNode *getOrInsertFnSpecificMDNode(Module &M, DISubprogram SP);

  /// getFnSpecificMDNode - Return a NameMDNode, if available, that is 
  /// suitable to hold function specific information.
-  NamedMDNode *getFnSpecificMDNode(const Module &M, StringRef Name);
+  NamedMDNode *getFnSpecificMDNode(const Module &M, DISubprogram SP);
+
+  /// createInlinedVariable - Create a new inlined variable based on current
+  /// variable.
+  /// @param DV            Current Variable.
+  /// @param InlinedScope  Location at current variable is inlined.
+  DIVariable createInlinedVariable(MDNode *DV, MDNode *InlinedScope,
+                                   LLVMContext &VMContext);
+
+  /// cleanseInlinedVariable - Remove inlined scope from the variable.
+  DIVariable cleanseInlinedVariable(MDNode *DV, LLVMContext &VMContext);

  class DebugInfoFinder {
  public:
@@ -23,7 +23,7 @@ class Type;
 class Value;

 class FindUsedTypes : public ModulePass {
-  SetVector<const Type *> UsedTypes;
+  SetVector<Type *> UsedTypes;
 public:
  static char ID; // Pass identification, replacement for typeid
  FindUsedTypes() : ModulePass(ID) {
@@ -33,7 +33,7 @@ public:
  /// getTypes - After the pass has been run, return the set containing all of
  /// the types used in the module.
  ///
-  const SetVector<const Type *> &getTypes() const { return UsedTypes; }
+  const SetVector<Type *> &getTypes() const { return UsedTypes; }

  /// Print the types found in the module.  If the optional Module parameter is
  /// passed in, then the types are printed symbolically if possible, using the
@@ -45,7 +45,7 @@ private:
  /// IncorporateType - Incorporate one type and all of its subtypes into the
  /// collection of used types.
  ///
-  void IncorporateType(const Type *Ty);
+  void IncorporateType(Type *Ty);

  /// IncorporateValue - Incorporate all of the types used by this value.
  ///
@@ -140,6 +140,8 @@ public:
  static char ID; // Pass ID, replacement for typeid
  IVUsers();

+  Loop *getLoop() const { return L; }
+
  /// AddUsersIfInteresting - Inspect the specified Instruction.  If it is a
  /// reducible SCEV, recursively add its users to the IVUsesByStride set and
  /// return true.  Otherwise, return false.
@@ -29,6 +29,7 @@ namespace llvm {
  class CallSite;
  template<class PtrType, unsigned SmallSize>
  class SmallPtrSet;
+  class TargetData;

  namespace InlineConstants {
    // Various magic constants used to adjust heuristics.
@@ -113,7 +114,7 @@ namespace llvm {

      /// analyzeFunction - Add information about the specified function
      /// to the current structure.
-      void analyzeFunction(Function *F);
+      void analyzeFunction(Function *F, const TargetData *TD);

      /// NeverInline - Returns true if the function should never be
      /// inlined into any caller.
@@ -124,11 +125,17 @@ namespace llvm {
    // the ValueMap will update itself when this happens.
    ValueMap<const Function *, FunctionInfo> CachedFunctionInfo;

+    // TargetData if available, or null.
+    const TargetData *TD;
+
    int CountBonusForConstant(Value *V, Constant *C = NULL);
    int ConstantFunctionBonus(CallSite CS, Constant *C);
    int getInlineSize(CallSite CS, Function *Callee);
    int getInlineBonuses(CallSite CS, Function *Callee);
  public:
+    InlineCostAnalyzer(): TD(0) {}
+
+    void setTargetData(const TargetData *TData) { TD = TData; }

    /// getInlineCost - The heuristic used to determine if we should inline the
    /// function call or not.
@@ -24,6 +24,8 @@ namespace llvm {
  class Instruction;
  class Value;
  class TargetData;
+  template<typename T>
+  class ArrayRef;

  /// SimplifyAddInst - Given operands for an Add, see if we can
  /// fold the result.  If not, this returns null.
@@ -121,9 +123,16 @@ namespace llvm {

  /// SimplifyGEPInst - Given operands for an GetElementPtrInst, see if we can
  /// fold the result.  If not, this returns null.
-  Value *SimplifyGEPInst(Value * const *Ops, unsigned NumOps,
+  Value *SimplifyGEPInst(ArrayRef<Value *> Ops,
                         const TargetData *TD = 0, const DominatorTree *DT = 0);

+  /// SimplifyInsertValueInst - Given operands for an InsertValueInst, see if we
+  /// can fold the result.  If not, this returns null.
+  Value *SimplifyInsertValueInst(Value *Agg, Value *Val,
+                                 ArrayRef<unsigned> Idxs,
+                                 const TargetData *TD = 0,
+                                 const DominatorTree *DT = 0);
+
  //=== Helper functions for higher up the class hierarchy.


@@ -33,6 +33,7 @@

 #include "llvm/Pass.h"
 #include "llvm/ADT/DenseMap.h"
+#include "llvm/ADT/DenseSet.h"
 #include "llvm/ADT/DepthFirstIterator.h"
 #include "llvm/ADT/GraphTraits.h"
 #include "llvm/ADT/SmallVector.h"
@@ -105,7 +106,7 @@ public:
    if (L == 0)    return false;
    return contains(L->getParentLoop());
  }
-    
+
  /// contains - Return true if the specified basic block is in this loop.
  ///
  bool contains(const BlockT *BB) const {
@@ -134,6 +135,11 @@ public:
  block_iterator block_begin() const { return Blocks.begin(); }
  block_iterator block_end() const { return Blocks.end(); }

+  /// getNumBlocks - Get the number of blocks in this loop in constant time.
+  unsigned getNumBlocks() const {
+    return Blocks.size();
+  }
+
  /// isLoopExiting - True if terminator in the block can branch to another
  /// block that is outside of the current loop.
  ///
@@ -479,12 +485,13 @@ public:
  }

  /// verifyLoop - Verify loop structure of this loop and all nested loops.
-  void verifyLoopNest() const {
+  void verifyLoopNest(DenseSet<const LoopT*> *Loops) const {
+    Loops->insert(static_cast<const LoopT *>(this));
    // Verify this loop.
    verifyLoop();
    // Verify the subloops.
    for (iterator I = begin(), E = end(); I != E; ++I)
-      (*I)->verifyLoopNest();
+      (*I)->verifyLoopNest(Loops);
  }

  void print(raw_ostream &OS, unsigned Depth = 0) const {
@@ -527,7 +534,7 @@ public:
  bool isLoopInvariant(Value *V) const;

  /// hasLoopInvariantOperands - Return true if all the operands of the
-  /// specified instruction are loop invariant. 
+  /// specified instruction are loop invariant.
  bool hasLoopInvariantOperands(Instruction *I) const;

  /// makeLoopInvariant - If the given value is an instruction inside of the
@@ -607,7 +614,7 @@ public:
  /// has a predecessor that is outside the loop.
  bool hasDedicatedExits() const;

-  /// getUniqueExitBlocks - Return all unique successor blocks of this loop. 
+  /// getUniqueExitBlocks - Return all unique successor blocks of this loop.
  /// These are the blocks _outside of the current loop_ which are branched to.
  /// This assumes that loop exits are in canonical form.
  ///
@@ -618,7 +625,7 @@ public:
  BasicBlock *getUniqueExitBlock() const;

  void dump() const;
-  
+
 private:
  friend class LoopInfoBase<BasicBlock, Loop>;
  explicit Loop(BasicBlock *BB) : LoopBase<BasicBlock, Loop>(BB) {}
@@ -635,13 +642,14 @@ class LoopInfoBase {
  DenseMap<BlockT *, LoopT *> BBMap;
  std::vector<LoopT *> TopLevelLoops;
  friend class LoopBase<BlockT, LoopT>;
+  friend class LoopInfo;

  void operator=(const LoopInfoBase &); // do not implement
  LoopInfoBase(const LoopInfo &);       // do not implement
 public:
  LoopInfoBase() { }
  ~LoopInfoBase() { releaseMemory(); }
-  
+
  void releaseMemory() {
    for (typename std::vector<LoopT *>::iterator I =
         TopLevelLoops.begin(), E = TopLevelLoops.end(); I != E; ++I)
@@ -650,7 +658,7 @@ public:
    BBMap.clear();                           // Reset internal state of analysis
    TopLevelLoops.clear();
  }
-  
+
  /// iterator/begin/end - The interface to the top-level loops in the current
  /// function.
  ///
@@ -658,7 +666,7 @@ public:
  iterator begin() const { return TopLevelLoops.begin(); }
  iterator end() const { return TopLevelLoops.end(); }
  bool empty() const { return TopLevelLoops.empty(); }
-  
+
  /// getLoopFor - Return the inner most loop that BB lives in.  If a basic
  /// block is in no loop (for example the entry node), null is returned.
  ///
@@ -667,13 +675,13 @@ public:
      BBMap.find(const_cast<BlockT*>(BB));
    return I != BBMap.end() ? I->second : 0;
  }
-  
+
  /// operator[] - same as getLoopFor...
  ///
  const LoopT *operator[](const BlockT *BB) const {
    return getLoopFor(BB);
  }
-  
+
  /// getLoopDepth - Return the loop nesting level of the specified block.  A
  /// depth of 0 means the block is not inside any loop.
  ///
@@ -687,7 +695,7 @@ public:
    const LoopT *L = getLoopFor(BB);
    return L && L->getHeader() == BB;
  }
-  
+
  /// removeLoop - This removes the specified top-level loop from this loop info
  /// object.  The loop is not deleted, as it will presumably be inserted into
  /// another loop.
@@ -698,16 +706,20 @@ public:
    TopLevelLoops.erase(TopLevelLoops.begin() + (I-begin()));
    return L;
  }
-  
+
  /// changeLoopFor - Change the top-level loop that contains BB to the
  /// specified loop.  This should be used by transformations that restructure
  /// the loop hierarchy tree.
  void changeLoopFor(BlockT *BB, LoopT *L) {
-    LoopT *&OldLoop = BBMap[BB];
-    assert(OldLoop && "Block not in a loop yet!");
-    OldLoop = L;
+    if (!L) {
+      typename DenseMap<BlockT *, LoopT *>::iterator I = BBMap.find(BB);
+      if (I != BBMap.end())
+        BBMap.erase(I);
+      return;
+    }
+    BBMap[BB] = L;
  }
-  
+
  /// changeTopLevelLoop - Replace the specified loop in the top-level loops
  /// list with the indicated loop.
  void changeTopLevelLoop(LoopT *OldLoop,
@@ -719,14 +731,14 @@ public:
    assert(NewLoop->ParentLoop == 0 && OldLoop->ParentLoop == 0 &&
           "Loops already embedded into a subloop!");
  }
-  
+
  /// addTopLevelLoop - This adds the specified loop to the collection of
  /// top-level loops.
  void addTopLevelLoop(LoopT *New) {
    assert(New->getParentLoop() == 0 && "Loop already in subloop!");
    TopLevelLoops.push_back(New);
  }
-  
+
  /// removeBlock - This method completely removes BB from all data structures,
  /// including all of the Loop objects it is nested in and our mapping from
  /// BasicBlocks to loops.
@@ -739,16 +751,16 @@ public:
      BBMap.erase(I);
    }
  }
-  
+
  // Internals
-  
+
  static bool isNotAlreadyContainedIn(const LoopT *SubLoop,
                                      const LoopT *ParentLoop) {
    if (SubLoop == 0) return true;
    if (SubLoop == ParentLoop) return false;
    return isNotAlreadyContainedIn(SubLoop->getParentLoop(), ParentLoop);
  }
-  
+
  void Calculate(DominatorTreeBase<BlockT> &DT) {
    BlockT *RootNode = DT.getRootNode()->getBlock();

@@ -757,7 +769,7 @@ public:
      if (LoopT *L = ConsiderForLoop(*NI, DT))
        TopLevelLoops.push_back(L);
  }
-  
+
  LoopT *ConsiderForLoop(BlockT *BB, DominatorTreeBase<BlockT> &DT) {
    if (BBMap.find(BB) != BBMap.end()) return 0;// Haven't processed this node?

@@ -812,9 +824,9 @@ public:

        // Normal case, add the block to our loop...
        L->Blocks.push_back(X);
-        
+
        typedef GraphTraits<Inverse<BlockT*> > InvBlockTraits;
-        
+
        // Add all of the predecessors of X to the end of the work stack...
        TodoStack.insert(TodoStack.end(), InvBlockTraits::child_begin(X),
                         InvBlockTraits::child_end(X));
@@ -878,7 +890,7 @@ public:

    return L;
  }
-  
+
  /// MoveSiblingLoopInto - This method moves the NewChild loop to live inside
  /// of the NewParent Loop, instead of being a sibling of it.
  void MoveSiblingLoopInto(LoopT *NewChild,
@@ -897,7 +909,7 @@ public:

    InsertLoopInto(NewChild, NewParent);
  }
-  
+
  /// InsertLoopInto - This inserts loop L into the specified parent loop.  If
  /// the parent loop contains a loop which should contain L, the loop gets
  /// inserted into L instead.
@@ -918,9 +930,9 @@ public:
    Parent->SubLoops.push_back(L);
    L->ParentLoop = Parent;
  }
-  
+
  // Debugging
-  
+
  void print(raw_ostream &OS) const {
    for (unsigned i = 0; i < TopLevelLoops.size(); ++i)
      TopLevelLoops[i]->print(OS);
@@ -990,7 +1002,7 @@ public:
  virtual void releaseMemory() { LI.releaseMemory(); }

  virtual void print(raw_ostream &O, const Module* M = 0) const;
-  
+
  virtual void getAnalysisUsage(AnalysisUsage &AU) const;

  /// removeLoop - This removes the specified top-level loop from this loop info
@@ -1024,6 +1036,12 @@ public:
    LI.removeBlock(BB);
  }

+  /// updateUnloop - Update LoopInfo after removing the last backedge from a
+  /// loop--now the "unloop". This updates the loop forest and parent loops for
+  /// each block so that Unloop is no longer referenced, but the caller must
+  /// actually delete the Unloop object.
+  void updateUnloop(Loop *Unloop);
+
  /// replacementPreservesLCSSAForm - Returns true if replacing From with To
  /// everywhere is guaranteed to preserve LCSSA form.
  bool replacementPreservesLCSSAForm(Instruction *From, Value *To) {
@@ -0,0 +1,186 @@
+//===--------- LoopIterator.h - Iterate over loop blocks --------*- C++ -*-===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+// This file defines iterators to visit the basic blocks within a loop.
+//
+// These iterators currently visit blocks within subloops as well.
+// Unfortunately we have no efficient way of summarizing loop exits which would
+// allow skipping subloops during traversal.
+//
+// If you want to visit all blocks in a loop and don't need an ordered traveral,
+// use Loop::block_begin() instead.
+//
+// This is intentionally designed to work with ill-formed loops in which the
+// backedge has been deleted. The only prerequisite is that all blocks
+// contained within the loop according to the most recent LoopInfo analysis are
+// reachable from the loop header.
+//===----------------------------------------------------------------------===//
+
+#ifndef LLVM_ANALYSIS_LOOP_ITERATOR_H
+#define LLVM_ANALYSIS_LOOP_ITERATOR_H
+
+#include "llvm/ADT/DepthFirstIterator.h"
+#include "llvm/ADT/PostOrderIterator.h"
+#include "llvm/Analysis/LoopInfo.h"
+
+namespace llvm {
+
+class LoopBlocksTraversal;
+
+/// Store the result of a depth first search within basic blocks contained by a
+/// single loop.
+///
+/// TODO: This could be generalized for any CFG region, or the entire CFG.
+class LoopBlocksDFS {
+public:
+  /// Postorder list iterators.
+  typedef std::vector<BasicBlock*>::const_iterator POIterator;
+  typedef std::vector<BasicBlock*>::const_reverse_iterator RPOIterator;
+
+  friend class LoopBlocksTraversal;
+
+private:
+  Loop *L;
+
+  /// Map each block to its postorder number. A block is only mapped after it is
+  /// preorder visited by DFS. It's postorder number is initially zero and set
+  /// to nonzero after it is finished by postorder traversal.
+  DenseMap<BasicBlock*, unsigned> PostNumbers;
+  std::vector<BasicBlock*> PostBlocks;
+
+public:
+  LoopBlocksDFS(Loop *Container) :
+    L(Container), PostNumbers(NextPowerOf2(Container->getNumBlocks())) {
+    PostBlocks.reserve(Container->getNumBlocks());
+  }
+
+  Loop *getLoop() const { return L; }
+
+  /// Traverse the loop blocks and store the DFS result.
+  void perform(LoopInfo *LI);
+
+  /// Return true if postorder numbers are assigned to all loop blocks.
+  bool isComplete() const { return PostBlocks.size() == L->getNumBlocks(); }
+
+  /// Iterate over the cached postorder blocks.
+  POIterator beginPostorder() const {
+    assert(isComplete() && "bad loop DFS");
+    return PostBlocks.begin();
+  }
+  POIterator endPostorder() const { return PostBlocks.end(); }
+
+  /// Reverse iterate over the cached postorder blocks.
+  RPOIterator beginRPO() const {
+    assert(isComplete() && "bad loop DFS");
+    return PostBlocks.rbegin();
+  }
+  RPOIterator endRPO() const { return PostBlocks.rend(); }
+
+  /// Return true if this block has been preorder visited.
+  bool hasPreorder(BasicBlock *BB) const { return PostNumbers.count(BB); }
+
+  /// Return true if this block has a postorder number.
+  bool hasPostorder(BasicBlock *BB) const {
+    DenseMap<BasicBlock*, unsigned>::const_iterator I = PostNumbers.find(BB);
+    return I != PostNumbers.end() && I->second;
+  }
+
+  /// Get a block's postorder number.
+  unsigned getPostorder(BasicBlock *BB) const {
+    DenseMap<BasicBlock*, unsigned>::const_iterator I = PostNumbers.find(BB);
+    assert(I != PostNumbers.end() && "block not visited by DFS");
+    assert(I->second && "block not finished by DFS");
+    return I->second;
+  }
+
+  /// Get a block's reverse postorder number.
+  unsigned getRPO(BasicBlock *BB) const {
+    return 1 + PostBlocks.size() - getPostorder(BB);
+  }
+
+  void clear() {
+    PostNumbers.clear();
+    PostBlocks.clear();
+  }
+};
+
+/// Traverse the blocks in a loop using a depth-first search.
+class LoopBlocksTraversal {
+public:
+  /// Graph traversal iterator.
+  typedef po_iterator<BasicBlock*, LoopBlocksTraversal, true> POTIterator;
+
+private:
+  LoopBlocksDFS &DFS;
+  LoopInfo *LI;
+
+public:
+  LoopBlocksTraversal(LoopBlocksDFS &Storage, LoopInfo *LInfo) :
+    DFS(Storage), LI(LInfo) {}
+
+  /// Postorder traversal over the graph. This only needs to be done once.
+  /// po_iterator "automatically" calls back to visitPreorder and
+  /// finishPostorder to record the DFS result.
+  POTIterator begin() {
+    assert(DFS.PostBlocks.empty() && "Need clear DFS result before traversing");
+    assert(DFS.L->getNumBlocks() && "po_iterator cannot handle an empty graph");
+    return po_ext_begin(DFS.L->getHeader(), *this);
+  }
+  POTIterator end() {
+    // po_ext_end interface requires a basic block, but ignores its value.
+    return po_ext_end(DFS.L->getHeader(), *this);
+  }
+
+  /// Called by po_iterator upon reaching a block via a CFG edge. If this block
+  /// is contained in the loop and has not been visited, then mark it preorder
+  /// visited and return true.
+  ///
+  /// TODO: If anyone is interested, we could record preorder numbers here.
+  bool visitPreorder(BasicBlock *BB) {
+    if (!DFS.L->contains(LI->getLoopFor(BB)))
+      return false;
+
+    return DFS.PostNumbers.insert(std::make_pair(BB, 0)).second;
+  }
+
+  /// Called by po_iterator each time it advances, indicating a block's
+  /// postorder.
+  void finishPostorder(BasicBlock *BB) {
+    assert(DFS.PostNumbers.count(BB) && "Loop DFS skipped preorder");
+    DFS.PostBlocks.push_back(BB);
+    DFS.PostNumbers[BB] = DFS.PostBlocks.size();
+  }
+
+  //===----------------------------------------------------------------------
+  // Implement part of the std::set interface for the purpose of driving the
+  // generic po_iterator.
+
+  /// Return true if the block is outside the loop or has already been visited.
+  /// Sorry if this is counterintuitive.
+  bool count(BasicBlock *BB) const {
+    return !DFS.L->contains(LI->getLoopFor(BB)) || DFS.PostNumbers.count(BB);
+  }
+
+  /// If this block is contained in the loop and has not been visited, return
+  /// true and assign a preorder number. This is a proxy for visitPreorder
+  /// called by POIterator.
+  bool insert(BasicBlock *BB) {
+    return visitPreorder(BB);
+  }
+};
+
+/// Specialize DFSetTraits to record postorder numbers.
+template<> struct DFSetTraits<LoopBlocksTraversal> {
+  static void finishPostorder(BasicBlock *BB, LoopBlocksTraversal& LBT) {
+    LBT.finishPostorder(BB);
+  }
+};
+
+} // End namespace llvm
+
+#endif
@@ -84,7 +84,7 @@ public:
 class LPPassManager : public FunctionPass, public PMDataManager {
 public:
  static char ID;
-  explicit LPPassManager(int Depth);
+  explicit LPPassManager();

  /// run - Execute all of the passes scheduled for execution.  Keep track of
  /// whether any of the passes modifies the module, and if so, return true.
@@ -51,14 +51,14 @@ const CallInst *isArrayMalloc(const Value *I, const TargetData *TD);
 ///   0: PointerType is the malloc calls' return type.
 ///   1: PointerType is the bitcast's result type.
 ///  >1: Unique PointerType cannot be determined, return NULL.
-const PointerType *getMallocType(const CallInst *CI);
+PointerType *getMallocType(const CallInst *CI);

 /// getMallocAllocatedType - Returns the Type allocated by malloc call.
 /// The Type depends on the number of bitcast uses of the malloc call:
 ///   0: PointerType is the malloc calls' return type.
 ///   1: PointerType is the bitcast's result type.
 ///  >1: Unique PointerType cannot be determined, return NULL.
-const Type *getMallocAllocatedType(const CallInst *CI);
+Type *getMallocAllocatedType(const CallInst *CI);

 /// getMallocArraySize - Returns the array size of a malloc call.  If the 
 /// argument passed to malloc is a multiple of the size of the malloced type,
@@ -52,9 +52,6 @@ namespace llvm {
      ///   1. Loads are clobbered by may-alias stores.
      ///   2. Loads are considered clobbered by partially-aliased loads.  The
      ///      client may choose to analyze deeper into these cases.
-      ///
-      /// A dependence query on the first instruction of the entry block will
-      /// return a clobber(self) result.
      Clobber,

      /// Def - This is a dependence on the specified instruction which
@@ -76,11 +73,27 @@ namespace llvm {
      ///      operands to the calls are the same.
      Def,
      
+      /// Other - This marker indicates that the query has no known dependency
+      /// in the specified block.  More detailed state info is encoded in the
+      /// upper part of the pair (i.e. the Instruction*)
+      Other
+    };
+    /// If DepType is "Other", the upper part of the pair
+    /// (i.e. the Instruction* part) is instead used to encode more detailed
+    /// type information as follows
+    enum OtherType {
      /// NonLocal - This marker indicates that the query has no dependency in
      /// the specified block.  To find out more, the client should query other
      /// predecessor blocks.
-      NonLocal
+      NonLocal = 0x4,
+      /// NonFuncLocal - This marker indicates that the query has no
+      /// dependency in the specified function.
+      NonFuncLocal = 0x8,
+      /// Unknown - This marker indicates that the query dependency
+      /// is unknown.
+      Unknown = 0xc
    };
+
    typedef PointerIntPair<Instruction*, 2, DepType> PairTy;
    PairTy Value;
    explicit MemDepResult(PairTy V) : Value(V) {}
@@ -98,19 +111,21 @@ namespace llvm {
      return MemDepResult(PairTy(Inst, Clobber));
    }
    static MemDepResult getNonLocal() {
-      return MemDepResult(PairTy(0, NonLocal));
+      return MemDepResult(
+        PairTy(reinterpret_cast<Instruction*>(NonLocal), Other));
+    }
+    static MemDepResult getNonFuncLocal() {
+      return MemDepResult(
+        PairTy(reinterpret_cast<Instruction*>(NonFuncLocal), Other));
    }
    static MemDepResult getUnknown() {
-      return MemDepResult(PairTy(0, Clobber));
+      return MemDepResult(
+        PairTy(reinterpret_cast<Instruction*>(Unknown), Other));
    }

    /// isClobber - Return true if this MemDepResult represents a query that is
    /// a instruction clobber dependency.
-    bool isClobber() const { return Value.getInt() == Clobber && getInst(); }
-
-    /// isUnknown - Return true if this MemDepResult represents a query which
-    /// cannot and/or will not be computed.
-    bool isUnknown() const { return Value.getInt() == Clobber && !getInst(); }
+    bool isClobber() const { return Value.getInt() == Clobber; }

    /// isDef - Return true if this MemDepResult represents a query that is
    /// a instruction definition dependency.
@@ -119,11 +134,31 @@ namespace llvm {
    /// isNonLocal - Return true if this MemDepResult represents a query that
    /// is transparent to the start of the block, but where a non-local hasn't
    /// been done.
-    bool isNonLocal() const { return Value.getInt() == NonLocal; }
+    bool isNonLocal() const {
+      return Value.getInt() == Other
+        && Value.getPointer() == reinterpret_cast<Instruction*>(NonLocal);
+    }
+
+    /// isNonFuncLocal - Return true if this MemDepResult represents a query
+    /// that is transparent to the start of the function.
+    bool isNonFuncLocal() const {
+      return Value.getInt() == Other
+        && Value.getPointer() == reinterpret_cast<Instruction*>(NonFuncLocal);
+    }
    
+    /// isUnknown - Return true if this MemDepResult represents a query which
+    /// cannot and/or will not be computed.
+    bool isUnknown() const {
+      return Value.getInt() == Other
+        && Value.getPointer() == reinterpret_cast<Instruction*>(Unknown);
+    }
+
    /// getInst() - If this is a normal dependency, return the instruction that
    /// is depended on.  Otherwise, return null.
-    Instruction *getInst() const { return Value.getPointer(); }
+    Instruction *getInst() const {
+      if (Value.getInt() == Other) return NULL;
+      return Value.getPointer();
+    }
    
    bool operator==(const MemDepResult &M) const { return Value == M.Value; }
    bool operator!=(const MemDepResult &M) const { return Value != M.Value; }
@@ -88,7 +88,7 @@ class RGPassManager : public FunctionPass, public PMDataManager {

 public:
  static char ID;
-  explicit RGPassManager(int Depth);
+  explicit RGPassManager();

  /// @brief Execute all of the passes scheduled for execution.
  ///
@@ -103,7 +103,7 @@ namespace llvm {

    /// getType - Return the LLVM type of this SCEV expression.
    ///
-    const Type *getType() const;
+    Type *getType() const;

    /// isZero - Return true if the expression is a constant zero.
    ///
@@ -241,31 +241,94 @@ namespace llvm {
    ///
    ValueExprMapType ValueExprMap;

+    /// ExitLimit - Information about the number of loop iterations for
+    /// which a loop exit's branch condition evaluates to the not-taken path.
+    /// This is a temporary pair of exact and max expressions that are
+    /// eventually summarized in ExitNotTakenInfo and BackedgeTakenInfo.
+    struct ExitLimit {
+      const SCEV *Exact;
+      const SCEV *Max;
+
+      /*implicit*/ ExitLimit(const SCEV *E) : Exact(E), Max(E) {}
+
+      ExitLimit(const SCEV *E, const SCEV *M) : Exact(E), Max(M) {}
+
+      /// hasAnyInfo - Test whether this ExitLimit contains any computed
+      /// information, or whether it's all SCEVCouldNotCompute values.
+      bool hasAnyInfo() const {
+        return !isa<SCEVCouldNotCompute>(Exact) ||
+          !isa<SCEVCouldNotCompute>(Max);
+      }
+    };
+
+    /// ExitNotTakenInfo - Information about the number of times a particular
+    /// loop exit may be reached before exiting the loop.
+    struct ExitNotTakenInfo {
+      AssertingVH<BasicBlock> ExitingBlock;
+      const SCEV *ExactNotTaken;
+      PointerIntPair<ExitNotTakenInfo*, 1> NextExit;
+
+      ExitNotTakenInfo() : ExitingBlock(0), ExactNotTaken(0) {}
+
+      /// isCompleteList - Return true if all loop exits are computable.
+      bool isCompleteList() const {
+        return NextExit.getInt() == 0;
+      }
+
+      void setIncomplete() { NextExit.setInt(1); }
+
+      /// getNextExit - Return a pointer to the next exit's not-taken info.
+      ExitNotTakenInfo *getNextExit() const {
+        return NextExit.getPointer();
+      }
+
+      void setNextExit(ExitNotTakenInfo *ENT) { NextExit.setPointer(ENT); }
+    };
+
    /// BackedgeTakenInfo - Information about the backedge-taken count
    /// of a loop. This currently includes an exact count and a maximum count.
    ///
-    struct BackedgeTakenInfo {
-      /// Exact - An expression indicating the exact backedge-taken count of
-      /// the loop if it is known, or a SCEVCouldNotCompute otherwise.
-      const SCEV *Exact;
+    class BackedgeTakenInfo {
+      /// ExitNotTaken - A list of computable exits and their not-taken counts.
+      /// Loops almost never have more than one computable exit.
+      ExitNotTakenInfo ExitNotTaken;

      /// Max - An expression indicating the least maximum backedge-taken
      /// count of the loop that is known, or a SCEVCouldNotCompute.
      const SCEV *Max;

-      /*implicit*/ BackedgeTakenInfo(const SCEV *exact) :
-        Exact(exact), Max(exact) {}
+    public:
+      BackedgeTakenInfo() : Max(0) {}

-      BackedgeTakenInfo(const SCEV *exact, const SCEV *max) :
-        Exact(exact), Max(max) {}
+      /// Initialize BackedgeTakenInfo from a list of exact exit counts.
+      BackedgeTakenInfo(
+        SmallVectorImpl< std::pair<BasicBlock *, const SCEV *> > &ExitCounts,
+        bool Complete, const SCEV *MaxCount);

      /// hasAnyInfo - Test whether this BackedgeTakenInfo contains any
      /// computed information, or whether it's all SCEVCouldNotCompute
      /// values.
      bool hasAnyInfo() const {
-        return !isa<SCEVCouldNotCompute>(Exact) ||
-               !isa<SCEVCouldNotCompute>(Max);
+        return ExitNotTaken.ExitingBlock || !isa<SCEVCouldNotCompute>(Max);
      }
+
+      /// getExact - Return an expression indicating the exact backedge-taken
+      /// count of the loop if it is known, or SCEVCouldNotCompute
+      /// otherwise. This is the number of times the loop header can be
+      /// guaranteed to execute, minus one.
+      const SCEV *getExact(ScalarEvolution *SE) const;
+
+      /// getExact - Return the number of times this loop exit may fall through
+      /// to the back edge, or SCEVCouldNotCompute. The loop is guaranteed not
+      /// to exit via this block before this number of iterations, but may exit
+      /// via another block.
+      const SCEV *getExact(BasicBlock *ExitingBlock, ScalarEvolution *SE) const;
+
+      /// getMax - Get the max backedge taken count for the loop.
+      const SCEV *getMax(ScalarEvolution *SE) const;
+
+      /// clear - Invalidate this result and free associated memory.
+      void clear();
    };

    /// BackedgeTakenCounts - Cache the backedge-taken count of the loops for
@@ -365,64 +428,59 @@ namespace llvm {
    /// loop will iterate.
    BackedgeTakenInfo ComputeBackedgeTakenCount(const Loop *L);

-    /// ComputeBackedgeTakenCountFromExit - Compute the number of times the
-    /// backedge of the specified loop will execute if it exits via the
-    /// specified block.
-    BackedgeTakenInfo ComputeBackedgeTakenCountFromExit(const Loop *L,
-                                                      BasicBlock *ExitingBlock);
+    /// ComputeExitLimit - Compute the number of times the backedge of the
+    /// specified loop will execute if it exits via the specified block.
+    ExitLimit ComputeExitLimit(const Loop *L, BasicBlock *ExitingBlock);

-    /// ComputeBackedgeTakenCountFromExitCond - Compute the number of times the
-    /// backedge of the specified loop will execute if its exit condition
-    /// were a conditional branch of ExitCond, TBB, and FBB.
-    BackedgeTakenInfo
-      ComputeBackedgeTakenCountFromExitCond(const Loop *L,
-                                            Value *ExitCond,
-                                            BasicBlock *TBB,
-                                            BasicBlock *FBB);
+    /// ComputeExitLimitFromCond - Compute the number of times the backedge of
+    /// the specified loop will execute if its exit condition were a conditional
+    /// branch of ExitCond, TBB, and FBB.
+    ExitLimit ComputeExitLimitFromCond(const Loop *L,
+                                       Value *ExitCond,
+                                       BasicBlock *TBB,
+                                       BasicBlock *FBB);

-    /// ComputeBackedgeTakenCountFromExitCondICmp - Compute the number of
-    /// times the backedge of the specified loop will execute if its exit
-    /// condition were a conditional branch of the ICmpInst ExitCond, TBB,
-    /// and FBB.
-    BackedgeTakenInfo
-      ComputeBackedgeTakenCountFromExitCondICmp(const Loop *L,
-                                                ICmpInst *ExitCond,
-                                                BasicBlock *TBB,
-                                                BasicBlock *FBB);
+    /// ComputeExitLimitFromICmp - Compute the number of times the backedge of
+    /// the specified loop will execute if its exit condition were a conditional
+    /// branch of the ICmpInst ExitCond, TBB, and FBB.
+    ExitLimit ComputeExitLimitFromICmp(const Loop *L,
+                                       ICmpInst *ExitCond,
+                                       BasicBlock *TBB,
+                                       BasicBlock *FBB);

-    /// ComputeLoadConstantCompareBackedgeTakenCount - Given an exit condition
+    /// ComputeLoadConstantCompareExitLimit - Given an exit condition
    /// of 'icmp op load X, cst', try to see if we can compute the
    /// backedge-taken count.
-    BackedgeTakenInfo
-      ComputeLoadConstantCompareBackedgeTakenCount(LoadInst *LI,
-                                                   Constant *RHS,
-                                                   const Loop *L,
-                                                   ICmpInst::Predicate p);
+    ExitLimit ComputeLoadConstantCompareExitLimit(LoadInst *LI,
+                                                  Constant *RHS,
+                                                  const Loop *L,
+                                                  ICmpInst::Predicate p);

-    /// ComputeBackedgeTakenCountExhaustively - If the loop is known to execute
-    /// a constant number of times (the condition evolves only from constants),
+    /// ComputeExitCountExhaustively - If the loop is known to execute a
+    /// constant number of times (the condition evolves only from constants),
    /// try to evaluate a few iterations of the loop until we get the exit
    /// condition gets a value of ExitWhen (true or false).  If we cannot
-    /// evaluate the backedge-taken count of the loop, return CouldNotCompute.
-    const SCEV *ComputeBackedgeTakenCountExhaustively(const Loop *L,
-                                                      Value *Cond,
-                                                      bool ExitWhen);
+    /// evaluate the exit count of the loop, return CouldNotCompute.
+    const SCEV *ComputeExitCountExhaustively(const Loop *L,
+                                             Value *Cond,
+                                             bool ExitWhen);

-    /// HowFarToZero - Return the number of times a backedge comparing the
-    /// specified value to zero will execute.  If not computable, return
+    /// HowFarToZero - Return the number of times an exit condition comparing
+    /// the specified value to zero will execute.  If not computable, return
    /// CouldNotCompute.
-    BackedgeTakenInfo HowFarToZero(const SCEV *V, const Loop *L);
+    ExitLimit HowFarToZero(const SCEV *V, const Loop *L);

-    /// HowFarToNonZero - Return the number of times a backedge checking the
-    /// specified value for nonzero will execute.  If not computable, return
+    /// HowFarToNonZero - Return the number of times an exit condition checking
+    /// the specified value for nonzero will execute.  If not computable, return
    /// CouldNotCompute.
-    BackedgeTakenInfo HowFarToNonZero(const SCEV *V, const Loop *L);
+    ExitLimit HowFarToNonZero(const SCEV *V, const Loop *L);

-    /// HowManyLessThans - Return the number of times a backedge containing the
-    /// specified less-than comparison will execute.  If not computable, return
-    /// CouldNotCompute. isSigned specifies whether the less-than is signed.
-    BackedgeTakenInfo HowManyLessThans(const SCEV *LHS, const SCEV *RHS,
-                                       const Loop *L, bool isSigned);
+    /// HowManyLessThans - Return the number of times an exit condition
+    /// containing the specified less-than comparison will execute.  If not
+    /// computable, return CouldNotCompute. isSigned specifies whether the
+    /// less-than is signed.
+    ExitLimit HowManyLessThans(const SCEV *LHS, const SCEV *RHS,
+                               const Loop *L, bool isSigned);

    /// getPredecessorWithUniqueSuccessorForBB - Return a predecessor of BB
    /// (which may not be an immediate predecessor) which has exactly one
@@ -450,7 +508,8 @@ namespace llvm {
    /// FoundLHS, and FoundRHS is true.
    bool isImpliedCondOperandsHelper(ICmpInst::Predicate Pred,
                                     const SCEV *LHS, const SCEV *RHS,
-                                     const SCEV *FoundLHS, const SCEV *FoundRHS);
+                                     const SCEV *FoundLHS,
+                                     const SCEV *FoundRHS);

    /// getConstantEvolutionLoopExitValue - If we know that the specified Phi is
    /// in the header of its containing loop, we know the loop executes a
@@ -479,17 +538,17 @@ namespace llvm {
    /// the SCEV framework. This primarily includes integer types, and it
    /// can optionally include pointer types if the ScalarEvolution class
    /// has access to target-specific information.
-    bool isSCEVable(const Type *Ty) const;
+    bool isSCEVable(Type *Ty) const;

    /// getTypeSizeInBits - Return the size in bits of the specified type,
    /// for which isSCEVable must return true.
-    uint64_t getTypeSizeInBits(const Type *Ty) const;
+    uint64_t getTypeSizeInBits(Type *Ty) const;

    /// getEffectiveSCEVType - Return a type with the same bitwidth as
    /// the given type and which represents how SCEV will treat the given
    /// type, for which isSCEVable must return true. For pointer types,
    /// this is the pointer-sized integer type.
-    const Type *getEffectiveSCEVType(const Type *Ty) const;
+    Type *getEffectiveSCEVType(Type *Ty) const;

    /// getSCEV - Return a SCEV expression for the full generality of the
    /// specified expression.
@@ -497,11 +556,11 @@ namespace llvm {

    const SCEV *getConstant(ConstantInt *V);
    const SCEV *getConstant(const APInt& Val);
-    const SCEV *getConstant(const Type *Ty, uint64_t V, bool isSigned = false);
-    const SCEV *getTruncateExpr(const SCEV *Op, const Type *Ty);
-    const SCEV *getZeroExtendExpr(const SCEV *Op, const Type *Ty);
-    const SCEV *getSignExtendExpr(const SCEV *Op, const Type *Ty);
-    const SCEV *getAnyExtendExpr(const SCEV *Op, const Type *Ty);
+    const SCEV *getConstant(Type *Ty, uint64_t V, bool isSigned = false);
+    const SCEV *getTruncateExpr(const SCEV *Op, Type *Ty);
+    const SCEV *getZeroExtendExpr(const SCEV *Op, Type *Ty);
+    const SCEV *getSignExtendExpr(const SCEV *Op, Type *Ty);
+    const SCEV *getAnyExtendExpr(const SCEV *Op, Type *Ty);
    const SCEV *getAddExpr(SmallVectorImpl<const SCEV *> &Ops,
                           SCEV::NoWrapFlags Flags = SCEV::FlagAnyWrap);
    const SCEV *getAddExpr(const SCEV *LHS, const SCEV *RHS,
@@ -529,6 +588,14 @@ namespace llvm {
      Ops.push_back(RHS);
      return getMulExpr(Ops, Flags);
    }
+    const SCEV *getMulExpr(const SCEV *Op0, const SCEV *Op1, const SCEV *Op2,
+                           SCEV::NoWrapFlags Flags = SCEV::FlagAnyWrap) {
+      SmallVector<const SCEV *, 3> Ops;
+      Ops.push_back(Op0);
+      Ops.push_back(Op1);
+      Ops.push_back(Op2);
+      return getMulExpr(Ops, Flags);
+    }
    const SCEV *getUDivExpr(const SCEV *LHS, const SCEV *RHS);
    const SCEV *getAddRecExpr(const SCEV *Start, const SCEV *Step,
                              const Loop *L, SCEV::NoWrapFlags Flags);
@@ -550,19 +617,19 @@ namespace llvm {

    /// getSizeOfExpr - Return an expression for sizeof on the given type.
    ///
-    const SCEV *getSizeOfExpr(const Type *AllocTy);
+    const SCEV *getSizeOfExpr(Type *AllocTy);

    /// getAlignOfExpr - Return an expression for alignof on the given type.
    ///
-    const SCEV *getAlignOfExpr(const Type *AllocTy);
+    const SCEV *getAlignOfExpr(Type *AllocTy);

    /// getOffsetOfExpr - Return an expression for offsetof on the given field.
    ///
-    const SCEV *getOffsetOfExpr(const StructType *STy, unsigned FieldNo);
+    const SCEV *getOffsetOfExpr(StructType *STy, unsigned FieldNo);

    /// getOffsetOfExpr - Return an expression for offsetof on the given field.
    ///
-    const SCEV *getOffsetOfExpr(const Type *CTy, Constant *FieldNo);
+    const SCEV *getOffsetOfExpr(Type *CTy, Constant *FieldNo);

    /// getNegativeSCEV - Return the SCEV object corresponding to -V.
    ///
@@ -579,33 +646,33 @@ namespace llvm {
    /// getTruncateOrZeroExtend - Return a SCEV corresponding to a conversion
    /// of the input value to the specified type.  If the type must be
    /// extended, it is zero extended.
-    const SCEV *getTruncateOrZeroExtend(const SCEV *V, const Type *Ty);
+    const SCEV *getTruncateOrZeroExtend(const SCEV *V, Type *Ty);

    /// getTruncateOrSignExtend - Return a SCEV corresponding to a conversion
    /// of the input value to the specified type.  If the type must be
    /// extended, it is sign extended.
-    const SCEV *getTruncateOrSignExtend(const SCEV *V, const Type *Ty);
+    const SCEV *getTruncateOrSignExtend(const SCEV *V, Type *Ty);

    /// getNoopOrZeroExtend - Return a SCEV corresponding to a conversion of
    /// the input value to the specified type.  If the type must be extended,
    /// it is zero extended.  The conversion must not be narrowing.
-    const SCEV *getNoopOrZeroExtend(const SCEV *V, const Type *Ty);
+    const SCEV *getNoopOrZeroExtend(const SCEV *V, Type *Ty);

    /// getNoopOrSignExtend - Return a SCEV corresponding to a conversion of
    /// the input value to the specified type.  If the type must be extended,
    /// it is sign extended.  The conversion must not be narrowing.
-    const SCEV *getNoopOrSignExtend(const SCEV *V, const Type *Ty);
+    const SCEV *getNoopOrSignExtend(const SCEV *V, Type *Ty);

    /// getNoopOrAnyExtend - Return a SCEV corresponding to a conversion of
    /// the input value to the specified type. If the type must be extended,
    /// it is extended with unspecified bits. The conversion must not be
    /// narrowing.
-    const SCEV *getNoopOrAnyExtend(const SCEV *V, const Type *Ty);
+    const SCEV *getNoopOrAnyExtend(const SCEV *V, Type *Ty);

    /// getTruncateOrNoop - Return a SCEV corresponding to a conversion of the
    /// input value to the specified type.  The conversion must not be
    /// widening.
-    const SCEV *getTruncateOrNoop(const SCEV *V, const Type *Ty);
+    const SCEV *getTruncateOrNoop(const SCEV *V, Type *Ty);

    /// getUMaxFromMismatchedTypes - Promote the operands to the wider of
    /// the types using zero-extension, and then perform a umax operation
@@ -653,6 +720,23 @@ namespace llvm {
    bool isLoopBackedgeGuardedByCond(const Loop *L, ICmpInst::Predicate Pred,
                                     const SCEV *LHS, const SCEV *RHS);

+    /// getSmallConstantTripCount - Returns the maximum trip count of this loop
+    /// as a normal unsigned value, if possible. Returns 0 if the trip count is
+    /// unknown or not constant.
+    unsigned getSmallConstantTripCount(Loop *L, BasicBlock *ExitBlock);
+
+    /// getSmallConstantTripMultiple - Returns the largest constant divisor of
+    /// the trip count of this loop as a normal unsigned value, if
+    /// possible. This means that the actual trip count is always a multiple of
+    /// the returned value (don't forget the trip count could very well be zero
+    /// as well!).
+    unsigned getSmallConstantTripMultiple(Loop *L, BasicBlock *ExitBlock);
+
+    // getExitCount - Get the expression for the number of loop iterations for
+    // which this loop is guaranteed not to exit via ExitingBlock. Otherwise
+    // return SCEVCouldNotCompute.
+    const SCEV *getExitCount(Loop *L, BasicBlock *ExitingBlock);
+
    /// getBackedgeTakenCount - If the specified loop has a predictable
    /// backedge-taken count, return it, otherwise return a SCEVCouldNotCompute
    /// object. The backedge-taken count is the number of times the loop header
@@ -64,16 +64,34 @@ namespace llvm {
    /// in a more literal form.
    bool CanonicalMode;

+    /// When invoked from LSR, the expander is in "strength reduction" mode. The
+    /// only difference is that phi's are only reused if they are already in
+    /// "expanded" form.
+    bool LSRMode;
+
    typedef IRBuilder<true, TargetFolder> BuilderType;
    BuilderType Builder;

+#ifndef NDEBUG
+    const char *DebugType;
+#endif
+
    friend struct SCEVVisitor<SCEVExpander, Value*>;

  public:
    /// SCEVExpander - Construct a SCEVExpander in "canonical" mode.
    explicit SCEVExpander(ScalarEvolution &se, const char *name)
      : SE(se), IVName(name), IVIncInsertLoop(0), IVIncInsertPos(0),
-        CanonicalMode(true), Builder(se.getContext(), TargetFolder(se.TD)) {}
+        CanonicalMode(true), LSRMode(false),
+        Builder(se.getContext(), TargetFolder(se.TD)) {
+#ifndef NDEBUG
+      DebugType = "";
+#endif
+    }
+
+#ifndef NDEBUG
+    void setDebugType(const char* s) { DebugType = s; }
+#endif

    /// clear - Erase the contents of the InsertedExpressions map so that users
    /// trying to expand the same expression into multiple BasicBlocks or
@@ -88,13 +106,21 @@ namespace llvm {
    /// canonical induction variable of the specified type for the specified
    /// loop (inserting one if there is none).  A canonical induction variable
    /// starts at zero and steps by one on each iteration.
-    PHINode *getOrInsertCanonicalInductionVariable(const Loop *L,
-                                                   const Type *Ty);
+    PHINode *getOrInsertCanonicalInductionVariable(const Loop *L, Type *Ty);
+
+    /// hoistStep - Utility for hoisting an IV increment.
+    static bool hoistStep(Instruction *IncV, Instruction *InsertPos,
+                          const DominatorTree *DT);
+
+    /// replaceCongruentIVs - replace congruent phis with their most canonical
+    /// representative. Return the number of phis eliminated.
+    unsigned replaceCongruentIVs(Loop *L, const DominatorTree *DT,
+                                 SmallVectorImpl<WeakVH> &DeadInsts);

    /// expandCodeFor - Insert code to directly compute the specified SCEV
    /// expression into the program.  The inserted code is inserted into the
    /// specified block.
-    Value *expandCodeFor(const SCEV *SH, const Type *Ty, Instruction *I);
+    Value *expandCodeFor(const SCEV *SH, Type *Ty, Instruction *I);

    /// setIVIncInsertPos - Set the current IV increment loop and position.
    void setIVIncInsertPos(const Loop *L, Instruction *Pos) {
@@ -127,13 +153,14 @@ namespace llvm {
    /// is useful for late optimization passes.
    void disableCanonicalMode() { CanonicalMode = false; }

+    void enableLSRMode() { LSRMode = true; }
+
    /// clearInsertPoint - Clear the current insertion point. This is useful
    /// if the instruction that had been serving as the insertion point may
    /// have been deleted.
    void clearInsertPoint() {
      Builder.ClearInsertionPoint();
    }
-
  private:
    LLVMContext &getContext() const { return SE.getContext(); }

@@ -145,20 +172,20 @@ namespace llvm {
    /// reusing an existing cast if a suitable one exists, moving an existing
    /// cast if a suitable one exists but isn't in the right place, or
    /// or creating a new one.
-    Value *ReuseOrCreateCast(Value *V, const Type *Ty,
+    Value *ReuseOrCreateCast(Value *V, Type *Ty,
                             Instruction::CastOps Op,
                             BasicBlock::iterator IP);

    /// InsertNoopCastOfTo - Insert a cast of V to the specified type,
    /// which must be possible with a noop cast, doing what we can to
    /// share the casts.
-    Value *InsertNoopCastOfTo(Value *V, const Type *Ty);
+    Value *InsertNoopCastOfTo(Value *V, Type *Ty);

    /// expandAddToGEP - Expand a SCEVAddExpr with a pointer type into a GEP
    /// instead of using ptrtoint+arithmetic+inttoptr.
    Value *expandAddToGEP(const SCEV *const *op_begin,
                          const SCEV *const *op_end,
-                          const PointerType *PTy, const Type *Ty, Value *V);
+                          PointerType *PTy, Type *Ty, Value *V);

    Value *expand(const SCEV *S);

@@ -166,7 +193,7 @@ namespace llvm {
    /// expression into the program.  The inserted code is inserted into the
    /// SCEVExpander's current insertion point. If a type is specified, the
    /// result will be expanded to have that type, with a cast if necessary.
-    Value *expandCodeFor(const SCEV *SH, const Type *Ty = 0);
+    Value *expandCodeFor(const SCEV *SH, Type *Ty = 0);

    /// isInsertedInstruction - Return true if the specified instruction was
    /// inserted by the code rewriter.  If so, the client should not modify the
@@ -208,11 +235,15 @@ namespace llvm {

    void restoreInsertPoint(BasicBlock *BB, BasicBlock::iterator I);

+    bool isNormalAddRecExprPHI(PHINode *PN, Instruction *IncV, const Loop *L);
+
+    bool isExpandedAddRecExprPHI(PHINode *PN, Instruction *IncV, const Loop *L);
+
    Value *expandAddRecExprLiterally(const SCEVAddRecExpr *);
    PHINode *getAddRecExprPHILiterally(const SCEVAddRecExpr *Normalized,
                                       const Loop *L,
-                                       const Type *ExpandTy,
-                                       const Type *IntTy);
+                                       Type *ExpandTy,
+                                       Type *IntTy);
  };
 }

@@ -42,7 +42,7 @@ namespace llvm {
  public:
    ConstantInt *getValue() const { return V; }

-    const Type *getType() const { return V->getType(); }
+    Type *getType() const { return V->getType(); }

    /// Methods for support type inquiry through isa, cast, and dyn_cast:
    static inline bool classof(const SCEVConstant *S) { return true; }
@@ -57,14 +57,14 @@ namespace llvm {
  class SCEVCastExpr : public SCEV {
  protected:
    const SCEV *Op;
-    const Type *Ty;
+    Type *Ty;

    SCEVCastExpr(const FoldingSetNodeIDRef ID,
-                 unsigned SCEVTy, const SCEV *op, const Type *ty);
+                 unsigned SCEVTy, const SCEV *op, Type *ty);

  public:
    const SCEV *getOperand() const { return Op; }
-    const Type *getType() const { return Ty; }
+    Type *getType() const { return Ty; }

    /// Methods for support type inquiry through isa, cast, and dyn_cast:
    static inline bool classof(const SCEVCastExpr *S) { return true; }
@@ -83,7 +83,7 @@ namespace llvm {
    friend class ScalarEvolution;

    SCEVTruncateExpr(const FoldingSetNodeIDRef ID,
-                     const SCEV *op, const Type *ty);
+                     const SCEV *op, Type *ty);

  public:
    /// Methods for support type inquiry through isa, cast, and dyn_cast:
@@ -101,7 +101,7 @@ namespace llvm {
    friend class ScalarEvolution;

    SCEVZeroExtendExpr(const FoldingSetNodeIDRef ID,
-                       const SCEV *op, const Type *ty);
+                       const SCEV *op, Type *ty);

  public:
    /// Methods for support type inquiry through isa, cast, and dyn_cast:
@@ -119,7 +119,7 @@ namespace llvm {
    friend class ScalarEvolution;

    SCEVSignExtendExpr(const FoldingSetNodeIDRef ID,
-                       const SCEV *op, const Type *ty);
+                       const SCEV *op, Type *ty);

  public:
    /// Methods for support type inquiry through isa, cast, and dyn_cast:
@@ -158,7 +158,7 @@ namespace llvm {
    op_iterator op_begin() const { return Operands; }
    op_iterator op_end() const { return Operands + NumOperands; }

-    const Type *getType() const { return getOperand(0)->getType(); }
+    Type *getType() const { return getOperand(0)->getType(); }

    NoWrapFlags getNoWrapFlags(NoWrapFlags Mask = NoWrapMask) const {
      return (NoWrapFlags)(SubclassData & Mask);
@@ -214,7 +214,7 @@ namespace llvm {
    }

  public:
-    const Type *getType() const {
+    Type *getType() const {
      // Use the type of the last operand, which is likely to be a pointer
      // type, if there is one. This doesn't usually matter, but it can help
      // reduce casts when the expressions are expanded.
@@ -263,7 +263,7 @@ namespace llvm {
    const SCEV *getLHS() const { return LHS; }
    const SCEV *getRHS() const { return RHS; }

-    const Type *getType() const {
+    Type *getType() const {
      // In most cases the types of LHS and RHS will be the same, but in some
      // crazy cases one or the other may be a pointer. ScalarEvolution doesn't
      // depend on the type for correctness, but handling types carefully can
@@ -441,11 +441,11 @@ namespace llvm {
    /// folded with other operations into something unrecognizable. This
    /// is mainly only useful for pretty-printing and other situations
    /// where it isn't absolutely required for these to succeed.
-    bool isSizeOf(const Type *&AllocTy) const;
-    bool isAlignOf(const Type *&AllocTy) const;
-    bool isOffsetOf(const Type *&STy, Constant *&FieldNo) const;
+    bool isSizeOf(Type *&AllocTy) const;
+    bool isAlignOf(Type *&AllocTy) const;
+    bool isOffsetOf(Type *&STy, Constant *&FieldNo) const;

-    const Type *getType() const { return getValPtr()->getType(); }
+    Type *getType() const { return getValPtr()->getType(); }

    /// Methods for support type inquiry through isa, cast, and dyn_cast:
    static inline bool classof(const SCEVUnknown *S) { return true; }
@@ -39,7 +39,7 @@ public:
  /// Argument ctor - If Function argument is specified, this argument is
  /// inserted at the end of the argument list for the function.
  ///
-  explicit Argument(const Type *Ty, const Twine &Name = "", Function *F = 0);
+  explicit Argument(Type *Ty, const Twine &Name = "", Function *F = 0);

  inline const Function *getParent() const { return Parent; }
  inline       Function *getParent()       { return Parent; }
@@ -65,8 +65,7 @@ const Attributes StackAlignment  = 7<<26; ///< Alignment of stack for
                                          ///of alignment with +1 bias
                                          ///0 means unaligned (different from
                                          ///alignstack(1))
-const Attributes Hotpatch    = 1<<29;     ///< Function should have special
-                                          ///'hotpatch' sequence in prologue
+const Attributes ReturnsTwice    = 1<<29; ///< Function can return twice
 const Attributes UWTable     = 1<<30;     ///< Function must be in a unwind
                                          ///table
 const Attributes NonLazyBind = 1U<<31;    ///< Function is called early and/or
@@ -93,7 +92,7 @@ const Attributes ParameterOnly = ByVal | Nest | StructRet | NoCapture;
 const Attributes FunctionOnly = NoReturn | NoUnwind | ReadNone | ReadOnly |
  NoInline | AlwaysInline | OptimizeForSize | StackProtect | StackProtectReq |
  NoRedZone | NoImplicitFloat | Naked | InlineHint | StackAlignment |
-  Hotpatch | UWTable | NonLazyBind;
+  UWTable | NonLazyBind | ReturnsTwice;

 /// @brief Parameter attributes that do not apply to vararg call arguments.
 const Attributes VarArgsIncompatible = StructRet;
@@ -107,7 +106,7 @@ const Attributes MutuallyIncompatible[4] = {
 };

 /// @brief Which attributes cannot be applied to a type.
-Attributes typeIncompatible(const Type *Ty);
+Attributes typeIncompatible(Type *Ty);

 /// This turns an int alignment (a power of 2, normally) into the
 /// form used internally in Attributes.
@@ -43,6 +43,10 @@ namespace llvm {
  /// This function checks debug info intrinsics. If an intrinsic is invalid
  /// then this function simply removes the intrinsic. 
  void CheckDebugInfoIntrinsics(Module *M);
+  
+  /// This function upgrades the old pre-3.0 exception handling system to the
+  /// new one. N.B. This will be removed in 3.1.
+  void UpgradeExceptionHandling(Module *M);
 } // End llvm namespace

 #endif
@@ -22,6 +22,7 @@

 namespace llvm {

+class LandingPadInst;
 class TerminatorInst;
 class LLVMContext;
 class BlockAddress;
@@ -144,6 +145,14 @@ public:
    return const_cast<BasicBlock*>(this)->getFirstNonPHIOrDbgOrLifetime();
  }

+  /// getFirstInsertionPt - Returns an iterator to the first instruction in this
+  /// block that is suitable for inserting a non-PHI instruction. In particular,
+  /// it skips all PHIs and LandingPad instructions.
+  iterator getFirstInsertionPt();
+  const_iterator getFirstInsertionPt() const {
+    return const_cast<BasicBlock*>(this)->getFirstInsertionPt();
+  }
+
  /// removeFromParent - This method unlinks 'this' from the containing
  /// function, but does not delete it.
  ///
@@ -258,6 +267,14 @@ public:
  /// to refer to basic block New instead of to us.
  void replaceSuccessorsPhiUsesWith(BasicBlock *New);

+  /// isLandingPad - Return true if this basic block is a landing pad. I.e.,
+  /// it's the destination of the 'unwind' edge of an invoke instruction.
+  bool isLandingPad() const;
+
+  /// getLandingPadInst() - Return the landingpad instruction associated with
+  /// the landing pad.
+  LandingPadInst *getLandingPadInst();
+
 private:
  /// AdjustBlockAddressRefCount - BasicBlock stores the number of BlockAddress
  /// objects using it.  This is almost always 0, sometimes one, possibly but
@@ -205,6 +205,23 @@ namespace bitc {
    BINOP_XOR  = 12
  };

+  /// These are values used in the bitcode files to encode AtomicRMW operations.
+  /// The values of these enums have no fixed relation to the LLVM IR enum
+  /// values.  Changing these will break compatibility with old files.
+  enum RMWOperations {
+    RMW_XCHG = 0,
+    RMW_ADD = 1,
+    RMW_SUB = 2,
+    RMW_AND = 3,
+    RMW_NAND = 4,
+    RMW_OR = 5,
+    RMW_XOR = 6,
+    RMW_MAX = 7,
+    RMW_MIN = 8,
+    RMW_UMAX = 9,
+    RMW_UMIN = 10
+  };
+
  /// OverflowingBinaryOperatorOptionalFlags - Flags for serializing
  /// OverflowingBinaryOperator's SubclassOptionalData contents.
  enum OverflowingBinaryOperatorOptionalFlags {
@@ -218,6 +235,23 @@ namespace bitc {
    PEO_EXACT = 0
  };

+  /// Encoded AtomicOrdering values.
+  enum AtomicOrderingCodes {
+    ORDERING_NOTATOMIC = 0,
+    ORDERING_UNORDERED = 1,
+    ORDERING_MONOTONIC = 2,
+    ORDERING_ACQUIRE = 3,
+    ORDERING_RELEASE = 4,
+    ORDERING_ACQREL = 5,
+    ORDERING_SEQCST = 6
+  };
+
+  /// Encoded SynchronizationScope values.
+  enum AtomicSynchScopeCodes {
+    SYNCHSCOPE_SINGLETHREAD = 0,
+    SYNCHSCOPE_CROSSTHREAD = 1
+  };
+
  // The function body block (FUNCTION_BLOCK_ID) describes function bodies.  It
  // can contain a constant block (CONSTANTS_BLOCK_ID).
  enum FunctionCodes {
@@ -266,7 +300,19 @@ namespace bitc {

    FUNC_CODE_INST_CALL        = 34, // CALL:       [attr, fnty, fnid, args...]

-    FUNC_CODE_DEBUG_LOC        = 35  // DEBUG_LOC:  [Line,Col,ScopeVal, IAVal]
+    FUNC_CODE_DEBUG_LOC        = 35, // DEBUG_LOC:  [Line,Col,ScopeVal, IAVal]
+    FUNC_CODE_INST_FENCE       = 36, // FENCE: [ordering, synchscope]
+    FUNC_CODE_INST_CMPXCHG     = 37, // CMPXCHG: [ptrty,ptr,cmp,new, align, vol,
+                                     //           ordering, synchscope]
+    FUNC_CODE_INST_ATOMICRMW   = 38, // ATOMICRMW: [ptrty,ptr,val, operation,
+                                     //             align, vol,
+                                     //             ordering, synchscope]
+    FUNC_CODE_INST_RESUME      = 39, // RESUME:     [opval]
+    FUNC_CODE_INST_LANDINGPAD  = 40, // LANDINGPAD: [ty,val,val,num,id0,val0...]
+    FUNC_CODE_INST_LOADATOMIC  = 41, // LOAD: [opty, op, align, vol,
+                                     //        ordering, synchscope]
+    FUNC_CODE_INST_STOREATOMIC = 42  // STORE: [ptrty,ptr,val, align, vol
+                                     //         ordering, synchscope]
  };
 } // End bitc namespace
 } // End llvm namespace
@@ -33,12 +33,12 @@ class SelectionDAG;
 /// of insertvalue or extractvalue indices that identify a member, return
 /// the linearized index of the start of the member.
 ///
-unsigned ComputeLinearIndex(const Type *Ty,
+unsigned ComputeLinearIndex(Type *Ty,
                            const unsigned *Indices,
                            const unsigned *IndicesEnd,
                            unsigned CurIndex = 0);

-inline unsigned ComputeLinearIndex(const Type *Ty,
+inline unsigned ComputeLinearIndex(Type *Ty,
                                   ArrayRef<unsigned> Indices,
                                   unsigned CurIndex = 0) {
  return ComputeLinearIndex(Ty, Indices.begin(), Indices.end(), CurIndex);
@@ -51,7 +51,7 @@ inline unsigned ComputeLinearIndex(const Type *Ty,
 /// If Offsets is non-null, it points to a vector to be filled in
 /// with the in-memory offsets of each of the individual values.
 ///
-void ComputeValueVTs(const TargetLowering &TLI, const Type *Ty,
+void ComputeValueVTs(const TargetLowering &TLI, Type *Ty,
                     SmallVectorImpl<EVT> &ValueVTs,
                     SmallVectorImpl<uint64_t> *Offsets = 0,
                     uint64_t StartingOffset = 0);
@@ -49,11 +49,6 @@ namespace llvm {
                   const MachineLoopInfo &loops) :
      MF(mf), LIS(lis), Loops(loops) {}

-    /// CalculateRegClass - recompute the register class for reg from its uses.
-    /// Since the register class can affect the allocation hint, this function
-    /// should be called before CalculateWeightAndHint if both are called.
-    void CalculateRegClass(unsigned reg);
-
    /// CalculateWeightAndHint - (re)compute li's spill weight and allocation
    /// hint.
    void CalculateWeightAndHint(LiveInterval &li);
@@ -54,8 +54,18 @@ protected:
  const TargetInstrInfo &TII;
  const TargetLowering &TLI;
  const TargetRegisterInfo &TRI;
+
+  /// The position of the last instruction for materializing constants
+  /// for use in the current block. It resets to EmitStartPt when it
+  /// makes sense (for example, it's usually profitable to avoid function
+  /// calls between the definition and the use)
  MachineInstr *LastLocalValue;

+  /// The top most instruction in the current block that is allowed for
+  /// emitting local variables. LastLocalValue resets to EmitStartPt when
+  /// it makes sense (for example, on function calls)
+  MachineInstr *EmitStartPt;
+
 public:
  /// getLastLocalValue - Return the position of the last instruction
  /// emitted for materializing constants for use in the current block.
@@ -63,7 +73,10 @@ public:

  /// setLastLocalValue - Update the position of the last instruction
  /// emitted for materializing constants for use in the current block.
-  void setLastLocalValue(MachineInstr *I) { LastLocalValue = I; }
+  void setLastLocalValue(MachineInstr *I) {
+    EmitStartPt = I;
+    LastLocalValue = I;
+  }

  /// startNewBlock - Set the current block to which generated machine
  /// instructions will be appended, and clear the local CSE map.
@@ -358,6 +371,11 @@ private:
  /// be materialized with new instructions.
  unsigned materializeRegForValue(const Value *V, MVT VT);

+  /// flushLocalValueMap - clears LocalValueMap and moves the area for the
+  /// new local variables to the beginning of the block. It helps to avoid
+  /// spilling cached variables across heavy instructions like calls.
+  void flushLocalValueMap();
+
  /// hasTrivialKill - Test whether the given value has exactly one use.
  bool hasTrivialKill(const Value *V) const;
 };
@@ -19,6 +19,7 @@
 #include "llvm/Instructions.h"
 #include "llvm/ADT/APInt.h"
 #include "llvm/ADT/DenseMap.h"
+#include "llvm/ADT/DenseSet.h"
 #include "llvm/ADT/IndexedMap.h"
 #include "llvm/ADT/SmallVector.h"
 #ifndef NDEBUG
@@ -139,7 +140,7 @@ public:

  unsigned CreateReg(EVT VT);
  
-  unsigned CreateRegs(const Type *Ty);
+  unsigned CreateRegs(Type *Ty);
  
  unsigned InitializeRegForValue(const Value *V) {
    unsigned &R = ValueMap[V];
@@ -198,12 +199,12 @@ public:
    LiveOutRegInfo[Reg].IsValid = false;
  }

-  /// setByValArgumentFrameIndex - Record frame index for the byval
+  /// setArgumentFrameIndex - Record frame index for the byval
  /// argument.
-  void setByValArgumentFrameIndex(const Argument *A, int FI);
+  void setArgumentFrameIndex(const Argument *A, int FI);
  
-  /// getByValArgumentFrameIndex - Get frame index for the byval argument.
-  int getByValArgumentFrameIndex(const Argument *A);
+  /// getArgumentFrameIndex - Get frame index for the byval argument.
+  int getArgumentFrameIndex(const Argument *A);

 private:
  /// LiveOutRegInfo - Information about live out vregs.
@@ -220,6 +221,11 @@ void AddCatchInfo(const CallInst &I,
 void CopyCatchInfo(const BasicBlock *SuccBB, const BasicBlock *LPad,
                   MachineModuleInfo *MMI, FunctionLoweringInfo &FLI);

+/// AddLandingPadInfo - Extract the exception handling information from the
+/// landingpad instruction and add them to the specified machine module info.
+void AddLandingPadInfo(const LandingPadInst &I, MachineModuleInfo &MMI,
+                       MachineBasicBlock *MBB);
+
 } // end namespace llvm

 #endif
@@ -95,7 +95,7 @@ namespace ISD {
    // execution to HANDLER. Many platform-related details also :)
    EH_RETURN,

-    // OUTCHAIN = EH_SJLJ_SETJMP(INCHAIN, buffer)
+    // RESULT, OUTCHAIN = EH_SJLJ_SETJMP(INCHAIN, buffer)
    // This corresponds to the eh.sjlj.setjmp intrinsic.
    // It takes an input chain and a pointer to the jump buffer as inputs
    // and returns an outchain.
@@ -323,6 +323,12 @@ namespace ISD {
    // i1 then the high bits must conform to getBooleanContents.
    SELECT,

+    // Select with a vector condition (op #0) and two vector operands (ops #1
+    // and #2), returning a vector result.  All vectors have the same length.
+    // Much like the scalar select and setcc, each bit in the condition selects
+    // whether the corresponding result element is taken from op #1 or op #2.
+    VSELECT,
+
    // Select with condition operator - This selects between a true value and
    // a false value (ops #2 and #3) based on the boolean result of comparing
    // the lhs and rhs (ops #0 and #1) of a conditional expression with the
@@ -333,16 +339,10 @@ namespace ISD {
    // true.  If the result value type is not i1 then the high bits conform
    // to getBooleanContents.  The operands to this are the left and right
    // operands to compare (ops #0, and #1) and the condition code to compare
-    // them with (op #2) as a CondCodeSDNode.
+    // them with (op #2) as a CondCodeSDNode. If the operands are vector types
+    // then the result type must also be a vector type.
    SETCC,

-    // RESULT = VSETCC(LHS, RHS, COND) operator - This evaluates to a vector of
-    // integer elements with all bits of the result elements set to true if the
-    // comparison is true or all cleared if the comparison is false.  The
-    // operands to this are the left and right operands to compare (LHS/RHS) and
-    // the condition code to compare them with (COND) as a CondCodeSDNode.
-    VSETCC,
-
    // SHL_PARTS/SRA_PARTS/SRL_PARTS - These operators are used for expanded
    // integer shift operations, just like ADD/SUB_PARTS.  The operation
    // ordering is:
@@ -566,14 +566,19 @@ namespace ISD {
    // HANDLENODE node - Used as a handle for various purposes.
    HANDLENODE,

-    // TRAMPOLINE - This corresponds to the init_trampoline intrinsic.
-    // It takes as input a token chain, the pointer to the trampoline,
-    // the pointer to the nested function, the pointer to pass for the
-    // 'nest' parameter, a SRCVALUE for the trampoline and another for
-    // the nested function (allowing targets to access the original
-    // Function*).  It produces the result of the intrinsic and a token
-    // chain as output.
-    TRAMPOLINE,
+    // INIT_TRAMPOLINE - This corresponds to the init_trampoline intrinsic.  It
+    // takes as input a token chain, the pointer to the trampoline, the pointer
+    // to the nested function, the pointer to pass for the 'nest' parameter, a
+    // SRCVALUE for the trampoline and another for the nested function (allowing
+    // targets to access the original Function*).  It produces a token chain as
+    // output.
+    INIT_TRAMPOLINE,
+
+    // ADJUST_TRAMPOLINE - This corresponds to the adjust_trampoline intrinsic.
+    // It takes a pointer to the trampoline and produces a (possibly) new
+    // pointer to the same trampoline with platform-specific adjustments
+    // applied.  The pointer it returns points to an executable block of code.
+    ADJUST_TRAMPOLINE,

    // TRAP - Trapping instruction
    TRAP,
@@ -592,22 +597,27 @@ namespace ISD {
    // and produces an output chain.
    MEMBARRIER,

+    // OUTCHAIN = ATOMIC_FENCE(INCHAIN, ordering, scope)
+    // This corresponds to the fence instruction. It takes an input chain, and
+    // two integer constants: an AtomicOrdering and a SynchronizationScope.
+    ATOMIC_FENCE,
+
+    // Val, OUTCHAIN = ATOMIC_LOAD(INCHAIN, ptr)
+    // This corresponds to "load atomic" instruction.
+    ATOMIC_LOAD,
+
+    // OUTCHAIN = ATOMIC_LOAD(INCHAIN, ptr, val)
+    // This corresponds to "store atomic" instruction.
+    ATOMIC_STORE,
+
    // Val, OUTCHAIN = ATOMIC_CMP_SWAP(INCHAIN, ptr, cmp, swap)
-    // this corresponds to the atomic.lcs intrinsic.
-    // cmp is compared to *ptr, and if equal, swap is stored in *ptr.
-    // the return is always the original value in *ptr
+    // This corresponds to the cmpxchg instruction.
    ATOMIC_CMP_SWAP,

    // Val, OUTCHAIN = ATOMIC_SWAP(INCHAIN, ptr, amt)
-    // this corresponds to the atomic.swap intrinsic.
-    // amt is stored to *ptr atomically.
-    // the return is always the original value in *ptr
-    ATOMIC_SWAP,
-
    // Val, OUTCHAIN = ATOMIC_LOAD_[OpName](INCHAIN, ptr, amt)
-    // this corresponds to the atomic.load.[OpName] intrinsic.
-    // op(*ptr, amt) is stored to *ptr atomically.
-    // the return is always the original value in *ptr
+    // These correspond to the atomicrmw instruction.
+    ATOMIC_SWAP,
    ATOMIC_LOAD_ADD,
    ATOMIC_LOAD_SUB,
    ATOMIC_LOAD_AND,
@@ -0,0 +1,248 @@
+//===- LexicalScopes.cpp - Collecting lexical scope info -*- C++ -*--------===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+//
+// This file implements LexicalScopes analysis.
+//
+// This pass collects lexical scope information and maps machine instructions
+// to respective lexical scopes.
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef LLVM_CODEGEN_LEXICALSCOPES_H
+#define LLVM_CODEGEN_LEXICALSCOPES_H
+
+#include "llvm/Metadata.h"
+#include "llvm/ADT/ArrayRef.h"
+#include "llvm/ADT/DenseMap.h"
+#include "llvm/ADT/SmallPtrSet.h"
+#include "llvm/ADT/SmallVector.h"
+#include "llvm/Support/DebugLoc.h"
+#include "llvm/Support/ValueHandle.h"
+#include <utility>
+namespace llvm {
+
+class MachineInstr;
+class MachineBasicBlock;
+class MachineFunction;
+class LexicalScope;
+
+//===----------------------------------------------------------------------===//
+/// InsnRange - This is used to track range of instructions with identical
+/// lexical scope.
+///
+typedef std::pair<const MachineInstr *, const MachineInstr *> InsnRange;
+
+//===----------------------------------------------------------------------===//
+/// LexicalScopes -  This class provides interface to collect and use lexical
+/// scoping information from machine instruction.
+///
+class LexicalScopes {
+public:
+  LexicalScopes() : MF(NULL),  CurrentFnLexicalScope(NULL) { }
+  virtual ~LexicalScopes();
+
+  /// initialize - Scan machine function and constuct lexical scope nest.
+  virtual void initialize(const MachineFunction &);
+
+  /// releaseMemory - release memory.
+  virtual void releaseMemory();
+  
+  /// empty - Return true if there is any lexical scope information available.
+  bool empty() { return CurrentFnLexicalScope == NULL; }
+
+  /// isCurrentFunctionScope - Return true if given lexical scope represents 
+  /// current function.
+  bool isCurrentFunctionScope(const LexicalScope *LS) { 
+    return LS == CurrentFnLexicalScope;
+  }
+
+  /// getCurrentFunctionScope - Return lexical scope for the current function.
+  LexicalScope *getCurrentFunctionScope() const { return CurrentFnLexicalScope;}
+
+  /// getMachineBasicBlocks - Populate given set using machine basic blocks
+  /// which have machine instructions that belong to lexical scope identified by
+  /// DebugLoc.
+  void getMachineBasicBlocks(DebugLoc DL,
+                             SmallPtrSet<const MachineBasicBlock*, 4> &MBBs);
+
+  /// dominates - Return true if DebugLoc's lexical scope dominates at least one
+  /// machine instruction's lexical scope in a given machine basic block.
+  bool dominates(DebugLoc DL, MachineBasicBlock *MBB);
+
+  /// findLexicalScope - Find lexical scope, either regular or inlined, for the
+  /// given DebugLoc. Return NULL if not found.
+  LexicalScope *findLexicalScope(DebugLoc DL);
+
+  /// getAbstractScopesList - Return a reference to list of abstract scopes.
+  ArrayRef<LexicalScope *> getAbstractScopesList() const {
+    return AbstractScopesList;
+  }
+
+  /// findAbstractScope - Find an abstract scope or return NULL.
+  LexicalScope *findAbstractScope(const MDNode *N) {
+    return AbstractScopeMap.lookup(N);
+  }
+
+  /// findInlinedScope - Find an inlined scope for the given DebugLoc or return
+  /// NULL.
+  LexicalScope *findInlinedScope(DebugLoc DL) {
+    return InlinedLexicalScopeMap.lookup(DL);
+  }
+
+  /// findLexicalScope - Find regular lexical scope or return NULL.
+  LexicalScope *findLexicalScope(const MDNode *N) {
+    return LexicalScopeMap.lookup(N);
+  }
+
+  /// dump - Print data structures to dbgs().
+  void dump();
+
+private:
+
+  /// getOrCreateLexicalScope - Find lexical scope for the given DebugLoc. If
+  /// not available then create new lexical scope.
+  LexicalScope *getOrCreateLexicalScope(DebugLoc DL);
+
+  /// getOrCreateRegularScope - Find or create a regular lexical scope.
+  LexicalScope *getOrCreateRegularScope(MDNode *Scope);
+
+  /// getOrCreateInlinedScope - Find or create an inlined lexical scope.
+  LexicalScope *getOrCreateInlinedScope(MDNode *Scope, MDNode *InlinedAt);
+
+  /// getOrCreateAbstractScope - Find or create an abstract lexical scope.
+  LexicalScope *getOrCreateAbstractScope(const MDNode *N);
+
+  /// extractLexicalScopes - Extract instruction ranges for each lexical scopes
+  /// for the given machine function.
+  void extractLexicalScopes(SmallVectorImpl<InsnRange> &MIRanges,
+                            DenseMap<const MachineInstr *, LexicalScope *> &M);
+  void constructScopeNest(LexicalScope *Scope);
+  void assignInstructionRanges(SmallVectorImpl<InsnRange> &MIRanges,
+                             DenseMap<const MachineInstr *, LexicalScope *> &M);
+
+private:
+  const MachineFunction *MF;
+
+  /// LexicalScopeMap - Tracks the scopes in the current function.  Owns the
+  /// contained LexicalScope*s.
+  DenseMap<const MDNode *, LexicalScope *> LexicalScopeMap;
+
+  /// InlinedLexicalScopeMap - Tracks inlined function scopes in current function.
+  DenseMap<DebugLoc, LexicalScope *> InlinedLexicalScopeMap;
+
+  /// AbstractScopeMap - These scopes are  not included LexicalScopeMap.  
+  /// AbstractScopes owns its LexicalScope*s.
+  DenseMap<const MDNode *, LexicalScope *> AbstractScopeMap;
+
+  /// AbstractScopesList - Tracks abstract scopes constructed while processing
+  /// a function. 
+  SmallVector<LexicalScope *, 4>AbstractScopesList;
+
+  /// CurrentFnLexicalScope - Top level scope for the current function.
+  ///
+  LexicalScope *CurrentFnLexicalScope;
+};
+
+//===----------------------------------------------------------------------===//
+/// LexicalScope - This class is used to track scope information.
+///
+class LexicalScope {
+
+public:
+  LexicalScope(LexicalScope *P, const MDNode *D, const MDNode *I, bool A)
+    : Parent(P), Desc(D), InlinedAtLocation(I), AbstractScope(A),
+      LastInsn(0), FirstInsn(0), DFSIn(0), DFSOut(0), IndentLevel(0) {
+    if (Parent)
+      Parent->addChild(this);
+  }
+
+  virtual ~LexicalScope() {}
+
+  // Accessors.
+  LexicalScope *getParent() const               { return Parent; }
+  const MDNode *getDesc() const                 { return Desc; }
+  const MDNode *getInlinedAt() const            { return InlinedAtLocation; }
+  const MDNode *getScopeNode() const            { return Desc; }
+  bool isAbstractScope() const                  { return AbstractScope; }
+  SmallVector<LexicalScope *, 4> &getChildren() { return Children; }
+  SmallVector<InsnRange, 4> &getRanges()        { return Ranges; }
+
+  /// addChild - Add a child scope.
+  void addChild(LexicalScope *S) { Children.push_back(S); }
+
+  /// openInsnRange - This scope covers instruction range starting from MI.
+  void openInsnRange(const MachineInstr *MI) {
+    if (!FirstInsn)
+      FirstInsn = MI;
+
+    if (Parent)
+      Parent->openInsnRange(MI);
+  }
+
+  /// extendInsnRange - Extend the current instruction range covered by
+  /// this scope.
+  void extendInsnRange(const MachineInstr *MI) {
+    assert (FirstInsn && "MI Range is not open!");
+    LastInsn = MI;
+    if (Parent)
+      Parent->extendInsnRange(MI);
+  }
+
+  /// closeInsnRange - Create a range based on FirstInsn and LastInsn collected
+  /// until now. This is used when a new scope is encountered while walking
+  /// machine instructions.
+  void closeInsnRange(LexicalScope *NewScope = NULL) {
+    assert (LastInsn && "Last insn missing!");
+    Ranges.push_back(InsnRange(FirstInsn, LastInsn));
+    FirstInsn = NULL;
+    LastInsn = NULL;
+    // If Parent dominates NewScope then do not close Parent's instruction
+    // range.
+    if (Parent && (!NewScope || !Parent->dominates(NewScope)))
+      Parent->closeInsnRange(NewScope);
+  }
+
+  /// dominates - Return true if current scope dominsates given lexical scope.
+  bool dominates(const LexicalScope *S) const {
+    if (S == this)
+      return true;
+    if (DFSIn < S->getDFSIn() && DFSOut > S->getDFSOut())
+      return true;
+    return false;
+  }
+
+  // Depth First Search support to walk and manipulate LexicalScope hierarchy.
+  unsigned getDFSOut() const            { return DFSOut; }
+  void setDFSOut(unsigned O)            { DFSOut = O; }
+  unsigned getDFSIn() const             { return DFSIn; }
+  void setDFSIn(unsigned I)             { DFSIn = I; }
+
+  /// dump - print lexical scope.
+  void dump() const;
+
+private:
+  LexicalScope *Parent;                          // Parent to this scope.
+  AssertingVH<const MDNode> Desc;                // Debug info descriptor.
+  AssertingVH<const MDNode> InlinedAtLocation;   // Location at which this 
+                                                 // scope is inlined.
+  bool AbstractScope;                            // Abstract Scope
+  SmallVector<LexicalScope *, 4> Children;       // Scopes defined in scope.  
+                                                 // Contents not owned.
+  SmallVector<InsnRange, 4> Ranges;
+
+  const MachineInstr *LastInsn;       // Last instruction of this scope.
+  const MachineInstr *FirstInsn;      // First instruction of this scope.
+  unsigned DFSIn, DFSOut;             // In & Out Depth use to determine
+                                      // scope nesting.
+  mutable unsigned IndentLevel;       // Private state for dump()
+};
+
+} // end llvm namespace
+
+#endif
@@ -100,6 +100,7 @@ namespace llvm {
    bool isDefByCopy() const { return copy != 0; }

    /// Returns true if one or more kills are PHI nodes.
+    /// Obsolete, do not use!
    bool hasPHIKill() const { return flags & HAS_PHI_KILL; }
    /// Set the PHI kill flag on this value.
    void setHasPHIKill(bool hasKill) {
@@ -313,7 +314,6 @@ namespace llvm {

    /// RenumberValues - Renumber all values in order of appearance and remove
    /// unused values.
-    /// Recalculate phi-kill flags in case any phi-def values were removed.
    void RenumberValues(LiveIntervals &lis);

    /// isOnlyLROfValNo - Return true if the specified live range is the only
@@ -411,6 +411,14 @@ namespace llvm {
      return I == end() ? 0 : I->valno;
    }

+    /// getVNInfoBefore - Return the VNInfo that is live up to but not
+    /// necessarilly including Idx, or NULL. Use this to find the reaching def
+    /// used by an instruction at this SlotIndex position.
+    VNInfo *getVNInfoBefore(SlotIndex Idx) const {
+      const_iterator I = FindLiveRangeContaining(Idx.getPrevSlot());
+      return I == end() ? 0 : I->valno;
+    }
+
    /// FindLiveRangeContaining - Return an iterator to the live range that
    /// contains the specified index, or end() if there is none.
    iterator FindLiveRangeContaining(SlotIndex Idx) {
@@ -452,10 +460,10 @@ namespace llvm {
      addRangeFrom(LR, ranges.begin());
    }

-    /// extendInBlock - If this interval is live before UseIdx in the basic
-    /// block that starts at StartIdx, extend it to be live at UseIdx and return
-    /// the value. If there is no live range before UseIdx, return NULL.
-    VNInfo *extendInBlock(SlotIndex StartIdx, SlotIndex UseIdx);
+    /// extendInBlock - If this interval is live before Kill in the basic block
+    /// that starts at StartIdx, extend it to be live up to Kill, and return
+    /// the value. If there is no live range before Kill, return NULL.
+    VNInfo *extendInBlock(SlotIndex StartIdx, SlotIndex Kill);

    /// join - Join two live intervals (this, and other) together.  This applies
    /// mappings to the value numbers in the LHS/RHS intervals as specified.  If
@@ -25,6 +25,8 @@
 namespace llvm {

  class LiveStacks : public MachineFunctionPass {
+    const TargetRegisterInfo *TRI;
+
    /// Special pool allocator for VNInfo's (LiveInterval val#).
    ///
    VNInfo::Allocator VNInfoAllocator;
@@ -231,6 +231,7 @@ public:
    }

    assert(Removed && "Register is not used by this instruction!");
+    (void)Removed;
    return true;
  }

@@ -265,6 +266,7 @@ public:
      }
    }
    assert(Removed && "Register is not defined by this instruction!");
+    (void)Removed;
    return true;
  }
  
@@ -232,7 +232,7 @@ public:

  /// setIsLandingPad - Indicates the block is a landing pad.  That is
  /// this basic block is entered via an exception handler.
-  void setIsLandingPad() { IsLandingPad = true; }
+  void setIsLandingPad(bool V = true) { IsLandingPad = V; }

  /// getLandingPadSuccessor - If this block has a successor that is a landing
  /// pad, return it. Otherwise return NULL.
@@ -1,4 +1,4 @@
-//====----- MachineBlockFrequency.h - MachineBlock Frequency Analysis ----====//
+//====----- MachineBlockFrequencyInfo.h - MachineBlock Frequency Analysis ----====//
 //
 //                     The LLVM Compiler Infrastructure
 //
@@ -11,10 +11,11 @@
 //
 //===----------------------------------------------------------------------===//

-#ifndef LLVM_CODEGEN_MACHINEBLOCKFREQUENCY_H
-#define LLVM_CODEGEN_MACHINEBLOCKFREQUENCY_H
+#ifndef LLVM_CODEGEN_MACHINEBLOCKFREQUENCYINFO_H
+#define LLVM_CODEGEN_MACHINEBLOCKFREQUENCYINFO_H

 #include "llvm/CodeGen/MachineFunctionPass.h"
+#include "llvm/Support/BlockFrequency.h"
 #include <climits>

 namespace llvm {
@@ -23,29 +24,29 @@ class MachineBranchProbabilityInfo;
 template<class BlockT, class FunctionT, class BranchProbInfoT>
 class BlockFrequencyImpl;

-/// MachineBlockFrequency pass uses BlockFrequencyImpl implementation to estimate
+/// MachineBlockFrequencyInfo pass uses BlockFrequencyImpl implementation to estimate
 /// machine basic block frequencies.
-class MachineBlockFrequency : public MachineFunctionPass {
+class MachineBlockFrequencyInfo : public MachineFunctionPass {

  BlockFrequencyImpl<MachineBasicBlock, MachineFunction, MachineBranchProbabilityInfo> *MBFI;

 public:
  static char ID;

-  MachineBlockFrequency();
+  MachineBlockFrequencyInfo();

-  ~MachineBlockFrequency();
+  ~MachineBlockFrequencyInfo();

  void getAnalysisUsage(AnalysisUsage &AU) const;

  bool runOnMachineFunction(MachineFunction &F);

-  /// getblockFreq - Return block frequency. Never return 0, value must be
-  /// positive. Please note that initial frequency is equal to 1024. It means
+  /// getblockFreq - Return block frequency. Return 0 if we don't have the
+  /// information. Please note that initial frequency is equal to 1024. It means
  /// that we should not rely on the value itself, but only on the comparison to
-  /// the other block frequencies. We do this to avoid using of the floating
-  /// points.
-  uint32_t getBlockFreq(MachineBasicBlock *MBB);
+  /// the other block frequencies. We do this to avoid using of floating points.
+  ///
+  BlockFrequency getBlockFreq(MachineBasicBlock *MBB) const;
 };

 }
@@ -34,15 +34,15 @@ class raw_ostream;
 /// Abstract base class for all machine specific constantpool value subclasses.
 ///
 class MachineConstantPoolValue {
-  const Type *Ty;
+  Type *Ty;

 public:
-  explicit MachineConstantPoolValue(const Type *ty) : Ty(ty) {}
+  explicit MachineConstantPoolValue(Type *ty) : Ty(ty) {}
  virtual ~MachineConstantPoolValue() {}

  /// getType - get type of this MachineConstantPoolValue.
  ///
-  const Type *getType() const { return Ty; }
+  Type *getType() const { return Ty; }

  
  /// getRelocationInfo - This method classifies the entry according to
@@ -54,7 +54,7 @@ public:
  virtual int getExistingMachineCPValue(MachineConstantPool *CP,
                                        unsigned Alignment) = 0;

-  virtual void AddSelectionDAGCSEId(FoldingSetNodeID &ID) = 0;
+  virtual void addSelectionDAGCSEId(FoldingSetNodeID &ID) = 0;

  /// print - Implement operator<<
  virtual void print(raw_ostream &O) const = 0;
@@ -104,7 +104,7 @@ public:
    return Alignment & ~(1 << (sizeof(unsigned)*CHAR_BIT-1));
  }

-  const Type *getType() const;
+  Type *getType() const;
  
  /// getRelocationInfo - This method classifies the entry according to
  /// whether or not it may generate a relocation entry.  This must be
@@ -174,6 +174,10 @@ class MachineFrameInfo {
  /// StackProtectorIdx - The frame index for the stack protector.
  int StackProtectorIdx;

+  /// FunctionContextIdx - The frame index for the function context. Used for
+  /// SjLj exceptions.
+  int FunctionContextIdx;
+
  /// MaxCallFrameSize - This contains the size of the largest call frame if the
  /// target uses frame setup/destroy pseudo instructions (as defined in the
  /// TargetFrameInfo class).  This information is important for frame pointer
@@ -220,6 +224,7 @@ public:
    AdjustsStack = false;
    HasCalls = false;
    StackProtectorIdx = -1;
+    FunctionContextIdx = -1;
    MaxCallFrameSize = 0;
    CSIValid = false;
    LocalFrameSize = 0;
@@ -244,6 +249,11 @@ public:
  int getStackProtectorIndex() const { return StackProtectorIdx; }
  void setStackProtectorIndex(int I) { StackProtectorIdx = I; }

+  /// getFunctionContextIndex/setFunctionContextIndex - Return the index for the
+  /// function context object. This object is used for SjLj exceptions.
+  int getFunctionContextIndex() const { return FunctionContextIdx; }
+  void setFunctionContextIndex(int I) { FunctionContextIdx = I; }
+
  /// isFrameAddressTaken - This method may be called any time after instruction
  /// selection is complete to determine if there is a call to
  /// \@llvm.frameaddress in this function.
@@ -32,6 +32,7 @@ namespace llvm {
 template <typename T> class SmallVectorImpl;
 class AliasAnalysis;
 class TargetInstrInfo;
+class TargetRegisterClass;
 class TargetRegisterInfo;
 class MachineFunction;
 class MachineMemOperand;
@@ -58,8 +59,6 @@ public:
  };
 private:
  const MCInstrDesc *MCID;              // Instruction descriptor.
-  uint16_t NumImplicitOps;              // Number of implicit operands (which
-                                        // are determined at construction time).

  uint8_t Flags;                        // Various bits of additional
                                        // information about machine
@@ -78,9 +77,6 @@ private:
  MachineBasicBlock *Parent;            // Pointer to the owning basic block.
  DebugLoc debugLoc;                    // Source line information.

-  // OperandComplete - Return true if it's illegal to add a new operand
-  bool OperandsComplete() const;
-
  MachineInstr(const MachineInstr&);   // DO NOT IMPLEMENT
  void operator=(const MachineInstr&); // DO NOT IMPLEMENT

@@ -393,6 +389,30 @@ public:
  /// none is found.
  int findFirstPredOperandIdx() const;

+  /// findInlineAsmFlagIdx() - Find the index of the flag word operand that
+  /// corresponds to operand OpIdx on an inline asm instruction.  Returns -1 if
+  /// getOperand(OpIdx) does not belong to an inline asm operand group.
+  ///
+  /// If GroupNo is not NULL, it will receive the number of the operand group
+  /// containing OpIdx.
+  ///
+  /// The flag operand is an immediate that can be decoded with methods like
+  /// InlineAsm::hasRegClassConstraint().
+  ///
+  int findInlineAsmFlagIdx(unsigned OpIdx, unsigned *GroupNo = 0) const;
+
+  /// getRegClassConstraint - Compute the static register class constraint for
+  /// operand OpIdx.  For normal instructions, this is derived from the
+  /// MCInstrDesc.  For inline assembly it is derived from the flag words.
+  ///
+  /// Returns NULL if the static register classs constraint cannot be
+  /// determined.
+  ///
+  const TargetRegisterClass*
+  getRegClassConstraint(unsigned OpIdx,
+                        const TargetInstrInfo *TII,
+                        const TargetRegisterInfo *TRI) const;
+
  /// isRegTiedToUseOperand - Given the index of a register def operand,
  /// check if the register def is tied to a source operand, due to either
  /// two-address elimination or inline assembly constraints. Returns the
@@ -34,7 +34,7 @@
 #include "llvm/Pass.h"
 #include "llvm/GlobalValue.h"
 #include "llvm/Metadata.h"
-#include "llvm/CodeGen/MachineLocation.h"
+#include "llvm/MC/MachineLocation.h"
 #include "llvm/MC/MCContext.h"
 #include "llvm/Support/Dwarf.h"
 #include "llvm/Support/DebugLoc.h"
@@ -107,36 +107,42 @@ class MachineModuleInfo : public ImmutablePass {
  /// want.
  MachineModuleInfoImpl *ObjFileMMI;

-  // FrameMoves - List of moves done by a function's prolog.  Used to construct
-  // frame maps by debug and exception handling consumers.
+  /// FrameMoves - List of moves done by a function's prolog.  Used to construct
+  /// frame maps by debug and exception handling consumers.
  std::vector<MachineMove> FrameMoves;

-  // LandingPads - List of LandingPadInfo describing the landing pad information
-  // in the current function.
+  /// CompactUnwindEncoding - If the target supports it, this is the compact
+  /// unwind encoding. It replaces a function's CIE and FDE.
+  uint32_t CompactUnwindEncoding;
+
+  /// LandingPads - List of LandingPadInfo describing the landing pad
+  /// information in the current function.
  std::vector<LandingPadInfo> LandingPads;

-  // Map of invoke call site index values to associated begin EH_LABEL for
-  // the current function.
+  /// LPadToCallSiteMap - Map a landing pad's EH symbol to the call site
+  /// indexes.
+  DenseMap<MCSymbol*, SmallVector<unsigned, 4> > LPadToCallSiteMap;
+
+  /// CallSiteMap - Map of invoke call site index values to associated begin
+  /// EH_LABEL for the current function.
  DenseMap<MCSymbol*, unsigned> CallSiteMap;

-  // The current call site index being processed, if any. 0 if none.
+  /// CurCallSite - The current call site index being processed, if any. 0 if
+  /// none.
  unsigned CurCallSite;

-  // TypeInfos - List of C++ TypeInfo used in the current function.
-  //
+  /// TypeInfos - List of C++ TypeInfo used in the current function.
  std::vector<const GlobalVariable *> TypeInfos;

-  // FilterIds - List of typeids encoding filters used in the current function.
-  //
+  /// FilterIds - List of typeids encoding filters used in the current function.
  std::vector<unsigned> FilterIds;

-  // FilterEnds - List of the indices in FilterIds corresponding to filter
-  // terminators.
-  //
+  /// FilterEnds - List of the indices in FilterIds corresponding to filter
+  /// terminators.
  std::vector<unsigned> FilterEnds;

-  // Personalities - Vector of all personality functions ever seen. Used to emit
-  // common EH frames.
+  /// Personalities - Vector of all personality functions ever seen. Used to
+  /// emit common EH frames.
  std::vector<const Function *> Personalities;

  /// UsedFunctions - The functions in the @llvm.used list in a more easily
@@ -144,7 +150,6 @@ class MachineModuleInfo : public ImmutablePass {
  /// llvm.compiler.used.
  SmallPtrSet<const Function *, 32> UsedFunctions;

-
  /// AddrLabelSymbols - This map keeps track of which symbol is being used for
  /// the specified basic block's address of label.
  MMIAddrLabelMap *AddrLabelSymbols;
@@ -156,8 +161,9 @@ class MachineModuleInfo : public ImmutablePass {
  /// in this module.
  bool DbgInfoAvailable;

-  /// True if this module calls VarArg function with floating point arguments.
-  /// This is used to emit an undefined reference to fltused on Windows targets.
+  /// CallsExternalVAFunctionWithFloatingPointArguments - True if this module
+  /// calls VarArg function with floating point arguments.  This is used to emit
+  /// an undefined reference to fltused on Windows targets.
  bool CallsExternalVAFunctionWithFloatingPointArguments;

 public:
@@ -170,7 +176,8 @@ public:

  MachineModuleInfo();  // DUMMY CONSTRUCTOR, DO NOT CALL.
  // Real constructor.
-  MachineModuleInfo(const MCAsmInfo &MAI, const TargetAsmInfo *TAI);
+  MachineModuleInfo(const MCAsmInfo &MAI, const MCRegisterInfo &MRI,
+                    const MCObjectFileInfo *MOFI);
  ~MachineModuleInfo();

  bool doInitialization();
@@ -229,6 +236,15 @@ public:
  /// handling comsumers.
  std::vector<MachineMove> &getFrameMoves() { return FrameMoves; }

+  /// getCompactUnwindEncoding - Returns the compact unwind encoding for a
+  /// function if the target supports the encoding. This encoding replaces a
+  /// function's CIE and FDE.
+  uint32_t getCompactUnwindEncoding() const { return CompactUnwindEncoding; }
+
+  /// setCompactUnwindEncoding - Set the compact unwind encoding for a function
+  /// if the target supports the encoding.
+  void setCompactUnwindEncoding(uint32_t Enc) { CompactUnwindEncoding = Enc; }
+
  /// getAddrLabelSymbol - Return the symbol to be used for the specified basic
  /// block when its address is taken.  This cannot be its normal LBB label
  /// because the block may be accessed outside its containing function.
@@ -286,12 +302,12 @@ public:
  /// addCatchTypeInfo - Provide the catch typeinfo for a landing pad.
  ///
  void addCatchTypeInfo(MachineBasicBlock *LandingPad,
-                        std::vector<const GlobalVariable *> &TyInfo);
+                        ArrayRef<const GlobalVariable *> TyInfo);

  /// addFilterTypeInfo - Provide the filter typeinfo for a landing pad.
  ///
  void addFilterTypeInfo(MachineBasicBlock *LandingPad,
-                         std::vector<const GlobalVariable *> &TyInfo);
+                         ArrayRef<const GlobalVariable *> TyInfo);

  /// addCleanup - Add a cleanup action for a landing pad.
  ///
@@ -315,18 +331,42 @@ public:
    return LandingPads;
  }

-  /// setCallSiteBeginLabel - Map the begin label for a call site
+  /// setCallSiteLandingPad - Map the landing pad's EH symbol to the call
+  /// site indexes.
+  void setCallSiteLandingPad(MCSymbol *Sym, ArrayRef<unsigned> Sites);
+
+  /// getCallSiteLandingPad - Get the call site indexes for a landing pad EH
+  /// symbol.
+  SmallVectorImpl<unsigned> &getCallSiteLandingPad(MCSymbol *Sym) {
+    assert(hasCallSiteLandingPad(Sym) &&
+           "missing call site number for landing pad!");
+    return LPadToCallSiteMap[Sym];
+  }
+
+  /// hasCallSiteLandingPad - Return true if the landing pad Eh symbol has an
+  /// associated call site.
+  bool hasCallSiteLandingPad(MCSymbol *Sym) {
+    return !LPadToCallSiteMap[Sym].empty();
+  }
+
+  /// setCallSiteBeginLabel - Map the begin label for a call site.
  void setCallSiteBeginLabel(MCSymbol *BeginLabel, unsigned Site) {
    CallSiteMap[BeginLabel] = Site;
  }

-  /// getCallSiteBeginLabel - Get the call site number for a begin label
+  /// getCallSiteBeginLabel - Get the call site number for a begin label.
  unsigned getCallSiteBeginLabel(MCSymbol *BeginLabel) {
-    assert(CallSiteMap.count(BeginLabel) &&
+    assert(hasCallSiteBeginLabel(BeginLabel) &&
           "Missing call site number for EH_LABEL!");
    return CallSiteMap[BeginLabel];
  }

+  /// hasCallSiteBeginLabel - Return true if the begin label has a call site
+  /// number associated with it.
+  bool hasCallSiteBeginLabel(MCSymbol *BeginLabel) {
+    return CallSiteMap[BeginLabel] != 0;
+  }
+
  /// setCurrentCallSite - Set the call site currently being processed.
  void setCurrentCallSite(unsigned Site) { CurCallSite = Site; }

@@ -83,8 +83,23 @@ private:
  /// This is only valid on definitions of registers.
  bool IsDead : 1;

-  /// IsUndef - True if this is a register def / use of "undef", i.e. register
-  /// defined by an IMPLICIT_DEF. This is only valid on registers.
+  /// IsUndef - True if this register operand reads an "undef" value, i.e. the
+  /// read value doesn't matter.  This flag can be set on both use and def
+  /// operands.  On a sub-register def operand, it refers to the part of the
+  /// register that isn't written.  On a full-register def operand, it is a
+  /// noop.  See readsReg().
+  ///
+  /// This is only valid on registers.
+  ///
+  /// Note that an instruction may have multiple <undef> operands referring to
+  /// the same register.  In that case, the instruction may depend on those
+  /// operands reading the same dont-care value.  For example:
+  ///
+  ///   %vreg1<def> = XOR %vreg2<undef>, %vreg2<undef>
+  ///
+  /// Any register can be used for %vreg2, and its value doesn't matter, but
+  /// the two operands must be the same register.
+  ///
  bool IsUndef : 1;

  /// IsEarlyClobber - True if this MO_Register 'def' operand is written to
@@ -253,6 +268,15 @@ public:
    return IsDebug;
  }

+  /// readsReg - Returns true if this operand reads the previous value of its
+  /// register.  A use operand with the <undef> flag set doesn't read its
+  /// register.  A sub-register def implicitly reads the other parts of the
+  /// register being redefined unless the <undef> flag is set.
+  bool readsReg() const {
+    assert(isReg() && "Wrong MachineOperand accessor");
+    return !isUndef() && (isUse() || getSubReg());
+  }
+
  /// getNextOperandForReg - Return the next MachineOperand in the function that
  /// uses or defines this register.
  MachineOperand *getNextOperandForReg() const {
@@ -25,6 +25,12 @@ namespace llvm {
 /// registers, including vreg register classes, use/def chains for registers,
 /// etc.
 class MachineRegisterInfo {
+  const TargetRegisterInfo *const TRI;
+
+  /// IsSSA - True when the machine function is in SSA form and virtual
+  /// registers have a single def.
+  bool IsSSA;
+
  /// VRegInfo - Information we keep for each virtual register.
  ///
  /// Each element in this list contains the register class of the vreg and the
@@ -65,7 +71,23 @@ class MachineRegisterInfo {
 public:
  explicit MachineRegisterInfo(const TargetRegisterInfo &TRI);
  ~MachineRegisterInfo();
-  
+
+  //===--------------------------------------------------------------------===//
+  // Function State
+  //===--------------------------------------------------------------------===//
+
+  // isSSA - Returns true when the machine function is in SSA form. Early
+  // passes require the machine function to be in SSA form where every virtual
+  // register has a single defining instruction.
+  //
+  // The TwoAddressInstructionPass and PHIElimination passes take the machine
+  // function out of SSA form when they introduce multiple defs per virtual
+  // register.
+  bool isSSA() const { return IsSSA; }
+
+  // leaveSSA - Indicates that the machine function is no longer in SSA form.
+  void leaveSSA() { IsSSA = false; }
+
  //===--------------------------------------------------------------------===//
  // Register Info
  //===--------------------------------------------------------------------===//
@@ -195,12 +217,25 @@ public:
  void setRegClass(unsigned Reg, const TargetRegisterClass *RC);

  /// constrainRegClass - Constrain the register class of the specified virtual
-  /// register to be a common subclass of RC and the current register class.
-  /// Return the new register class, or NULL if no such class exists.
+  /// register to be a common subclass of RC and the current register class,
+  /// but only if the new class has at least MinNumRegs registers.  Return the
+  /// new register class, or NULL if no such class exists.
  /// This should only be used when the constraint is known to be trivial, like
  /// GR32 -> GR32_NOSP. Beware of increasing register pressure.
+  ///
  const TargetRegisterClass *constrainRegClass(unsigned Reg,
-                                               const TargetRegisterClass *RC);
+                                               const TargetRegisterClass *RC,
+                                               unsigned MinNumRegs = 0);
+
+  /// recomputeRegClass - Try to find a legal super-class of Reg's register
+  /// class that still satisfies the constraints from the instructions using
+  /// Reg.  Returns true if Reg was upgraded.
+  ///
+  /// This method can be used after constraints have been removed from a
+  /// virtual register, for example after removing instructions or splitting
+  /// the live range.
+  ///
+  bool recomputeRegClass(unsigned Reg, const TargetMachine&);

  /// createVirtualRegister - Create and return a new virtual register in the
  /// function with the specified register class.
@@ -24,7 +24,7 @@ namespace llvm {
  class MachineFunctionPass;
  class PassInfo;
  class TargetLowering;
-  class RegisterCoalescer;
+  class TargetRegisterClass;
  class raw_ostream;

  /// createUnreachableBlockEliminationPass - The LLVM code generator does not
@@ -81,6 +81,9 @@ namespace llvm {
  /// register allocators.
  extern char &TwoAddressInstructionPassID;

+  /// RegisteCoalescer pass - This pass merges live ranges to eliminate copies.
+  extern char &RegisterCoalescerPassID;
+
  /// SpillPlacement analysis. Suggest optimal placement of spill code between
  /// basic blocks.
  ///
@@ -125,21 +128,15 @@ namespace llvm {
  ///
  FunctionPass *createDefaultPBQPRegisterAllocator();

-  /// RegisterCoalescer Pass - Coalesce all copies possible.  Can run
-  /// independently of the register allocator.
-  ///
-  RegisterCoalescer *createRegisterCoalescer();
-
  /// PrologEpilogCodeInserter Pass - This pass inserts prolog and epilog code,
  /// and eliminates abstract frame references.
  ///
  FunctionPass *createPrologEpilogCodeInserter();

-  /// LowerSubregs Pass - This pass lowers subregs to register-register copies
-  /// which yields suboptimal, but correct code if the register allocator
-  /// cannot coalesce all subreg operations during allocation.
+  /// ExpandPostRAPseudos Pass - This pass expands pseudo instructions after
+  /// register allocation.
  ///
-  FunctionPass *createLowerSubregsPass();
+  FunctionPass *createExpandPostRAPseudosPass();

  /// createPostRAScheduler - This pass performs post register allocation
  /// scheduling.
@@ -229,6 +226,14 @@ namespace llvm {
  ///
  FunctionPass *createExpandISelPseudosPass();

+  /// createExecutionDependencyFixPass - This pass fixes execution time
+  /// problems with dependent instructions, such as switching execution
+  /// domains to match.
+  ///
+  /// The pass will examine instructions using and defining registers in RC.
+  ///
+  FunctionPass *createExecutionDependencyFixPass(const TargetRegisterClass *RC);
+
 } // End llvm namespace

 #endif
@@ -450,6 +450,10 @@ public:
  SDValue getVectorShuffle(EVT VT, DebugLoc dl, SDValue N1, SDValue N2,
                           const int *MaskElts);

+  /// getAnyExtOrTrunc - Convert Op, which must be of integer type, to the
+  /// integer type VT, by either any-extending or truncating it.
+  SDValue getAnyExtOrTrunc(SDValue Op, DebugLoc DL, EVT VT);
+
  /// getSExtOrTrunc - Convert Op, which must be of integer type, to the
  /// integer type VT, by either sign-extending or truncating it.
  SDValue getSExtOrTrunc(SDValue Op, DebugLoc DL, EVT VT);
@@ -560,17 +564,13 @@ public:
  ///
  SDValue getSetCC(DebugLoc DL, EVT VT, SDValue LHS, SDValue RHS,
                   ISD::CondCode Cond) {
+    assert(LHS.getValueType().isVector() == RHS.getValueType().isVector() &&
+      "Cannot compare scalars to vectors");
+    assert(LHS.getValueType().isVector() == VT.isVector() &&
+      "Cannot compare scalars to vectors");
    return getNode(ISD::SETCC, DL, VT, LHS, RHS, getCondCode(Cond));
  }

-  /// getVSetCC - Helper function to make it easier to build VSetCC's nodes
-  /// if you just have an ISD::CondCode instead of an SDValue.
-  ///
-  SDValue getVSetCC(DebugLoc DL, EVT VT, SDValue LHS, SDValue RHS,
-                    ISD::CondCode Cond) {
-    return getNode(ISD::VSETCC, DL, VT, LHS, RHS, getCondCode(Cond));
-  }
-
  /// getSelectCC - Helper function to make it easier to build SelectCC's if you
  /// just have an ISD::CondCode instead of an SDValue.
  ///
@@ -589,19 +589,37 @@ public:
  /// takes 3 operands
  SDValue getAtomic(unsigned Opcode, DebugLoc dl, EVT MemVT, SDValue Chain,
                    SDValue Ptr, SDValue Cmp, SDValue Swp,
-                    MachinePointerInfo PtrInfo, unsigned Alignment=0);
+                    MachinePointerInfo PtrInfo, unsigned Alignment,
+                    AtomicOrdering Ordering,
+                    SynchronizationScope SynchScope);
  SDValue getAtomic(unsigned Opcode, DebugLoc dl, EVT MemVT, SDValue Chain,
                    SDValue Ptr, SDValue Cmp, SDValue Swp,
-                    MachineMemOperand *MMO);
+                    MachineMemOperand *MMO,
+                    AtomicOrdering Ordering,
+                    SynchronizationScope SynchScope);

-  /// getAtomic - Gets a node for an atomic op, produces result and chain and
-  /// takes 2 operands.
+  /// getAtomic - Gets a node for an atomic op, produces result (if relevant)
+  /// and chain and takes 2 operands.
  SDValue getAtomic(unsigned Opcode, DebugLoc dl, EVT MemVT, SDValue Chain,
                    SDValue Ptr, SDValue Val, const Value* PtrVal,
-                    unsigned Alignment = 0);
+                    unsigned Alignment, AtomicOrdering Ordering,
+                    SynchronizationScope SynchScope);
  SDValue getAtomic(unsigned Opcode, DebugLoc dl, EVT MemVT, SDValue Chain,
-                    SDValue Ptr, SDValue Val,
-                    MachineMemOperand *MMO);
+                    SDValue Ptr, SDValue Val, MachineMemOperand *MMO,
+                    AtomicOrdering Ordering,
+                    SynchronizationScope SynchScope);
+
+  /// getAtomic - Gets a node for an atomic op, produces result and chain and
+  /// takes 1 operand.
+  SDValue getAtomic(unsigned Opcode, DebugLoc dl, EVT MemVT, EVT VT,
+                    SDValue Chain, SDValue Ptr, const Value* PtrVal,
+                    unsigned Alignment,
+                    AtomicOrdering Ordering,
+                    SynchronizationScope SynchScope);
+  SDValue getAtomic(unsigned Opcode, DebugLoc dl, EVT MemVT, EVT VT,
+                    SDValue Chain, SDValue Ptr, MachineMemOperand *MMO,
+                    AtomicOrdering Ordering,
+                    SynchronizationScope SynchScope);

  /// getMemIntrinsicNode - Creates a MemIntrinsicNode that may produce a
  /// result and takes a list of operands. Opcode may be INTRINSIC_VOID,
@@ -20,6 +20,7 @@
 #define LLVM_CODEGEN_SELECTIONDAGNODES_H

 #include "llvm/Constants.h"
+#include "llvm/Instructions.h"
 #include "llvm/ADT/FoldingSet.h"
 #include "llvm/ADT/GraphTraits.h"
 #include "llvm/ADT/ilist_node.h"
@@ -917,6 +918,13 @@ public:
  bool isVolatile() const { return (SubclassData >> 5) & 1; }
  bool isNonTemporal() const { return (SubclassData >> 6) & 1; }

+  AtomicOrdering getOrdering() const {
+    return AtomicOrdering((SubclassData >> 7) & 15);
+  }
+  SynchronizationScope getSynchScope() const {
+    return SynchronizationScope((SubclassData >> 11) & 1);
+  }
+
  /// Returns the SrcValue and offset that describes the location of the access
  const Value *getSrcValue() const { return MMO->getValue(); }
  int64_t getSrcValueOffset() const { return MMO->getOffset(); }
@@ -968,6 +976,8 @@ public:
           N->getOpcode() == ISD::ATOMIC_LOAD_MAX     ||
           N->getOpcode() == ISD::ATOMIC_LOAD_UMIN    ||
           N->getOpcode() == ISD::ATOMIC_LOAD_UMAX    ||
+           N->getOpcode() == ISD::ATOMIC_LOAD         ||
+           N->getOpcode() == ISD::ATOMIC_STORE        ||
           N->isTargetMemoryOpcode();
  }
 };
@@ -977,6 +987,23 @@ public:
 class AtomicSDNode : public MemSDNode {
  SDUse Ops[4];

+  void InitAtomic(AtomicOrdering Ordering, SynchronizationScope SynchScope) {
+    // This must match encodeMemSDNodeFlags() in SelectionDAG.cpp.
+    assert((Ordering & 15) == Ordering &&
+           "Ordering may not require more than 4 bits!");
+    assert((SynchScope & 1) == SynchScope &&
+           "SynchScope may not require more than 1 bit!");
+    SubclassData |= Ordering << 7;
+    SubclassData |= SynchScope << 11;
+    assert(getOrdering() == Ordering && "Ordering encoding error!");
+    assert(getSynchScope() == SynchScope && "Synch-scope encoding error!");
+
+    assert((readMem() || getOrdering() <= Monotonic) &&
+           "Acquire/Release MachineMemOperand must be a load!");
+    assert((writeMem() || getOrdering() <= Monotonic) &&
+           "Acquire/Release MachineMemOperand must be a store!");
+  }
+
 public:
  // Opc:   opcode for atomic
  // VTL:    value type list
@@ -988,20 +1015,28 @@ public:
  // Align:  alignment of memory
  AtomicSDNode(unsigned Opc, DebugLoc dl, SDVTList VTL, EVT MemVT,
               SDValue Chain, SDValue Ptr,
-               SDValue Cmp, SDValue Swp, MachineMemOperand *MMO)
+               SDValue Cmp, SDValue Swp, MachineMemOperand *MMO,
+               AtomicOrdering Ordering, SynchronizationScope SynchScope)
    : MemSDNode(Opc, dl, VTL, MemVT, MMO) {
-    assert(readMem() && "Atomic MachineMemOperand is not a load!");
-    assert(writeMem() && "Atomic MachineMemOperand is not a store!");
+    InitAtomic(Ordering, SynchScope);
    InitOperands(Ops, Chain, Ptr, Cmp, Swp);
  }
  AtomicSDNode(unsigned Opc, DebugLoc dl, SDVTList VTL, EVT MemVT,
               SDValue Chain, SDValue Ptr,
-               SDValue Val, MachineMemOperand *MMO)
+               SDValue Val, MachineMemOperand *MMO,
+               AtomicOrdering Ordering, SynchronizationScope SynchScope)
    : MemSDNode(Opc, dl, VTL, MemVT, MMO) {
-    assert(readMem() && "Atomic MachineMemOperand is not a load!");
-    assert(writeMem() && "Atomic MachineMemOperand is not a store!");
+    InitAtomic(Ordering, SynchScope);
    InitOperands(Ops, Chain, Ptr, Val);
  }
+  AtomicSDNode(unsigned Opc, DebugLoc dl, SDVTList VTL, EVT MemVT,
+               SDValue Chain, SDValue Ptr,
+               MachineMemOperand *MMO,
+               AtomicOrdering Ordering, SynchronizationScope SynchScope)
+    : MemSDNode(Opc, dl, VTL, MemVT, MMO) {
+    InitAtomic(Ordering, SynchScope);
+    InitOperands(Ops, Chain, Ptr);
+  }

  const SDValue &getBasePtr() const { return getOperand(1); }
  const SDValue &getVal() const { return getOperand(2); }
@@ -1025,7 +1060,9 @@ public:
           N->getOpcode() == ISD::ATOMIC_LOAD_MIN     ||
           N->getOpcode() == ISD::ATOMIC_LOAD_MAX     ||
           N->getOpcode() == ISD::ATOMIC_LOAD_UMIN    ||
-           N->getOpcode() == ISD::ATOMIC_LOAD_UMAX;
+           N->getOpcode() == ISD::ATOMIC_LOAD_UMAX    ||
+           N->getOpcode() == ISD::ATOMIC_LOAD         ||
+           N->getOpcode() == ISD::ATOMIC_STORE;
  }
 };

@@ -1291,7 +1328,7 @@ public:
  unsigned getAlignment() const { return Alignment; }
  unsigned char getTargetFlags() const { return TargetFlags; }

-  const Type *getType() const;
+  Type *getType() const;

  static bool classof(const ConstantPoolSDNode *) { return true; }
  static bool classof(const SDNode *N) {
@@ -7,7 +7,7 @@
 //
 //===----------------------------------------------------------------------===//
 //
-// This file implements SlotIndex and related classes. The purpuse of SlotIndex
+// This file implements SlotIndex and related classes. The purpose of SlotIndex
 // is to describe a position at which a register can become live, or cease to
 // be live.
 //
@@ -33,42 +33,13 @@ namespace llvm {


 class TargetLoweringObjectFileELF : public TargetLoweringObjectFile {
-protected:
-  /// TLSDataSection - Section directive for Thread Local data.
-  ///
-  const MCSection *TLSDataSection;        // Defaults to ".tdata".
-
-  /// TLSBSSSection - Section directive for Thread Local uninitialized data.
-  /// Null if this target doesn't support a BSS section.
-  ///
-  const MCSection *TLSBSSSection;         // Defaults to ".tbss".
-
-  const MCSection *DataRelSection;
-  const MCSection *DataRelLocalSection;
-  const MCSection *DataRelROSection;
-  const MCSection *DataRelROLocalSection;
-
-  const MCSection *MergeableConst4Section;
-  const MCSection *MergeableConst8Section;
-  const MCSection *MergeableConst16Section;
 public:
-  TargetLoweringObjectFileELF();
-  ~TargetLoweringObjectFileELF() {}
-
-  virtual void Initialize(MCContext &Ctx, const TargetMachine &TM);
-
-  virtual const MCSection *getEHFrameSection() const;
-  virtual const MCSection *getWin64EHFuncTableSection(StringRef) const {
-    return NULL;
-  }
-  virtual const MCSection *getWin64EHTableSection(StringRef) const{return NULL;}
+  virtual ~TargetLoweringObjectFileELF() {}

  virtual void emitPersonalityValue(MCStreamer &Streamer,
                                    const TargetMachine &TM,
                                    const MCSymbol *Sym) const;

-  const MCSection *getDataRelSection() const { return DataRelSection; }
-
  /// getSectionForConstant - Given a constant with the SectionKind, return a
  /// section that it should be placed in.
  virtual const MCSection *getSectionForConstant(SectionKind Kind) const;
@@ -99,48 +70,8 @@ public:


 class TargetLoweringObjectFileMachO : public TargetLoweringObjectFile {
-  /// TLSDataSection - Section for thread local data.
-  ///
-  const MCSection *TLSDataSection;        // Defaults to ".tdata".
-
-  /// TLSBSSSection - Section for thread local uninitialized data.
-  ///
-  const MCSection *TLSBSSSection;         // Defaults to ".tbss".
-  
-  /// TLSTLVSection - Section for thread local structure information.
-  /// Contains the source code name of the variable, visibility and a pointer
-  /// to the initial value (.tdata or .tbss).
-  const MCSection *TLSTLVSection;         // Defaults to ".tlv".
-  
-  /// TLSThreadInitSection - Section for thread local data initialization
-  /// functions.
-  const MCSection *TLSThreadInitSection;  // Defaults to ".thread_init_func".
-  
-  const MCSection *CStringSection;
-  const MCSection *UStringSection;
-  const MCSection *TextCoalSection;
-  const MCSection *ConstTextCoalSection;
-  const MCSection *ConstDataSection;
-  const MCSection *DataCoalSection;
-  const MCSection *DataCommonSection;
-  const MCSection *DataBSSSection;
-  const MCSection *FourByteConstantSection;
-  const MCSection *EightByteConstantSection;
-  const MCSection *SixteenByteConstantSection;
-
-  const MCSection *LazySymbolPointerSection;
-  const MCSection *NonLazySymbolPointerSection;
 public:
-  TargetLoweringObjectFileMachO();
-  ~TargetLoweringObjectFileMachO() {}
-
-  virtual void Initialize(MCContext &Ctx, const TargetMachine &TM);
-
-  virtual const MCSection *getEHFrameSection() const;
-  virtual const MCSection *getWin64EHFuncTableSection(StringRef) const {
-    return NULL;
-  }
-  virtual const MCSection *getWin64EHTableSection(StringRef) const{return NULL;}
+  virtual ~TargetLoweringObjectFileMachO() {}

  virtual const MCSection *
  SelectSectionForGlobal(const GlobalValue *GV, SectionKind Kind,
@@ -158,30 +89,6 @@ public:
  virtual bool shouldEmitUsedDirectiveFor(const GlobalValue *GV,
                                          Mangler *) const;

-  /// getTextCoalSection - Return the "__TEXT,__textcoal_nt" section we put weak
-  /// text symbols into.
-  const MCSection *getTextCoalSection() const {
-    return TextCoalSection;
-  }
-
-  /// getConstTextCoalSection - Return the "__TEXT,__const_coal" section
-  /// we put weak read-only symbols into.
-  const MCSection *getConstTextCoalSection() const {
-    return ConstTextCoalSection;
-  }
-
-  /// getLazySymbolPointerSection - Return the section corresponding to
-  /// the .lazy_symbol_pointer directive.
-  const MCSection *getLazySymbolPointerSection() const {
-    return LazySymbolPointerSection;
-  }
-
-  /// getNonLazySymbolPointerSection - Return the section corresponding to
-  /// the .non_lazy_symbol_pointer directive.
-  const MCSection *getNonLazySymbolPointerSection() const {
-    return NonLazySymbolPointerSection;
-  }
-
  /// getExprForDwarfGlobalReference - The mach-o version of this method
  /// defaults to returning a stub reference.
  virtual const MCExpr *
@@ -193,30 +100,13 @@ public:
  virtual MCSymbol *
  getCFIPersonalitySymbol(const GlobalValue *GV, Mangler *Mang,
                          MachineModuleInfo *MMI) const;
-
-  virtual unsigned getPersonalityEncoding() const;
-  virtual unsigned getLSDAEncoding() const;
-  virtual unsigned getFDEEncoding(bool CFI) const;
-  virtual unsigned getTTypeEncoding() const;
 };



 class TargetLoweringObjectFileCOFF : public TargetLoweringObjectFile {
-  const MCSection *DrectveSection;
-  const MCSection *PDataSection;
-  const MCSection *XDataSection;
 public:
-  TargetLoweringObjectFileCOFF();
-  ~TargetLoweringObjectFileCOFF() {}
-
-  virtual void Initialize(MCContext &Ctx, const TargetMachine &TM);
-
-  virtual const MCSection *getEHFrameSection() const;
-  virtual const MCSection *getWin64EHFuncTableSection(StringRef) const;
-  virtual const MCSection *getWin64EHTableSection(StringRef) const;
-
-  virtual const MCSection *getDrectveSection() const { return DrectveSection; }
+  virtual ~TargetLoweringObjectFileCOFF() {}

  virtual const MCSection *
  getExplicitSectionGlobal(const GlobalValue *GV, SectionKind Kind,
@@ -144,14 +144,14 @@ namespace llvm {
    /// isFloatingPoint - Return true if this is a FP, or a vector FP type.
    bool isFloatingPoint() const {
      return ((SimpleTy >= MVT::f32 && SimpleTy <= MVT::ppcf128) ||
-        (SimpleTy >= MVT::v2f32 && SimpleTy <= MVT::v4f64));
+	      (SimpleTy >= MVT::v2f32 && SimpleTy <= MVT::v4f64));
    }

    /// isInteger - Return true if this is an integer, or a vector integer type.
    bool isInteger() const {
      return ((SimpleTy >= MVT::FIRST_INTEGER_VALUETYPE &&
               SimpleTy <= MVT::LAST_INTEGER_VALUETYPE) ||
-               (SimpleTy >= MVT::v2i8 && SimpleTy <= MVT::v8i64));
+	      (SimpleTy >= MVT::v2i8 && SimpleTy <= MVT::v8i64));
    }

    /// isVector - Return true if this is a vector value type.
@@ -380,7 +380,7 @@ namespace llvm {
  struct EVT {
  private:
    MVT V;
-    const Type *LLVMTy;
+    Type *LLVMTy;

  public:
    EVT() : V((MVT::SimpleValueType)(MVT::INVALID_SIMPLE_VALUE_TYPE)),
@@ -438,6 +438,21 @@ namespace llvm {
      return MVT::INVALID_SIMPLE_VALUE_TYPE;
    }

+    /// changeVectorElementTypeToInteger - Return a vector with the same number
+    /// of elements as this vector, but with the element type converted to an
+    /// integer type with the same bitwidth.
+    EVT changeVectorElementTypeToInteger() const {
+      if (!isSimple())
+        return changeExtendedVectorElementTypeToInteger();
+      MVT EltTy = getSimpleVT().getVectorElementType();
+      unsigned BitWidth = EltTy.getSizeInBits();
+      MVT IntTy = MVT::getIntegerVT(BitWidth);
+      MVT VecTy = MVT::getVectorVT(IntTy, getVectorNumElements());
+      assert(VecTy != MVT::INVALID_SIMPLE_VALUE_TYPE &&
+             "Simple vector VT not representable by simple integer vector VT!");
+      return VecTy;
+    }
+
    /// isSimple - Test if the given EVT is simple (as opposed to being
    /// extended).
    bool isSimple() const {
@@ -645,12 +660,12 @@ namespace llvm {
    /// getTypeForEVT - This method returns an LLVM type corresponding to the
    /// specified EVT.  For integer types, this returns an unsigned type.  Note
    /// that this will abort for types that cannot be represented.
-    const Type *getTypeForEVT(LLVMContext &Context) const;
+    Type *getTypeForEVT(LLVMContext &Context) const;

    /// getEVT - Return the value type corresponding to the specified type.
    /// This returns all pointers as iPTR.  If HandleUnknown is true, unknown
    /// types are returned as Other, otherwise they are invalid.
-    static EVT getEVT(const Type *Ty, bool HandleUnknown = false);
+    static EVT getEVT(Type *Ty, bool HandleUnknown = false);

    intptr_t getRawBits() {
      if (isSimple())
@@ -674,6 +689,7 @@ namespace llvm {
    // Methods for handling the Extended-type case in functions above.
    // These are all out-of-line to prevent users of this header file
    // from having a dependency on Type.h.
+    EVT changeExtendedVectorElementTypeToInteger() const;
    static EVT getExtendedIntegerVT(LLVMContext &C, unsigned BitWidth);
    static EVT getExtendedVectorVT(LLVMContext &C, EVT VT,
                                   unsigned NumElements);
@@ -1,54 +0,0 @@
-//===--- Action.h - The LLVM Compiler Driver --------------------*- C++ -*-===//
-//
-//                     The LLVM Compiler Infrastructure
-//
-// This file is distributed under the University of Illinois Open
-// Source License. See LICENSE.TXT for details.
-//
-//===----------------------------------------------------------------------===//
-//
-//  Action - encapsulates a single shell command.
-//
-//===----------------------------------------------------------------------===//
-
-#ifndef LLVM_INCLUDE_COMPILER_DRIVER_ACTION_H
-#define LLVM_INCLUDE_COMPILER_DRIVER_ACTION_H
-
-#include <string>
-#include <vector>
-
-namespace llvmc {
-
-  typedef std::vector<std::string> StrVector;
-
-  /// Action - A class that encapsulates a single shell command.
-  class Action {
-    /// Command_ - The actual command (for example, 'ls').
-    std::string Command_;
-    /// Args_ - Command arguments. Stdout redirection ("> file") is allowed.
-    std::vector<std::string> Args_;
-    /// StopCompilation_ - Should we stop compilation after executing
-    /// this action?
-    bool StopCompilation_;
-    /// OutFile_ - The output file name.
-    std::string OutFile_;
-
-  public:
-    void Construct (const std::string& C, const StrVector& A,
-                    bool S, const std::string& O) {
-      Command_ = C;
-      Args_ = A;
-      StopCompilation_ = S;
-      OutFile_ = O;
-    }
-    bool IsConstructed () { return (Command_.size() != 0);}
-
-    /// Execute - Executes the command. Returns -1 on error.
-    int Execute () const;
-    bool StopCompilation () const { return StopCompilation_; }
-    const std::string& OutFile() { return OutFile_; }
-  };
-
-}
-
-#endif // LLVM_INCLUDE_COMPILER_DRIVER_ACTION_H
@@ -1,40 +0,0 @@
-//===--- AutoGenerated.h - The LLVM Compiler Driver -------------*- C++ -*-===//
-//
-//                     The LLVM Compiler Infrastructure
-//
-// This file is distributed under the University of Illinois Open
-// Source License. See LICENSE.TXT for details.
-//
-//===----------------------------------------------------------------------===//
-//
-//  Interface to the autogenerated driver code.
-//
-//===----------------------------------------------------------------------===//
-
-#ifndef LLVM_INCLUDE_COMPILER_DRIVER_AUTOGENERATED_H
-#define LLVM_INCLUDE_COMPILER_DRIVER_AUTOGENERATED_H
-
-namespace llvmc {
-  class LanguageMap;
-  class CompilationGraph;
-
-  namespace autogenerated {
-
-    int PreprocessOptions();
-    int PopulateLanguageMap(LanguageMap& langMap);
-    int PopulateCompilationGraph(CompilationGraph& graph);
-
-    inline int RunInitialization (LanguageMap& M, CompilationGraph& G) {
-      if (int ret = PreprocessOptions())
-        return ret;
-      if (int ret = PopulateLanguageMap(M))
-        return ret;
-      if (int ret = PopulateCompilationGraph(G))
-        return ret;
-
-      return 0;
-    }
-  }
-}
-
-#endif // LLVM_INCLUDE_COMPILER_DRIVER_AUTOGENERATED_H
@@ -1 +1 @@
 .2.2
 .2.1