Index: llvm/utils/lit/lit/cl_arguments.py
===================================================================
--- llvm/utils/lit/lit/cl_arguments.py
+++ llvm/utils/lit/lit/cl_arguments.py
@@ -11,6 +11,7 @@
 class TestOrder(enum.Enum):
     DEFAULT = enum.auto()
     RANDOM = enum.auto()
+    LEXICAL = enum.auto()
 
 
 def parse_args():
@@ -150,9 +151,6 @@
             metavar="N",
             help="Maximum time to spend testing (in seconds)",
             type=_positive_int)
-    selection_group.add_argument("--shuffle",
-            help="Run tests in random order",
-            action="store_true")
     selection_group.add_argument("-i", "--incremental",
             help="Run failed tests first (DEPRECATED: now always enabled)",
             action="store_true")
@@ -189,6 +187,14 @@
             type=_positive_int,
             default=os.environ.get("LIT_RUN_SHARD"))
 
+    order_group = selection_group.add_mutually_exclusive_group()
+    order_group.add_argument("--shuffle",
+            help="Run tests in random order",
+            action="store_true")
+    order_group.add_argument("--lexical-order",
+            help="Run tests in lexical order",
+            action="store_true")
+
     debug_group = parser.add_argument_group("Debug and Experimental Options")
     debug_group.add_argument("--debug",
             help="Enable debugging (for 'lit' development)",
@@ -217,6 +223,8 @@
 
     if opts.shuffle:
         opts.order = TestOrder.RANDOM
+    elif opts.lexical_order:
+        opts.order = TestOrder.LEXICAL
     else:
         opts.order = TestOrder.DEFAULT
 
Index: llvm/utils/lit/lit/main.py
===================================================================
--- llvm/utils/lit/lit/main.py
+++ llvm/utils/lit/lit/main.py
@@ -169,6 +169,8 @@
     if order == TestOrder.RANDOM:
         import random
         random.shuffle(tests)
+    elif order == TestOrder.LEXICAL:
+        tests.sort(key=lambda t: t.getFullName())
     else:
         assert order == TestOrder.DEFAULT, 'Unknown TestOrder value'
         tests.sort(key=lambda t: (not t.previous_failure, -t.previous_elapsed, t.getFullName()))
Index: llvm/utils/lit/tests/custom-result-category.py
===================================================================
--- llvm/utils/lit/tests/custom-result-category.py
+++ llvm/utils/lit/tests/custom-result-category.py
@@ -1,10 +1,7 @@
 # UNSUPPORTED: system-windows
 # Test lit.main.add_result_category() extension API.
 
-# FIXME: this test depends on order of tests
-# RUN: rm -f %{inputs}/custom-result-category/.lit_test_times.txt
-
-# RUN: not %{lit} -j 1 %{inputs}/custom-result-category | FileCheck %s
+# RUN: not %{lit} --lexical -j 1 %{inputs}/custom-result-category | FileCheck %s
 
 # CHECK: CUSTOM_PASS: custom-result-category :: test1.txt
 # CHECK: CUSTOM_FAILURE: custom-result-category :: test2.txt
Index: llvm/utils/lit/tests/googletest-format.py
===================================================================
--- llvm/utils/lit/tests/googletest-format.py
+++ llvm/utils/lit/tests/googletest-format.py
@@ -1,9 +1,6 @@
 # Check the various features of the GoogleTest format.
 
-# FIXME: this test depends on order of tests
-# RUN: rm -f %{inputs}/googletest-format/.lit_test_times.txt
-
-# RUN: not %{lit} -j 1 -v %{inputs}/googletest-format > %t.out
+# RUN: not %{lit} --lexical -j 1 -v %{inputs}/googletest-format > %t.out
 # FIXME: Temporarily dump test output so we can debug failing tests on
 # buildbots.
 # RUN: cat %t.out
Index: llvm/utils/lit/tests/googletest-upstream-format.py
===================================================================
--- llvm/utils/lit/tests/googletest-upstream-format.py
+++ llvm/utils/lit/tests/googletest-upstream-format.py
@@ -1,9 +1,6 @@
 # Check the various features of the GoogleTest format.
 
-# FIXME: this test depends on order of tests
-# RUN: rm -f %{inputs}/googletest-upstream-format/.lit_test_times.txt
-
-# RUN: not %{lit} -j 1 -v %{inputs}/googletest-upstream-format > %t.out
+# RUN: not %{lit} --lexical -j 1 -v %{inputs}/googletest-upstream-format > %t.out
 # RUN: FileCheck < %t.out %s
 #
 # END.
Index: llvm/utils/lit/tests/progress-bar.py
===================================================================
--- llvm/utils/lit/tests/progress-bar.py
+++ llvm/utils/lit/tests/progress-bar.py
@@ -1,9 +1,6 @@
 # Check the simple progress bar.
 
-# FIXME: this test depends on order of tests
-# RUN: rm -f %{inputs}/progress-bar/.lit_test_times.txt
-
-# RUN: not %{lit} -j 1 -s %{inputs}/progress-bar > %t.out
+# RUN: not %{lit} --lexical -j 1 -s %{inputs}/progress-bar > %t.out
 # RUN: FileCheck < %t.out %s
 #
 # CHECK: Testing:
Index: llvm/utils/lit/tests/shtest-env.py
===================================================================
--- llvm/utils/lit/tests/shtest-env.py
+++ llvm/utils/lit/tests/shtest-env.py
@@ -1,9 +1,6 @@
 # Check the env command
 
-# FIXME: this test depends on order of tests
-# RUN: rm -f %{inputs}/shtest-env/.lit_test_times.txt
-
-# RUN: not %{lit} -j 1 -a -v %{inputs}/shtest-env \
+# RUN: not %{lit} --lexical -j 1 -a -v %{inputs}/shtest-env \
 # RUN: | FileCheck -match-full-lines %s
 #
 # END.
Index: llvm/utils/lit/tests/shtest-format.py
===================================================================
--- llvm/utils/lit/tests/shtest-format.py
+++ llvm/utils/lit/tests/shtest-format.py
@@ -1,10 +1,7 @@
 # Check the various features of the ShTest format.
 
-# FIXME: this test depends on order of tests
-# RUN: rm -f %{inputs}/shtest-format/.lit_test_times.txt
-
 # RUN: rm -f %t.xml
-# RUN: not %{lit} -j 1 -v %{inputs}/shtest-format --xunit-xml-output %t.xml > %t.out
+# RUN: not %{lit} --lexical -j 1 -v %{inputs}/shtest-format --xunit-xml-output %t.xml > %t.out
 # RUN: FileCheck < %t.out %s
 # RUN: FileCheck --check-prefix=XUNIT < %t.xml %s
 
Index: llvm/utils/lit/tests/shtest-keyword-parse-errors.py
===================================================================
--- llvm/utils/lit/tests/shtest-keyword-parse-errors.py
+++ llvm/utils/lit/tests/shtest-keyword-parse-errors.py
@@ -1,7 +1,4 @@
-# FIXME: this test depends on order of tests
-# RUN: rm -f %{inputs}/shtest-keyword-parse-errors/.lit_test_times.txt
-
-# RUN: not %{lit} -j 1 -vv %{inputs}/shtest-keyword-parse-errors > %t.out
+# RUN: not %{lit} --lexical -j 1 -vv %{inputs}/shtest-keyword-parse-errors > %t.out
 # RUN: FileCheck -input-file %t.out %s
 #
 # END.
Index: llvm/utils/lit/tests/shtest-not.py
===================================================================
--- llvm/utils/lit/tests/shtest-not.py
+++ llvm/utils/lit/tests/shtest-not.py
@@ -1,9 +1,6 @@
 # Check the not command
 
-# FIXME: this test depends on order of tests
-# RUN: rm -f %{inputs}/shtest-not/.lit_test_times.txt
-
-# RUN: not %{lit} -j 1 -a -v %{inputs}/shtest-not \
+# RUN: not %{lit} --lexical -j 1 -a -v %{inputs}/shtest-not \
 # RUN: | FileCheck -match-full-lines %s
 #
 # END.
Index: llvm/utils/lit/tests/shtest-run-at-line.py
===================================================================
--- llvm/utils/lit/tests/shtest-run-at-line.py
+++ llvm/utils/lit/tests/shtest-run-at-line.py
@@ -1,10 +1,7 @@
 # Check that -vv makes the line number of the failing RUN command clear.
 # (-v is actually sufficient in the case of the internal shell.)
 
-# FIXME: this test depends on order of tests
-# RUN: rm -f %{inputs}/shtest-run-at-line/.lit_test_times.txt
-
-# RUN: not %{lit} -j 1 -vv %{inputs}/shtest-run-at-line > %t.out
+# RUN: not %{lit} --lexical -j 1 -vv %{inputs}/shtest-run-at-line > %t.out
 # RUN: FileCheck --input-file %t.out %s
 #
 # END.
Index: llvm/utils/lit/tests/shtest-shell.py
===================================================================
--- llvm/utils/lit/tests/shtest-shell.py
+++ llvm/utils/lit/tests/shtest-shell.py
@@ -1,9 +1,6 @@
 # Check the internal shell handling component of the ShTest format.
 
-# FIXME: this test depends on order of tests
-# RUN: rm -f %{inputs}/shtest-shell/.lit_test_times.txt
-
-# RUN: not %{lit} -j 1 -v %{inputs}/shtest-shell > %t.out
+# RUN: not %{lit} --lexical -j 1 -v %{inputs}/shtest-shell > %t.out
 # FIXME: Temporarily dump test output so we can debug failing tests on
 # buildbots.
 # RUN: cat %t.out