Merge with LLVM upstream r144606 (Nov 15th 2011)

Conflicts:
	Makefile.rules
	configure
	docs/ReleaseNotes.html
	lib/Analysis/ScalarEvolution.cpp
	lib/CodeGen/AsmPrinter/DwarfCompileUnit.cpp
	lib/CodeGen/ExecutionDepsFix.cpp
	lib/CodeGen/MachineBlockPlacement.cpp
	lib/CodeGen/MachineBranchProbabilityInfo.cpp
	lib/CodeGen/SelectionDAG/LegalizeDAG.cpp
	lib/ExecutionEngine/JIT/LLVMBuild.txt
	lib/MC/LLVMBuild.txt
	lib/MC/MCDisassembler/LLVMBuild.txt
	lib/MC/MCDwarf.cpp
	lib/Object/LLVMBuild.txt
	lib/Target/ARM/ARMExpandPseudoInsts.cpp
	lib/Target/ARM/ARMFastISel.cpp
	lib/Target/ARM/ARMInstrInfo.td
	lib/Target/ARM/AsmParser/ARMAsmParser.cpp
	lib/Target/ARM/Disassembler/ARMDisassembler.cpp
	lib/Target/ARM/Disassembler/LLVMBuild.txt
	lib/Target/ARM/TargetInfo/LLVMBuild.txt
	lib/Target/CBackend/TargetInfo/LLVMBuild.txt
	lib/Target/CellSPU/MCTargetDesc/LLVMBuild.txt
	lib/Target/CellSPU/TargetInfo/LLVMBuild.txt
	lib/Target/CppBackend/TargetInfo/LLVMBuild.txt
	lib/Target/LLVMBuild.txt
	lib/Target/MBlaze/Disassembler/LLVMBuild.txt
	lib/Target/MBlaze/TargetInfo/LLVMBuild.txt
	lib/Target/MSP430/MCTargetDesc/LLVMBuild.txt
	lib/Target/MSP430/TargetInfo/LLVMBuild.txt
	lib/Target/Mips/CMakeLists.txt
	lib/Target/Mips/InstPrinter/MipsInstPrinter.cpp
	lib/Target/Mips/Mips64InstrInfo.td
	lib/Target/Mips/MipsAsmPrinter.cpp
	lib/Target/Mips/MipsISelLowering.cpp
	lib/Target/Mips/MipsMCInstLower.cpp
	lib/Target/Mips/TargetInfo/LLVMBuild.txt
	lib/Target/PTX/LLVMBuild.txt
	lib/Target/PTX/PTXAsmPrinter.cpp
	lib/Target/PTX/TargetInfo/LLVMBuild.txt
	lib/Target/PowerPC/TargetInfo/LLVMBuild.txt
	lib/Target/Sparc/TargetInfo/LLVMBuild.txt
	lib/Target/X86/TargetInfo/LLVMBuild.txt
	lib/Target/X86/X86ISelLowering.cpp
	lib/Target/X86/X86InstrSSE.td
	lib/Target/XCore/MCTargetDesc/LLVMBuild.txt
	lib/Target/XCore/TargetInfo/LLVMBuild.txt
	lib/Transforms/IPO/LLVMBuild.txt
	lib/Transforms/Utils/LLVMBuild.txt
	test/CodeGen/ARM/2011-10-26-memset-with-neon.ll
	test/CodeGen/ARM/2011-11-07-PromoteVectorLoadStore.ll
	test/CodeGen/ARM/fast-isel-cmp-imm.ll
	test/CodeGen/ARM/fast-isel-ldrh-strh-arm.ll
	test/CodeGen/CellSPU/call_indirect.ll
	test/CodeGen/X86/avx2-logic.ll
	test/CodeGen/X86/block-placement.ll
	test/CodeGen/X86/sse-domains.ll
	test/CodeGen/X86/sse3.ll
	test/CodeGen/X86/vec_shuffle-39.ll
	test/MC/ARM/neon-vld-encoding.s
	test/MC/ARM/neon-vst-encoding.s
	tools/llvm-config-2/llvm-config.cpp
	utils/TableGen/LLVMBuild.txt

Change-Id: I70f454db6fc79d7799f56d0f6f2eb7b99561c504

1 files changed, 79 insertions, 1 deletions

diff --git a/lib/Analysis/MemoryDependenceAnalysis.cpp b/lib/Analysis/MemoryDependenceAnalysis.cpp
index 92967c0..323c84f 100644
--- a/lib/Analysis/MemoryDependenceAnalysis.cpp
+++ b/lib/Analysis/MemoryDependenceAnalysis.cpp
@@ -22,6 +22,7 @@
 #include "llvm/Function.h"
 #include "llvm/LLVMContext.h"
 #include "llvm/Analysis/AliasAnalysis.h"
+#include "llvm/Analysis/CaptureTracking.h"
 #include "llvm/Analysis/Dominators.h"
 #include "llvm/Analysis/InstructionSimplify.h"
 #include "llvm/Analysis/MemoryBuiltins.h"
@@ -91,6 +92,7 @@ void MemoryDependenceAnalysis::getAnalysisUsage(AnalysisUsage &AU) const {
 bool MemoryDependenceAnalysis::runOnFunction(Function &) {
   AA = &getAnalysis<AliasAnalysis>();
   TD = getAnalysisIfAvailable<TargetData>();
+  DT = getAnalysisIfAvailable<DominatorTree>();
   if (PredCache == 0)
     PredCache.reset(new PredIteratorCache());
   return false;
@@ -331,6 +333,82 @@ getLoadLoadClobberFullWidthSize(const Value *MemLocBase, int64_t MemLocOffs,
   return 0;
 }
 
+namespace {
+  /// Only find pointer captures which happen before the given instruction. Uses
+  /// the dominator tree to determine whether one instruction is before another.
+  struct CapturesBefore {
+    CapturesBefore(const Instruction *I, DominatorTree *DT)
+      : BeforeHere(I), DT(DT), Captured(false) {}
+
+    void tooManyUses() { Captured = true; }
+
+    bool shouldExplore(Use *U) {
+      Instruction *I = cast<Instruction>(U->getUser());
+      if (BeforeHere != I && DT->dominates(BeforeHere, I))
+        return false;
+      return true;
+    }
+
+    bool captured(Instruction *I) {
+      if (BeforeHere != I && DT->dominates(BeforeHere, I))
+        return false;
+      Captured = true;
+      return true;
+    }
+
+    const Instruction *BeforeHere;
+    DominatorTree *DT;
+
+    bool Captured;
+  };
+}
+
+AliasAnalysis::ModRefResult
+MemoryDependenceAnalysis::getModRefInfo(const Instruction *Inst,
+                                        const AliasAnalysis::Location &MemLoc) {
+  AliasAnalysis::ModRefResult MR = AA->getModRefInfo(Inst, MemLoc);
+  if (MR != AliasAnalysis::ModRef) return MR;
+
+  // FIXME: this is really just shoring-up a deficiency in alias analysis.
+  // BasicAA isn't willing to spend linear time determining whether an alloca
+  // was captured before or after this particular call, while we are. However,
+  // with a smarter AA in place, this test is just wasting compile time.
+  if (!DT) return AliasAnalysis::ModRef;
+  const Value *Object = GetUnderlyingObject(MemLoc.Ptr, TD);
+  if (!isIdentifiedObject(Object) || isa<GlobalVariable>(Object))
+    return AliasAnalysis::ModRef;
+  ImmutableCallSite CS(Inst);
+  if (!CS.getInstruction()) return AliasAnalysis::ModRef;
+
+  CapturesBefore CB(Inst, DT);
+  llvm::PointerMayBeCaptured(Object, CB);
+
+  if (isa<Constant>(Object) || CS.getInstruction() == Object || CB.Captured)
+    return AliasAnalysis::ModRef;
+
+  unsigned ArgNo = 0;
+  for (ImmutableCallSite::arg_iterator CI = CS.arg_begin(), CE = CS.arg_end();
+       CI != CE; ++CI, ++ArgNo) {
+    // Only look at the no-capture or byval pointer arguments.  If this
+    // pointer were passed to arguments that were neither of these, then it
+    // couldn't be no-capture.
+    if (!(*CI)->getType()->isPointerTy() ||
+        (!CS.paramHasAttr(ArgNo+1, Attribute::NoCapture) &&
+         !CS.paramHasAttr(ArgNo+1, Attribute::ByVal)))
+      continue;
+
+    // If this is a no-capture pointer argument, see if we can tell that it
+    // is impossible to alias the pointer we're checking.  If not, we have to
+    // assume that the call could touch the pointer, even though it doesn't
+    // escape.
+    if (!AA->isNoAlias(AliasAnalysis::Location(*CI),
+                       AliasAnalysis::Location(Object))) {
+      return AliasAnalysis::ModRef;
+    }
+  }
+  return AliasAnalysis::NoModRef;
+}
+
 /// getPointerDependencyFrom - Return the instruction on which a memory
 /// location depends.  If isLoad is true, this routine ignores may-aliases with
 /// read-only operations.  If isLoad is false, this routine ignores may-aliases
@@ -478,7 +556,7 @@ getPointerDependencyFrom(const AliasAnalysis::Location &MemLoc, bool isLoad,
     }
 
     // See if this instruction (e.g. a call or vaarg) mod/ref's the pointer.
-    switch (AA->getModRefInfo(Inst, MemLoc)) {
+    switch (getModRefInfo(Inst, MemLoc)) {
     case AliasAnalysis::NoModRef:
       // If the call has no effect on the queried pointer, just ignore it.
       continue;