--- a/browser/extensions/formautofill/FormAutofillHandler.jsm
+++ b/browser/extensions/formautofill/FormAutofillHandler.jsm
@@ -478,16 +478,18 @@ this.FormAutofillHeuristics = {
         contactType: info.contactType,
         fieldName: info.fieldName,
         elementWeakRef: Cu.getWeakReference(element),
       };
 
       fieldDetails.push(formatWithElement);
     }
 
+    this.clearLabelMap();
+
     return fieldDetails;
   },
 
   /**
    * Get the autocomplete info (e.g. fieldName) determined by the regexp
    * (this.RULES) matching to a feature string. The result is based on the
    * existing field names to prevent duplicating predictions
    * (e.g. address-line[1-3).
@@ -652,47 +654,60 @@ this.FormAutofillHeuristics = {
         }
         _extractLabelStrings(node);
       }
     };
     _extractLabelStrings(element);
     return strings;
   },
 
-  findLabelElements(element) {
-    let document = element.ownerDocument;
-    let id = element.id;
-    let labels = [];
-    // TODO: querySelectorAll is inefficient here. However, bug 1339726 is for
-    // a more efficient implementation from DOM API perspective. This function
-    // should be refined after input.labels API landed.
-    for (let label of document.querySelectorAll("label[for]")) {
-      if (id == label.htmlFor) {
-        labels.push(label);
+  generateLabelMap(doc) {
+    let mappedLabels = {};
+    let unmappedLabels = [];
+
+    for (let label of doc.getElementsByTagName("label")) {
+      let id = label.htmlFor;
+      if (!id) {
+        let control = label.control;
+        if (!control) {
+          continue;
+        }
+        id = control.id;
+      }
+      if (id) {
+        if (!mappedLabels[id]) {
+          mappedLabels[id] = [label];
+        } else {
+          mappedLabels[id].push(label);
+        }
+      } else {
+        unmappedLabels.push(label);
       }
     }
 
-    if (labels.length > 0) {
-      return labels;
+    this._mappedLabels = mappedLabels;
+    this._unmappedLabels = unmappedLabels;
+  },
+
+  clearLabelMap() {
+    delete this._mappedLabels;
+    delete this._unmappedLabels;
+  },
+
+  findLabelElements(element) {
+    if (!this._mappedLabels) {
+      this.generateLabelMap(element.ownerDocument);
     }
 
-    let parent = element.parentNode;
-    if (!parent) {
-      return [];
+    let id = element.id;
+    let labels = this._mappedLabels[id];
+    if (labels) {
+      return labels;
     }
-    do {
-      if (parent.tagName == "LABEL" &&
-          parent.control == element &&
-          !parent.hasAttribute("for")) {
-        return [parent];
-      }
-      parent = parent.parentNode;
-    } while (parent);
-
-    return [];
+    return this._unmappedLabels.filter(label => label.control == element);
   },
 };
 
 XPCOMUtils.defineLazyGetter(this.FormAutofillHeuristics, "RULES", () => {
   let sandbox = {};
   let scriptLoader = Cc["@mozilla.org/moz/jssubscript-loader;1"]
                        .getService(Ci.mozIJSSubScriptLoader);
   const HEURISTICS_REGEXP = "chrome://formautofill/content/heuristicsRegexp.js";

--- a/browser/extensions/formautofill/test/unit/test_findLabelElements.js
+++ b/browser/extensions/formautofill/test/unit/test_findLabelElements.js
@@ -79,12 +79,13 @@ TESTCASES.forEach(testcase => {
   add_task(async function() {
     do_print("Starting testcase: " + testcase.description);
 
     let doc = MockDocument.createTestDocument(
       "http://localhost:8080/test/", testcase.document);
 
     let input = doc.getElementById(testcase.inputId);
     let labels = FormAutofillHeuristics.findLabelElements(input);
+    FormAutofillHeuristics.clearLabelMap();
 
     Assert.deepEqual(labels.map(l => l.id), testcase.expectedLabelIds);
   });
 });

--- a/browser/extensions/formautofill/test/unit/test_getInfo.js
+++ b/browser/extensions/formautofill/test/unit/test_getInfo.js
@@ -214,12 +214,13 @@ TESTCASES.forEach(testcase => {
   add_task(async function() {
     do_print("Starting testcase: " + testcase.description);
 
     let doc = MockDocument.createTestDocument(
       "http://localhost:8080/test/", testcase.document);
 
     let element = doc.getElementById(testcase.elementId);
     let value = FormAutofillHeuristics.getInfo(element, testcase.addressFieldDetails);
+    FormAutofillHeuristics.clearLabelMap();
 
     Assert.deepEqual(value, testcase.expectedReturnValue);
   });
 });