Index: lib/CodeGen/SelectionDAG/ScheduleDAGRRList.cpp
===================================================================
--- lib/CodeGen/SelectionDAG/ScheduleDAGRRList.cpp
+++ lib/CodeGen/SelectionDAG/ScheduleDAGRRList.cpp
@@ -28,6 +28,7 @@
 #include "llvm/IR/InlineAsm.h"
 #include "llvm/Support/Debug.h"
 #include "llvm/Support/ErrorHandling.h"
+#include "llvm/Support/RandomNumberGenerator.h"
 #include "llvm/Support/raw_ostream.h"
 #include "llvm/Target/TargetInstrInfo.h"
 #include "llvm/Target/TargetLowering.h"
@@ -103,6 +104,17 @@
   "sched-avg-ipc", cl::Hidden, cl::init(1),
   cl::desc("Average inst/cycle whan no target itinerary exists."));
 
+static cl::opt<bool> RandomizeSchedule(
+  "sched-randomize",
+  cl::desc("Enable randomization of scheduling"),
+  cl::init(false));
+
+static cl::opt<unsigned> SchedRandPercentage(
+  "sched-randomize-percentage",
+  cl::desc("Percentage of instructions where schedule is randomized"),
+  cl::init(50));
+
+
 namespace {
 //===----------------------------------------------------------------------===//
 /// ScheduleDAGRRList - The actual register reduction list scheduler
@@ -1757,6 +1769,16 @@
 class RegReductionPriorityQueue : public RegReductionPQBase {
   SF Picker;
 
+  static SUnit *popRandom(std::vector<SUnit*> &Q) {
+    RandomNumberGenerator *randGen = RandomNumberGenerator::Get();
+    size_t randIndex = randGen->Random(Q.size());
+    SUnit *V = Q[randIndex];
+    if (randIndex < Q.size() - 1)
+      std::swap(Q[randIndex], Q.back());
+    Q.pop_back();
+    return V;
+  }
+
 public:
   RegReductionPriorityQueue(MachineFunction &mf,
                             bool tracksrp,
@@ -1777,7 +1799,18 @@
   SUnit *pop() override {
     if (Queue.empty()) return nullptr;
 
-    SUnit *V = popFromQueue(Queue, Picker, scheduleDAG);
+    SUnit *V;
+    if (RandomizeSchedule) {
+      RandomNumberGenerator *randGen = RandomNumberGenerator::Get();
+      unsigned int Roll = randGen->Random(100);
+      if (Roll < SchedRandPercentage) {
+        V = popRandom(Queue);
+      } else {
+        V = popFromQueue(Queue, Picker, scheduleDAG);
+      }
+    } else {
+      V = popFromQueue(Queue, Picker, scheduleDAG);
+    }
     V->NodeQueueId = 0;
     return V;
   }
Index: test/CodeGen/X86/sched-rnd-test.ll
===================================================================
--- /dev/null
+++ test/CodeGen/X86/sched-rnd-test.ll
@@ -0,0 +1,36 @@
+; RUN: llc < %s -rng-seed=1 -sched-randomize -sched-randomize-percentage=100 | FileCheck %s --check-prefix=SEED1
+; RUN: llc < %s -rng-seed=5 -sched-randomize -sched-randomize-percentage=100 | FileCheck %s --check-prefix=SEED2
+; RUN: llc < %s -rng-seed=5 -sched-randomize -sched-randomize-percentage=50 | FileCheck %s --check-prefix=PERCENTAGE
+
+; This test case checks that the schedule randomization is changing
+; scheduling decisions, that different seeds result in different
+; schedules, and that the percentage alters the amount of
+; randomization
+
+define i32 @test(i32 %x, i32 %y, i32 %z) {
+entry:
+    %a = add i32 %x, %y
+    %b = add i32 %x, %z
+    %c = add i32 %y, %z
+    %d = mul i32 %a, %b
+    %e = mul i32 %d, %c
+    ret i32 %e
+}
+
+; SEED1: leal (%rdi,%rsi), %eax
+; SEED1-NEXT:	addl  %edx, %esi
+; SEED1-NEXT:	addl  %edx, %edi
+; SEED1-NEXT:	imull %edi, %eax
+; SEED1-NEXT:	imull %esi, %eax
+
+; SEED2: leal (%rdi,%rsi), %eax
+; SEED2-NEXT:	addl  %edx, %edi
+; SEED2-NEXT:	imull %edi, %eax
+; SEED2-NEXT:	addl  %edx, %esi
+; SEED2-NEXT:	imull %esi, %eax
+
+; PERCENTAGE: leal  (%rdi,%rsi), %eax
+; PERCENTAGE:	addl  %edx, %esi
+; PERCENTAGE:	addl  %edx, %edi
+; PERCENTAGE:	imull %edi, %eax
+; PERCENTAGE:	imull %esi, %eax